Democracy on Rugged Landscapes: Phase Transitions in Optimal Voting Rules
Authors: Joshua Nunley
Organizations: Indiana University, Bloomington, IN, USA
Abstract
Laws and institutions shape individual outcomes through complex interactions with citizens' diverse circumstances, yet how different voting methods navigate this coupled landscape remains poorly understood. We model collective governance as optimization on NK fitness landscapes, where shared bits (laws) are updated by voting while individual bits (personal traits) remain fixed. A cross-dependency parameter α controls how legislation's effects depend on individual circumstances. We compare eight standard voting methods and a generalized scoring family across landscape ruggedness K∈{1,…,20} and α∈[0,1] with 1000 runs per configuration. Under direct democracy, the optimal voting method undergoes sharp phase transitions as a function of landscape complexity: cardinal score voting dominates on smooth landscapes, ordinal scoring with p=0.35 at low-to-moderate ruggedness, Borda count across a wide middle range, and STAR voting at the highest complexity. A two-parameter empirical formula reduces the (K,α) plane to a single complexity axis for visualization. Borda count achieves the highest mean fitness and lowest variance across most of the parameter space. We further introduce a representative democracy model parameterized by identity weight β and candidate self-interest pself. Representation reshapes the complexity-dependent structure even under favorable conditions: cardinal score voting dominates across most regimes, with plurality emerging as the top method at high β and low-to-moderate pself.
Majority voting is one of the few black-box interventions that can improve a fixed stochastic predictor: repeated access can be cheaper than changing a high-capability model. Classical fixed-competence theory makes this intervention look monotone -- more votes help above the majority threshold and hurt below it. We show that this picture is fundamentally incomplete. Under the de Finetti representation for exchangeable repeated correctness, voting is governed by a latent distribution of per-example correctness probabilities. Even simple latent mixtures can generate sharply different voting curves, including nonmonotone behavior and, in an explicit construction, infinitely many trend changes. The full latent law determines the curve, but the curve does not determine the law. The exact object recovered by voting is a signed voting signature: at each binomial variance scale, it records excess latent mass above rather than below the majority threshold. Our main theorem proves that the complete odd-budget curve and this signature are equivalent: the curve increments are signed Hausdorff moments, and the full curve recovers the signature uniquely. This viewpoint explains shape phenomena, branch-symmetric nonidentifiability, realizability, variation, and endpoint rates. It also separates estimation regimes: direct per-example success-probability information targets the full signature, whereas fixed-depth grouped labels reveal only a finite prefix.
The communication complexity of a voting rule is the worst-case number of bits that n voters must transmit to a central authority under the most efficient elicitation protocol in an election with m candidates. We study the communication complexity of Instant-Runoff Voting (IRV). Conitzer and Sandholm [2005] established an upper bound of O(n (log m)2), but did not provide a matching lower bound beyond Ω(n log m). We resolve this open problem by raising the lower bound to Ω(n (log m)2) using the fooling set technique, thereby showing that the communication complexity of IRV is Θ(n (log m)2). We further show that this complexity drops to Θ(n log m) under the single-peakedness restriction, and that both the IRV-Average variant and Single Transferable Vote (STV), the multiwinner extension of IRV, have the same asymptotic communication complexity as IRV.
A common problem in social choice is to determine whether there is a social choice procedure, such as a voting method, satisfying some desired criteria. Computer-aided methods such as SAT solving can sometimes answer these questions. However, under typical encodings, a SAT solver may only synthesize a voting method on a finite domain, while we may want one on an infinite domain, such as the domain of all preference profiles for a fixed number of candidates but any finite number of voters. In this paper, we use an approach based on reasoning with constrained Horn clauses and computation with polyhedra to synthesize a voting method on an infinite domain. We then use SMT and Lean to verify its properties. Our main result is a possibility theorem about four well-known criteria from voting theory: the Condorcet winner and loser criteria, positive involvement, and resolvability. Previous work has shown that for five or more candidates, there is no voting method satisfying these axioms, and that for four candidates, there is no method satisfying these core axioms plus one more invariance axiom. Here we show that for four candidates, there does exist a method satisfying the core axioms and more.