Weak Strategyproofness in Randomized Social Choice

Felix Brandt, Patrick LedererAAAI 2025 · DOI

TL;DR

This paper explores "weak strategyproofness" in voting systems that use randomization. Unlike traditional "strong strategyproofness," which prevents manipulation even if a voter is indifferent about the outcome, weak strategyproofness only cares if a voter can strictly improve their outcome. The authors show this weaker condition allows for more attractive voting rules that can be both fair and efficient, especially when voters have strict preferences, but highlights significant limitations when preferences are weak.

What Problem Does This Paper Address?

In collective decision-making, we want voting systems to be "strategyproof," meaning voters shouldn't be able to benefit by lying about their preferences. A seminal result by Gibbard and Satterthwaite showed that for deterministic voting rules, this is almost impossible – only dictatorships are strategyproof. Even when allowing for randomization (Social Decision Schemes or SDSs), Gibbard's theorem showed that only "random dictatorships" are strategyproof and efficient.

The catch is that Gibbard's definition of strategyproofness is quite strict. It considers a manipulation successful if it leads to an outcome that is at least as good for at least one possible interpretation of the voter's preferences. This paper tackles the question: what if we relax this? What if a manipulation is only considered successful if it leads to an outcome that is strictly better for all possible interpretations of the voter's preferences? This is the core of "weak strategyproofness." The authors investigate what kinds of voting rules become possible and desirable under this weaker, yet still meaningful, fairness condition.

Methods

The paper introduces and analyzes "weak strategyproofness" for Social Decision Schemes (SDSs). The key methodological shift is the definition of how voters compare lotteries (probabilistic outcomes). Instead of requiring a deviation to be beneficial for any utility function consistent with their preferences (strong strategyproofness), they require it to be beneficial for all such utility functions (weak strategyproofness).

They then explore two main avenues:

  1. Possibility Theorems: They identify classes of SDSs that satisfy weak strategyproofness. A significant contribution is the characterization of "score-based SDSs," a broad class that includes many appealing rules. They also analyze "tops-only SDSs," which only consider voters' most preferred alternatives.
  2. Impossibility Theorems: They investigate the limitations of weak strategyproofness, particularly when combined with desirable properties like efficiency and Condorcet-consistency (selecting a winner that beats all others pairwise). They prove that for strict preferences, certain combinations of desirable properties are impossible for specific types of SDSs (even-chance, pairwise, neutral). For weak preferences, they demonstrate even more severe limitations, showing that mild efficiency and fairness requirements become incompatible with weak strategyproofness.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on abstract properties of voting rules rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Weak Strategyproofness is More Permissive: The core insight is that weakening the definition of strategyproofness significantly expands the set of desirable voting rules. Rules that fail strong strategyproofness can be weakly strategyproof.
  • Score-Based Rules Shine: The paper introduces "score-based SDSs" and proves they are all weakly strategyproof. This is a powerful result, as it allows for the construction of rules that can approximate deterministic voting rules (like Plurality or Copeland) while being weakly strategyproof, something impossible under strong strategyproofness.
  • Trade-offs Remain: While weak strategyproofness opens doors, it doesn't eliminate all trade-offs. The paper shows that for strict preferences, achieving weak strategyproofness along with both Condorcet-consistency and ex post efficiency is impossible for certain classes of SDSs (like even-chance SDSs).
  • Weak Preferences are Much Harder: The most striking finding is the severe limitations when voters have weak preferences (allowing indifference between alternatives). Here, even mild efficiency and fairness conditions become incompatible with weak strategyproofness, leading to highly restrictive outcomes like dictatorial or bidictatorial rules.

Key Results

  • Possibility for Strict Preferences:
    • All "score-based SDSs" are weakly strategyproof.
  • This allows for weakly strategyproof SDSs that are approximately ex post efficient or Condorcet-consistent.
  • Characterizations of weakly strategyproof "tops-only" SDSs are provided.
  • Impossibility for Strict Preferences:
    • No "even-chance" SDS can simultaneously be weakly strategyproof, Condorcet-consistent, and ex post efficient (for m, n ≥ 5).
  • No "pairwise" and "neutral" SDS can be weakly strategyproof and ex post efficient (for m ≥ 5).
  • Impossibility for Weak Preferences:
    • No anonymous, neutral SDS on weak preferences can be ex ante efficient and weakly strategyproof.
  • Every ex post efficient and weakly strategyproof "even-chance" SDS on weak preferences must be dictatorial or bidictatorial (for m, n ≥ 3).

Limitations and Future Work

  • Conjecture on Strict Preferences: The authors conjecture that no SDS can simultaneously satisfy weak strategyproofness, Condorcet-consistency, and ex post efficiency for strict preferences, even beyond the specific classes of SDSs they analyzed. Proving this would unify several existing results.
  • Weak Preferences and Dictatorships: The strong results for weak preferences raise the question of whether all weakly strategyproof and ex post efficient SDSs on weak preferences are restricted to randomizing over the top-ranked alternatives of only a few voters.
  • Even vs. Odd Number of Voters: Similar to many results in social choice theory, some impossibility results are proven for odd numbers of voters and might not hold for even numbers. The authors note they cannot prove their main impossibility result for even n but suggest a related result for "strong Condorcet-consistency."
  • Generalizing to Other Notions: The paper focuses on weak strategyproofness. Future work could explore other relaxed notions of strategyproofness and their implications.

Summary updated

BibTeX
@inproceedings{brandt2025weak,
  author = {Felix Brandt and Patrick Lederer},
  title = {{Weak Strategyproofness in Randomized Social Choice}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33493},
}
Figure