CS Paper Radar

Sampford Apportionment Satisfies Threshold Monotonicity

Haris Aziz, Simon Mackenzie, Mashbat Suzuki

cs.GT ·submitted 2026-08-24 09:48 UTC · v1
theory

Abstract

Apportionment distributes a fixed number of legislative seats among political parties in proportion to their vote shares. Randomization can satisfy quota in every realization and exact proportionality in expectation, but these requirements determine only the parties' marginal seat distributions. We study threshold monotonicity, which requires that when every standard quota inside a coalition weakly increases and every standard quota outside it weakly decreases, the coalition's new seat total stochastically dominates its old one. We prove that Sampford apportionment satisfies threshold monotonicity, resolving the threshold-monotonicity conjecture of Correa et al. (2024). Complementing this result, we prove that no quota-respecting, ex-ante proportional method satisfies pairwise threshold monotonicity even for disjoint coalitions when there are at least seven parties. This impossibility applies whether or not the method has full support.

Closest papers

Nearest neighbours by meaning across the whole index.

Envy-Free Randomized Apportionment

cs.GT ·2026-10-16 ·Francesco La Commare, Jamie Tucker-Foltz, Victor Verdugo
theory similarity 0.75
Abstract

The United States allocates representatives to each state in proportion to its population, while many parliamentary democracies select representatives from party lists in proportion to the number of votes each party receives. In both settings, the legislature's small size necessitates rounding to the nearest whole number of seats. Recent work has shown a plethora of ways to randomly round seat shares to achieve perfect ex ante fairness. As a result, party (state) $i$ may have a larger number of votes (population) than party $j$ but receive fewer seats. In this case, we say that party $i$ envies party $j$. We investigate the extent to which such envy is avoidable. Specifically, we seek to design apportionment rules that minimize the expected number of envious pairs $(i, j)$. If the expectation is zero, we say that the seat allocation is envy-free. On the negative side, we show that any $n$-party apportionment rule that ignores lower quotas (the floors of the deserved number of seats for each party) suffers from a worst-case envy of $Θ(n^2)$, even on instances where an envy-free allocation exists. All previously studied apportionment rules fall into this class and thus do a poor job of minimizing envy. In the case where all lower quotas are equal, we prove that all allocations have the same expected envy. In the general case, we we introduce a general polynomial-time LP framework for a large class of apportionment objectives, including minimizing the expectation and variance of envy, by efficiently solving the separation problem on the dual. Finally, we empirically demonstrate that envy-free allocations exist very frequently, including in every historical instance from the US decennial census. Taken together, these results provide a clear recipe for implementing randomized apportionment in a less objectionable way in practice.

0.06

Existence of the Core in Approval-Based Committee Elections

cs.GT ·2026-09-10 ·Patrick Becker, Matthias Greger, Dominik Peters
theoryhighly cited similarity 0.67
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

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

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

cs.GT ·2026-08-27 ·Paul Gölz, Hannane Yaghoubizade
similarity 0.66
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

Proportional Representation for Almost-Solid Coalitions and the Proportional Veto Core for Rankings

cs.GT ·2026-11-19 ·Evi Micha, Fatih Erdem Kizilkaya
similarity 0.65
Abstract

A proportional ranking should give groups of voters representation commensurate with their size at every prefix. Proportionality for solid coalitions (PSC) provides this guarantee to groups whose members rank the same set of candidates above all others. How much representation should a group receive when a few outside candidates disrupt that agreement? We extend the proportional veto core to rankings through candidatewise and setwise guarantees. We show that setwise veto protection is equivalent to robust Rank-PSC under reversal of both the voters' preferences and the collective ranking. Robust Rank-PSC extends representation guarantees to almost-solid coalitions at every prefix. Each distinct outside candidate that disrupts a coalition's agreement reduces its guaranteed representation by at most one, and this bound is tight. Using reverse-sequential variants of Ordered Phragmén and STV, we construct rankings satisfying robust Rank-PSC$+$ in polynomial time. This stronger axiom preserves the guarantee after deleting any suffix of the collective ranking and restricting voters' preferences to the remaining candidates. Verifying robust Rank-PSC is coNP-complete, whereas verifying robust Rank-PSC$+$ takes polynomial time. We also introduce Rank-Aligned PJR$+$, which requires the first $r$ candidates of the collective ranking to satisfy PJR$+$ when each voter approves their top $r$ candidates. We give a polynomial-time algorithm that meets this requirement simultaneously for every $r$. For fixed-size committees, the Expanding Approvals Rule guarantees Rank-PJR$+$ but can violate robust PSC regardless of how ties are broken or payments are assigned. We give a modification that satisfies both guarantees for any prescribed committee size.

0.14

Stable Voting Rules on the Edge of Optimal Metric Distortion

cs.GT ·2026-09-08 ·Ziyi Cai, Fabian Frank, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang +1 more
theory similarity 0.65
Abstract

We prove the existence of a randomized voting rule with metric distortion at most $2.1248$, within $0.013$ of the lower bound of $2.11264$. Our rule comes from a generalization of \emph{stable $k$-lotteries} developed in the context of committee selection. In contrast to prior work, our rule samples from a single distribution derived from a zero-sum game, without mixing between voting rules. Our result also gives sharp distortion bounds for stable $k$-lotteries. In particular we show that stable $2$-lotteries have distortion $7/3$, despite only relying on aggregate preferences over triples of candidates, and that stable $2$-lotteries are optimal in this class of voting rules.

0.37

Veto Proportionality in Multiwinner Voting with Ranked Preferences

cs.GT ·2026-11-14 ·Haris Aziz, Yuhang Guo, Patrick Lederer
similarity 0.64
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

Best-of-Both Worlds Proportionality in Structured Committee Elections

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