Lune

AAAI2025Top-tier venue

Weak Strategyproofness in Randomized Social Choice

Felix Brandt, Patrick Lederer

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. Preserving Condorcet Winners under Strategic ManipulationSirin Botan, Ulle EndrissAAAI 2021 · 2 citations

Related papers

  1. Strategyproof Voting under Correlated BeliefsDaniel Halpern, Rachel Li, Ariel D. ProcacciaNeurIPS 2023
  2. Semi-random Impossibilities of Condorcet CriterionLirong XiaAAAI 2023 · 6 citations
  3. Strategyproofness and Proportionality in Party-Approval Multiwinner ElectionsThéo Delemazure, Tom Demeulemeester, Manuel Eberl, Jonas Israel et al.AAAI 2023 · 13 citations
  4. Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location MechanismHaris Aziz, Alexander Lam, Mashbat Suzuki, Toby WalshNeurIPS 2022 · 11 citations
  5. Robust Voting Rules from Algorithmic Robust StatisticsAllen Liu, Ankur MoitraSODA 2023
Dusk over the sea between two cliffs drawn in fine vertical lines