Preserving Condorcet Winners under Strategic Manipulation

Sirin Botan, Ulle EndrissAAAI 2021 · DOI

Abstract

This paper investigates the robustness of Condorcet extensions—voting rules designed to select the alternative that beats all others in head-to-head matchups—against strategic manipulation. While Condorcet consistency is a desirable property, it often assumes truthful preference reporting. We introduce the concept of robust Condorcet extensions, proving a fundamental impossibility result: any tournament solution that is even "weakly resolute" (occasionally picking a single winner in the absence of a Condorcet winner) is susceptible to manipulation that displaces the true Condorcet winner. Conversely, we identify that "indecisive" rules, specifically the Minimal Extending Set (ME), maintain robustness under pessimistic preference extensions.

Introduction

In social choice theory, a Condorcet winner is an alternative that defeats every other candidate in a pairwise majority contest. Voting rules that always select this winner when it exists are known as Condorcet extensions. However, the stability of these rules is threatened by strategic voting. If an agent can improve their outcome by misreporting their preferences—specifically by causing the true Condorcet winner to lose—the rule's normative appeal is significantly diminished.

This research asks a critical question: Can we design a Condorcet extension such that no agent has an incentive to strategically manipulate the outcome away from a truthful Condorcet winner? We define this property as robustness.

Methods: Tournament Solutions and Majority Graphs

The authors focus on tournament solutions (C1 rules), which are voting rules that depend solely on the majority graph (the tournament) rather than the underlying numerical margins or full preference profiles. In these models, the "majority graph" represents who beats whom in pairwise contests.

Example of a tournament graph (majority graph) used to analyze social choice rules.

To evaluate robustness, the authors employ several formal axioms:

  • Robustness Axiom: A rule is robust if, whenever a Condorcet winner exists in the truthful profile, reporting truthfully is a weakly dominant strategy for all agents.
  • Preference Extensions: Because tournament solutions often return a set of winners (irresolute rules), the authors use extensions like Gärdenfors or Kelly to model how voters compare sets of alternatives.
  • McGarvey’s Theorem: This theorem is used to prove that any arbitrary tournament graph can be realized by some specific voter profile, allowing for general impossibility proofs.

The Decisiveness-Robustness Trade-off

A central insight of the paper is that decisiveness is the enemy of robustness. Popular voting rules like Copeland (which ranks candidates by their number of victories) or Slater (which seeks the closest transitive ranking) are "weakly resolute"—they attempt to pick a single "best" candidate even when the majority graph contains cycles.

The authors demonstrate that this desire to be decisive in "messy" situations creates vulnerabilities in "clean" situations. If a rule is forced to pick a single winner in a cycle, a strategic voter can often lie about their preferences to create such a cycle, thereby displacing a Condorcet winner they dislike in favor of a preferred alternative from the resulting set.

Key Results: The Impossibility of Resolute Robustness

The most striking result is a general impossibility theorem: No tournament solution that is weakly resolute can be robust under all standard preference extensions. If a rule ever selects a single winner outside of the Condorcet domain, it provides an opening for strategic manipulation.

The manipulation mechanism: how changing preferences (flipping a set S) affects the tournament outcome and enables manipulation.

However, the paper offers positive results for "indecisive" rules. They prove that the Minimal Extending Set (ME) is robust under "pessimistic" preference extensions. In this context, if voters are cautious about ties and assume the worst-case winner will be selected from a set, they have no incentive to manipulate the tournament to remove a true Condorcet winner. Furthermore, robustness is shown to be "inherited": if a rule is robust, any coarser rule (one that returns a superset of the original winners, such as the Banks Set) is also robust.

Limitations and Future Directions

The current study is restricted to C1 tournament solutions. Future research is needed to determine if these results extend to C2 rules (which consider margins of victory) or C3 rules (which use the full preference profile). Additionally, while the positive results for ME are encouraging, they rely on pessimistic voter assumptions. Exploring robustness under risk-neutral or optimistic models remains an open challenge. Finally, the practical application of "indecisive" rules requires further study into tie-breaking mechanisms that do not inadvertently re-introduce manipulability.

Summary updated

BibTeX
@inproceedings{botan2021preserving,
  author = {Sirin Botan and Ulle Endriss},
  title = {{Preserving Condorcet Winners under Strategic Manipulation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16657},
}
Figure