CS Paper Radar

Trembling toward Duverger: Convergence and Cycles in Synchronous Plurality Dynamics

Maximilian Weigel, Damien Berriaud, Roger Wattenhofer

cs.GT ·submitted 2026-10-16 11:32 UTC · v1

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.

Comment
19 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

The Voter Model with Opinion Graph

cs.GT cs.DC ·2026-10-12 ·Petra Berenbrink, Thorsten Götte, Martin Hoefer, Tim Koglin
similarity 0.65
Abstract · Abstract shortened to comply Arxiv requirements

We study the \emph{voter model with opinion graph}, a generalization of the standard (pull) voter model that adds a notion of bounded confidence. In this process, we consider a finite set $A$ of $n$ agents. Each agent $u \in A$ has an opinion $x_u \in O$, where we model opinions as vertices in an undirected opinion graph $G = (O,E)$ with $|O|=q$. In each step, an agent $u$ interacts with another agent $v \in A$. In contrast to classical voting, $u$ adopts the opinion $x_v$ if and only if $x_v$ and $x_u$ are neighbors in $G$. The process is stable once all remaining opinions are an independent set in $G$. We analyze two variants of the process: the ordinary EdgeVOG process, which samples a pair of interacting agents uniformly at random from all possible pairs, and the productive EdgeVOG process, which samples only pairs with neighboring opinions in $G$. We show the following: - For every opinion graph and every initial configuration, ordinary EdgeVOG stabilizes within $O(n^2\log n)$ steps in expectation and with high probability. The expectation bound is asymptotically tight. For the productive EdgeVOG process, the expected stabilization time is exactly the initial number of compatible agent pairs, while $O(n^2\log n)$ steps suffice with high probability. - An opinion $i$ with initial support $s_i$ survives with probability at least $p_i:=s_i/(s_i+\sum_{j\in N(i)}s_j)$. Further, let $μ= \sum_{i \in O} p_i$, then we show the probability that less than $(1-δ)μ$ opinions survive is at most $\exp(-δ^2μ/(2(Δ^2+1)))$ for every $0\leqδ\leq1$. -If $G$ has maximum degree $Δ$ and every opinion initially has support at most $\hat{s}$, then no opinion ever acquires more than $\tilde{O}(\min\{n,Δ^6\hat{s}\})$ agents with high probability. This yields near-linear stabilization bounds for productive EdgeVOG for a large class of configurations.

0.21

Beyond persuasion: Mobile electoral interfaces in polarized societies

cs.SI physics.soc-phcond-mat.stat-mechnlin.AO ·2026-08-13 ·Nuno Crokidakis, Celia Anteneodo
similarity 0.64
Abstract · 7 pages, 2 figures, submitted for publication

Many traditional models of electoral dynamics emphasize opinion change, social influence and persuasion mechanisms. In contrast, contemporary polarized societies often exhibit relatively stable partisan blocs coexisting with an electorally relevant mobile population. We propose a minimal dynamical model in which electoral competition is governed not by direct persuasion between opposing blocs, but by the dynamics and allocation of a mobile electoral interface. The electorate is partitioned into two stable partisan blocs and a mobile fraction, while direct transitions between the polarized blocs are strongly suppressed. Mobile voters are allocated between the competing blocs through a Fermi-like probabilistic rule governed by rejection asymmetries. Analytical calculations show that the electoral susceptibility to political shocks is proportional to the stationary size of the mobile electoral interface, identifying electoral mobility as the key quantity controlling the macroscopic response of polarized systems to external perturbations. The model naturally predicts a continuum of mobility regimes, ranging from frozen polarization to highly responsive electoral states characterized by a broad mobile interface. These results suggest that, in strongly polarized elections, aggregate electoral changes may be governed primarily by fluctuations at the mobile electoral interface rather than by large-scale ideological conversion.

0.07

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

Sequential Phragmén Guarantees 2-Approximate Core Stability

cs.GT ·2026-09-11 ·Jianan Lin, Chenhao Wang
similarity 0.63
Abstract

