PaperlayerView exact revision on arXiv

Source-linked AI summary

An autocomplete model for elections

Moon Duchin, Kristopher Tapp

arXiv:2610.33035v1cs.SIcs.GTmath.PR

TL;DR

Ranked-choice research needs compact summaries of preference profiles and synthetic profiles that resemble them, including for completing partial ballots. The paper develops succession-based autocomplete and new profile statistics, finding that it captures held-out ballot structure, performs especially well on partial-ballot completion, and often preserves STV outcomes better than positional and head-to-head approaches.

  • Problem

    The paper addresses how to summarize ranked-choice profiles compactly and generate realistic synthetic profiles, including complete ballots from partial-ballot data.

    Source: §1 · pp. 1–2, §1.1 · p. 2

  • Method

    It estimates empirical candidate-to-candidate successions, including a start/stop symbol, and uses the resulting matrix for autocomplete generation and comparison with positional and head-to-head summaries.

    Source: §1.1 · p. 3, §3 · p. 5

  • Results

    Succession-based generation performs strongly across held-out ballot structure, partial-ballot completion, and STV winner-set preservation, outperforming positional and head-to-head approaches across many tests.

    Source: §1 · p. 2, §9 · p. 16

  • Takeaways & Limitations

    The experiments suggest that local succession information captures substantial global profile structure and can support synthetic profiles that match key properties of observed elections.

    Source: §9 · p. 16

    Autocomplete is trained on a single profile and therefore generates profiles with the same candidates, not a different candidate pool.

    Source: §9 · p. 16

Abstract

from arXiv · show

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.

1 Introduction

The paper links compactly summarizing ranked-choice profiles with generating synthetic profiles that resemble them, addressing the limited roster of generative models and the need for realistic profile statistics. It introduces succession-based autocomplete and evaluates its ability to reproduce ballot structure, complete partial ballots, and preserve election outcomes.

1 Introduction

  • The paper addresses both compactly summarizing a preference profile and generating profiles that resemble it, with reconstruction serving to assess summary quality.A practical use is constructing counterfactual complete ballots from partial ballots when ballot length is capped.Source: §1 · pp. 1–2
  • Succession-based generation outperforms positional and head-to-head alternatives across tests of held-out ballots, partial-ballot completion, and STV winner-set preservation.The comparison uses summaries based on candidate positions and pairwise comparisons.Source: §1 · p. 2

1.2 Contributions

  • The succession matrix records empirical transitions between candidates, including a start/stop symbol, and supports random-walk generation with tunable ballot length.The paper contrasts this nonparametric approach with positional and head-to-head summaries and introduces profile statistics for evaluating realism.Source: §1.2 · pp. 3–4, §1.1 · p. 3
  • Autocomplete recovers held-out ballot types about as well as bootstrapping, with novelty rates close to true held-out data, and is calibrated on rare ballots.The contribution summary also reports that it rarely hallucinates ballot types.Source: §1.2 · p. 4
  • For partial-ballot completion, autocomplete has the strongest performance among compared methods and is the only method to beat the random-completion benchmark.The benchmark samples a short-ballot prefix and completes it uniformly at random.Source: §1.2 · p. 4
  • Succession-based generation yields the original STV winner set more often than positional or head-to-head generation in the case study.The paper frames generated profiles as realistic perturbations for examining sensitivity of algorithmic output to profile changes.Source: §1.2 · p. 4

2 Preliminaries

The preliminaries establish the objects and graph concepts used to describe ranked-choice profiles and their Markov representation.

2 Preliminaries

  • A preference profile is a multiset of ballots, each ranking some or all candidates, and a voting rule maps the profile to an outcome.Ballots may be partial or complete; profile notation also tracks candidate mention frequencies and average ballot length.Source: §2 · p. 4
  • A weighted directed graph is acyclic when it has no positive-weight directed cycle passing only through candidates.Source: §2 · p. 4
  • A Markov chain is specified by a row-stochastic transition matrix; when it is ergodic, it has a unique stationary distribution attracting other probability vectors.The text defines irreducibility and aperiodicity as the conditions that together make a chain ergodic.Source: §2 · p. 4

