TL;DR
This paper tackles the problem of group fairness in multi-winner elections (committee selection) by ensuring no sub-group of voters is incentivized to deviate and form their own proportionally smaller committee. Because deterministic "stable" committees don't always exist, the authors introduce the concept of stable lotteries (distributions over committees), proving they always exist for standard voting models and providing a polynomial-time algorithm to compute them.
What Problem Does This Paper Address?
Imagine you are selecting a parliament, a group of new hires, or a set of shared data items to cache in a cloud system. You need to choose a committee of size $K$ from $m$ candidates, based on the preferences of $n$ voters. A classic goal in social choice theory is proportionality or fairness: every demographic should feel fairly represented.
The authors formalize this using the economic concept of core stability. A committee is stable if no coalition of voters of size $\beta n$ (for $\beta \in (0,1]$) can deviate and choose a new committee of size $\beta K$ such that every voter in the coalition strictly prefers the new committee.
The challenge? For voters who rank candidates, a deterministic stable committee simply might not exist due to cyclic preferences (similar to the Condorcet paradox). Furthermore, existing voting rules designed for fairness, like Proportional Approval Voting (PAV), fail to guarantee stability. The paper addresses this gap by asking: if we allow randomization (lotteries over committees), can we guarantee group fairness, and can we compute these fair outcomes efficiently?
Methods
The authors shift the paradigm from deterministic committees to stable lotteries—probability distributions over committees of size $K$. To prove existence and design an algorithm, they use a clever mix of game theory and randomized algorithms:
- Zero-Sum Game Formulation: They frame stability as a zero-sum game between an "attacker" (a deviating coalition trying to find a blocking committee) and a "defender" (the algorithm choosing the stable lottery). By the minimax theorem, proving a stable lottery exists is equivalent to showing this game has a negative value.
- Probability Matching: To prove the defender can always win, the authors design a novel rounding procedure. The defender looks at the attacker's distribution of candidates and "probability matches" it—selecting candidates proportionally to their marginal probabilities in the attacker's strategy, scaled up to preserve the committee size $K$.
- Probability Matching Lemma: To make the math work for the Approval Set model, the authors prove a brand new large deviation inequality. It bounds the probability that a sum of negatively correlated Bernoulli random variables falls below a specific threshold.
- Multiplicative Weights Update (MWU): For computation, they plug their rounding procedure into the standard MWU framework, treating attacker committees as "experts" to iteratively converge on an approximately stable lottery.
Datasets
Not discussed in the paper. This is a theoretical computer science and algorithmic game theory paper; results are proven mathematically rather than evaluated empirically on datasets.
Key Insights and Ideas
- Randomization Rescues Fairness: While deterministic stability is impossible in ranking-based elections, introducing lotteries completely smooths out the paradoxes, guaranteeing that a fair representation exists.
- A Unifying Algorithm: Remarkably, the exact same algorithmic procedure works for both the Approval Set model (voters approve a subset of candidates) and the Ranking model (voters rank candidates). This means the algorithm can handle a mixed population where some voters submit rankings and others submit approval sets.
- Standard Rules Fall Short: The authors prove that Proportional Approval Voting (PAV)—a highly regarded rule in social choice that satisfies "justified representation"—can actually be incredibly far from stable. It only guarantees $O(\sqrt{K})$-approximate stability, highlighting the need for the authors' new approach.
Key Results
- Existence: Stable lotteries always exist for both the Approval Set and Ranking preference models.
- Algorithmic Efficiency: An $\epsilon$-approximate $L$-stable lottery can be computed in $poly(m^L, 1/\epsilon)$ time. For the Ranking model, stability only requires checking deviations of size $L=1$, meaning a fully stable lottery can be computed in strictly polynomial time.
- Deterministic Progress: While the general deterministic case remains open, the authors prove that for the Approval Set model, a deterministic stable committee always exists if the committee size is small ($K \le 3$), and it can be found in $O(m^3n)$ time.
Limitations and Future Work
- The Deterministic Approval Set Conjecture: The authors leave open a tantalizing question: does a deterministic stable committee always exist for the Approval Set model for any committee size $K$? They conjecture yes (and verified it computationally for small instances up to 14 voters/candidates), but a mathematical proof remains elusive.
- General Cardinal Utilities: The current proofs rely heavily on the specific structures of Approval and Ranking models. Extending the Probability Matching Lemma to handle voters with arbitrary additive cardinal utilities is a major open challenge.
- Runtime Dependence on $L$: The algorithm for computing stable lotteries runs in time exponential to the size of the deviating committee ($m^L$). Finding a fully polynomial-time algorithm for arbitrary $L$ in the Approval Set setting (or proving it is NP-hard) is an important next step.
Summary updated