Weak Strategyproofness in Randomized Social Choice
Abstract
An important - but very demanding - property in collective decision-making is strategyproofness, which requires that voters cannot benefit from submitting insincere preferences. Gibbard (1977) has shown that only rather unattractive rules are strategyproof, even when allowing for randomization. However, Gibbard's theorem is based on a rather strong interpretation of strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for at least one utility function consistent with his ordinal preferences. In this paper, we study weak strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for all utility functions consistent with his ordinal preferences. We show how to systematically design attractive, weakly strategyproof social decision schemes (SDSs) and explore their limitations for both strict and weak preferences. In particular, for strict preferences, we show that there are weakly strategyproof SDSs that are either ex post efficient or Condorcet-consistent, while neither even-chance SDSs nor pairwise SDSs satisfy both properties and weak strategyproofness at the same time. By contrast, for the case of weak preferences, we discuss two sweeping impossibility results that preclude the existence of appealing weakly strategyproof SDSs.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on1
Related papers
- Strategyproof Voting under Correlated BeliefsDaniel Halpern, Rachel Li, Ariel D. ProcacciaNeurIPS 2023
- Semi-random Impossibilities of Condorcet CriterionLirong XiaAAAI 2023 · 6 citations
- Strategyproofness and Proportionality in Party-Approval Multiwinner ElectionsThéo Delemazure, Tom Demeulemeester, Manuel Eberl, Jonas Israel et al.AAAI 2023 · 13 citations
- Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location MechanismHaris Aziz, Alexander Lam, Mashbat Suzuki, Toby WalshNeurIPS 2022 · 11 citations
- Robust Voting Rules from Algorithmic Robust StatisticsAllen Liu, Ankur MoitraSODA 2023
