Arrow, Gibbard, and Satterthwaite
Markus Schulze
schulze at speedy.physik.TU-Berlin.DE
Tue Aug 12 08:39:33 PDT 1997
In the last months, there was a discussion about Arrow's theorem.
It was discussed, which voting methods fail to meet Arrow's IIAC
and Gibbard's and Satterthwaite's Non-Manipulability Criterion.
The answer is, that almost all voting methods (e.g. Condorcet
Criterion methods, Borda methods, Approval voting, methods with
additional ballotings) fail to meet Arrow's IIAC or Gibbard's
and Satterthwaite's Non-Manipulability Criterion.
Only dictatorial methods (where one voter always gets
his way) and random methods (where the probability of being
elected is proportional to the number of votes) can
meet IIAC and Gibbard-Satterthwaite.
*********************************************************
Majority criterion:
Suppose, there is a candidate, who is prefered to every
other candidate by a majority of the voters. In other words:
Suppose, there is a candidate, who gets an unshared majority
of all votes resp. first preferences.
Then: A voting method meets the "Majority
Criterion" if & only if this candidate wins.
Pairwise Majority Criterion:
Suppose, there are only two candidates X and Y.
Suppose, a majority of the voters prefer X to Y.
Then: A voting method meets the "Pairwise Majority
Criterion" (PMC) if & only if X wins.
Remark:
Every method, that meets the Majority Criterion,
also meets PMC.
*************************************************************
A method, that meets PMC, always fails to meet Arrow's IIAC.
Proof:
Suppose, there is a tie between the
candidates A, B, and C. (A>B>C>A)
Suppose, the used method meets PMC.
Case 1: Suppose, A is elected. Then candidate B changes the
result of the elections without being elected, because:
If B hadn't run, then C would have been elected, because
the method meets PMC.
Case 2: Suppose, B is elected. Then candidate C changes the
result of the elections without being elected, because:
If C hadn't run, then A would have been elected, because
the method meets PMC.
Case 3: Suppose, C is elected. Then candidate A changes the
result of the elections without being elected, because:
If A hadn't run, then B would have been elected, because
the method meets PMC.
Thus: If there is a tie, then independently on who is elected
[that means: independently on which tie breaker is used]
there is always a candidate, who changes the result of the
elections without being elected.
Remarks:
My only supposition is, that the method meets PMC.
When I wrote, that there is a tie between A, B, and C,
I didn't suppose that there is a tie due to the votes.
I only supposed that there is a tie due to the opinions
of the voters. Thus, I didn't have to suppose, that
a ranking method is used.
The incompatibility between PMC and IIAC is also true for
every other method (e.g. Approval voting, methods with
additional ballotings). Even Borda methods fail to meet IIAC,
because (although Borda methods don't meet the Majority
criterion) even Borda methods meet PMC.
**************************************************************
Arrow used different criteria (Pareto, Non-Dictatorial,
etc.), because he wanted to have more general results and
because "social choice functions" don't necessarily meet PMC.
************************************************************
To prove the incompatibility between PMC and
Gibbard's and Satterthwaite's Non-Manipulability Criterion,
you only need Arrow. As no voting method (that meets PMC)
meets IIAC, Gibbard and Satterhwaite just proposed:
Suppose, a majority of the voters prefer proposal A to B.
Suppose, the commitee proposes another proposal C, so that
A > B > C > A and B would win, if all the voters vote
sincerely.
[Due to Arrow, it is possible to propose another proposal C,
which changes the result of the elections without being
chosen.]
Then Gibbard and Satterthwaite say: Those voters,
who prefer A to B, should simply ignore proposal C and give
proposal C the worst preference. Then the supporters of
proposal A get an advantage by voting insincerely.
Remark:
Again, I want to mention, that the incompatibility between
PMC and Gibbard's and Satterthwaite's Non-Manipulability
Criterion is valid for each method (e.g. Borda methods,
Approval voting, methods with additional ballotings).
Markus Schulze (schulze at speedy.physik.tu-berlin.de)
More information about the Election-Methods
mailing list