Extremal Social Choice Theory?

Computational social choice is a burgeoning subject which uses methods from Computer Science and ideas from Social Sciences. In what follows, I will briefly describe an even more interesting recent interplay of fields namely extremal combinatorics and social choice theory. This interesting connection  was described in an enjoyable talk given by Felix Brandt last week in the TUM Mathematics Department.

A key goal in social choice theory is to find suitable social choice functions which satisfy desirable axioms. This quest for finding suitable functions was given a jolt by Arrow’s Impossibility Theorem that showed that even finding a social choice function which satisfies a set of very mild and desirable axioms is impossible. Since then social choice theorists have been trying to further relax desirable axioms to circumvent Arrow’s theorem. In this line of work, an intriguing case is that of a function called the Tournament Equilibrium Set (TEQ) which is defined over the asymmetric and complete graph based on majority comparisons. TEQ was introduced by a political scientist Thomas Schwartz in 1990. Schwartz conjectured about a property of the TEQ which if true would make TEQ a very appealing social choice function. Weakened versions of the conjecture can be suitably stated purely in graph theoretic terms. Since the proposal of TEQ, researchers have tried to prove various desirable properties of TEQ and interestingly all of them hinged on whether the conjecture of Schwartz holds or not. This “all or nothing scenario” made the Schwartz’ conjecture even more intriguing. 

This year, the conjecture has finally been settled in the negative. So what is the counter example to the conjecture? It is an example on 10^136 alternatives and its existence has been proved via the probabilistic method! So whereas it is difficult to show the example, we know that such an example does exist. The conclusion is that TEQ does not satisfy nice properties or at least not for elections in which the number of alternatives is larger than 10^136.

I would suggest that the next time extremal graph theorists apply for funding, they should include a reference to how a 22 year old conjecture by a political scientist was answered via the probabilistic method.

Comments

Post a Comment

Popular posts from this blog

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Image
Working Paper: https://cgi.cse.unsw.edu.au/~haziz/PIRMES.pdf  Abstract: In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In this paper, we propose a new efficiency-improving stable `smart lottery' mechanism. We aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the ...
Read more

Fair budgets from ranked ballots: PB-EAR

How do you split a shared budget fairly when people rank projects that cost very different amounts? PB-EAR, from our AAAI 2021 paper  Proportionally Representative Participatory Budgeting with Ordinal Preferences  ( AAAI version ), gives every voter an equal slice of the budget and lets groups pool their slices to fund the projects they rank highest, looking further down the ballots only when nothing is yet affordable. Every cohesive group is guaranteed its proportional share, and the rule extends our  Expanding Approvals Rule  for elections to budgets with project costs, ties and unequal voter weights.  That makes it a natural fit for DAO grant rounds such as   TheDAO Security Fund 's ETHSecurity Initiatives, where badge holders will rank the security initiatives listed on   the app  to allocate the fund's budget. The two-minute video below walks through a worked example. Here's an educational tool someone built to show how PB-EAR works. 
Read more

Proportionally Representative Clustering

Image
H. Aziz, B. Lee, S. Morota Chu, and J. Vollen. Proportionally Representative Clustering.  WINE 2024 .  [  Pdf  ]  In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering— one of the fundamental tasks in unsupervised machine learning. We pro- pose a new axiom “proportionally representative fairness” (PRF) that is designed for clustering problems where the selection of centroids re- flects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair cluster- ing algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approxi- mation algorithm for the well-studied Proportional Fairness (PF) axiom [ 13 ]. Our algorithm for the discrete setting also matches the best kn...
Read more