Arrow and Gibbard-Satterthwaite

[schulze at sol.physik.tu-berlin.de]

Definition ("Pareto"):

   A method meets Pareto if & only if:
   An alternative B must not be elected, if there
   is an alternative A such that every voter
   prefers A to B.

Definition ("Smith//Random"):

   The winner is chosen randomly from the members 
   of the Smith set. Each member of the Smith set
   is chosen with the same probability.

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.

Thus: A method, that meets the Condorcet Criterion
or the Smith Criterion, doesn't necessarily meet Pareto.

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