In multi-winner elections, the goal is to select a committee of $k$ candidates that fairly represents a pool of voters. While many voting rules focus on maximizing total satisfaction, a more rigorous standard of fairness is core stability. A committee is core-stable if no group of voters is "under-represented" to the point that they could justify seceding and choosing their own smaller committee.
Despite its intuitive appeal, the central challenge in this field is the existence problem: for many years, researchers could not prove whether a core-stable committee always exists for any set of voter preferences.
The Intuition of the Core
The core is a concept borrowed from cooperative game theory. In the context of committee selection, it acts as a safeguard against the "tyranny of the majority."
Imagine an election for a committee of size $k=10$ with 100 voters. Any group of 10 voters (a $1/k$ fraction) should, in theory, have enough collective "buying power" to choose at least one representative they all approve of. As Aziz et al. explain, this creates a distinction between majoritarian stability—where a single large majority might sweep all seats—and proportional stability, which ensures diverse voter blocks are guaranteed representation.
A committee is in the core if no coalition of voters can identify a set of candidates that they prefer more than the current winners, provided the size of that coalition is large enough to "afford" those candidates. If such a committee exists, it is immune to objections from any sub-group.
The Existence Challenge
The primary difficulty is that voter preferences are discrete and often conflicting. Peters and Skowron highlight a fundamental trade-off: you can maximize total voter welfare, or you can ensure equal influence (power), but satisfying both simultaneously while guaranteeing core stability is mathematically elusive.
For years, it remained an open question whether a stable committee could be guaranteed for all possible election profiles. Aziz et al. noted that many robust voting rules fail to guarantee existence, requiring the use of heuristics or relaxed constraints in practice. Similarly, market-based fairness concepts like Stable Priceability, which use virtual currency to justify selections, are not guaranteed to exist for every set of preferences when the committee size is strictly fixed, as shown by Peters et al..
Recent Breakthroughs in Existence
Recent research has begun to map the boundaries of where core-stable outcomes are guaranteed. Peters provided a significant breakthrough by proving that for small-scale elections—specifically committee sizes up to $k=8$ or candidate pools up to $m=15$—a stable outcome is always guaranteed to exist.
Further constraints also yield guarantees. Association for Artificial Intelligence 2026 et al. used automated reasoning and Mixed-Integer Linear Programming (MILP) to prove that a core-stable committee always exists when the number of candidates is exactly one greater than the committee size ($m = k+1$). Their work identifies the Droop core as the optimal target for these stability guarantees.
Strategies for Guaranteed Stability
When a deterministic stable committee cannot be guaranteed for general cases, researchers employ three main strategies:
1. Restricting the Preference Structure
By narrowing how voters can express preferences, stability becomes easier to achieve. Brill et al. and Peters et al. demonstrate that if voters approve of parties rather than individual candidates (approval-based apportionment), a core-stable outcome is always mathematically guaranteed. This restriction bridges the gap between simple party-list systems and complex candidate elections.
2. Randomization (Stable Lotteries)
If no single fixed committee is stable, a distribution over committees might be. Cheng et al. introduced the concept of stable lotteries. They proved that while deterministic outcomes are elusive, a randomized selection (a lottery) that satisfies the stability requirement in expectation always exists and can be computed in polynomial time.
3. Alternative Stability Definitions
In fields like Federated Learning, the core is adapted to handle different types of data. Chaudhury et al. proposed the Proportional Veto Core (PVC), which uses the ordinal rank of models. In this framework, a model is stable if no subset of participants can collectively veto it in favor of an alternative they all prefer, ensuring that diverse groups of participants are not disadvantaged by the global model.
Key Foundational Work
The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality (2017) — contributed 5 concept elements to this direction.
Group Fairness in Committee Selection (2019) — contributed 2 concept elements to this direction.
Proportionality and the Limits of Welfarism (2019) — contributed 1 concept elements to this direction.