AGCO-MIPP Seminar

AGCO-MIPP Seminar – Wednesday, April 2

🕕 6:00 – 6:30 PM | Paul Golz

Talk Title: Generative Social Choice.

Abstract: The mathematical study of voting, social choice theory, has traditionally only been applicable to choices among a few predetermined alternatives, but not to open-ended decisions such as collectively selecting a textual statement. We introduce generative social choice, a design methodology for open-ended democratic processes that combines the rigor of social choice theory with the capability of large language models to generate text and extrapolate preferences.
Our framework divides the design of AI-augmented democratic processes into two components: first, proving that the process satisfies representation guarantees when given access to oracle queries; second, empirically validating that these queries can be approximately implemented using a large language model.
We apply this framework to the problem of summarizing free-form opinions into a proportionally representative slate of opinion statements; specifically, we develop a democratic process with representation guarantees and use this process to portray the opinions of participants in a survey about abortion policy. In a trial with 100 representative US residents, we find that 84 out of 100 participants feel «excellently» or «exceptionally» represented by the slate of five statements we extracted.

🕡 6:30 – 7:00 PM | Ulrike Schmidt-Kraepelin

Talk Title: Truthful Budget Aggregation: Beyond Moving-Phantom Mechanisms.

Abstract: We study a budget-aggregation setting in which a number of voters report their ideal distribution of a budget over a set of alternatives, and a mechanism aggregates these reports into an allocation. Ideally, such mechanisms are truthful, i.e., voters should not be incentivized to misreport their preferences.
For the case of two alternatives, the set of mechanisms that are truthful and additionally meet a range of basic desiderata (anonymity, neutrality, and continuity) exactly coincides with the so-called moving-phantom mechanisms, but whether this space is richer for more alternatives was repeatedly stated as an open question.
We answer this question in the affirmative by presenting a class of truthful mechanisms that are not moving-phantoms but satisfy the three properties. Since moving-phantom mechanisms can only provide limited fairness guarantees (measured as the worst-case distance to a fair share solution), one motivation for broadening the class of truthful mechanisms is the hope for improved fairness guarantees. We dispel this hope by showing that lower bounds holding for the class of moving-phantom mechanisms extend to all truthful, anonymous, neutral, and continuous mechanisms. This is joint work with Mark de Berg, Rupert Freeman, and Markus Utke.

🕖 7:00 – 7:30 PM | Jamie Tucker-Foltz

Talk Title: Sampling tree-weighted balanced graph partitions in polynomial time

Abstract: When judging the fairness of a political redistricting map, it is useful to be able to generate a large ensemble of «random» alternative maps. Formally, this is a graph partitioning problem. The objective is to output random partitions of the vertex set into k equal-sized pieces inducing connected subgraphs. Numerous algorithms have been developed to sample either exactly or approximately from the so-called «spanning tree distribution,» where each partition is weighted by the product of the numbers of spanning trees in each part. However, none of these algorithms had been shown to run in polynomial time, even on very tame families of graphs. In a recent paper, Charikar, Liu, Liu, and Vuong proposed a simple algorithm, and conjectured that it runs in polynomial time on grid graphs for constant k. We prove this conjecture, and extend to a wide class of «grid-like» planar graphs encapsulating the kinds of graphs typically encountered in real geographical data. Based on joint work with Sarah Cannon and Wesley Pegden: https://arxiv.org/abs/2310.15152