3 Succession data and autocomplete

The succession matrix represents empirical ballot transitions as a Markov chain on candidates and a start/stop symbol. Random walks through this chain can be converted into synthetic ballots using several rules for handling repeated candidates.

3 Succession data and autocomplete

  • The succession matrix M is the weighted adjacency matrix of a graph on candidates plus a start/stop symbol, and the autocomplete model is the family of methods that reconstruct profiles from M.Source: §3 · p. 5
  • The transition matrix defines a random walk beginning at the start/stop symbol, whose sample paths provide the basis for generating ballots.The walk produces a sequence of candidate states that can be cut at visits to the start/stop symbol to form raw ballots.Source: §3 · pp. 5–6
  • Reject, Terminate, KeepFirst, and loop-erased random walk turn repeated-candidate paths into valid ballots using distinct processing rules.Other considered alternatives include self-avoiding walks and sampling from a maximum-entropy distribution.Source: §3 · p. 6
  • MaxEntropy best matches training profiles on many measurable benchmarks, but is computationally costly and becomes intractable for moderate candidate counts.Source: §3 · p. 6

4 Properties

The section characterizes the succession matrix’s steady state and how ballot-generation processing changes profile properties. It also relates cyclicity to ordered profiles and reports how common full circulation is in the Scottish elections studied.

4.1 Steady state

  • The stationary weight of each candidate is proportional to its mention frequency; the start/stop state’s weight is 1/(L + 1), revealing average ballot length L from the matrix.The matrix also recovers mention frequencies as π_i/π⋆.Source: §4.1 · p. 7
  • When all ballots are complete rankings, the uniform distribution is stationary.Source: §4.1 · p. 7

4.2 Generated ballots and profiles

  • Reconstitution usually preserves first-place frequencies, but can alter last-place frequencies, expected length, and relative succession probabilities.Source: §4.2 · p. 7
  • A profile is ordered exactly when its succession matrix is acyclic; then all generation methods coincide and produce ordered profiles with probability 1.The α-cyclicity statistic discounts longer candidate loops and vanishes exactly for ordered profiles.Source: §4.2 · p. 8
  • All 1,070 Scottish local-government elections studied were full-circulation profiles; 99.76% of candidates received bullet votes and 25,983 of 25,985 same-contest pairs formed 2-cycles.Source: §4.2 · p. 8
  • For full-circulation profiles, Terminate, KeepFirst, and LERW strictly shorten expected ballots, while Reject and SARW effects depend on the profile; only MaxEntropy is guaranteed to preserve length and stopping weight.Reconstitution can suppress or modify cycles, increasing conditional stopping and shortening ballots.Source: Table 1 · p. 8, §4.2 · p. 8

5 Tuning ballot length via stopping weights

The authors tune expected ballot length by shifting stopping odds while retaining relative transitions among candidates. This gives a continuous, non-increasing length response over a stated attainable range, with method-specific limits.

5 Tuning ballot length via stopping weights

  • The tuning approach compensates for processing-induced ballot shortening by decreasing stopping weights before generation.Source: §5 · p. 9
  • Multiplying each candidate’s stopping odds by λ changes stopping weights while proportionally rescaling other transitions, leaving relative probabilities among candidates unchanged.λ = 1 retains the original matrix, λ = 0 suppresses ordinary stopping, and increasing λ forces earlier stopping.Source: §5 · p. 9
  • For the stated autocomplete processing rule, expected length varies continuously and non-increasingly with λ, and every target length 1 < ℓ ≤ LR(0) is attainable.Source: §5 · p. 9
  • For Terminate, LR(0) is the expected number of distinct candidates visited before a repeat, so matching the profile’s mean length requires L ≤ LTerminate(0), which holds for almost all Scottish profiles.Source: §5 · p. 9
  • Reject and LERW can be numerically tuned only to lengths in their attainable ranges, and LERW need not attain the original mean length L.The clean existence result does not extend to these methods because their processing makes the effect of decreasing λ less controlled.Source: §5 · p. 9
  • Monotonicity supports a fast iterative search for λ; the authors also contrast uniform stopping-weight adjustment with MaxEntropy’s broader tuning of succession weights.They illustrate tuning to complete ballots and to the election’s observed average length.Source: §5 · p. 10

