Proves that a core committee always exists in approval-based multi-winner elections and gives a polynomial-time algorithm via entropy optimization over committees and payments.
Yes, the paper "Existence of the Core in Approval-Based Committee Elections" by Becker, Greger, and Peters (arXiv:2609.11912, September 2026) proves that a core committee always exists in approval-based multi-winner elections. The authors establish this by introducing a new voting rule that optimizes an entropy-like objective function (called harmonic entropy) over committees and payment systems.
Key findings include: Core Existence: The study settles the main open question in the theory of approval-based elections by demonstrating that the core is non-empty for all instances. Polynomial-Time Algorithm: The proof shows that all local optima of the proposed harmonic entropy objective function lie in the core, implying that a core committee can be found in polynomial time. * Methodology: The approach combines the global structure of welfare-maximizing rules with the flexibility of payment-based methods, using a new analog of Shannon entropy to ensure stability and group fairness.
Summary
The paper studies core stability in approval-based multi-winner elections, where each voter approves a set of candidates and a fixed-size committee is selected. The model also allows monetary payments or transfers as part of the outcome. A committee is in the core if no coalition of voters can block it by choosing a different committee and redistributing payments so that every member of the coalition weakly prefers the new outcome and at least one member strictly prefers it. The main theoretical contribution is an existence result: every such election instance admits a core committee. This is a meaningful guarantee because core stability is a strong coalition-proof notion, and the multi-winner approval setting is inherently combinatorial, so the existence of a stable committee is not immediate.
The paper’s constructive contribution is a polynomial-time algorithm that computes a core committee together with an associated payment scheme. The method is based on entropy optimization over committees and payments, converting a combinatorial stability problem into a tractable optimization formulation. The entropy-regularized approach is key to handling the exponential number of possible committees while preserving the economic interpretation of the core constraints. Rather than merely providing an existence proof, the algorithm makes core stability computationally accessible.
This result matters because it bridges social choice theory, mechanism design, and optimization. Core stability is a natural desideratum for collective decision-making: a stable outcome is one that no group of agents can credibly challenge by reorganizing around an alternative. By proving that such outcomes always exist in approval-based multi-winner elections and by giving an efficient way to find them, the paper strengthens the theoretical foundation of committee selection mechanisms. It also has practical relevance for settings such as participatory budgeting, platform recommendation, and public decision-making, where committee outcomes may be accompanied by budgets, subsidies, or other forms of compensation.