TL;DR
This paper explores how to design fair and truthful voting systems (Social Decision Schemes or SDSs) when voters have preferences over lotteries (probabilistic outcomes). They demonstrate that a common way to model these preferences, called pairwise comparison (PC), leads to fundamental impossibilities: you can't simultaneously have efficient outcomes, truthful voting, and fair treatment of voters and alternatives when there are 4 or more options. This means there's a trade-off between efficiency and truthful incentives in these systems.
What Problem Does This Paper Address?
Designing collective decision-making systems (like voting) that are both fair and encourage honest participation is a long-standing challenge. Social Decision Schemes (SDSs) offer a way to handle this by allowing for probabilistic outcomes (lotteries) instead of just picking a single winner. This can help avoid some of the paradoxes that plague deterministic voting systems.
Traditionally, preferences over lotteries are modeled using "stochastic dominance" (SD), which is based on expected utility. However, this paper focuses on an alternative model called "pairwise comparison" (PC). In PC, a voter prefers one lottery to another if it's more likely to yield a better outcome. The authors investigate whether PC preferences allow for desirable properties like efficiency (no lottery is unanimously preferred to the chosen one), strategyproofness (no one can benefit by lying about their preferences), and participation (voters are better off participating). They specifically address three open questions from prior work, asking if it's possible to have SDSs that are:
- Condorcet-consistent (always pick the Condorcet winner if one exists) and PC-strategyproof.
- Anonymous (treat voters equally), neutral (treat alternatives equally), PC-efficient, and PC-strategyproof.
- Anonymous, neutral, PC-efficient, and strictly PC-participating (voters are strictly better off participating).
Methods
The paper uses a proof-by-contradiction approach, constructing specific preference profiles and using the axioms of SDSs to derive contradictions. They leverage the definitions of PC preferences, efficiency, strategyproofness, and participation.
Key techniques include:
- Constructing specific preference profiles: The authors carefully design scenarios with a small number of voters and alternatives to highlight the incompatibilities.
- Applying PC preference extension: They use the rule that lottery $p$ is preferred to lottery $q$ if $\sum_{x,y \in A: x >_i y} p(x)q(y) \ge \sum_{x,y \in A: x >_i y} q(x)p(y)$.
- Deriving inequalities from strategyproofness: If an SDS is strategyproof, a voter will not deviate if their reported preference leads to a lottery they don't strictly prefer. This is used to establish bounds on the probabilities assigned to alternatives.
- Using Condorcet-consistency and PC-efficiency: These axioms are used to fix probabilities for certain outcomes in specific profiles, which then constrain the possibilities for other outcomes.
- Generalization: They show that impossibilities holding for $m=4$ alternatives can be extended to any $m \ge 4$ by introducing Pareto-dominated "dummy" alternatives. They also show that these impossibilities disappear for $m \le 3$.
Datasets
Not discussed in the paper. The paper focuses on theoretical impossibilities and constructions rather than empirical evaluation on datasets.
Key Insights and Ideas
- PC preferences are "harder" than SD preferences: While stochastic dominance (SD) allows for systems like uniform random dictatorship to satisfy many desirable properties, the pairwise comparison (PC) extension of preferences reveals deeper incompatibilities. This suggests that the way voters compare lotteries significantly impacts what's achievable.
- No "perfect" SDS for PC preferences: Unlike with SD preferences where uniform random dictatorship is a strong candidate, there's no single SDS that simultaneously achieves PC-efficiency and PC-strategyproofness (and other fairness criteria) when there are 4 or more alternatives.
- A fundamental trade-off: The core takeaway is a trade-off between efficiency and incentive compatibility (strategyproofness and participation) when using PC preferences. You can have one, but not both, along with fairness criteria.
- PC doesn't circumvent Arrow's Impossibility: While PC preferences have been shown to circumvent other paradoxes (like the No-Show paradox), they don't offer a way around the fundamental Gibbard-Satterthwaite theorem's implications for strategyproofness.
Key Results
The paper proves three main impossibility theorems for $m \ge 4$ alternatives:
- Impossibility of Condorcet-consistent and PC-strategyproof SDSs: There is no SDS that is both Condorcet-consistent and PC-strategyproof. This is shown by constructing profiles where a voter can manipulate the outcome by switching their reported preferences, leading to a violation of strategyproofness.
- Impossibility of Anonymous, Neutral, PC-efficient, and PC-strategyproof SDSs: There is no SDS that satisfies all these properties simultaneously. This result is derived by first showing that these axioms imply the "absolute winner property" (where an alternative ranked highest by a majority wins with certainty) and then demonstrating that any PC-efficient SDS satisfying the absolute winner property is PC-manipulable.
- Impossibility of Anonymous, Neutral, PC-efficient, and strictly PC-participating SDSs: Similar to the previous result, this impossibility is proven by showing that these axioms lead to a situation where a voter has a disincentive to participate, contradicting strict PC-participation.
Crucially, all these impossibilities are shown to disappear when the number of alternatives $m$ is 3 or less. For $m=3$, they construct specific SDSs that do satisfy the desired properties.
Limitations and Future Work
- Number of alternatives: The main limitation is that the impossibility results require $m \ge 4$ alternatives. The paper explicitly shows that for $m \le 3$, these properties can be achieved by constructing specific SDSs.
- Even number of voters: Theorem 1's proof sketch focuses on an odd number of voters. While they mention the argument for even $n$ is similar, it's not fully detailed in the sketch.
- Anonymity and Neutrality for Theorem 3: The authors are unsure if anonymity and neutrality are strictly necessary for Theorem 3 (the strict PC-participation impossibility). They conjecture that Theorem 2 (PC-strategyproofness impossibility) might hold even without neutrality.
- Future Work: The paper suggests exploring whether the impossibility results hold for even numbers of voters and investigating the necessity of anonymity and neutrality for Theorem 3. They also highlight the trade-off between efficiency and incentive compatibility as a key area for future research in designing SDSs with PC preferences.
Summary updated