Random Ballot Tiebreaker

[Markus Schulze]

Dear Blake,

you wrote (26 Aug 1998):
> I wonder if you're algorithm will really give results
> that are less random.  I'll give you an example of
> what I mean.
>
> A > B 60
> B > C 60
> C > A 60
>
> My random ballot method will directly select one of
> these candidates.  Your method will sometimes do this,
> but sometimes eliminate one of the candidates and
> rerun the algorithm instead.  In abstract, it seems
> less random to do it this way; in the above example it
> clearly isn't less random.  Can you give an example
> where it would be?

It is difficult to give an example, because I wasn't
talking about a certain tiebreaker that needs an
additional random tiebreaker. I was talking about what
should be done _in principle_ when a given deterministic
tiebreaker doesn't lead to a unique winner but to a set
of potential winners.

Example (25 Aug 1998):

   {A,B,C} > D 1
   D > E 1
   E > {A,B,C} 1
   A > B 1
   B > C 1
   C > A 1

As far as I have understood you correctly, you would
choose a random ballot. I would do that, too.
Suppose, that this random ballot ranks the candidates
as follows: A=B=C=E>D.

Your method: As this random ballot doesn't lead to a
unique ranking, you would choose another random ballot.
When you find one that orders previously unsorted
candidates, you use the ballot to sort them without
changing the order of the already sorted.
You would proceed until you have either a unique ranking
or considered the ranking of every voter. If you go
through all ballots, and some candidates are still not
sorted, you order them randomly. Then the winner is
that candidate, who is top ranked in this ranking.

My method: As I have already chosen a random ballot,
that ranks the candidates A=B=C=E>D, I have already
decided that (independently on how the later random
ballots rank the candidates) the winner must be
either A or B or C or E. So there is -to my opinion-
no need for a second random ballot. I can simply
restart the whole algorithm with A, B, C, and E.
Thus, I get:

   E > {A,B,C} 1
   A > B 1
   B > C 1
   C > A 1 

Thus, candidate E wins.

Of course, both random tiebreakers are random. But your
tiebreaker has to make random decisions more frequently.

*****

You wrote (26 Aug 1998):
> This provides you with a fully ranked tie-breaker
> ballot. The simplest way to use this is every time
> you run into a tie during your decision procedure,
> you go to this ballot to resolve it.

I don't understand this paragraph. Could you -please-
explain it! Suppose, that you successively ignore the
weakest defeat in the matrix of pairwise defeats.
Suppose, that you reach a situation with two equal
defeats, e.g. A defeats B with a surplus of 30 votes
and C defeats D with a surplus of 30 votes. Suppose,
your randomly created ballot ranks D > B > C > A. How
does this randomly created ballot help you solve this
situation?

Markus Schulze