Efficient, Private, and eps-Strategyproof Elicitation of Tournament Voting Rules

David Timothy LeeIJCAI 2015

Abstract

Large-scale crowdsourced decision-making faces significant hurdles in preference elicitation, strategic manipulation, and participant privacy. This paper introduces a suite of algorithms that identify approximate winners for a broad class of tournament voting rules while maintaining efficiency and security. By relaxing the requirement from finding an exact winner to an $\epsilon$-approximate one, the authors bypass classic impossibility results in social choice theory. The proposed methods provide the first simultaneous guarantees for low communication complexity, differential privacy, and $\epsilon$-strategyproofness.

Introduction

When aggregating preferences from a large crowd to rank options or select a winner, three major challenges arise. First, preference elicitation is often prohibitively expensive; asking every voter to rank hundreds of candidates is impractical. Second, strategic manipulation is a constant threat, as voters may lie about their true preferences to achieve a more favorable outcome. Finally, participant privacy is paramount, as individual votes can reveal sensitive personal information.

Classic results in social choice theory, such as the Gibbard-Satterthwaite theorem, suggest that any non-dictatorial voting rule is susceptible to strategic manipulation. This paper demonstrates that by accepting a small degree of approximation, it is possible to design voting systems that are efficient, private, and resistant to both individual and group manipulation.

Methodology: Tournament Voting Rules and Approximation

The authors focus on Tournament Voting Rules, where the winner is determined solely by a tournament matrix—a table of pairwise comparisons between candidates. Common examples include Borda, Copeland, and Maximin.

Example of a tournament matrix showing pairwise preferences between candidates A, B, and C in a 100-voter scenario.

The core innovation lies in the definition of an $\epsilon$-approximate winner. A candidate is an $\epsilon$-approximate winner if they would have won under the chosen rule if a small fraction (at most $\epsilon$) of the pairwise comparisons in the tournament matrix were changed. This "wiggle room" allows the algorithms to use sampling and noise to protect privacy and prevent gaming. For instance, in a 100-voter example, a candidate who loses a pairwise matchup by only a few votes might still be considered an approximate winner if the system allows for a small error margin.

Algorithmic Approaches

The paper proposes three main algorithmic frameworks:

  1. BORDA+RANDOM: Specifically for the Borda rule, this algorithm asks voters for a limited number of random pairwise comparisons. It incorporates a "random winner" step—picking a winner at random with a very small probability—to provide differential privacy and strategyproofness.
  2. SAMPLE-VOTERS+RANDOM: This approach selects a small, random subset of voters and asks for their full rankings. This is shown to be sufficient to approximate the winner for any tournament voting rule.
  3. SAMPLED-SUBSETS: To reduce individual voter burden, each participant is asked to rank only a small, random subset of candidates. This distributes the elicitation workload across the entire population.

Theoretical Guarantees and Key Results

The integration of Differential Privacy (DP) and $\epsilon$-strategyproofness ensures that a single voter's input has a negligible effect on the final outcome. This makes it mathematically "not worth it" for a voter to lie, as the potential gain is outweighed by the inherent noise in the system.

Key Findings

  • Efficiency Gains: The Borda winner can be identified using only $\tilde{O}(m/\epsilon^2)$ total comparisons, a significant reduction from the standard $\Omega(mn)$ requirement.
  • Broad Applicability: The sampling-based approach generalizes to complex tournament rules, including Kemeny-Young and Schulze.
  • Security and Privacy: These are the first algorithms to achieve efficient elicitation, DP, and strategyproofness simultaneously.
  • Collusion Resistance: The algorithms are proven to be "group strategyproof," meaning even coordinated lying by a small group of voters cannot significantly alter the results.

Discussion and Limitations

While the paper solves the "elicitation" problem (how to ask for data efficiently), it does not necessarily solve the "computation" problem. For rules like Kemeny-Young, which are NP-hard to compute, the algorithm still requires solving a hard problem once the data is collected. Additionally, the number of voters required for certain guarantees scales with $1/\epsilon^4$, which may necessitate very large populations for high-precision applications.

Future research could explore alternative definitions of approximation, such as those based on Kendall-tau distance, to better align with specific real-world applications where candidate displacement in individual rankings is more critical than changes in the tournament matrix.

Summary updated

BibTeX
@inproceedings{lee2015efficient,
  author = {David Timothy Lee},
  title = {{Efficient, Private, and eps-Strategyproof Elicitation of Tournament Voting Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure