Analysis of Equilibria in Iterative Voting Schemes

Zinovi Rabinovich, Svetlana Obraztsova, Omer Lev, Evangelos Markakis, Jeffrey S. RosenscheinAAAI 2015 · DOI

Abstract

The Gibbard-Satterthwaite theorem establishes that any non-dictatorial voting system with at least three candidates is susceptible to strategic manipulation. This paper explores the "reachability" of Nash equilibria in iterative plurality voting—a dynamic process where voters sequentially adjust their ballots to achieve better outcomes. We demonstrate that while identifying reachable stable states is NP-complete in a purely strategic model, incorporating realistic behavioral assumptions like "truth bias" or "laziness" renders the problem computationally tractable.

Introduction

In social choice theory, the study of strategic behavior often centers on Nash Equilibria (NE)—states where no individual voter can improve the election result by unilaterally changing their vote. However, standard NE analysis frequently produces a "noisy" set of outcomes, including many that are practically implausible. For instance, in a large election, a profile where every voter supports their least preferred candidate can be a Nash equilibrium simply because no single voter has the power to change the winner.

To address this, we focus on Iterative Voting. This framework models elections as a multi-stage process starting from a truthful state, where voters move step-by-step toward equilibrium. The central challenge lies in determining which equilibria are actually "reachable" from an honest starting point and the computational difficulty of identifying them.

Methodology and Models

We analyze three distinct game-theoretic models under the Plurality Rule, where the candidate with the most votes wins. These models are defined by the voters' underlying incentives:

  1. The Basic Model: Voters are purely strategic, caring only about the identity of the winner.
  2. Truth-Biased Model: Voters possess a slight preference for honesty. They only manipulate their vote if doing so results in a strictly better winner according to their true preferences.
  3. Lazy Voter Model: Voters prefer to abstain unless their participation is "pivotal" (meaning their vote can change the election outcome).

The foundation of these models is the preference profile, which maps each voter's ranking of candidates.

Figure 1: A sample preference profile for three voters (1, 2, 3) over three candidates (c1, c2, c3). This truthful starting point serves as the basis for iterative strategic adjustments.

For each model, we employ formal mathematical proofs to characterize the properties of reachable equilibria and establish the computational complexity of finding them.

Theoretical Insights

Our analysis reveals that behavioral nuances fundamentally alter the mathematical landscape of iterative voting:

  • The Complexity of Strategy: In the basic model, determining if a specific voting profile is a reachable equilibrium is NP-complete. This result, derived via a reduction from the Hitting Set problem, suggests that the path from honesty to strategic stability can be prohibitively complex to map.
  • The Efficiency of Truth Bias: The truth-biased model introduces a striking simplification. We found that if a reachable equilibrium exists (other than the truthful profile), it can be reached in just a single step by a single voter. This "one-step" property suggests that truth-biased equilibria are more stable and natural.
  • Convergence through Laziness: In the lazy voter model, we examine "restricted dynamics" where a voter who chooses to abstain cannot later rejoin the election. We prove that this process always converges to a stable state, providing a predictable endpoint for the iterative process.

Key Results

The computational complexity of identifying reachable equilibria varies significantly across the models:

  • Basic Model: Proved that checking reachability is NP-complete.
  • Truth-Biased Model: Developed a characterization that allows all reachable equilibria to be found in $O(mn)$ time (where $m$ is candidates and $n$ is voters).
  • Lazy Voter Model: Provided a polynomial-time algorithm ($O(m^2 n^2)$) to find all reachable stable states under restricted dynamics.

Furthermore, we provide a mathematical characterization using the "chasing set"—a specific set of conditions that define which candidates can realistically challenge the current winner during the iterative process.

Limitations and Future Work

While these results provide a rigorous foundation for understanding iterative voting, several avenues for future research remain. Our findings are currently limited to the Plurality Rule and a specific lexicographic tie-breaking mechanism. Other voting rules, such as Borda count or Single Transferable Vote (STV), may exhibit different equilibrium properties. Additionally, the "restricted dynamics" in the lazy voter model—where abstention is permanent—is a simplification that could be relaxed in future behavioral models.

Summary updated

BibTeX
@inproceedings{rabinovich2015analysis,
  author = {Zinovi Rabinovich and Svetlana Obraztsova and Omer Lev and Evangelos Markakis and Jeffrey S. Rosenschein},
  title = {{Analysis of Equilibria in Iterative Voting Schemes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9328},
}
Figure