Random Ballot Tiebreaker

[Blake Cretney]

--

On Fri, 28 Aug 1998 13:15:26   Markus Schulze wrote:
>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.

You have understood me.

>
>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.
>
I suggest that the way to judge the randomness of a method should
be by outcome.  If given a certain example, method X has
5 possible outcomes, while method Y has only 3, I would conclude that
in that case at least, X has behaved more randomly.

The example you provide does not show this.  You will find that if you
eliminate D, E will be the winner.  If you eliminate E, one of A, B,
or C will be chosen randomly.  If you eliminate A, then B, then C, the
result will be D.  So all results are possible, just as in my method.




>*****
>
>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?
>
The lowest ranked pair-wise winner should have its
victory dropped.  Alternately, the highest ranked
pair-wise loser could have its loss dropped.  You
would have to specify one of these ways ahead of
time.  I suspect they are equally valid.

>Markus Schulze
>
>
>


-----== Sent via Deja News, The Discussion Network ==-----
http://www.dejanews.com/  Easy access to 50,000+ discussion forums