CS Paper Radar

Nash Core in Multiwinner Election

Ashish Goel, Zhihao Jiang, Chenghan Zhou

cs.GT ·submitted 2026-08-31 23:32 UTC · v1
theory

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.

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.78
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

Best-of-Both Worlds Proportionality in Structured Committee Elections

cs.GT ·2026-10-20 ·Dimitris Avramidis, Mark de Berg, Ulrike Schmidt-Kraepelin
similarity 0.75
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

Veto Proportionality in Multiwinner Voting with Ranked Preferences

cs.GT ·2026-11-14 ·Haris Aziz, Yuhang Guo, Patrick Lederer
similarity 0.74
Abstract · Abstract shortened due to arXiv length restrictions

Proportional representation in committee voting with ranked preferences requires voter groups to influence the selected committee in proportion to their size. Existing axioms, such as proportionality for solid coalitions (PSC), demand that like-minded groups of voters are entitled to elect a fair number of candidates to the committee. However, in applications where voters are collectively affected by the entire committee, it may be equally important that no group is confronted with a disproportionate number of candidates that it regards as undesirable. Motivated by this, we initiate the study of veto proportionality in committee elections with ranked preferences. Our central notion, the proportional multiwinner veto core (PMVC), generalizes Moulin's proportional singlewinner veto core to multiwinner elections by allowing groups of voters to partially veto sets of candidates. We analyze how the PMVC relates to existing fairness notions and design rules that are guaranteed to select committees from the PMVC. Specifically, we first introduce a duality framework that connects inclusion- and exclusion-based fairness notions and show, e.g., that the dual axiom of the PMVC strengthens PSC. We further show that STV satisfies the dual axiom of the PMVC, which also implies the existence of committees in the PMVC. Subject to a strengthening of committee monotonicity, we characterize the rules that always return committees in the PMVC as sequential adaptations of singlewinner voting rules that always select from the proportional singlewinner veto core. By our duality framework, this also gives rise to a new class of rules that satisfy PSC. We further prove that the dual axiom of the PMVC and RankPJR+ are jointly satisfiable, thereby pushing the frontier of fairness guarantees that can always be attained. Finally, we show that deciding whether a given committee belongs to the PMVC is coNP-complete.

0.09

Sparse Disapproval Guarantees a Nonempty Hare Core

cs.GT ·2026-09-03 ·Jiarui Fang
theorycode/data similarity 0.71
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

Robust Proportionality Axioms for Additive Utilities

cs.GT ·2026-10-11 ·Piotr Skowron
similarity 0.71
Abstract

We study the model of participatory budgeting, in which a subset of candidates is selected subject to a budget constraint. Voters express their preferences by assigning a numerical utility to each candidate. Our focus is on formal analysis of proportionality, a central notion of fairness in multi-winner elections. Intuitively, proportionality means that each group of voters should influence the election outcome roughly in proportion to its size. Recent "plus" axioms of proportionality are particularly appealing notions: they are verifiable in polynomial time, and they provide strong representation guarantees without requiring groups of voters to have cohesive preferences. However, their existing formulations are restricted to approval-based preferences. We generalise extended justified representation plus (EJR+), and Core plus (Core+) to general additive utilities. Our approach builds on a payment-based interpretation of proportionality: candidates' costs are shared among their supporters, with the aim of balancing voters' total payments.

0.33

Approval-Based Apportionment: Like Portioning, Approximately like Committee Voting

cs.GT ·2026-08-27 ·Paul Gölz, Hannane Yaghoubizade
similarity 0.70
Abstract

We study approval-based apportionment, a variant of committee elections in which candidates ("parties") can be selected several times. We show that the proportionality axioms EJR, EJR+, and FJR coincide, and so do PJR, PJR+, and FPJR; that Lindahl priceability, an axiom implying core stability, is equivalent to a notion of approximate optimality with respect to the proportional approval voting (PAV) score; and that locally PAV-optimal committees are priceable. Approval-based apportionment (where a candidate receives an integer number of seats) lies between committee elections (zero or one seat) and portioning (a fractional number of seats). We formally connect portioning and apportionment by giving a construction that lifts axioms from apportionment to portioning and preserves implications between them. Several of our new implications between apportionment axioms are natural from a portioning perspective, leading us to believe that apportionment sits closer to portioning than to committee elections. None of them holds in committee elections, but several extend approximately, which makes apportionment a fruitful setting for conjecturing approximate relationships in approval-based committee elections.

0.44

Subgame-Perfect Nash Equilibria of Plurality Voting with Abstention: a PSPACE-Completeness Result for Restricted Ballots

cs.GT ·2026-09-21 ·Edith Elkind
theory similarity 0.69
Abstract

We consider sequential Plurality elections in which each voter may abstain or vote for a single candidate. Each voter assigns utilities to all candidates; for each voter, this induces a (weak) order over the candidates. Ties are resolved uniformly at random, and voting has a small positive cost, so that a voter prefers to abstain when their vote cannot change the election outcome. We consider a variant of this model where, for each voter, we additionally specify a prefix of her ranking, so that she is only allowed to vote for a candidate from that prefix (or abstain). We prove that for this variant of the model, deciding whether a designated candidate is among the election winners in a subgame-perfect equilibrium of the associated extensive-form game is PSPACE-complete. This partially resolves an open problem from the work of Desmedt and Elkind [2010].

0.10

The Distortion of Threshold Approval Multiwinner Voting

cs.GT ·2026-10-09 ·Mohamad Latifian, Marzieh Nilipour, Alexandros A. Voudouris
similarity 0.69
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