The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem

Details The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem

2009-11-03

arxiv.org/abs/0911.0517v4

Mathematics

Combinatorics

Scientific paper

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 $q \ge 4$ alternatives and n voters will be manipulable with probability at least $10^{-4} \eps^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.

Affiliated with

Also associated with

No associations

Rating

The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256288