We study approximately stable committee selection under approval preferences, following Cheng et al.~[EC~2019] and Jiang, Munagala, and Wang~[STOC~2020]. In an approval-based committee election, $n$ voters each approve a subset of the candidates, and a committee of size $k$ is selected. A size-$k$ committee is $λ$-stable if, for every nonempty subset $T$ of candidates, the number of voters who strictly prefer $T$ is less than $λ$ times the proportional share $\frac{n|T|}{k}$. We consider sequential Phragmén, a classical polynomial-time voting rule, and prove that it always returns a $2$-stable committee. This implies that the $2$-core is always nonempty and improves upon the $3.651$-stability guarantee of Gao, Sun, and Vondrák~[EC~2026]. The guarantee also extends to weighted voters and is tight even for unweighted elections: for every $1\leλ<2$, sequential Phragmén can return a committee that is not $λ$-stable. Compared with the exact-core algorithm developed in concurrent work by Becker, Greger, and Peters~[arXiv~2026], sequential Phragmén is simpler to implement, and our proof of its $2$-stability is elementary.

0.39

The Deterministic Hare Core Is Nonempty for Nine-Seat Approval Elections

cs.GT math.CO ·2026-09-03 ·Jiarui Fang
theorycode/data similarity 0.61
Abstract · 12 pages. Verification code and reproducibility materials: https://github.com/Baymax-ray/approval-core-nine-seats

Core stability gives approval-based committee elections a strong form of coalitional proportionality, but deterministic existence is not known for an arbitrary number of seats. We prove that every finite election with nine seats has a deterministic Hare-quota core committee. Starting from an eight-seat committee that is both a global Proportional Approval Voting (PAV) maximizer and core stable, we suppose that all one-candidate extensions are blocked and extract an inclusion-minimal closed response system. Singleton responses are eliminated by exact equality rigidity. For the remaining responses, rational Farkas certificates bound every nonpositive PAV add-marginal drift below by $-n/189$ and force every successor drift above $n/126$. The uniform response chain is irreducible, so stationarity makes these bounds incompatible. The computer-assisted component comprises an exact pointwise check over 7,356 voter types, 36 one-blocker cells, and a symmetry-complete family of 19 two-blocker motifs. Exact certificate archives and standard-library verifiers support these checks. The theorem settles the nine-seat case but does not decide deterministic core existence for arbitrary committee size.

0.46

Plurality Consensus for $h$-Majority via First-Repetition Rules

cs.DC cs.DS ·2026-11-11 ·Niccolò D'Archivio, George Giakkoupis, Frédéric Giroire, Emanuele Natale
similarity 0.60
Abstract · 16 pages

In the h-Majority dynamics, each of n agents holds one of k opinions and, in every synchronous round, observes the opinions of h agents chosen independently and uniformly at random and adopts a most frequent one among them, breaking ties uniformly at random. Let M_0 be the initial number of agents holding the most frequent opinion, and Delta_0 its bias, its lead over the second most frequent opinion. We show that, for every sample size h >= 3, if Delta_0 >= L sqrt(M_0 log n) max{1, n/(h^2 M_0)} for a sufficiently large constant L, then h-Majority reaches consensus on the initially most frequent opinion within O((1 + n/(h^2 M_0)) log n) rounds with high probability. This is the time bound proved for the DejaVu dynamics with h samples (arXiv:2604.03648); our bias condition is that of DejaVu when h >= sqrt(n/M_0), and larger by a factor sqrt(n/(h^2 M_0)) otherwise. Our main contribution, the analysis of one round, rests on a comparison principle: among all rules that read the same observations and treat opinions symmetrically, plurality maximizes the difference between the probability of outputting the most frequent opinion and that of outputting any fixed competitor. We apply it to the rule that adopts the first opinion repeated among h-1 observations, and otherwise the h-th observation: its output law is the law of the new opinion of a random agent after one round of DejaVu with h-1 samples. Hence, in expectation, one round of h-Majority widens the gap between the most frequent opinion and each competitor at least as much as that round of DejaVu, whose analysis we use as a black box. Independently and concurrently, d'Amore, Rybicki, Shimizu, Shiraga and Vacus (arXiv:2610.40562) obtained, among other results, the same time bound under the weaker bias condition of DejaVu, with a different analysis of one round and a martingale analysis over many rounds.

0.13

Sampford Apportionment Satisfies Threshold Monotonicity

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