Abstract
The Gibbard-Satterthwaite Theorem asserts that any reasonable voting rule cannot be strategyproof. A large body of research in AI deals with circumventing this theorem via computational considerations; the goal is to design voting rules that are computationally hard, in the worst-case, to manipulate. However, recent work indicates that the prominent voting rules are usually easy to manipulate. In this paper, we suggest a new CS-oriented approach to circumventing Gibbard-Satterthwaite, using randomization and approximation. Specifically, we wish to design strategyproof randomized voting rules that are close, in a standard approximation sense, to prominent score-based (deterministic) voting rules. We give tight lower and upper bounds on the approximation ratio achievable via strategyproof randomized rules with respect to positional scoring rules, Copeland, and Maximin.
Introduction
In the field of Computational Social Choice, the Gibbard-Satterthwaite Theorem stands as a formidable "no-go" result. It establishes that any deterministic voting rule involving three or more candidates is either dictatorial or susceptible to tactical manipulation, where voters can achieve better outcomes by misrepresenting their true preferences.
Historically, researchers attempted to bypass this by making manipulation computationally difficult (e.g., NP-hard). However, empirical and theoretical evidence suggests that even if manipulation is hard in the worst case, it remains frequently feasible in practice. This paper explores a different avenue: Randomization. By allowing a voting rule to output a probability distribution over winners, we investigate whether we can achieve strategyproofness (SP)—where no voter increases their expected utility by lying—while approximating the performance of classic deterministic rules.
Methodology and Framework
The success of a randomized rule is measured using the approximation ratio $\gamma$. A rule achieves a ratio of $\gamma$ if the expected score of its selected winner is at least a $\gamma$-fraction of the maximum possible score under a target deterministic rule, such as Borda or Plurality.
The analysis is grounded in a characterization by Gibbard (1977), which identifies all SP randomized rules as mixtures of two types:
- Unilateral rules: The outcome depends solely on one voter's ballot.
- Duple rules: The outcome is restricted to a choice between two specific candidates.
The paper evaluates two primary "proportional" rules. Rule 1 selects a voter at random and then a candidate with probability proportional to that voter's assigned score. Rule 2 selects a pair of candidates at random for a majority face-off. Using Yao’s Minimax Principle, the author derives tight bounds for these mixtures.
Key Results
The study provides a definitive "scorecard" for the approximability of various voting rules under the constraint of strategyproof randomization.
The findings reveal a significant "Halfway Barrier" for rules like Borda and Copeland, where the best possible SP approximation ratio is approximately $1/2$. This represents a "price of stability" for immunity to manipulation. Notably, Plurality is significantly harder to approximate than Borda, with its ratio scaling as $1/\sqrt{m}$ (where $m$ is the number of candidates). Conversely, the Maximin rule—which prioritizes candidates based on their worst pairwise performance—is essentially inapproximable, yielding a ratio of zero in the limit.
Discussion and Future Work
While an approximation ratio of $1/2$ might be viewed as a negative result—capturing only half the social welfare in the worst case—it provides a clear theoretical limit for strategyproofness. The "proportional" rules introduced here are nearly optimal within the class of SP randomized rules for Borda and Copeland.
Future research should look beyond approximation ratios to other axiomatic properties of randomized rules, such as positive response. Additionally, exploring the approximability of other systems like Veto or Bucklin voting, particularly in scenarios with a small number of candidates, remains a promising direction.
Summary updated