Papers for
election system designers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Proportional election rule works under complex voting constraints
Proportionality in Elections under Feasibility Constraints and Ranked Ballots: The Solid Coalition Refinement Rule
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.
Coalitions and stability unite majoritarian and proportional election methods
Coalitions, Stability, and Majority Jackpots: Frameworks for Unifying Majoritarian and Proportional Allocation in Multiwinner Elections
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.
Positional scoring rules optimize various voting welfare measures
Optimal Voting: Beyond a Utilitarian View
Abstract: A common measure of the quality of a voting rule is the social welfare of the alternatives it elects. Prior work shows that, when voter utilities are drawn from a neutral distribution, expected utilitarian welfare is maximized by a positional scoring rule. We extend this approach to the power mean family of welfare functions, which includes utilitarian, Nash, and egalitarian welfare as special cases. We show that, across the power mean family, a deterministic positional scoring rule (PSR) is asymptotically optimal for expected social welfare among all social choice functions and we characterize this rule for a broad class of utility distributions. We further show that, among randomized PSRs, plurality uniquely maximizes expected social welfare for all power means. Experimentally, we find that optimal score vectors often yield substantially higher welfare than canonical score vectors. On highly structured utility distributions, optimal score vectors take on novel shapes unlike existing canonical score vectors, highlighting open questions for future analysis.
Plurality voting often narrows to two candidates but can cycle unpredictably
Trembling toward Duverger: Convergence and Cycles in Synchronous Plurality Dynamics
Abstract: Duverger's law states that plurality elections tend to concentrate support on two candidates. Pivotal-voter models typically derive this from aggregate uncertainty about votes, so that two-candidate competition emerges in the limit of large electorates. We instead propose a model for a fixed, finite population. A poll reveals the current support counts, and each voter best responds under trembling-hand beliefs, assuming that every other voter may deviate with a small probability. Starting from truthful votes, we show that a single update typically suffices for the dynamics to converge to a stable profile in which every voter supports her preferred candidate among the two poll leaders. For any number of candidates and any full-support tremble belief, a four-vote lead of the runner-up over all lower candidates suffices; for three candidates, a lead of two suffices. As a consequence, under random preferences, Duverger's law emerges after one update with probability $1-\mathcal O(N^{-1/2})$. While these results may suggest that the dynamics always settle, convergence can fail. Mild period-two cycles already arise, with a few voters swapping ballots around an otherwise stable profile. We show that substantially richer behavior is possible, even with three candidates. Period-three cycles arise with six voters changing their ballots, and no such cycle can involve fewer than four. Cycles can also alternate the plurality winner. Moreover, larger electorates support ever longer cycles: for every odd $\ell\geq3$, truthful voting can lead to a cycle whose vote counts repeat every $\ell$ rounds and whose full ballot profile repeats every $2\ell$ rounds.
Complexity of clustering binary strings with missing data for voting design
Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting
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.
Fractional dichromatic number bounds domination size in tournaments
Fractional Dichromatic Number and Domination in Tournaments
Abstract: Bourneuf, Charbit and Thomassé [BCT25] showed that the domination number of a tournament can be bounded as a function of its fractional dichromatic number. The function proved was exponential and the tools were based on VC-dimension. In this paper, we present two new proofs of this theorem. The first proof is based on a reduction to the problem of bounding the domination number of a $(1/2-ε)$-majority tournament, for which [BCT25] and Charikar, Ramakrishnan and Wang [CRW26] gave tight bounds. This proof yields the same exponential bound on the domination number as in [BCT25]. The second proof gives a quasilinear bound for the domination in terms of the fractional dichromatic number. It was obtained via AI and was inspired by the recent book proof of the existence of a Condorcet Winning Set of size five due to Ramakrishnan [Ram26].
Stronger group representation methods in approval voting systems
Diverse Representation in Approval-Based Committee Voting
Abstract: The study of approval-based committee (ABC) voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin--Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P=NP), but both can be on the Candidate Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show Local DR performs well on multiple empirical measures of diversity.
Complexity of predicting winners in plurality voting with abstentions
Subgame-Perfect Nash Equilibria of Plurality Voting with Abstention: a PSPACE-Completeness Result for Restricted Ballots
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].
Voting methods balance candidate quality with fair group representation
Approval-Based Multiwinner Voting with Candidate Qualities
Abstract: We initiate the study of a new model of approval-based multiwinner voting in which each candidate carries an exogenous quality score, capturing, for instance, the reliability of the candidate or their relevance to the context of the selection. Quality scores break with the standard assumption of approval-based multiwinner voting that candidates are fully defined by the set of their supporters. We rethink what proportional representation means in the presence of quality scores. For this, we introduce a threshold-based and a value-based family of axioms, analyze their relationships, satisfiability, and computational complexity, and present rules that achieve the strongest jointly satisfiable combinations of our proportionality axioms. We then analyze the compatibility of proportionality with the natural goal of maximizing the summed quality of the selected candidates. While imposing standard proportionality notions can lead to an almost complete loss of quality, we show that under a new class of reciprocal axioms, which scale a group's entitlement by the quality of its commonly approved candidate(s), there always exist proportional committees retaining at least 3/4 of the optimal summed quality, and such committees can be computed by our voting rules at no additional computational cost.