Semi-random Impossibilities of Condorcet Criterion

Lirong XiaAAAI 2023 · DOI

Abstract

In social choice theory, the Condorcet criterion is often viewed as a gold standard for democratic fairness. However, mathematical impossibilities have long shown it to be incompatible with other desirable properties like voter participation and strategy-proofness. This paper, presented at AAAI-23, moves beyond traditional worst-case analysis to provide the first "semi-random" impossibility theorems. It demonstrates that for any Condorcet-consistent voting rule, violations of these key axioms are not just possible but inevitable in large-scale elections, occurring with a frequency of at least $\Omega(\sqrt{B/n})$. These findings suggest that many existing voting rules are already asymptotically optimal.

Introduction

The Condorcet criterion (CC) states that if a candidate wins every head-to-head matchup against all other candidates, they should be the overall winner. While intuitive, CC is famously incompatible with several other axioms:

  • Participation (PAR): A voter should never be worse off by participating in an election.
  • Strategy-proofness (SP): Voters should not have an incentive to misrepresent their preferences.
  • Monotonicity (HM/MM): Increasing support for a winner should not cause them to lose.

Traditional proofs of these incompatibilities rely on worst-case analysis, identifying specific, often rare, profiles where the axioms clash. Critics argue these scenarios might be negligible in practice. This paper addresses this by quantifying the likelihood of such violations under semi-random models, which provide a more realistic "smoothed" view of election dynamics.

Methodology: From Templates to Scaling

The core of the paper's proof strategy is a two-step process that transforms discrete worst-case scenarios into probabilistic bounds.

1. Violation Templates

The author first identifies "violation templates"—small sets of voting profiles where any Condorcet-consistent rule must fail a specific axiom. These templates are often derived from existing worst-case proofs, sometimes aided by SAT solvers.

Figure 1: A base violation template for four candidates, showing how adding specific sets of votes leads to different winners and potential axiom violations.

2. Semi-Random Scaling

To move from a single instance to a general probability, the author "scales up" these templates. In a semi-random model, an adversary chooses a base distribution for each voter, to which a small amount of noise is added. The author proves that by scaling the template by a factor of $\sqrt{n}$ (where $n$ is the number of voters), one can create a region in the profile space where violations are highly likely to occur.

Figure 2: The scaled-up semi-random version of the violation template. The transitions now involve probabilistic "flips" and scaling factors proportional to $\sqrt{n}$.

Using point-wise concentration bounds, the author shows that for any voting rule, there exists a distribution where a significant fraction of profiles fall into these scaled templates.

Key Results and Insights

The paper establishes four major semi-random impossibility theorems. For any voting rule $r$ satisfying the Condorcet criterion:

  • Inevitability of Violations: The probability that $r$ violates Participation, Half-way Monotonicity, Maskin Monotonicity, or Strategy-proofness is at least $\Omega(\sqrt{B/n})$, where $B$ is the size of the manipulating group.
  • Group Impact: As the group size $B$ increases (up to $\sqrt{n}$), the likelihood of a violation increases, making larger-scale manipulations or participation failures more probable.
  • Asymptotic Optimality: A key insight is that popular rules like Copeland, Maximin, and Schulze already meet this theoretical lower bound. This suggests that we have likely reached the limit of how "perfect" a Condorcet-consistent rule can be in terms of avoiding paradoxes.

Discussion and Future Work

The paper argues that even if the probability of a violation decreases as the electorate grows, it does not vanish quickly enough. In large-scale elections, even a rare violation of the participation axiom can lead to significant social outcry or legal challenges. The expected "social cost" of these paradoxes may actually increase with the size of the electorate.

While the results are robust for the number of voters, the constants involved may grow exponentially with the number of candidates ($m$). Future work includes extending this "template-scaling" technique to other foundational results like Arrow’s Theorem and testing these theoretical bounds against empirical datasets from real-world elections.

Summary updated

BibTeX
@inproceedings{xia2023semi,
  author = {Lirong Xia},
  title = {{Semi-random Impossibilities of Condorcet Criterion}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25727},
}
Figure