Abstract
This paper introduces 2-Agree, a randomized voting mechanism that queries random voters for their top choice until two agree. Despite its simplicity and low sample complexity, 2-Agree achieves near-optimal distortion for small sets of alternatives and remains robust against strategic manipulation.
Introduction
In social choice theory, the challenge is to aggregate individual preferences into a single outcome that maximizes social utility. While traditional research focuses on fairness and utilitarian criteria, the practical constraint of sample complexity is often overlooked. Eliciting full ranked lists of preferences from every voter is frequently expensive and time-consuming. This paper addresses the "implicit utilitarian voting" problem: how to select a winner using limited ordinal information while minimizing distortion—the ratio of the actual social cost to the theoretical minimum.
The 2-Agree Mechanism
The authors propose an elegant and simple "tops-only" mechanism called 2-Agree. The algorithm proceeds as follows:
- Select a voter at random and ask for their top-ranked alternative.
- If this alternative has been named by a previous voter in the current round, it is declared the winner.
- If not, repeat the process with a new random voter.
This mechanism is highly efficient, requiring at most $m+1$ queries (where $m$ is the number of alternatives) to guarantee a winner. In terms of information theory, it requires only $O(m \log m)$ bits, a significant improvement over standard rules like Borda count which require $O(mn)$ bits for $n$ voters.
Theoretical Framework
The evaluation of 2-Agree is grounded in mathematical proofs and numerical simulations within a standard metric space framework. In this model, voter preferences are induced by their distances to alternatives, and costs are assumed to satisfy the triangle inequality. The study establishes both upper and lower bounds for distortion across varying numbers of alternatives.
Performance and Distortion
A key finding is the "Power of Two": moving from Random Dictatorship (effectively "1-Agree") to 2-Agree significantly reduces distortion. While Random Dictatorship maintains a constant distortion of 3 in general metric spaces, 2-Agree brings this value closer to 2 for small sets of alternatives.
For $m=3$ alternatives, 2-Agree achieves a distortion of approximately 2.33, nearly reaching the theoretical lower bound of $3 - 2/m$. The mechanism is particularly effective when voters are "decisive"—having a strong preference for their top choice over their second. In such cases, 2-Agree can outperform more complex rules even as the number of alternatives increases.
Incentives and Truthfulness
Beyond efficiency and utility, 2-Agree offers strong participation incentives. It satisfies "very strong SD-participation," meaning a voter is always strictly better off participating than abstaining. Furthermore, while not perfectly strategy-proof, the mechanism is approximately truthful.
As shown in the data, the potential gain from strategic manipulation is very small, especially in larger populations. For $n \ge 50$, the incentive to misreport preferences is negligible, with a worst-case truthfulness ratio of approximately 1.04.
Conclusion
2-Agree represents a powerful tool for collective decision-making in scenarios where the cost of eliciting preferences is high. While its performance relative to Random Dictatorship eventually degrades for very large sets of alternatives, it occupies a "sweet spot" for small-to-medium $m$. Future work may explore the strategic complexities of sequential voting and the relaxation of metric assumptions to better capture human psychological preferences.
Summary updated