The Manipulability of Voting Systems

(i)     Neither election results in a tie.
(ii)    The only ballot change is by Bob.
(iii)   Bob prefers the outcome of the second election to that of the first.

honest election:
 

Voter 1                  Voter 2

A	B
B	C
C	A
D	D

Borda Scores: A - 4, B - 5, C - 3, D - 0

manipulated election:
 

Voter 1                  Voter 2

A	B
C	C
D	A
B	D

Borda Scores: A - 4, B - 3, C - 3, D - 1

May's Theorem for Manipulability
Among all two-candidate voting systems that never result in a tie, majority rule is the only one that treats all voters equally, treats both candidates equally and is nonmanipulable.

Proofidea: If Bob already ranks A over B, he cannot demote B further. He can only raise B (his choice was for A to win). Monotonicity is equivalent to nonmanipulability here.

Theorem: Nonmanipulability of Condorcet's Method
A single voter cannot unilaterally change an election result from one candidate to another candidate that he/she prefers.
(However it is possible that a voter can singlehandedly change an election with a Condorcet winner to an election without a Condorcet winner.)

Bob wants A to win.

 

Honest Election

First	A	B	C
Second	C	C	A
Third	B	A	B
	Bob	1	1

C : A = 2 : 1, C : B = 2 : 1.
 

Manipulated Election

First	A	B	C
Second	B	C	A
Third	C	A	B
	Bob	1	1

no Condorcet winner. Any other configuration on Bob's ballot would place A lower and thus would not improve the chances of A to win.

Proof: Bob wants A to win over B. However B is the Borda winner. Three cases for Bob's honest vote:
Case A B C: switch to A C B - could result in A B tie, but not A win.
Case C A B: cannot lower B's Borda count.
                     switch to A C B -  could result in A B tie, but not A win.
Case A C B: cannot lower B's Borda count, cannot raise A's Borda count.

Theorem: Manipulability of Borda Count with 4 or more Candidates
There exists an election where a single voter can unilaterally change the result from one candidate to another candidate that he/she prefers.

Proof: Need an even number of voters.
Basic ballot situation like in first example.

1.    any additional candidates are placed below A, B, C, D.
2.    add an even number of voters: they are paired up A B C D E - E D C B A, so that their Borda counts cancel out.

Then the "extended" first example demonstrates the general manipulability of the Borda Count.
 

Theorem: Manipulability of Simple Runoff Voting
There exists an election where a single voter can unilaterally change the result from one candidate to another candidate that he/she prefers.

Proof:

 

Honest Election

First	A	A	C	C	B
Second	B	B	A	A	C
Third	C	C	B	B	A
	Bob	1	1	1	1

runoff between A and C. But C : A = 3 : 2.

 

Manipulated Election

First	B	A	C	C	B
Second	A	B	A	A	C
Third	C	C	B	B	A
	Bob	1	1	1	1

runoff between B and C. But B : C = 3 : 2.

 

Honest Election

First	A	B	C	D
Second	B	A	B	B
Third	C	C	A	C
Fourth	D	D	D	A
	Bob	1	2	1

drop A, B, D in first round and C wins.
 

Manipulated Election

First	B	B	C	D
Second	A	A	B	B
Third	C	C	A	C
Fourth	D	D	D	A
	Bob	1	2	1

drop A in first round, D in second round, then B : C = 3 : 2.

Theorem: The group manipulability of Plurality Voting
Plurality voting cannot be manipulated by a single individual. However it is group manipulable.

Example: any real world election in which a third-party candidate acted as a "spoiler", e.g. in the 2000 election with candidates Bush, Gore and Nader.

Gibbard Satterthwaite Theorem
With three or more candidates and any number of voters, there does not exist a voting system that

• always produces a winner
• never ties
• satisfies the Pareto condition
• is nonmanipulable
• is not a dictatorship

Weak Version:
Any voting system for three candidates that agrees with Condorcet's method whenever there is a Condorcet winner - and that additionally produces a unique winner when confronted by the ballots in the Condorcet voting paradox - is manipulable.

Proof:
Honest Election:
 

First	A	B	C
Second	B	C	A
Third	C	A	B
	Bob	1	1

 
Say C wins, but Bob prefers A and B over C. We already saw that any switch between B and C will not affect the election Condorcet outcome.
Manipulated election:
 

First	B	B	C
Second	A	C	A
Third	C	A	B
	Bob	1	1

Condorcet will result in B being the winner. Not optimal from Bob's perspective but better than C. In this sense Condorcet can be manipulated.
Now suppose B is the winner of the original election.
Thus with every election outcome, there is one particular voter, who is able to manipulate the election outcome by enhancing the chances of his/her second choice.