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.

Fri 6 NovComputer Science and Game Theory
The gist
Choosing a fair group of winners in elections can get tricky when there are special rules about which sets of candidates can win. The authors introduce a new fairness rule that works for many kinds of these rules and voting with ranked choices. They show this fairness fits well with known ideas and prove it works perfectly for certain mathematical cases called matroids. While the basic way to use their rule can be slow, they find practical shortcuts that make it efficient in many real situations. They also tested the rule in practice and discuss its limits when voters just approve multiple candidates instead of ranking them.
Open → 2611.10229v1

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.

Mon 2 NovComputer Science and Game Theory
The gist
Elections that pick multiple winners often try to be either fair to the majority or fair to all groups proportionally. The authors study systems in between these two extremes, such as majority jackpot systems. They introduce new ways to understand and analyze these approaches using ideas called coalitions and stability. Their work explains how these election systems behave mathematically and computationally, providing new insights into voting methods that haven't been well studied before.
Open → 2611.02325v1

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.

Fri 23 OctComputer Science and Game Theory
The gist
Deciding the best way to choose a winner by voting can depend on how you value different people's happiness. The authors studied many ways to measure overall happiness, beyond just adding up everyone's scores. They found that voting rules using a certain scoring system pick winners that maximize these happiness measures over time. They also discovered that the simple plurality rule does best when randomness is allowed, and that sometimes the best scoring choices look different from known methods. This helps us understand how to design better voting systems for different fairness goals.
Open → 2610.33293v1

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.

Fri 16 OctComputer Science and Game Theory
The gist
Plurality elections usually end up focusing on two main candidates, a rule known as Duverger's law, but this paper studies how this happens in small fixed groups of voters. The authors show that when voters adjust their votes based on others' current support and some chance of mistakes, the group usually converges quickly to two leading candidates. However, the paper also finds that voting can sometimes cycle through patterns without settling, even with just three candidates. These cycles can be complex and cause the winning candidate to switch repeatedly over time.
Open → 2610.23330v1

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.

Mon 28 SeptComputer Science and Game Theory
The gist
This paper explores the problem of grouping binary strings—sequences made of just zeros and ones—when some data may be missing. The goal is to find a fixed number of representative strings (centers) so that every original string is close enough to some center. The authors focus mainly on how this applies to voting systems where voters can delegate their choices to representatives. They analyze how hard it is to solve this problem depending on the number of centers and the strictness of agreement needed, providing a detailed map of the computing challenges involved.
Open → 2609.35386v1

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

Mon 28 SeptDiscrete Mathematics
The gist
Tournaments are a special kind of network where every player beats another in a one-on-one game. A key question is how to find a small group of players that can influence or 'dominate' all others. The authors studied a mathematical measure called the fractional dichromatic number that helps estimate how big this dominating group must be. They provided two new proofs for a previous result, including one that uses artificial intelligence and offers a much tighter estimate. This work improves understanding of how tournament structure controls domination size.
Open → 2609.35186v1

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.

Thu 24 SeptComputer Science and Game Theory
The gist
Choosing a committee that fairly represents voters often focuses on proportional representation. The authors redefine what diverse representation means by making sure many groups of voters, not just individuals, have their views represented. They introduce new fairness criteria that demand stricter group representation and analyze their computational challenges. Their new methods work well in certain special cases and perform strongly in tests on real and simulated voting data.
Open → 2609.29332v1

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

Mon 21 SeptComputer Science and Game Theory
The gist
This paper looks at a type of voting where people vote one after another and may choose not to vote at all. Each voter has a list of favorite candidates and can only vote for some of the top ones in their list or abstain. The authors study how hard it is to figure out whether a certain candidate can win if everyone votes strategically, thinking about how others will vote. They find that this problem is very complex and belongs to a class called PSPACE-complete, meaning it is generally tough to solve with a computer. This answers a question left open by earlier work on voting strategy.
Open → 2609.24292v1

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.

Tue 8 SeptComputer Science and Game Theory
The gist
Choosing a group of winners often means picking popular candidates, but sometimes candidates also have different qualities. This paper studies how to select winners so that groups get fair representation while still picking high-quality candidates. The authors introduce new rules to balance these goals and show they can pick committees that keep much of the top quality without losing fairness. Their methods can find good groups efficiently, even when balancing these competing goals.
Open → 2609.08830v1