Arrow and Gibbard-Satterthwaite

[Markus Schulze]

Dear Steve,

I said, that Arrow's theorem cannot be used in its original
version, because some of the election methods, which were
discussed in the election methods list, fail to meet Pareto.
In this e-mail, I will present two examples.

[By the way, I also mentioned, that Arrow supposed, that
the method is deterministic and regards only relative
preferences. (That means: They don't consider absolute
preferences or the strength of preferences.) Some of the
election methods, which were discussed in the election
methods list, also fail to meet these suppositions.]

Smith//Random fails to meet Pareto.

Example:

   40 voters vote ABCD.
   35 voters vote CDAB.
   25 voters vote DABC.

   A:B=100:0
   A:C=65:35
   A:D=40:60
   B:C=65:35
   B:D=40:60
   C:D=75:25

   The Smith set consists of A, B, C, and D, because
   A > B > C > D > A.

   Thus, B is elected with a probability of 25%, although
   every voter prefers A to B.

Smith//Condorcet[EM] with the subcycle rule fails
to meet Pareto.

Example:

   25 voters vote BCDFEA.
   24 voters vote CDFEAB.
   20 voters vote ABFECD.
   15 voters vote EABCDF.
   8 voters vote EBCADF.
   4 voters vote ECADBF.
   4 voters vote ECABDF.

   A:B=67:33
   A:C=35:65
   A:D=51:49
   A:E=20:80
   A:F=51:49
   B:C=68:32
   B:D=72:28
   B:E=45:55
   B:F=76:24
   C:D=100:0
   C:E=49:51
   C:F=80:20
   D:E=49:51
   D:F=80:20
   E:F=31:69

   The Smith set consists of A, B, C, D, E, and F
   because A > B > C > D > F > E > A.

   Step 1:

   A, B, and C are a subcycle of the Smith set because
   A > B > C > A is a cycle and because

   A > D,
   B > D,
   C > D,

   E > A,
   E > B,
   E > C,

   A > F,
   B > F,
   C > F.

   Thus, we use the Condorcet[EM] tie breaker to
   solve the subcycle:

   A:B=67:33
   A:C=35:65
   B:C=68:32

   The winner of the Condorcet[EM] tie breaker
   of the subcycle is A.

   Step 2:

   Now, we eliminate all of the candidates of the subcycle,
   except for the winner of the Condorcet[EM] tie breaker
   of the subcycle.

   A:D=51:49
   A:E=20:80
   A:F=51:49
   D:E=49:51
   D:F=80:20
   E:F=31:69

   The winner of the Condorcet[EM] tie breaker is D.

   Thus: D wins although every voter prefers C to D.

I hope, I haven't made any typing errors.

I don't want to criticize Smith//Condorcet[EM] with the
subcycle rule. In the election methods list, it has never
been said, that Pareto is important.

Even Smith//Random, which fails to meet Pareto very obviously,
has never been criticized for that.

I only want to show, that even a method, that meets the
Condorcet Criterion, the Smith Criterion, GMC, ITC, and LO2E,
doesn't necessarily meet Pareto.

Thus: Arrow's theorem in its original version, which says,
that every method, that meets Pareto and some other suppositions,
fails to meet IIAC, has a dubious relevance.

Thus: To have a constructive discussion, we have to investigate,
whether there are other criteria such that, if a method
meets these criteria, it fails to meet IIAC.

In my e-mail "Arrow and Gibbard-Satterthwaite", I demonstrated,
that every method, that meets PMC, fails to meet IIAC.
A method meets PMC if & only if:

  If there are only two candidates, then that candidate is
  elected, who is prefered by more voters.

This version of the impossibility theorem shows, that
the failure to meet IIAC is a problem of every method,
that meets majority rule. The failure to meet IIAC is not
a problem only of preferential election methods.

My version of the impossibility theorem shows the price,
you have to pay to get IIAC. And as I believe, that only
few people will want to pay that price, I demonstrated,
that the failure to meet IIAC cannot be used to argue
against preferential election methods.

Markus Schulze (schulze at sol.physik.tu-berlin.de)