CS Paper Radar

Exact Sizewise Least Cores for Candidate-Disjoint Approval Chains

Jiarui Fang

cs.GT ·submitted 2026-09-03 23:08 UTC · v1
code/data

Abstract

For approval-based committee elections, the sizewise least-core value $Γ(P)$ minimizes the maximum excess support of a deviation over size-$k$ committees. Deviations are nonempty and contain at most $k$ candidates, with support measured relative to their Hare quota. A negative value certifies core nonemptiness, while $-Γ(P)$ is the largest worst-case quota shortfall secured by any committee. We quantify this margin on candidate-disjoint approval chains, a domain whose qualitative core nonemptiness is already known. We first factor each committee's deviation score over disjoint components. For chains, a closed local table yields the exact value and an attaining committee in polynomial time for rational weights. For nonnegative normalized real weights, let $q_{\mathrm{act}}\ge1$ count the connected components of the positive-support incidence graph. Then \[ Γ(P)\le-\frac{1}{k\min\{q_{\mathrm{act}},k+1\}}. \] Explicit extremal profiles show that this dependence on the active-component count is sharp. The margin is $1$-Lipschitz in total variation on the full ballot space. Each negative margin therefore certifies a neighborhood with nonempty core, even when perturbations leave the chain domain.

Comment
14 pages, code and other materials are available at: https://github.com/Baymax-ray/sizewise-least-core

Closest papers

Nearest neighbours by meaning across the whole index.

Existence of the Core in Approval-Based Committee Elections

cs.GT ·2026-09-10 ·Patrick Becker, Matthias Greger, Dominik Peters
theoryhighly cited similarity 0.70
Abstract · 43 pages, with a completely rewritten exposition of the argument

We resolve the central open question in the theory of approval-based committee elections: we prove that the core is always non-empty. This means that there always exists a committee for which no coalition of voters can deviate to an alternative committee of proportional size that every member strictly prefers. This property was introduced by Aziz et al. (2017) to capture proportional representation and coalitional stability, but no known algorithm achieved it except up to a constant approximation factor or in special cases. Our approach begins by strengthening the core to core+, which requires the committee to be robust even to fractional deviations. Using LP duality, this property can equivalently be defined in terms of a payment-based certificate under which no losing candidate gathers too much support. We then define a voting rule that chooses a committee admitting a certificate that maximizes a novel harmonic entropy objective function, which rewards balanced payment distributions. We show that the payment system associated with an optimal committee certifies that the committee satisfies core+, establishing existence. The same is true for local optima, which allows us to design a polynomial-time algorithm computing a core+ committee.

0.45

Sparse Disapproval Guarantees a Nonempty Hare Core

cs.GT ·2026-09-03 ·Jiarui Fang
theorycode/data similarity 0.68
Abstract · 4 pages, code and other materials are available at: https://github.com/Baymax-ray/approval-core-corank-two

An approval committee is Hare-core stable if no coalition meeting the Hare quota can strictly improve by moving to another candidate set. Whether every approval election has such a committee remains open. We prove nonemptiness when each voter disapproves at most two candidates, with no bounds on the numbers of candidates, seats, or voter types. The result also permits arbitrary positive rational voter weights. Our deterministic rule represents a committee by its missing set. It first maximizes weighted coverage of two-candidate disapproval sets and then maximizes total disapproval incidence. An exact coverage inequality excludes targets one seat below the committee. The incidence objective excludes unanimous equal-size targets, while targets of size at most $k-2$ cannot improve any voter. Two implementation-level independent verifiers audit overlapping finite grids. The symbolic proof, not this bounded enumeration, establishes the theorem's unbounded quantifiers. The argument identifies complement-side coverage as a tractable mechanism for a broad parameter range within a sharply defined preference domain.

0.31

The Distortion of Threshold Approval Multiwinner Voting

cs.GT ·2026-10-09 ·Mohamad Latifian, Marzieh Nilipour, Alexandros A. Voudouris
similarity 0.67
Abstract

