Approval with Runoff

Théo Delemazure, Jérôme Lang, Jean-François Laslier, M. Remzi SanverIJCAI 2022 · DOI

TL;DR

This paper introduces "Approval with Runoff," a novel two-round election system that leverages approval ballots in the first round to select finalists. By exploring a family of rules for selecting these finalists, the authors provide a more nuanced and potentially more robust alternative to traditional plurality-with-runoff systems, offering a richer set of outcomes and properties.

What Problem Does This Paper Address?

Traditional plurality-with-runoff voting, while widely used, suffers from significant drawbacks like sensitivity to cloning, manipulation, and a lack of Condorcet consistency. The authors argue that these issues stem from the limitations of the first round's input (single-choice ballots). They propose to retain the informational benefits of a two-round system while mitigating the drawbacks by using approval ballots in the first round. This allows voters to express support for multiple candidates, potentially leading to a more representative selection of finalists.

Methods

The core of the paper is the definition and analysis of a family of "Approval with Runoff" (AVR) rules. These rules operate in two stages:

  1. Finalist Selection: An Approval-based Committee (ABC) rule is used to select two finalists from the candidates based on approval ballots. The paper explores various ABC rules, including:
  2. MAV (Multi-Winner Approval Voting): Selects candidates with the highest individual approval scores.
  3. PAV (Proportional Approval Voting) and CCAV (Approval Chamberlin Courant): Discount voters who approve both finalists, aiming for proportionality or diversity.
  4. Sequential versions (S-PAV, S-CCAV): Ensure the first finalist is an approval winner.
  5. Eneström Phragmen (EnePhr) and Sequential Phragmen (S-Phr): Rules that balance proportionality and diversity.
  6. Splitted Approval Voting (SAV): Voters split their approval weight among approved candidates.
  7. Trivial Approval Voting (TRIV): A baseline rule that selects all pairs.
  8. Majority Vote: A standard majority vote is conducted between the two selected finalists to determine the overall winner.

The authors analyze these AVR rules using axiomatic properties (like Pareto-efficiency, monotonicity, strategy-proofness, and clone-proofness) and through simulations on one-dimensional Euclidean preferences and real-world datasets.

Datasets

The paper uses several real-world datasets for experimental analysis:

  • 2017 French Presidential Election Datasets: Poll data from "Voter Autrement" for several cities (Strasbourg, HSC, Grenoble, Crolles-1, Crolles-2). These datasets contain approval ballots from around 1000 voters for 11 candidates.
  • 2002 French Presidential Election Dataset: A dataset with 16 candidates.
  • San Sebastian Poster Competition Datasets (Best-Poster-A, Best-Poster-B): Datasets with 17 candidates and around 60 voters each.

Key Insights and Ideas

  • The choice of ABC rule for finalist selection profoundly impacts the AVR outcome: Different ABC rules lead to significantly different pairs of finalists, highlighting the importance of this parameter.
  • There's a trade-off between desirable properties: Axiomatic analysis reveals that no single AVR rule can simultaneously satisfy all desirable properties like Pareto-efficiency, strategy-proofness, and clone-proofness. This suggests that the "best" rule depends on the specific priorities of an election.
  • Approval ballots offer a richer input: Using approval ballots in the first round allows for a more nuanced selection of finalists compared to single-choice ballots, potentially leading to more diverse or representative outcomes.
  • Sequential rules are crucial for favorite-consistency: Only sequential ABC rules (where the first finalist is guaranteed to be an approval winner) satisfy the "favorite-consistency" property, which is important for voter acceptance.

Key Results

  • Impossibility Results: The paper establishes several key impossibility theorems:
  • No AVR rule is both weakly strategy-proof and Pareto-efficient.
  • No AVR rule is both clone-proof and Pareto-efficient.
  • No AVR rule is both monotonic and weakly clone-proof.
  • Rule Characterizations:
    • MAVR (using MAV for finalist selection) is monotonic and Pareto-efficient.
  • CCAVR and S-CCAVR are weakly clone-proof but not Pareto-efficient.
  • TRIVR is strategy-proof but not Pareto-efficient.
  • Experimental Findings:
    • On one-dimensional Euclidean preferences, rules closer to MAV tend to select centrist finalists, while rules closer to CCAV tend to select more extreme or diverse finalists.
  • Real-world data analysis shows that the choice of ABC rule can significantly impact the selected finalists, reinforcing the importance of this choice.

Limitations and Future Work

  • Ballot Consistency Assumption: While most results hold without it, the paper initially assumes ballot consistency (voters approve candidates they rank above a certain threshold). The implications of strategic, insincere approval ballots are noted as a limitation.
  • Evolution Between Rounds: The current framework does not account for the dynamic aspects of a two-round election, such as candidate negotiations or shifts in voter opinion between rounds. This is left for future research.
  • Voter Understanding and Acceptance: The paper raises the question of whether voters will understand and accept these new rules, especially compared to familiar plurality-with-runoff systems. This is an important area for future investigation.
  • Characterizing MAVR: While MAVR is shown to be monotonic and Pareto-efficient, it's not uniquely characterized by these properties, suggesting further axiomatic work is needed.

Summary updated

BibTeX
@inproceedings{delemazure2022approval,
  author = {Théo Delemazure and Jérôme Lang and Jean-François Laslier and M. Remzi Sanver},
  title = {{Approval with Runoff}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/33},
}
Figure