Source-linked AI summary
Existence of the Core in Approval-Based Committee Elections
Patrick Becker, Matthias Greger, Dominik Peters
TL;DR
Core non-emptiness had remained a central open question in approval-based committee elections. The paper optimizes a harmonic-entropy objective over committees and payment systems; its local optima satisfy core+, yielding core existence and a polynomial-time computation result.
Problem
The non-emptiness of the core, a stability concept for proportional representation, had remained a central open problem.
Source: §1 · p. 1Method
Results
Every size-k committee maximizing V satisfies core+ for quota q, and every local maximum under single-candidate replacements satisfies core+ when q > n/(k + 1).
Source: §6 · pp. 15–16Takeaways & Limitations
The results establish core existence for every election instance and show that a Hare-core committee can be computed in polynomial time.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We settle the main open question in the theory of approval-based multi-winner elections: we show that there always exists a committee in the core. The core is a stability and group fairness concept. The proof introduces a new voting rule that optimizes an entropy-like objective function over committees and payment systems. All local optima of this objective function lie in the core, which implies that a core committee can be found in polynomial time.
1 Introduction
Core stability asks whether a coalition controlling a proportional share of seats can choose an alternative that makes all its members better off, and its non-emptiness had remained a central open problem. The paper proves core existence for every instance and gives a polynomial-time method, using a harmonic-entropy voting rule whose local optima satisfy the stronger core+ condition.
1 Introduction
- Core stability tests whether a coalition with a proportional share of seats can choose an alternative that strictly improves every member’s utility.Unlike EJR, coalition members need not agree on the same candidates.Source: §1 · p. 1
- Every election instance has a core-stable committee, including under the Droop quota, and a Hare-core committee can be computed in polynomial time.The proof also yields a polynomial-time method for finding a core+ committee.Source: §1 · p. 2
- The proposed rule optimizes over committees and payment systems using harmonic entropy, an objective designed to bound the effects of candidate additions and deletions.The approach combines a PAV-like global optimization with the flexibility of payment-based methods.Source: §1 · p. 2
- The proof strengthens core to core+: its payment-based certificate is related to Lindahl priceability, and local optima of the objective satisfy core+.The non-emptiness question for the core had remained a central open problem.Source: §1 · pp. 1–2
2 Preliminaries
An approval-based election consists of voters’ approval sets over candidates and a fixed committee size. The quota specifies how many voters are needed to deserve one candidate, with Hare as the default.
2 Preliminaries
- An election instance I = (A, k) consists of an approval profile and committee size; voter i’s utility for W is the number of approved candidates in W.Each voter submits an approval set A_i ⊆ C.Source: §2 · p. 3
- The quota q specifies how many voters are needed to deserve one candidate, and the default Hare quota is q = n/k.The stated quota range is n/(k + 1) < q ≤ n/k.Source: §2 · p. 3
- The notation defines committee additions and deletions, the probability simplex, non-negative reals, and the positive part of a real number.For a, (a)+ = max{a, 0}.Source: §2 · p. 3
3 The core and core+
The section characterizes core stability and introduces core+, a stronger condition that rules out fractional deviations. It gives a payment-based certificate for core+ and connects that certificate to priceability.
3 The core and core+
- A committee is in the core when no coalition can afford a proposal that makes every coalition member strictly better off.Affordability requires at least q voters per proposed candidate.Source: §3 · p. 3
- The core condition can be expressed as infeasibility of a binary-variable system, with assignment variables encoding each coalition member’s required improvement.For each participating voter, the assignment represents approval of at least u_i(W) + 1 candidates in the proposed set.Source: §3 · p. 3
- Core+ strengthens core by relaxing the integrality constraints, allowing fractional deviations and fractional participation by voters.A given committee’s core+ status can be checked by solving a linear program.Source: §3 · p. 4
- Core+ is characterized by the existence of a payment system with additional conditions, obtained as a positive certificate through Farkas’ lemma.The certificate is closely related to priceability.Source: §3 · p. 4
- A payment system assigns non-negative payments and reserves, with each voter paying at most one unit and each winner receiving at most the quota.The payment bounds alone do not guarantee fairness; additional conditions involving reserves for supporters of losing candidates characterize core+.Source: §3 · p. 4
- Core+ is equivalent to frugal Lindahl priceability, implies Lindahl priceability, and is implied by stable priceability.Stable priceability is not always satisfiable.Source: §3 · p. 6
4 Harmonic entropy
The section develops harmonic entropy as an objective over committees and payment systems, designed to reward broadly distributed payments. Water-filling operators make its behavior under a one-coordinate shift explicit, supporting the analysis of the objective.
4 Harmonic entropy
- The harmonic entropy objective rewards payment systems that spread voters’ payments more uniformly across approved winners and as many winners as possible.The proof shows that at an optimum, the payment system satisfies the conditions of Theorem 3.3, so the committee satisfies core+.Source: §4 · p. 6
4.1 Water-filling operators
- For each ℓ ≥ 1, fℓ(x) is the unique level at which lowering large coordinates releases enough mass to create ℓ new coordinates of that size.The shift operator Φ truncates existing coordinates at f1(x) and adds a coordinate of that size; it shifts the water-filling levels so fℓ(Φ(x)) = fℓ+1(x).Source: §4.1 · pp. 6–8
4.2 Defining harmonic entropy
- Harmonic entropy F is maximized at the uniform distribution, where it equals the (d − 1)-th harmonic number, and more concentrated distributions have lower potential.F is continuous, concave, symmetric, and unchanged by appending a zero coordinate.Source: §4.2 · pp. 8–9
- Applying Φ increases F(x) by exactly the largest coordinate of x, as the shifted water-filling terms cancel telescopically.For every distribution x, F(Φ(x)) − F(x) = max_j x_j.Source: §4.2 · p. 9
5 A new voting rule based on harmonic entropy
The section defines a voting rule by maximizing harmonic entropy over committees and their feasible payment systems. Exchange bounds connect candidate reserve loads to changes in the objective, supporting the core+ existence argument.
5 A new voting rule based on harmonic entropy
- The rule selects committees maximizing V(W), the largest total harmonic entropy attainable by a feasible payment system for W.V(W) maximizes the sum of voters’ harmonic entropies over payment systems in P(W).Source: §5 · p. 10
5.1 Exchange bounds for candidate additions and deletions
- When committee capacity exceeds voters’ total budget, some candidate can be removed with an objective loss strictly below the quota.This deletion bound complements the addition bound in the exchange argument.Source: §5.1 · p. 11
- A losing candidate with reserve load at least q raises the objective by at least q when added to the committee.The exchange proof redistributes supporters’ reserves among approved candidates while respecting their capacities.Source: §5.1 · pp. 11, 13
- The exchange construction distributes relevant reserves as payments to approved candidates, with each candidate’s total payment kept within quota.A flow saturating the source edges represents distributing all reserves.Source: §5.1 · p. 13, Figure 3 · p. 13
6 Existence of a core+ committee
The section establishes core+ existence by relating local objective improvements to reserve loads on losing candidates. It also proves existence under the strict Droop quota.
6 Existence of a core+ committee
- A committee maximizing V among size-k committees satisfies core+ for the specified quota q.Finiteness of the size-k committee set guarantees such a maximizer.Source: §6 · pp. 15–16
- If no single-candidate replacement improves V by the stated threshold, every losing candidate has reserve load below q, yielding the payment conditions for core+.Together with (O1), this gives the payment-system characterization in Theorem 3.3.Source: §6 · p. 15
- Every local maximum of V under single-candidate replacements satisfies core+.The improvement threshold is positive for the stated quota range.Source: §6 · p. 16
- Core+ is non-empty under the strict Droop quota.The proof takes a committee recurring among solutions for quotas approaching the Droop quota and rules out a fractional objection.Source: §6 · p. 16
7 Polynomial-time computation
The section gives a polynomial-time route to a core+-satisfying committee: it approximates the objective with a linear program and uses local search whose termination criterion certifies core+.
7 Polynomial-time computation
- If a committee fails core+, a single-candidate replacement improves its objective by at least δ, so sufficiently accurate objective estimates can detect an improving swap.The algorithm uses an approximation error of at most δ/4 to retain this guarantee.Source: §7 · pp. 16–17
- The linear program encodes water-filling thresholds with auxiliary variables, linearizing positive-part terms to represent the truncated objective.Maximization sets each threshold variable to its smallest feasible value, recovering the truncated objective.Source: §7 · pp. 17–18
- The truncated committee objective V_T(W) is computable by a polynomial-size linear program, with O(nkT) variables and constraints.For polynomially large T, truncation approximates the objective with inverse-polynomial accuracy.Source: §7 · pp. 17–18
7.1 Local search
- A committee satisfying core+ can be computed in polynomial time by repeatedly checking single-candidate replacements and returning a committee with no sufficiently large improving swap.The returned committee satisfies core+ because every replacement improves the true objective by less than δ.Source: §7.1 · p. 18
- The local-search procedure evaluates at most k(m−k) neighboring committees per iteration and runs in polynomial time using T=O(k^3).It performs at most 4k(k+1)H_k candidate replacements.Source: §7.1 · p. 18
8 Conclusion
The conclusion introduces a voting rule based on harmonic entropy. The authors are exploring its properties beyond core+ and suggest harmonic entropy may have other applications in proportional representation.
8 Conclusion
- The paper introduces a new voting rule based on a harmonic entropy objective function.The authors hope harmonic entropy may find other applications in the study of proportional representation.Source: §8 · p. 19
- The authors are exploring the rule’s properties beyond core+ and describe it as appearing overall very attractive.Source: §8 · p. 19
- The authors suggest harmonic entropy may have applications beyond this voting rule in the study of proportional representation.Source: §8 · p. 19