CS Paper Radar

An autocomplete model for elections

Moon Duchin, Kristopher Tapp

cs.SI cs.GTmath.PR ·submitted 2026-10-14 22:25 UTC · v1

Abstract

We consider two linked problems for ranked choice elections: building a compact summary of a preference profile $P$, and generating synthetic profiles that resemble $P$ in key ways. We introduce a Markov model based on which candidate names follow which on observed ballots and record this in a succession matrix on candidates together with a start/stop symbol. This provides the basis for new ``autocomplete'' methods for generating synthetic profiles, with ballot length that can be tuned to a target. We compare succession-based generation to parallel use of summaries built from positional frequencies and head-to-head comparisons. To execute this comparison, we introduce new descriptive statistics of profiles that allow new tests of whether synthetic profiles are realistic. In experiments on Scottish ranked-choice profiles, succession-based generation captures held-out ballot structure well, performs especially strongly when completing partial ballots, and often preserves election outcomes, outperforming the alternatives on all counts. Finally, we study the dynamics of iterating the train-and-generate process.

Closest papers

Nearest neighbours by meaning across the whole index.

STV Audit Graphs: A Visual Tool to Measure Election Stability

cs.GT stat.AP ·2026-09-09 ·Edouard Heitzmann
similarity 0.60
Abstract

The Single Transferable Vote (STV) is an algorithmic election rule. Round by round, a profile of ranked-choice ballots is reinterpreted to determine which decision to make next, and candidates are seated or eliminated until a full winner set emerges. This algorithmic nature makes STV theoretically more brittle than other election rules: uncertainty about an early round of the election might percolate irreversibly into the rest. For this reason, a generalized non-trivial Risk-Limiting Audit (RLA) framework has remained elusive for STV. Such a framework must concoct a set of null hypotheses, or assertions, whose rejection would bound the probability that the outcome of the election was incorrectly reported. We present audit graphs as a solution to design the assertions needed for RLAs of arbitrary STV elections, as well as quantitatively describe the uncertainty (or lack thereof) of their outcomes. These audit graphs explore election paths that are ``close'' to the recorded one by considering the alternative decisions the STV algorithm might have made if a small number of ballots were perturbed.

0.10

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

VoteGEO-Bench: Measuring the Impact of Generative Engine Optimization on Electoral Visibility

cs.IR cs.CLcs.CY ·2026-10-15 ·Shiqi Zhang, Xiaokui Xiao
benchmark similarity 0.59
Abstract

Large language models (LLMs) are increasingly used for election information, yet little is known about how external web content shapes the political information they present. Generative engine optimization (GEO) rewrites web content to improve its visibility in generated responses. To investigate its potential risks in voting scenarios (VoteGEO), we introduce VoteGEO-Bench, a benchmark covering the 2024 U.S. presidential election and the 2026 Japanese House of Representatives election, combining election-related queries, historical webpages, and voter personas. We first analyze sources cited by generative engines and find that many citations come from lower-cost owned and open-platform sources, while some webpages remain visible across days. We then evaluate 11 rewriting strategies in 4 categories, examining target specification, effectiveness across engines and elections, and the role of voter personas. Rewriting without specifying a target rarely increases target exposure, whereas target-specified rewriting more often does. Strategies that improve page organization or strengthen a position through argumentation yield greater gains than adding supporting evidence or changing wording. For the two strongest strategies, gains remain broadly positive across evaluated U.S. personas, but persona conditioning shows no consistent effect on these gains. Explicit partisan identities can create baseline exposure gaps larger than the gain from rewriting one webpage. When partisanship is implicit in the voter profile, baseline shifts depend on how strongly the engine responds to that signal.

0.31

Counting by the Book: Verifying Alaska's Ranked-Choice Elections

cs.LO cs.CY ·2026-10-27 ·Lucy Horowitz
similarity 0.59
Abstract

We present Alaska's ranked-choice elections as a case study in Formally Verified Democracy, a program to establish election results through formally checked proofs. We formalize an interpretation of Alaska's tabulation rules in Lean, verify its implementation, and prove election-specific results. Across 115 ranked-choice contests in Alaska since 2022, we identify 75 ballot records across 10 contests that were counted differently from this interpretation by a program reproducing the published results, without changing any winners. We trace these differences to overvotes and duplicate rankings and examine their legal justification, showing how formal verification can expose consequential choices in translating election law into software.

0.17

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

Trembling toward Duverger: Convergence and Cycles in Synchronous Plurality Dynamics

cs.GT ·2026-10-16 ·Maximilian Weigel, Damien Berriaud, Roger Wattenhofer
similarity 0.58
Abstract · 19 pages, 2 figures

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.

0.29

Proportional Representation in Temporal Voting with Ranked Preferences

cs.GT cs.AI ·2026-09-24 ·Noam Hazon, Leora Schmerler, Nicholas Teh
similarity 0.56
Abstract

We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutoff may differ across voters and rounds. We therefore require proportionality to hold for every admissible choice of cutoffs, whether fixed and common, common but varying across rounds, or set individually for each voter in each round. Combining these interpretations with temporal versions of justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC) gives us a hierarchy of axioms. We ask which of these axioms can be guaranteed, and with how much knowledge of the future. Unlike with approval ballots, no version of EJR can be guaranteed, and for the other axioms, flexibility in the cutoffs comes at a price. With a fixed common cutoff, JR, PJR, and PSC can be guaranteed, but only by rules that see all preferences in advance. Once the cutoff may vary across rounds, even such rules cannot guarantee JR or PSC for groups that agree in only some rounds. For groups that agree in every round, however, knowing only the number of rounds suffices for PJR in polynomial time, and PSC needs no knowledge of the future at all. Under individual cutoffs, no version of JR or PJR can be guaranteed, yet a rule as simple as serial dictatorship achieves PJR up to an additive loss that no rule can improve on, however much it knows. Natural preference restrictions restore exact guarantees. Finally, we show that checking our axioms is often coNP-complete; but perhaps surprisingly, a stronger axiom can be easier to check.

0.27

Political Sorting Can Drive AI Models Apart Through User Feedback

cs.CY ·2026-08-11 ·Petter Törnberg, Michael Heseltine, Nicolò Pagan, Christopher Bail, Michelle Schimmel +1 more
similarity 0.56
Abstract

Large language models are rapidly becoming an important source of political information. This raises a fundamental question: will AI systems support a shared basis for political knowledge, or lead different political groups to rely on increasingly different models? Political sorting can drive model fragmentation if three conditions hold: politically different users select into different models, learning from user feedback pushes those models apart politically, and the resulting differences shape subsequent model choices. We call this self-reinforcing process the Centrifugal Alignment Spiral. We study its components in three steps. First, we draw on a human experiment showing that political identity predicts model choice. Second, we fine-tune language models on synthetic feedback reflecting predominantly Democratic or Republican preferences. Across five independent runs per model family, paired models diverged on 12-41% of unseen survey questions with large partisan gaps, and in every run the differences moved in the expected political direction; for some models, differentiation extended even to issue areas excluded from training. Pooling feedback across groups instead suppressed divergence. Third, an empirically anchored agent-based model shows what follows when political sorting and model adaptation operate together: models attract politically distinct audiences, learn from them, and diverge further. User feedback can therefore turn political sorting among AI users into durable differences between the models on which they rely for political information.

0.04