Sequential Phragmén Guarantees 2-Approximate Core Stability

Abstract

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én, 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ák~[EC~2026], that a $3.651$-stable committee always exists.

arXiv commentThis work is submitted on Aug 29th, 2026, independent with the exact core work of 2609.11912