6 Comparing generative methods

The section compares sequential ballot generators built from succession, positional, and head-to-head summaries of an observed profile. Each uses local decisions, and completion experiments suppress stopping for the relevant models.

6 Comparing generative methods

  • The comparison tests information retained by three empirical profile summaries, not performance against the best fitted ranking models; their generators use similar stopping roles for length tuning.Source: §6 · p. 10
  • Autocomplete-SARW generates ballots by walking from the start/stop symbol, selecting among unranked candidates and the stop symbol in proportion to observed succession frequencies.Source: §6 · p. 10
  • The position model generates ballots top-down, selecting among unranked candidates and the stop symbol using rank-specific position frequencies.Source: §6 · p. 10
  • The H2H model uses pairwise preference shares, including single-ranked-candidate ballots as wins, to insert candidates in a randomized order; the ballot is the segment above the stop symbol.In completion experiments, stopping is suppressed for Succession and H2H; all generators make local sequential decisions.Source: §6 · pp. 10–11

7 Empirics

The experiments assess how well synthetic profiles reproduce held-out ballot structure, complete rankings, and STV winners. Succession-based generation matches held-out novelty closely, improves on random completion, and performs strongly on winner-set recovery.

7 Empirics

  • Succession matches held-out novelty most closely while achieving coverage similar to bootstrap, improves on random completion, and performs strongly on STV winner-set recovery.The STV comparison finds maximum-entropy autocomplete nearly as effective as full-profile bootstrap.Source: §7.1 · p. 12, §7.2 · p. 13, §7.3 · p. 14

7.1 Structural fidelity

  • Succession stays within 20% of the correct expected mass for rare ballot types, while positional generation tends to overweight more common types.The frequency spectrum measures expected counts of ballot types occurring a specified number of times in a test-size sample.Source: §7.1 · p. 12, Table 2 · p. 12
  • For the unseen party-disrupting ballot 1 ≻5, Succession predicts 11.6 occurrences, versus 235.9 for Positional and 45.8 for H2H.The ballot appears in neither training nor testing data; the passage attributes Succession’s lower estimate to its ability to capture same-party runs.Source: §7.1 · p. 13

7.2 Completion

  • When trained on ballots of length at most four, autocomplete is the only generator that improves on random completion at predicting complete ballots.The comparison uses normalized Wasserstein distance between generated and observed complete ballots across the same 282 seven-candidate elections.Source: §7.2 · p. 13

7.3 STV outcomes

  • For 7-candidate, 4-winner contests, maximum-entropy autocomplete performs nearly as well as full-profile bootstrap at recovering STV winner sets; head-to-head generation predicts them poorly.Even resampling the original profile changes winners approximately 6% of the time, reflecting STV’s sensitivity.Source: §7.3 · p. 14, Figure 3 · p. 14

8 Iteration dynamics

This section studies repeated training and generation as a dynamical system on succession matrices. Iteration leads toward acyclic matrices, and the limit can encode a candidate ordering.

8 Iteration dynamics

  • The iteration studies the map from a transition matrix to generated ballot distributions and back; MaxEntropy is excluded because its induced map is the identity.The ballot-to-matrix map records the probability of a successor given that a candidate appears; the reverse map generates ballots under a chosen rule.Source: §8 · p. 15
  • For two-sided matrices, iteration preserves the start-symbol row and does not decrease candidate stop probabilities; stop probabilities strictly increase for candidates on positive-weight cycles.A matrix is two-sided when every candidate has positive probability of appearing first and of appearing last.Source: §8 · p. 15
  • A matrix is fixed under iteration exactly when it is acyclic, and every limit point is an acyclic fixed matrix whose generated profiles are ordered.Under Terminate, the orbit has a unique limit.Source: §8 · p. 15
  • With two candidates, Terminate and SARW coincide, and the sign of φ determines which candidate succession survives or whether neither survives.The first-place shares α and β are preserved; when there are no bullet votes, the direction is determined by majority preference.Source: §8 · pp. 15–16
  • Across three Scottish elections, the sign of φ_ij predicted which direction survived for 57 of 63 candidate pairs; observed limits had low cyclicity after a few dozen iterations.In Pentland Hills, the strongest surviving successions were sequentially ordered within parties.Source: §8 · p. 16

