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

DOI10.1007/S00493-012-2704-1zbMATH Open1265.05015arXiv0911.0517OpenAlexW2177286302MaRDI QIDQ452827FDOQ452827

Authors: Marcus Isaksson, Guy Kindler, Elchanan Mossel 

Publication date: 17 September 2012

Published in: Combinatorica (Search for Journal in Brave)

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.

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

Recommendations

• scientific article
• 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

zbMATH Keywords

voting systemsocial choice functionmanipulabilitydictator

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (22)

• 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
• Taxonomy of powerful voters and manipulation in the framework of social choice functions
• A law of large numbers for weighted plurality
• A weak version of Barberà-Kelly's theorem
• The probability of intransitivity in dice and close elections
• 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
• A quantitative Arrow theorem

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)