We study multiwinner voting with $n$ voters and $m$ candidates, where the goal is to select a committee of size $k$. Voters have unit-sum cardinal utilities but report only coarse information induced by $t$ utility thresholds. In particular, each voter partitions the candidates into approval sets, with the utilities of all candidates in the same set lying between the same pair of consecutive thresholds. We model the utility of each voter for a committee as a normalized monotone symmetric norm, capturing, among others, additive welfare, best-representative utility, top-$r$ welfare, $\ell_p$ welfare, and normalized non-increasing ordered weighted averages. We design a deterministic rule with distortion at most $2(2m)^{1/t}$ and a randomized rule with distortion at most $2\min\{m^{1/(t+1)},m/k\}$. These guarantees hold for every committee size $k$ and every norm in our framework. Consequently, a single threshold yields distortion $O(m)$ for deterministic rules and $O(\sqrt{m})$ for randomized rules, while $O(\log m)$ thresholds suffice for constant distortion. We complement these results with norm-dependent lower bounds that asymptotically match our upper bounds for constant committee sizes, including the single-winner case.

0.18

Sequential Phragmén Guarantees 2-Approximate Core Stability

cs.GT ·2026-09-11 ·Jianan Lin, Chenhao Wang
similarity 0.65
Abstract

We study approximately stable committee selection under approval preferences, following Cheng et al.~[EC~2019] and Jiang, Munagala, and Wang~[STOC~2020]. In an approval-based committee election, $n$ voters each approve a subset of the candidates, and a committee of size $k$ is selected. A size-$k$ committee is $λ$-stable if, for every nonempty subset $T$ of candidates, the number of voters who strictly prefer $T$ is less than $λ$ times the proportional share $\frac{n|T|}{k}$. We consider sequential Phragmén, a classical polynomial-time voting rule, and prove that it always returns a $2$-stable committee. This implies that the $2$-core is always nonempty and improves upon the $3.651$-stability guarantee of Gao, Sun, and Vondrák~[EC~2026]. The guarantee also extends to weighted voters and is tight even for unweighted elections: for every $1\leλ<2$, sequential Phragmén can return a committee that is not $λ$-stable. Compared with the exact-core algorithm developed in concurrent work by Becker, Greger, and Peters~[arXiv~2026], sequential Phragmén is simpler to implement, and our proof of its $2$-stability is elementary.

0.39

Nash Core in Multiwinner Election

cs.GT ·2026-08-31 ·Ashish Goel, Zhihao Jiang, Chenghan Zhou
theory similarity 0.65
Abstract

In the approval-based committee selection problem, a committee is said to be in the core if no subset of voters has an incentive to deviate by selecting a \emph{blocking} committee of proportional size, such that every voter in the deviating group strictly prefers the blocking committee. We consider the setting where candidates can be selected fractionally. Under a mild regularity assumption, we show that there always exists a weighting of candidates such that the fractional committee maximizing the candidate-weighted Nash Social Welfare is in the core. We refer to such a solution as being in the \emph{Nash core}. Additionally, we show that a Nash core solution admits a payment assignment between voters and candidates, where each voter pays a candidate they approve in proportion to the weight. For the discrete setting, where each candidate is either included or excluded from the committee, we prove that every approval-based committee election with at most eight equally weighted voters has a core committee by rounding the fractional Nash core solution. Although the non-emptiness of the core in this setting remains an open question and checking core membership is coNP-hard, we extend the notion of the Nash core to the discrete case, yielding a formulation that is efficiently verifiable and offers a promising path toward establishing core existence in discrete settings. Finally, we test our approach on real voting data using a payment-guided heuristic. We empirically show that the Nash core solution can be efficiently computed through an iterative algorithm in both the fractional and discrete settings.

0.38

Best-of-Both Worlds Proportionality in Structured Committee Elections

cs.GT ·2026-10-20 ·Dimitris Avramidis, Mark de Berg, Ulrike Schmidt-Kraepelin
similarity 0.63
Abstract

