The Core of Approval-Based Committee Elections with Few Seats

Dominik PetersIJCAI 2025 · DOI

TL;DR

This paper tackles the long-standing open question of whether fair committee selection rules always guarantee a "stable" outcome. The authors prove that for committee sizes up to 8, or when the number of candidates is small (up to 15), such stable committees always exist. This is a significant step towards ensuring fairness in multi-winner elections.

What Problem Does This Paper Address?

In multi-winner elections, we want to select a committee of $k$ candidates from a pool of $m$ candidates, based on voters' preferences. Voters express their preferences by approving a subset of candidates. A key concept in ensuring fairness is the "core" of an election, which represents committees that are stable against certain types of objections. A committee is in the core if no group of voters who are "underrepresented" by the current committee can credibly form a blocking coalition to demand a different committee.

For years, it was unknown if such a core committee always exists for any set of voter preferences. While some progress had been made for very small committee sizes (like $k=3$) or specific types of voter preferences, a general guarantee remained elusive. This paper aims to close this gap by proving the existence of core-stable committees under certain conditions.

Methods

The paper leverages the Proportional Approval Voting (PAV) rule, a well-established voting method, and its variants. The core of the paper's methodology involves:

  • Linear Programming (LP): The authors extensively use mixed-integer linear programming to search for counterexamples to core existence. When an LP solver finds no feasible solution for a specific problem setup, it implies that the core must exist for those parameters. This is a powerful technique for proving non-existence of counterexamples.
  • Computer-Assisted Search: The LP formulations are solved using computer searches, allowing the analysis of larger parameter spaces than previously possible.
  • Recursive PAV Rule: For cases where PAV itself might not yield a core-stable committee, the authors introduce a novel "recursive PAV" rule. This rule iteratively "patches" a committee by adding candidates from blocking coalitions and re-evaluating, ensuring that eventually a core-stable committee is found.
  • Farkas' Lemma: This mathematical lemma is used to provide certificates of infeasibility for the LP problems, allowing for verifiable proofs of the results.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and uses constructed examples and computational searches rather than real-world datasets.

Key Insights and Ideas

  • PAV's Surprising Robustness: The PAV rule, despite being known to fail the core in some specific instances, turns out to be remarkably good at producing core-stable committees, especially for smaller committee sizes ($k \le 7$). This suggests PAV is a strong candidate for practical applications where fairness is paramount.
  • The Power of LP for Existence Proofs: The paper demonstrates a sophisticated application of linear programming not just for finding optimal solutions, but for proving the existence of solutions (or non-existence of counterexamples) in a complex combinatorial setting.
  • Recursive Patching as a General Strategy: The "recursive PAV" rule offers a constructive approach to finding core-stable committees. By iteratively addressing blocking coalitions, it provides a systematic way to guarantee a stable outcome, even when simpler methods fail.
  • Small Parameters Matter: The results highlight that for many practical scenarios (small $k$ or small $m$), the core is guaranteed to be non-empty, making these scenarios more amenable to fair committee selection.

Key Results

  • Core Existence for Small Committee Sizes: The paper proves that for committee sizes $k \le 8$, a core-stable committee always exists for any number of voters and candidates. This improves upon prior results that only guaranteed existence for $k=3$.
  • Core Existence for Few Candidates: For instances with $m \le 15$ candidates, a core-stable committee is guaranteed to exist, regardless of the committee size $k$ (as long as $k \le m$).
  • PAV's Performance: The PAV rule always selects a core-stable committee when $k \le 7$, and at least one core-stable committee when $k=8$.
  • Recursive PAV Guarantees: The proposed recursive PAV rule is shown to always find a core-stable committee when $m \le 15$.

Limitations and Future Work

  • General Case for Large $m$ and $k$: While the paper provides strong results for small $k$ and $m$, it does not prove core existence for arbitrarily large $m$ and $k$. The recursive PAV rule fails for $m=16$ in some cases, suggesting that a more general approach might be needed.
  • Droop Quota: The paper notes that their positive results do not extend to the "Droop quota," a stricter fairness criterion. PAV fails the Droop core for $k=6$, and the recursive PAV rule also struggles with this criterion.
  • Computational Complexity: While LP is used effectively, the complexity of solving these LPs can still be a barrier for very large instances, even though the paper pushes the boundaries of what's computationally feasible.
  • Future Work: The authors suggest exploring whether the core is always non-empty for $n=3$ voters, and investigating more general methods for proving core existence beyond the specific recursive PAV approach. They also point out the difficulty of finding counterexamples for other voting rules, suggesting that new theoretical tools might be needed.

Summary updated

BibTeX
@inproceedings{peters2025core,
  author = {Dominik Peters},
  title = {{The Core of Approval-Based Committee Elections with Few Seats}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/447},
}
Figure