The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem

DOI10.1007/S00493-012-2704-1MaRDI QIDQ452827zbMATH OpenOpenAlexFDO

Authors Marcus Isaksson, Guy Kindler, Elchanan Mossel

Publication date 17 September 2012

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.0517

zbMATH Keywords

voting systemsocial choice functionmanipulabilitydictator

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Social choice (91B14) Voting theory (91B12)

Abstract: We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function f of $qge4$ alternatives and n voters will be manipulable with probability at least $10^{-4}ep{s}^2{n}^{-3}{q}^{-30}$, where $eps$ is the minimal statistical distance between f and the family of dictator functions. Our results extend those of FrKaNi:08, which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in BarthOrline:91, ConitzerS03b, ElkindL05, ProcacciaR06 and ConitzerS06) cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.

Recommendations

• scientific article; zbMATH DE number 5501205
• Minimally manipulable anonymous social choice functions
• Manipulability measures of common social choice functions
• Arrow and Gibbard--Satterthwaite revisited. Extended domains and shorter proofs
• A new informational base for social choice
• Dictatorship versus manipulability
• On asymptotic strategy-proofness of classical social choice rules
• Computational complexity of manipulation: a survey
• Strategy-proof voting schemes with continuous preferences

Cites work

• scientific article; zbMATH DE number 177833 (Why is no real title available?)
• Algorithms and Computation
• Almost all social choice rules are highly manipulable, but a few aren't
• Complexity of constructing solutions in the core based on synergies among coalitions
• Manipulation of Voting Schemes: A General Result
• Mixing times of lozenge tiling and card shuffling Markov chains
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(22)

• Trade-off between manipulability and dictatorial power: a proof of the Gibbard-Satterthwaite theorem
• Between Arrow and Gibbard-Satterthwaite. A representation theoretic approach
• Generalizing the Gibbard-Satterthwaite theorem: partial preferences, the degree of manipulation, and multi-valuedness
• Complexity of manipulation with partial information in voting
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• A quantitative Gobbard-Satterthwaite theorem without neutrality
• Probabilistic view of voting, paradoxes, and manipulation
• The probability of intransitivity in dice and close elections
• A law of large numbers for weighted plurality
• A phase transition in Arrow's theorem with three alternatives
• A new informational base for social choice
• Normalized range voting broadly resists control
• A geometric look at manipulation
• Minimally manipulable anonymous social choice functions
• The Manipulability of Voting Systems
• A quantitative Arrow theorem
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• A tight quantitative version of Arrow's impossibility theorem
• Permutation cycles and manipulation of choice functions
• On the likelihood of single-peaked preferences
• A weak version of Barberà-Kelly's theorem
• Taxonomy of powerful voters and manipulation in the framework of social choice functions

This page was built for publication: The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q452827)