A quantitative Gibbard-Satterthwaite theorem without neutrality

Details A quantitative Gibbard-Satterthwaite theorem without neutrality A quantitative Gibbard-Satterthwaite theorem without neutrality

2011-10-26

arxiv.org/abs/1110.5888v2

Mathematics

Combinatorics

46 pages; v2 has minor structural changes and adds open problems

Scientific paper

Recently, quantitative versions of the Gibbard-Satterthwaite theorem were proven for $k=3$ alternatives by Friedgut, Kalai, Keller and Nisan and for neutral functions on $k \geq 4$ alternatives by Isaksson, Kindler and Mossel. We prove a quantitative version of the Gibbard-Satterthwaite theorem for general social choice functions for any number $k \geq 3$ of alternatives. In particular we show that for a social choice function $f$ on $k \geq 3$ alternatives and $n$ voters, which is $\epsilon$-far from the family of nonmanipulable functions, a uniformly chosen voter profile is manipulable with probability at least inverse polynomial in $n$, $k$, and $\epsilon^{-1}$. Removing the neutrality assumption of previous theorems is important for multiple reasons. For one, it is known that there is a conflict between anonymity and neutrality, and since most common voting rules are anonymous, they cannot always be neutral. Second, virtual elections are used in many applications in artificial intelligence, where there are often restrictions on the outcome of the election, and so neutrality is not a natural assumption in these situations. Ours is a unified proof which in particular covers all previous cases established before. The proof crucially uses reverse hypercontractivity in addition to several ideas from the two previous proofs. Much of the work is devoted to understanding functions of a single voter, and in particular we also prove a quantitative Gibbard-Satterthwaite theorem for one voter.

Affiliated with

Also associated with

No associations

Rating

A quantitative Gibbard-Satterthwaite theorem without neutrality 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 A quantitative Gibbard-Satterthwaite theorem without neutrality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A quantitative Gibbard-Satterthwaite theorem without neutrality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718026