Arrow, Gibbard, and Satterthwaite

[Markus Schulze]

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)