Elections can be Manipulated Often

Today I will talk about the paper by Firedgut Kalai and Nisan titled "Elections can be Manipulated Often".

The Gibbard-Satterhwaite (GS) theorem states any non-dictatorial social choice function (SCF)/ voting procedure is manipulable. The one of the approach to circumvent this problem is to use voting procedure that are difficult to manipulate though not impossible. That is manipulation in the SCF is NP-Complete. However, notion of NP-completeness relies on worst case complexity. It may be hard to manipulate at some type profiles but easy on other.

In this paper, authors show that when there are 3 alternatives, any random manipulation can be beneficial with non-negligible probability. Let M_i(f) be the the probability that a random manipulation is profitable for an agent i. The main theorem of the paper is:

For every \epsilon > 0, if f is \epsilon-far from dictatorship, there exists constant C such that \sum_{i=1}^n M_i(f) >= C\epsilon^2 .

That means, if f is away from dictatorship, there is some agent who has non-negligible manipulation power. Also one cannot give bound independent of n. The proof is in three steps.

First step:
As social welfare function, F is neutral, it can be determined using a single boolean function. Now, if this boolean function is epsilon away from dictatorship, then there is delta probability that F does not have condorect winner. (delta = C*epsilon)

Second step:
They define notion of manipulation by many voters. (M^{a,b}(f) ) and if this quantity is low, then we can construct IIA SWF that is very close to Condorcet winner and due to step one, f will be very close to dictatorship. That is if f is away from dictatorship, M^{a,b}(f) is also reasonably high.

Third Step:
Authors show that, M^{a,b}(f) <= 6 \sum_i M_i(f). All these three steps together imply the theorem in the paper. Its quite interesting result as well the results cited therein. For the paper: http://www.cs.huji.ac.il/~noam/apx-gs.pdf



---
Sujit Gujar
Research Student,
Indian Institute of Science, Bangalore.