We study randomized committee elections with additive preferences, where we seek best-of-both-worlds proportionality. That is, we strive for strong guarantees for the selection probabilities ex ante and each realized committee ex post. We focus on structured preferences and introduce antichain single-peakedness, a restricted domain generalizing single-peaked additive preferences as well as several well-studied approval domains. Our approach first computes a fractional committee and then decomposes it through a rounding rule called systematic rounding. Among profile-oblivious rounding rules, we characterize systematic rounding as the unique rule satisfying natural quota guarantees, and thereby the only promising rule for our two-step approach. We show that ex-ante core stability is incompatible with ex-post justified representation $JR$, even under single-peaked preferences. However, applying systematic rounding to certain fractional allocations that form so-called Lindahl equilibria yields ex-ante core stability and ex-post core stability up to one. Alternatively, we retain exact ex-post proportionality and approximate the ex-ante core using two parameters: $α$ raises the utility gain required for a deviation, while $β$ reduces the coalition's proportional share. We establish the tight threshold $αβ$=2. Below it, ex-post JR is incompatible even under single-peaked preferences; at and above it, adapting a fractional rule called BestRepresentative [Pierczyński and Skowron, 2022] and applying systematic rounding to its output yields ex-ante $α, β$-fractional core stability and ex-post PJR under antichain single-peaked preferences.

0.07

Learning Proportional Committees from Violation Feedback

cs.GT ·2026-08-31 ·Frank Connor
theory similarity 0.62
Abstract

We study violation-feedback learning of proportionally representative approval-based committees. In each round, a learner proposes a committee of size $k$. An oracle either accepts the proposal or adversarially selects a representation violation with respect to a single fixed hidden approval profile. We compare \emph{full-witness feedback}, which reveals the violation level, an omitted candidate, and the affected voter group, with \emph{candidate-only feedback}, which reveals only that candidate. The target notions are proportional justified representation plus (PJR+) and extended justified representation plus (EJR+). In every setting we study, the number of rejected proposals can be bounded solely in terms of $k$, with no dependence on the numbers of voters and candidates. For PJR+, the optimal deterministic and randomized rejection complexities equal $k$ under both feedback models. For EJR+, the picture is more nuanced. Under full-witness feedback, we prove an $Ω(k^{3/2})$ deterministic lower bound and give a deterministic polynomial-time algorithm using $O(k^2\log k)$ rejections. Under candidate-only feedback, randomization achieves $O(k^2\log k)$ expected rejections via uniform random deletion, while deterministic exhaustive branching gives a $2^{O(k^2(\log k)^2)}$ rejection bound. Even with full-witness feedback, randomized learners may require $k$ rejections.

0.22

Finding Representative and Approximately Efficient Committees

cs.GT ·2026-09-07 ·Dominik Peters, Rohit Vaish, Jatin Yadav
similarity 0.62
Abstract

In approval-based committee voting, proportional approval voting (PAV) is a well-studied rule that combines proportional representation with Pareto efficiency. However, computing a PAV committee is NP-hard, raising a natural question: Can the proportionality and efficiency properties of PAV be achieved via computationally efficient procedures? We make two contributions toward answering this question. First, building on the known proportionality guarantees of the local-search-based variant of PAV (or local PAV), we systematically study its efficiency properties. We show that local PAV committees are weakly Pareto optimal, meaning that no other committee is strictly preferred by every voter. We also identify limitations: Local PAV guarantees only a $2$-approximation to fractional Pareto optimality ($2$-fPO) and a $2/3$-approximation to the optimal PAV score, and both bounds are tight. In contrast, global PAV is Pareto optimal and satisfies the stronger $α^\star$-fPO guarantee, where $α^\star \approx 1.346$ is the unique solution of $\int_0^{α^\star} \frac{1-e^{-y}}{y} \, dy = 1$, and this approximation is tight. Second, we design a polynomial-time algorithm that combines the best of these guarantees. The committee returned by our algorithm satisfies EJR$+$ (a proportionality guarantee), $α^\star$-fPO, and weak Pareto optimality. It also achieves a $0.79$-approximation to the optimal PAV score, matching the best possible polynomial-time approximation assuming $P \neq NP$. Our algorithm works by pipage rounding a concave relaxation of the PAV objective and using that committee to initialize local PAV, thereby combining global approximation guarantees with local search stability.

0.42