9 Conclusion

The conclusion presents the succession matrix as a compact profile summary for generating synthetic rankings, and reports strong empirical fidelity alongside a study of repeated reconstruction. The MaxEntropy method samples from a maximum-entropy distribution constrained by the profile’s succession data.

9 Conclusion

  • The succession matrix is proposed as a compact summary that supports inexpensive generation of profiles faithful to many key properties of the original profile.The conclusion also reports that experiments on real-world ranking data demonstrate compression and regeneration at practical scale.Source: §9 · p. 16
  • Synthetic profiles generally match held-out ballot novelty and coverage; the autocomplete model is calibrated on rare ballots, completes partial ballots better than alternatives, and often reproduces original STV winner sets.MaxEntropy performs best on many measurable benchmarks, while faster random-walk methods remain strong against positional and tournament-based alternatives.Source: §9 · p. 16
  • Repeated reconstruction forms a dynamical system whose limit points are acyclic; the paper characterizes the two-candidate base case and gives a heuristic for predicting general limits.An acyclic limit point induces a partial order on candidates.Source: §9 · p. 16
  • Autocomplete is trained on one profile and therefore generates ballots only for that profile’s candidate pool; pooling succession data across elections is proposed as future work.The paper identifies allowing candidate pools to vary as a direction for that work.Source: §9 · p. 16

A Maximum entropy

  • MaxEntropy samples from the maximum-Shannon-entropy distribution constrained to have the profile’s succession matrix.The implementation fits a matrix W so the resulting distribution matches the candidate-pairs matrix; when the maximum-entropy distribution lacks full support, it is obtained as a boundary limit of the exponential-family distributions.Source: A Maximum entropy · pp. 20–21

B Details on ballot statistics

The ballot-statistics results show that reconstruction can change ballot lengths and stopping weights, with the direction of length change depending on the generation rule and profile. In particular, longer reconstructed ballots can occur under Reject and SARW.

B Details on ballot statistics

  • For unordered profiles, Terminate, KeepFirst, and LERW strictly reduce expected average ballot length after reconstruction.The result does not extend to every method or profile: length shrinkage under Reject and SARW holds for typical profiles, but not all.Source: B Details on ballot statistics · p. 21
  • Autocomplete-Reject can increase expected average ballot length because rejected raw ballots may be shorter than accepted ones.The example uses equal portions of bullet votes, two-candidate ballots, and a long ballot; rejected ballots contain only A1 and A2.Source: B Details on ballot statistics · p. 21
  • 1.47826 for the original profile rises to 1.49251 under Autocomplete-SARW in the reported example.Walks beginning with ⋆34 cannot return to 3 and are forced onto a longer path, which more than offsets increased stopping probabilities.Source: B Details on ballot statistics · p. 21
  • All five random-walk methods weakly increase each candidate’s stopping weight, with strict increases for candidates on positive-weight cycles under the stated circulation conditions.The methods are Reject, Terminate, KeepFirst, LERW, and SARW; strictness holds for full-circulation profiles or the specified two-sided cycle condition.Source: B Details on ballot statistics · p. 21

C Details on empirical comparisons

Across the Scottish-election comparisons, succession-based reconstruction matches observed profiles more closely than positional- or head-to-head-based approaches on the reported median distance measures. The appendix also sets up the iteration dynamics, whose behavior depends on the processing rule.

