Research map / Learning theory and algorithms / Submodular and game algorithms
Weak Strategyproofness in Randomized Social Choice
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies weak strategyproofness (manipulation counts only if it helps for all utility functions consistent with ordinal preferences) for social decision schemes, giving possibility results (score-based SDSs, tops-only characterizations) and impossibility results for strict and weak preferences.
Problem
Gibbard's random dictatorship theorem relies on strong strategyproofness, which is very demanding; the question is which randomized voting rules (SDSs) remain strategyproof under a weaker notion where only manipulations successful for all consistent utilities count.
Approach
Defines weak strategyproofness via comparable lotteries only, introduces a broad class of score-based SDSs (with balancedness and localizedness conditions) proven weakly strategyproof, and characterizes weakly strategyproof tops-only and even-chance SDSs, revealing a sharp contrast between strict and weak preferences.
Key results
- Score-based SDSs (e.g., s_C^k, s_P^k) are weakly strategyproof for strict preferences, and some are Condorcet-consistent or approximately ex post efficient.
- No even-chance SDS on strict preferences satisfies weak strategyproofness, Condorcet-consistency, and ex post efficiency (for m>=5, odd n>=5).
- For weak preferences, every ex post efficient, weakly strategyproof even-chance SDS is dictatorial or bidictatorial; no anonymous, neutral, weakly strategyproof SDS is ex ante efficient (simplified proof).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a score-based SDS | SDSs on strict preferences · Strict preferences | weak strategyproofness | Helped |
| Use the Condorcet rule or a Copeland score variant with a Condorcet-winner score | SDSs on strict preferences · Strict preferences | Condorcet-consistency | Helped |
| Require an even-chance SDS | Weakly strategyproof SDSs with strict preferences · Strict preferences; m≥5, n≥5 odd | simultaneous Condorcet-consistency and ex post efficiency | Hurt |
| Restrict the SDS to be pairwise and neutral | Weakly strategyproof SDSs on strict preferences · Strict preferences; m≥5 | ex post efficiency | Hurt |
| Require anonymity and neutrality | Weakly strategyproof SDSs on weak preferences · Weak preferences; n≥4, m≥4 | ex ante efficiency | Hurt |
| Require ex post efficiency and weak strategyproofness while restricting to even-chance SDSs | SDSs on weak preferences · Weak preferences; m≥3, n≥3 | dictatorial or bidictatorial outcome | Hurt |
Surprising findings
- Weak strategyproofness permits Condorcet-consistent and approximately ex post efficient SDSs, unlike strong strategyproofness.
- For weak preferences, even mild strategyproofness restricts even-chance ex post efficient SDSs to (bi)dictatorial rules.
Limitations
- Conjecture that no weakly strategyproof SDS satisfies both Condorcet-consistency and ex post efficiency remains open.
- Several impossibility results require anonymity/neutrality or odd number of voters and bounds on m and n.
- Condorcet-consistency and ex post efficiency impossibility proven only for even-chance or pairwise SDSs.
Experimental setup
Baselines: random dictatorship omninomination rule Condorcet rule random serial dictatorship
Builds on: Gibbard random dictatorship theorem stochastic dominance for lotteries even-chance strategyproofness
Closest papers by meaning
- Strategyproof Voting under Correlated Beliefs (NeurIPS 2023 · similarity 0.90)
- The Smoothed Possibility of Social Choice (NeurIPS 2020 · similarity 0.89)
- Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice (AAAI 2019 · similarity 0.89)
- Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.87)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.86)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.