TL;DR
This paper introduces "U-strategyproofness," a weaker form of strategyproofness for randomized voting systems that only requires immunity to manipulation for a specific subset of voter utility functions. This allows for a more nuanced analysis of the trade-off between strategyproofness and desirable properties like decisiveness, potentially enabling more practical voting mechanisms.
What Problem Does This Paper Address?
In social choice theory, a major challenge is ensuring that voting systems are "strategyproof," meaning voters cannot benefit by misrepresenting their preferences. For deterministic voting rules, it's been proven that no system can be both strategyproof and fair (not dictatorial or imposing). Randomized voting systems, called Social Decision Schemes (SDSs), offer a way around this, but the standard definition of strategyproofness for SDSs (SD-strategyproofness) is so strong that it leads to similarly undesirable outcomes: systems are either unfair, indecisive (rely heavily on chance), or both. This paper aims to find a middle ground by relaxing the strategyproofness requirement. Instead of demanding that all possible utility functions are immune to manipulation, they propose focusing on a predefined set of plausible utility functions, U. This allows for a more flexible analysis of strategyproofness and its compatibility with other desirable properties like decisiveness.
Methods
The core innovation is the introduction of U-strategyproofness. This axiom states that an SDS is U-strategyproof if no voter whose utility function belongs to a specific set U can improve their expected utility by misrepresenting their preferences. This is a weaker condition than the standard SD-strategyproofness, which requires this for all possible utility functions consistent with a voter's preference relation.
The authors then analyze the compatibility of U-strategyproofness with several decisiveness axioms:
- k-unanimity: An alternative is chosen with probability 1 if it's ranked first by at least n-k voters.
- Condorcet-consistency: The Condorcet winner (an alternative that beats all others in pairwise comparisons) is chosen with probability 1.
- Ex post efficiency: Alternatives that are Pareto-dominated (worse for all voters than another alternative) are never chosen.
They propose two new SDSs, RDk (k-random dictatorships) and OMNI*, which aim to balance k-unanimity and U-strategyproofness for specific sets of utility functions. They also investigate impossibility results, showing when U-strategyproofness is incompatible with Condorcet-consistency and ex post efficiency, particularly for certain types of utility functions.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- U-strategyproofness as a flexible tool: The paper argues that focusing on a subset of utility functions (U) is more realistic and allows for a finer-grained understanding of strategyproofness. It's not about whether a system is universally strategyproof, but whether it is strategyproof for the types of voters we care about.
- The trade-off is nuanced: The paper demonstrates that by weakening strategyproofness, we can achieve better decisiveness. However, the "cost" of this is that the remaining vulnerability to manipulation is tied to specific utility functions, particularly those where voters are close to indifferent between their top choices.
- Indifference is the enemy of strategyproofness: A recurring theme is that voters who are very decisive about their top preferences are less likely to manipulate. Conversely, voters who are nearly indifferent between their best alternatives are the ones who can exploit weaknesses in a system, even under U-strategyproofness.
- Impossibility results are conditional: The paper shows that Condorcet-consistency and U-strategyproofness are incompatible for most utility functions when there are 4 or more alternatives. However, for the specific case of 3 alternatives and "equi-distant" utility functions, the Condorcet rule is U-strategyproof.
Key Results
- RDk and OMNI* SDSs: These systems satisfy k-unanimity and U-strategyproofness for utility functions where the difference between the top two choices is sufficiently large relative to other preferences.
- Condorcet-consistency and U-strategyproofness incompatibility: For 4 or more alternatives, no Condorcet-consistent SDS is U-strategyproof for any non-empty set of utility functions satisfying minimal symmetry conditions. This is a strong negative result.
- Condorcet rule for 3 alternatives: For 3 alternatives and a specific type of utility function (equi-distant), the Condorcet rule is U-strategyproof and Condorcet-consistent.
- Ex post efficiency and decisiveness: When utility functions are close to indifferent between the top two alternatives, no U-strategyproof and ex post efficient SDS can be significantly more decisive than a simple random dictatorship.
Limitations and Future Work
- Tightness of bounds: While the paper provides bounds for U-strategyproofness, it acknowledges that finding rank-based SDSs that satisfy U-strategyproofness and k-unanimity for larger sets of utility functions remains an open question.
- Generalizing impossibility results: The paper shows that Condorcet-consistency and U-strategyproofness are incompatible for many scenarios, but further work could explore the exact conditions under which this incompatibility holds.
- Practical implications of U: The paper suggests that U-strategyproofness is relevant in practice because not all utility functions are equally plausible. Future work could explore how to best define these sets U based on empirical data or behavioral economics.
- The role of indifference: The results strongly suggest that voters' indifference between alternatives is the primary driver of manipulability. Further research could focus on designing systems that are robust to this indifference.
Summary updated