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)

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

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)