CS Paper Radar

Outer Diversity of Condorcet Domains

Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs

cs.GT cs.AIcs.MA ·submitted 2026-09-30 21:13 UTC · v1

Abstract

A Condorcet domain is a set of rankings over a given candidate set, such that every election that consists only of (an odd number of) votes from the domain has a transitive majority relation. We study outer diversity of Condorcet domains, i.e., a measure that quantifies expected swap distance from a random vote to a closest one in the domain. We numerically analyze outer diversity for maximal Condorcet domains with few candidates, and then we establish its asymptotic behavior for several special domains, mostly obtaining theoretical results.

Comment
33 pages, 12 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Nearly Group-Separable Elections

cs.GT cs.MA ·2026-09-27 ·Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich +1 more
similarity 0.67
Abstract

We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several other domains, including caterpillar group-separable, balanced group-separable, single-peaked, and single-crossing ones. Our problem is generally intractable, but we find practical FPT algorithms parameterized by the number of candidates or swaps. For the latter case, our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.

0.14

Condorcet-Winning Sets and Peer Selection in Planar Metric Elections

cs.GT cs.CG ·2026-08-27 ·Gabriel de Azevedo, Ulysse Hennebelle
theory similarity 0.62
Abstract

In ranked-choice voting, a Condorcet-winning set is a group of candidates for which no outside candidate is preferred to every member of the group by a majority of voters. We study Condorcet-winning sets in planar metric elections, where voters rank candidates according to their distance under a given norm. We formulate general metric elections, peer selection, and the one-round Voronoi game as instances of a two-player Stackelberg game and place these problems in a common hierarchy. We also introduce a new variant, which we call strong peer selection. Our main result concerns peer selection under the $\ell_1$ and $\ell_\infty$ norms. We prove that every planar instance admits a Condorcet-winning set of size at most three, even under strong peer selection. This follows from a new result for strong rectangular $\varepsilon$-nets. We show that, for every set of points in the plane, one can choose at most three input points that intersect every axis-parallel rectangle containing more than half of the points, improving the previous threshold of $9 / 16$ due to Ashok et al. Under the $\ell_2$ norm, we prove that every planar metric election admits a Condorcet-winning set of size at most four, improving on the general bound of five due to Song et al. Finally, we give new norm-independent bounds for the one-round Voronoi game.

0.22

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.61
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.33

Sampford Apportionment Satisfies Threshold Monotonicity

cs.GT ·2026-08-24 ·Haris Aziz, Simon Mackenzie, Mashbat Suzuki
theory similarity 0.60
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.

0.28

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

cs.GT ·2026-08-15 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.59
Abstract

In metric social choice, voters and candidates lie in a common but unknown metric space, voters rank candidates by distance, and a voting rule seeks to minimize total distance to the voters. Its distortion is the worst-case approximation ratio relative to the minimum possible total distance. We study weighted-tournament rules (also known as C2 rules), which observe only the fraction of voters who prefer $a$ to $b$ for each pair of candidates $a,b$. These frequencies form a weighted tournament on candidates, a compressed representation that omits voter identities and the association of comparisons with individual voters. Prior work placed the optimal distortion of deterministic C2 rules between $3.1128$ and $3.9312$ [Charikar et al., EC 2025]. We introduce the Path-Unblanketed Set rule, a polynomial-time deterministic C2 rule with distortion at most $1+2\sqrt{2}\approx3.8284$ for every finite number of candidates. For elections with no more than six candidates, we prove with computer assistance that the distortion is at most $3.3346$. Furthermore, using an exact computer-assisted certificate, we provide a lower bound of $3.1828$ for deterministic C2 rules as a byproduct.

0.32

Coalitions, Stability, and Majority Jackpots: Frameworks for Unifying Majoritarian and Proportional Allocation in Multiwinner Elections

cs.GT ·2026-11-02 ·Kit Scriven, Nitin Kohli
similarity 0.58
Abstract

Social choice literature on multiwinner elections tends to focus on characterizing two distinct tasks: majoritarian representation and proportional representation. However, many real world systems can be viewed as operating between these two extremes, such as majority jackpot systems used in several countries throughout history. Towards the goal of better understanding these systems from a social choice perspective, we introduce two frameworks that encompass existing desiderata for majoritarian and proportional settings: coalitions, which encompasses properties such as fixed majority and solid coalitions; and stability, which encompasses various generalizations of Condorcet's criterion for single-winner elections, such as Gehrlein stability and local stability, among others. We develop theory and tools that characterize the mathematical and computational aspects of both frameworks across a wide array of preference structures (such as the unrestricted domain over candidates and the restricted domain of party lists). Building on this foundation, we shed new light on majority jackpot electoral systems, which to date have received limited mathematical analysis in the social choice literature.

0.14

Metric Distortion of Social Welfare Functions

cs.GT cs.MA ·2026-08-22 ·Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha
similarity 0.58
Abstract · 11 pages, 1 table

Metric distortion has primarily been studied for social choice functions, which select a single winner from ordinal preferences. We extend this framework to social welfare functions, which output a ranking of $m$ candidates. We associate each voter $v$ with a monotone weight vector $\mathbf{w}_v = (w_{v1},\ldots,w_{vm})$, specifying the importance of the $i$-th position for voter $v$, and define the cost of a ranking as the position-weighted sum of their distances to the ranked candidates. This model generalizes both single-winner voting and committee selection. We consider three information regimes. First, we study the setting where the positional weight vectors are known. A natural approach recursively applies a single-winner rule with distortion $β$ to construct the ranking one position at a time. We show that this yields distortion at most $3β$ in general. This gap is not merely an artifact of the analysis: we show that no analysis based solely on per-round guarantees can certify a bound better than $2β$. By exploiting structural properties specific to Fractional Veto of Kizilkaya and Kempe, we show that its recursive extension achieves the optimal distortion of 3. Second, when all voters share the same unknown weight vector, recursively applying any social choice function with distortion $β$ achieves distortion at most $1+(β-1)\text{range}(\mathbf{w})$, where $\text{range}(\mathbf{w})=(w_1-w_m)/w_1$ denotes the normalized range of the common weight vector $\mathbf{w}$. Finally, we study unknown heterogeneous weights. Without further assumptions, every rule has unbounded distortion. We therefore consider two natural normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. Under both models, we show that the optimal distortion is $Θ(m)$.

0.40

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