[EM] Ties (was Condorcet Voting)

[Markus Schulze]

Dear Alex,

you wrote (7 Jan 2003):
> Markus Schulze wrote (7 Jan 2003):
> > However, consider the following example:
> >
> >    40 voters vote A > B > C > D > E.
> >    40 voters vote B > C > D > A > E.
> >    40 voters vote C > A > D > E > B.
> >
> > Although this is not a symmetric situation, the used election
> > method must violate Neutrality or Anonymity or Decisiveness or
> > Local Independence from Irrelevant Alternatives in this example.
>
> I'm not sure I see why.  And what is the local version of
> Independence from Irrelevant Alternatives?

The "Smith set" is the smallest set of candidates such that for
each candidate A in this set and for each candidate B outside
this set the number of voters who strictly prefer candidate A
to candidate B is strictly larger than the number of voters who
strictly prefer candidate B to candidate A. "Local Independence
from Irrelevant Alternatives" says that adding a candidate who
doesn't get in the Smith set must not change the result of the
elections.

In the example above, candidate D and candidate E are not in the
Smith set. Therefore, they must not change the result of the
elections. However, when we ignore candidate D and candidate E
we get:

    40 voters vote A > B > C.
    40 voters vote B > C > A.
    40 voters vote C > A > B.

Now, every anonymous neutral election method is necessarily
indecisive. Therefore, every anonymous neutral election method
that meets Local Independence from Irrelevant Alternatives
is necessarily indecisive in the original example.

******

Here is another scenario:

    40 voters vote A > B > C > D > E.
    40 voters vote B > D > E > C > A.
    40 voters vote E > C > D > A > B.

This is not a symmetric situation. (E.g.: The Copeland method
chooses candidate B decisively. The Borda method chooses
candidate B decisively.)

The candidates C, D, and E are a set of clones. Therefore,
Independence from Clones says that when the candidates C, D, and
E are substituted by a single macro-candidate F then for each
candidate X outside this set of clones the probability that
candidate X is elected must not change. Therefore, we get:

    40 voters vote A > B > F.
    40 voters vote B > F > A.
    40 voters vote F > A > B.

Now, every anonymous neutral election method is necessarily
indecisive. Therefore, every anonymous neutral election method
that meets Independence from Clones is necessarily indecisive
in the original example.

Markus Schulze

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em