Abstract
In this paper, we study fairness in committee selection problems. We consider a general notion of fairness via stability: A committee is stable if no coalition of voters can deviate and choose a committee of proportional size, so that all these voters strictly prefer the new committee to the existing one. Our main contribution is to extend this definition to stability of a distribution (or lottery) over committees. We consider two canonical voter preference models: the Approval Set setting where each voter approves a set of candidates and prefers committees with larger intersection with this set; and the Ranking setting where each voter ranks committees based on how much she likes her favorite candidate in a committee. Our main result is to show that stable lotteries always exist for these canonical preference models. Interestingly, given preferences of voters over committees, the procedure for computing an approximately stable lottery is the same for both models and therefore extends to the setting where some voters have the former preference structure and others have the latter. Our existence proof uses the probabilistic method and a new large deviation inequality that may be of independent interest.
Introduction
Committee selection is a fundamental problem in multi-winner elections, with applications ranging from parliamentary representation to hiring committees and cloud resource allocation. The goal is to select a committee of size $K$ from a pool of $m$ candidates based on the preferences of $n$ voters. A central objective in this domain is ensuring group fairness, often formalized through the concept of core stability.
A committee is considered stable if no sub-group of voters—a coalition—has both the incentive and the power to "opt out." Specifically, a coalition of size $\beta n$ (where $\beta \in (0,1]$) is blocking if it can propose a smaller committee of size $\beta K$ that every member of the coalition strictly prefers over the current selection. This ensures that every demographic or interest group receives representation proportional to its size.
The Challenge of Deterministic Stability
Achieving stability deterministically is notoriously difficult. In the Ranking model, where voters rank candidates and value a committee based on their most-preferred member within it, deterministic stable committees often fail to exist. This is primarily due to cyclic preferences, a multi-winner extension of the Condorcet paradox.
As shown in the figure above, voters 1, 2, and 3 exhibit a cycle over candidates $a, b,$ and $c$. In such scenarios, any deterministic choice can be "blocked" by a coalition that prefers a different candidate, leading to instability. Furthermore, standard fairness-oriented voting rules like Proportional Approval Voting (PAV) do not guarantee stability; PAV only achieves $O(\sqrt{K})$-approximate stability, highlighting the need for a new approach.
Methodology: From Committees to Lotteries
To overcome the impossibility of deterministic stability, we shift the focus to stable lotteries—probability distributions over committees of size $K$. A lottery is stable if the expected utility it provides to any coalition is high enough that no coalition can find a smaller committee that all its members strictly prefer.
Our approach utilizes a game-theoretic framework, modeling stability as a zero-sum game between an "attacker" (the deviating coalition) and a "defender" (the algorithm). By applying the minimax theorem, we demonstrate that a stable lottery exists if the defender can always find a strategy to counter any possible attack.
Probability Matching and Rounding
The core of our existence proof is a novel rounding procedure. The defender observes the attacker's distribution of candidates and employs "probability matching." By selecting candidates with marginal probabilities proportional to those in the attacker's strategy—scaled to maintain committee size $K$—the defender can neutralize the threat of deviation.
For the Approval Set model, where voters value committees based on the size of the intersection with their approved set, we developed a new large deviation inequality. This "Probability Matching Lemma" bounds the probability that a sum of negatively correlated Bernoulli variables falls below a critical threshold, ensuring the defender's randomized selection remains stable in expectation.
Algorithmic Implementation
We provide a polynomial-time algorithm to compute these fair outcomes by integrating our rounding procedure into the Multiplicative Weights Update (MWU) framework. By treating potential blocking committees as "experts," the algorithm iteratively converges toward an approximately stable lottery.
Key Results
Our research yields several primary findings:
- Universal Existence: Stable lotteries are guaranteed to exist for both the Approval Set and Ranking preference models.
- Unified Computation: The same algorithmic procedure works for both models, allowing for "mixed" electorates where different voters use different preference structures.
- 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.
While the general deterministic case for the Approval Set model remains an open conjecture, we proved that for small committees ($K \le 3$), a deterministic stable committee always exists and can be found in $O(m^3n)$ time.
Conclusion and Future Work
By introducing stable lotteries, we provide a robust solution to the group fairness problem in committee selection, smoothing over the paradoxes that plague deterministic methods. Future research will focus on proving the deterministic stability conjecture for the Approval Set model across all committee sizes and extending these results to voters with arbitrary additive cardinal utilities. Additionally, improving the runtime dependence on the deviation size $L$ in the Approval Set setting remains a key algorithmic challenge.
Summary updated