C Details on empirical comparisons

  • Across 282 seven-candidate Scottish elections, succession methods have stronger median profile-reproduction performance than position- or head-to-head-based regeneration, with MaxEntropy especially close to the original profiles.Figure 4’s top panel reports D(P, ˜P); the passage also reports that MaxEntropy outperforms the positional method under positional-frequency distance.Source: C Details on empirical comparisons · pp. 22–23, Figure 4 · p. 23
  • For 157 Scottish contests with seven candidates and three winners, the reported STV winner-set overlap results are very similar to the four-winner results.Figure 5 displays the three-winner comparison.Source: C Details on empirical comparisons · p. 23, Figure 5 · p. 24

D.1 Setup

  • The iteration setup uses Terminate, SARW, LERW, or KeepFirst; MaxEntropy is excluded because its fidelity to the succession matrix makes its iteration map the identity.The dynamics arise from the lossiness of the cheaper reconstruction rules.Source: §D.1 · p. 24
  • An acyclic succession matrix is equivalent to an ordered reconstructed profile, and all processing rules agree on acyclic matrices.Acyclicity is preserved by iteration, and an ordered profile remains ordered under reconstruction.Source: §D.1 · p. 25

D.2 Fixed points and convergence

For the four principal processing rules, iteration from a two-sided matrix has acyclic fixed limit points, and Terminate has a unique limit. The Reject case has a weaker limit property, while the paper also gives an exact two-candidate characterization and empirical examples of limiting orders.

D.2 Fixed points and convergence

  • Stopping weights increase for candidates on positive-weight cycles, and the α-cyclicity of the iterates converges to zero for every 0 < α < 1.The paper also states that every two-sided fixed point is acyclic.Source: §D.2 · pp. 25–26
  • Every limit point from a two-sided starting matrix is acyclic and fixed; under Terminate, the orbit converges to a unique limit.For Terminate, stopping weights are non-decreasing and between-candidate transition weights are non-increasing.Source: §D.2 · p. 26

D.3 Acyclicity for Reject limits

  • Reject does not satisfy the general acyclic-limit result: a limit point cannot have a positive-weight candidate cycle reachable from ⋆, but first-place votes may tend to zero.In that case the limit may not be a fixed point because it is outside the map’s domain.Source: §D.3 · pp. 26–27

D.4 Exact limits for two candidates

  • For two candidates, the sign of φ determines which between-candidate transition survives in the limit; when φ is zero, both transition weights vanish.The exact-limit argument preserves the sign of ψ through iteration and establishes the corresponding limiting transition weights.Source: §D.4 · p. 27

D.5 Examples of limiting orders

  • On random matrices, the φ predictor with an α_i^2 m_ij term outperforms both raw m_ij and the simpler α_i m_ij at predicting limiting edges.For the three highlighted Scottish elections, the map is iterated exactly on ballot distributions, feasible here for seven candidates.Source: §D.5 · p. 27
  • Figure 6 compares exact Pentland Hills limits under SARW and Terminate using the full ballot distribution, with displayed arrows thresholded at 0.025.At that threshold, 1 →7 is the only edge significant under one convention but not the other.Source: Figure 6 · p. 28
  • In the thresholded Pentland Hills limits, the strongest surviving successions follow the sequential order of candidates within parties.The figure shows 12 versus 13 edges at the stated threshold, while the true limits have 20 or 21 nonvanishing edges.Source: §D.5 · p. 28

E Empirical convergence

Across the five methods, iterates appear to converge quickly to unique acyclic limits. The average ballot length also declines toward a method-dependent limit.

E Empirical convergence

  • The maximum 1/2-cyclicity across 282 seven-candidate elections quickly approaches zero, including in the worst elections.The authors report evidence consistent with fast convergence to unique acyclic limits across all five methods.Source: E Empirical convergence · p. 28
  • In the reported limiting order, only the 6 → 5 comparison is ambiguous, with weight around 8 × 10^-10.The weight is near the edge of numerical precision.Source: E Empirical convergence · p. 28
  • Average distances between consecutive matrices decrease, consistent with convergence to a single limit.The authors average across elections to reduce noise from random reconstruction.Source: E Empirical convergence · p. 29, Figure 8 · p. 29
  • Average ballot length decreases through the iterations toward a limit that depends on the method.Source: E Empirical convergence · p. 30, Figure 9 · p. 30
Loading 2610.33035v1…