Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion

Fatih Erdem Kizilkaya, David Kempe

TL;DR

This paper introduces PLURALITYVETO, a remarkably simple voting rule that achieves the theoretically optimal "metric distortion" of 3. This rule is not only efficient, requiring minimal voter input, but also provides a constructive proof for a previously complex mathematical result, and its generalization offers a spectrum of randomized voting rules with controlled variance.

What Problem Does This Paper Address?

Imagine a scenario where voters rank candidates based on how "close" they are to their own preferences in some abstract space. The goal of a voting rule is to pick a candidate that minimizes the total "distance" to all voters, but crucially, the rule only sees the rankings, not the actual distances. This is known as the "metric distortion" problem. It's been established that any deterministic voting rule will, in the worst case, pick a candidate whose total distance is at least three times worse than the best possible candidate (a distortion of 3). While a recent breakthrough proved that achieving this optimal distortion of 3 is possible, the proposed voting rule was extremely complex and its existence proof was non-constructive. This paper tackles the challenge of finding a simple, constructive, and practical voting rule that achieves this optimal distortion.

Methods

The core contribution is the PLURALITYVETO voting rule. Here's how it works:

  1. Initialization: Each candidate starts with a score equal to their number of first-place votes (the plurality score).
  2. Veto Rounds: The rule proceeds in rounds. In each round, a voter is selected (arbitrarily). This voter then "vetoes" (decrements the score of) their least preferred candidate among those still remaining (i.e., those whose score is still positive).
  3. Elimination: When a candidate's score reaches zero, they are eliminated.
  4. Winner: The last candidate to be eliminated is the winner.

This process is surprisingly simple and requires only two pieces of information from each voter: their top choice and their bottom choice among the currently uneliminated candidates.

The authors also introduce FRACTIONALVETO, a generalization of PLURALITYVETO that uses fractional scores. This is used to provide a constructive proof for the more general Ranking-Matching Lemma, a key result in the field that was previously proven non-constructively.

Finally, they propose k-ROUNDPLURALITYVETO, a family of randomized voting rules. These rules run PLURALITYVETO for k rounds and then select a winner probabilistically, with probabilities proportional to the remaining scores. This interpolates between RANDOMDICTATORSHIP (where k=0, and a random voter's top choice wins) and PLURALITYVETO (where k = n-1, and the last remaining candidate wins).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Simplicity is Powerful: The most striking insight is that a very simple, intuitive voting rule like PLURALITYVETO can achieve the theoretically optimal worst-case performance (distortion 3). This contrasts sharply with the complexity of previous rules that achieved the same bound.
  • Constructive Proofs Matter: By developing FRACTIONALVETO, the authors provide a constructive method to prove the Ranking-Matching Lemma. This is significant because constructive proofs are often more valuable in practice, as they directly yield algorithms.
  • Vetoing the Worst is Key: The core mechanism of PLURALITYVETO – voters eliminating their least preferred remaining candidate – is what drives its optimal distortion. This "veto" process effectively prunes away candidates that are furthest from the voters' collective preferences.
  • Randomization for Control: The k-ROUNDPLURALITYVETO family shows how randomization can be used to tune the trade-off between distortion and variance. While the deterministic PLURALITYVETO has a fixed distortion, its randomized counterparts allow for a spectrum of outcomes.

Key Results

  • PLURALITYVETO achieves optimal distortion of 3: This is the main theoretical result, proven with a concise argument.
  • Low Communication Overhead: PLURALITYVETO requires only O(log m) bits per voter, making it highly practical for eliciting preferences.
  • Constructive Proof of Ranking-Matching Lemma: The generalized FRACTIONALVETO provides a simpler, constructive proof for a significant theoretical result.
  • k-ROUNDPLURALITYVETO has expected distortion ≤ 3: This class of randomized rules offers a way to interpolate between random dictatorships and PLURALITYVETO, with the parameter k controlling variance without increasing the worst-case expected distortion.
  • Polynomial-time Multi-winner Rule: A corollary of their work leads to a polynomial-time multi-winner voting rule with distortion 3, resolving an open question in the field.

Limitations and Future Work

  • Order Dependence: The paper acknowledges that the specific winner of PLURALITYVETO can depend on the order in which voters are processed. While the distortion bound holds regardless of the order, the identity of the winner might change. This dependence is noted as an interesting object of study for future work.
  • Axiomatic Properties: The authors suggest exploring whether PLURALITYVETO satisfies other standard axiomatic properties of voting rules.
  • Incentives and "Price of Anarchy": An interesting future direction is to study the strategic incentives of voters under PLURALITYVETO, particularly in a setting where agents might not truthfully reveal their preferences, leading to a "Price of Anarchy" analysis.
  • Peer Selection Setting: The paper briefly touches upon the "Peer Selection" setting (where voters and candidates are the same set) and suggests further investigation into the properties of PLURALITYVETO in this context, including the number of potential winners.

Summary updated

Abstract

The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search. Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead. We also show that a straightforward extension can be used to give a constructive proof of the more general Ranking-Matching Lemma of Gkatzelis et al. We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k < n rounds; then, a candidate is chosen with probability proportional to his residual score. This general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output. We show that for all k, this rule has expected distortion at most 3.
BibTeX
@inproceedings{kizilkaya2022plurality,
  author = {Fatih Erdem Kizilkaya and David Kempe},
  title = {{Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=0s3vxkbceR},
}
Figure