Source-linked AI summary
Sequential Phragm\'en Guarantees 2-Approximate Core Stability
Jianan Lin, Chenhao Wang
TL;DR
Whether an exactly stable committee always exists in approval-based committee voting remains unresolved, motivating guarantees for relaxed stability. The paper analyzes weighted sequential Phragmén and proves it always returns a 2-stable committee, making the 2-core nonempty.
Problem
Whether the exact core is always nonempty in approval-based committee voting remains an open problem, motivating the search for small λ-stability guarantees.
Source: §1 · pp. 1–2Method
The paper analyzes weighted sequential Phragmén using a combinatorial argument based on voter-load updates and candidate-credit bounds.
Source: §1 · p. 2, §4 · pp. 5–6Results
Takeaways & Limitations
The result guarantees a nonempty 2-core, and rationally encoded voter weights allow a 2-stable committee to be computed in polynomial time.
Source: §4 · p. 8The result does not settle exact-core nonemptiness, and its proof essentially relies on unit-cost candidates and integer-valued approval utilities.
Source: §5 · p. 8
Abstract
from arXiv · showhide
In an approval-based committee election, a committee of size $k$ is selected from a set of candidates to represent voters of total weight $n$, each of whom has positive weight and approves a subset of the candidates. A size-$k$ committee is $\lambda$-stable if, for every nonempty subset $T$ of candidates, the total weight of voters who strictly prefer $T$ is less than $\lambda$ times the proportional share $n|T|/k$. Whether there exists a committee that is exactly stable, corresponding to $\lambda=1$, remains a major open problem in approval-based committee voting. Thus, a natural objective is to identify small values of $\lambda>1$ for which $\lambda$-stability can always be guaranteed. We prove that weighted sequential Phragm\'en, a classical and natural rule, always returns a $2$-stable committee of size $k$. Since the $\lambda$-core is the set of all $\lambda$-stable committees, our result implies that the $2$-core is always nonempty. This improves upon the previously best-known guarantee, due to Gao, Sun, and Vondr\'ak~[EC~2026], that a $3.651$-stable committee always exists.
1 Introduction
Approval-based committee voting selects fixed-size committees from voters’ approvals, but whether an exactly stable committee always exists remains open. This paper studies weighted sequential Phragmén and proves a 2-stability guarantee.
1 Introduction
- Whether an exactly stable committee always exists remains open, despite existence results for instances with bounded committee size, candidate count, or voter types.The exact core is nonempty when k ≤ 8, |C| ≤ 15, or there are at most seven distinct voter types.Source: §1 · p. 1
- Earlier relaxations yielded a 16-stable committee, while a general monotone-preference result gave 32-stability and a later approval-based result gave 3.651-stability.Jiang, Munagala, and Wang [9] established the 16 and 32 guarantees; Gao, Sun, and Vondrák [6] established 3.651.Source: §1 · p. 2
- Sequential Phragmén builds a committee by selecting the candidate whose approvers can cover its unit cost at the lowest common voter-load height.Approvers’ loads below that height rise to it, leaving less-loaded voters better positioned to support later candidates.Source: §1 · p. 2
- Weighted sequential Phragmén guarantees 2-stability for arbitrary positive real voter weights and any tie-breaking, improving the previous 3.651 guarantee.The proof is combinatorial rather than based on Lindahl equilibria and rounding.Source: §1 · p. 2
- Core stability considers every coalition and alternative candidate set, unlike proportional-representation notions focused on structured cohesive groups; other core relaxations use different preference models or thresholds.Peters and Skowron [12] study utility-improvement relaxations; Fain, Munagala, and Shah [7] and Munagala et al. [10] study other public-good or committee-selection settings.Source: §1 · p. 2
2 Model
The model represents an election through candidates, positively weighted voters, approval sets, and a fixed committee size. It defines objections through alternative candidate sets and identifies stable committees as those admitting no qualifying deviation.
2 Model
- An instance consists of a finite candidate set, finite voters with positive real weights and approval sets, and a committee size k; every candidate is assumed approved by someone.An ordinary unweighted election is the special case in which every voter has weight one.Source: §2 · pp. 2–3
- A feasible committee W is a candidate set of size k, and each voter’s approval utility for a set D is the number of approved candidates in D.Source: §2 · p. 3
- A group may object through a nonempty alternative set; a committee is λ-stable when it admits no λ-blocking deviation, and the λ-core collects all such committees.The exact core is the 1-core.Source: §2 · p. 3
- Alternatives may overlap the committee, empty approval sets are permitted, and alternatives larger than k automatically satisfy the stated condition for λ ≥ 1.Source: §2 · p. 3
3 Weighted sequential Phragmén
Weighted sequential Phragmén funds candidates by raising their approvers’ loads to a common height, with each step adding one unit of weighted load. The paper establishes that every execution returns a 2-stable size-k committee, regardless of tie-breaking.
3 Weighted sequential Phragmén
- The rule selects the candidate with the lowest funding height, raising its approving voters’ loads to the first common height at which they cover its unit cost.The increase in water corresponds to the added weighted load used to fund the candidate.Source: §3 · p. 3
- Each funding height exists uniquely, selected heights are positive and nondecreasing, and every selection adds exactly one unit of total weighted load.The funding function is continuous, eventually increases without bound, and is strictly increasing once positive.Source: §3 · p. 4
- For rationally encoded voter weights, the algorithm can be implemented in polynomial time, while the stability theorem applies to arbitrary positive real weights.Funding heights are computed by sorting approvers’ current loads and solving a piecewise-linear equation.Source: §3 · p. 5
- Every tie-breaking execution of weighted sequential Phragmén returns a 2-stable size-k committee.The guarantee applies to every finite weighted approval election.Source: §3 · p. 5
4 Proof
The proof uses load updates and a strict area bound to exclude every 2-blocking deviation, establishing 2-stability and a nonempty 2-core. It also gives polynomial-time computation for rationally encoded voter weights.
4 Proof
- The load bound contradicts the lower bound L ≥ k/n whenever a coalition reaches twice its proportional share.The proof handles the boundary 2|T| = k as well as the range where 2|T| > k is automatic.Source: §4 · pp. 5, 8
- History gaps measure voter load increases between approved winners, and the weighted gaps ending at each selected candidate sum to that candidate’s unit payment.The final artificial gap ensures each voter’s gaps sum to the final load.Source: §4 · p. 5
- The area lemma aggregates unused credit across unelected candidates, with multiplicity for voters who approve several, and supplies the strict inequality at the blocking threshold.Its strict sign excludes a coalition exactly at its blocking quota.Source: §4 · pp. 5–6
- A deviation is split into retained winners and added candidates; actual payments cover the retained part, while an area inequality bounds the additions.Voters who prefer the deviation must approve enough additions to replace dropped approved winners and gain one more.Source: §4 · pp. 5, 6, 8
- The proof excludes every 2-blocking deviation, and the resulting theorem guarantees a nonempty 2-core.For rationally encoded voter weights, weighted sequential Phragmén computes a 2-stable committee in polynomial time.Source: §4 · p. 8
5 Discussion and open questions
Sequential Phragmén guarantees a 2-core for approval-based committee elections, improving the factor 3.651 guarantee to 2. The result does not settle exact-core existence, and the proof depends essentially on unit-cost candidates and integer-valued approval utilities.
5 Discussion and open questions
- Sequential Phragmén gives a universal 2-core guarantee, improving the group-size approximation factor from 3.651 [6] to 2.The guarantee holds for arbitrary tie-breaking and all positive voter weights; its proof is combinatorial and uses a single sequential water-filling execution.Source: §5 · p. 8
- The result does not resolve exact-core nonemptiness, and factor two is not known to be tight for approval preferences.The near-two lower bound for arbitrary monotone preferences [9] does not rule out an exact core for approval preferences.Source: §5 · p. 8
- The proof relies essentially on unit-cost candidates and integer-valued approval utilities; extending it to heterogeneous costs or general cardinal utilities remains open.The open questions include whether correlations among omitted candidates can strengthen the sum-of-squares estimate enough to improve factor two or reach the exact core.Source: §5 · p. 8