CS Paper Radar

Nearly Group-Separable Elections

Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich, Ildikó Schlotter

cs.GT cs.MA ·submitted 2026-09-27 13:03 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Outer Diversity of Condorcet Domains

cs.GT cs.AIcs.MA ·2026-09-30 ·Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak, Krzysztof Sornat, Stanisław Szufa +1 more
similarity 0.67
Abstract · 33 pages, 12 figures

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.

0.22

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

cs.GT ·2026-08-15 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.65
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

Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting

cs.GT ·2026-09-28 ·Jakub Dargaj, Aris Filos-Ratsikas, Paul W. Goldberg
similarity 0.64
Abstract

We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a given relative distance of the closest center. The problem has applications in binary $k$-center clustering and bioinformatics, but our main motivation comes from computational social choice. In the setting of multi-issue approval voting, we consider an algorithmic question that precedes any election: how should representatives be designed so that as many voters as possible are willing to delegate? We study the problem in two dimensions, namely the number of centers and the agreement threshold, parameters that are application-specific, and provide a complete picture of its computational complexity when entries may be missing. For the special case without missing entries, we extend our hardness results to any number of centers and large values of threshold, leaving a narrow range of thresholds unresolved.

0.21

Interlacing Committees with Edge-Expansion

cs.MA ·2026-11-19 ·Gili Bielous, Reshef Meir
similarity 0.64
Abstract

Approval-based committee selection has recently been studied through the lens of \emph{interlacing}, a framework for studying polarization in approval elections, in which committees induce a similarity graph over voters. The quality of committees is then evaluated through the connectivity of the resulting graph. We revisit the connectivity measures used in this framework and propose \emph{edge-expansion}, a classical graph-theoretic measure with well-established connections to polarization in networks, as the optimization objective. We provide a theoretical foundation for this proposal by relating interlacing to classical models of information diffusion and by comparing edge-expansion with previously proposed connectivity objectives, identifying qualitative differences in the structural properties they capture. Finally, we study the computational complexity of optimizing edge-expansion, showing that hardness persists even for voter-interval preferences, while the problem is polynomial-time solvable for every fixed committee size, with an improved dependence on the committee size for voter-candidate-interval preferences.

0.23

Proportionality in Elections under Feasibility Constraints and Ranked Ballots: The Solid Coalition Refinement Rule

cs.GT ·2026-11-06 ·Grzegorz Kwacz, Georgios Papasotiropoulos, Piotr Skowron
similarity 0.63
Abstract

We study elections with ranked ballots and general feasibility constraints, which indicate which sets of candidates are allowed as outcomes. We introduce the first proportionality axiom for this general setting and show that it extends the established notions from specific models that fit our general framework. We extend the Solid Coalition Refinement (SCR) rule to general constraints and prove that it satisfies our axiom exactly for matroid constraints. Although the naive implementation of SCR involves a step that is computationally intractable for weak orders, we show that in practical cases it can be implemented in polynomial time or efficiently in FPT time. We also illustrate limitations of this rule for approval ballots and provide its first empirical evaluation.

0.08

Faster Verification of PJR$^+$ via Mincuts

cs.GT ·2026-09-17 ·Drew Springham
similarity 0.62
Abstract · 15 pages, 10 page main body, 3 figures

PJR$^+$ is a polynomial-time verifiable proportionality axiom for approval-based committee elections, but its known polynomial-time verification procedure relies on general submodular-function minimisation. We show that its objective is a maximum-closure problem and give a direct mincut formulation of the problem on a bipartite graph. Using an almost-linear-time maximum-flow algorithm, this yields an $\mathcal{O}(m(nk)^{1+o(1)})$-time verifier, where $n$, $m$, and $k$ are the numbers of voters, candidates, and committee members, respectively. The dependence of this bound on each parameter separately is almost linear: it is linear in $m$, and almost linear in $n$ and $k$. The verifier also returns an explicit group witnessing a violation and admits a slower but immediately implementable variant based on the preflow--push mincut algorithm. Finally, for the parameterised axiom $α$-PJR$^+$, where $α$ is used as a multiplier in the group size, we demonstrate how to compute the largest value of $α$ for which a committee still fails the axiom using this mincut formulation.

0.12

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

Query-efficient winner prediction in district-based elections

cs.DS cs.AI ·2026-09-30 ·Koustav De, Debajyoti Kar, Swagato Sanyal
theory similarity 0.62
Abstract

In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality rule (i.e. the candidate getting the largest number of votes is declared the winner, breaking ties as per some fixed rule), and the overall winner is determined by applying plurality to the district winners; we assume that there is a unique winner amongst the district winners. The margin of victory of such an election is the minimum number of votes that must be altered so that the current winner ceases to be the unique district winner. We study the problem of predicting the winner of a district-based election in the query complexity model, where one has query access to individual votes. The objective is to minimise the number of queries. This setting captures exit polling, where queries correspond to interviewing voters, and is closely related to problems in query complexity and property testing. Assuming that the margin of victory of the election is at least eps N, Dey, Kar and Sanyal (AAMAS 2023) gave algorithms for the case of two candidates with error probability del and query complexity tilde{O}(1/eps^6 log^2 1/del), which improves to tilde{O}(1/eps^4 log^2 1/del) under the additional assumption that district populations are balanced. Our main result is an adaptive randomised algorithm that, for an arbitrary district-based election and any error parameter del, with probability at least 1-del, predicts the winner correctly using tilde{O}(1/eps^2 log m/del log 1/del) queries. In particular, we improve the bounds of Dey et al. for arbitrary district populations and extend their results to any number of candidates. Furthermore, for constantly many candidates, our algorithm nearly matches a lower bound of Omega(1/eps^2 log 1/del) on the query complexity that holds even for two candidates and a single district.

0.21