Random Ballot Tiebreaker

[Blake Cretney]

--

On Tue, 25 Aug 1998 10:38:09   Norman Petry wrote:
>Blake,
>
>Thanks for the example.
>
>You're right -- you've shown that a random tiebreaker ballot _is_ better
>than random selection for achieving *perfect* clone independence.
>
>***
>
>Schulze's Method:
>
>The example shows an _extremely rare_ case where Schulze's proposed
>tiebreaker is insufficient.  Since all candidates are tied, the Schwartz set
>of the beat-path winners consists of all 3 candidates {A,B,C}, and no
>further reduction is possible, so his method is still indecisive.  Markus
>didn't specify a second tiebreaker for the beat-path method, probably
>because it would only be needed in situations like this where all candidates
>are tied.  With even a single majority beat-path in the matrix, I don't
>think the tiebreaker would ever be necessary.
>
>Provided there are no objections from voters to using a random ballot as the
>second tiebreaker (maybe it could be sold to them using a "lottery ticket"
>analogy), I guess it would be better, since it's a slight technical
>improvement.  Still, given the fact that the situation you describe is so
>improbable, just using a random selection would be just as good in
>practice -- for Schulze's method.
>
>***
>
>Tideman's Method:
>
>In Tideman's method, the random-ballot tiebreaker is more useful, since it
>not only solves the problem you demonstrated in your example, but is also
>needed to help determine the _order_ in which defeats should be
>locked/skipped.  When subsets of candidates are tied, it's not clear using
>Tideman's original method which of the tied defeats should be locked or
>skipped first.  Tideman noticed that if the processing order is arbitrary,
>it was possible to produce examples where Clone Independence was violated.
.. I've omitted the example

>random tiebreaker ballot is used to determine the processing order of the
>tied propositions, then Tideman claims that his method is completely
>clone-independent.
>
>Note that because Schulze is not a sequential method, when it is applied to
>this example, the winner is decisively C.  This is true with or without the
>presence of B', therefore no tiebreaker ballot is required to achieve clone
>independence.
>
>***
>
>Regarding the tiebreaker ballot, you earlier wrote:
>
>>The best way to resolve ties is for a chairman, president, or random voter
>to enter a special ballot.  This ballot must not be truncated.
>
>The way Tideman proposes handling this is to choose the ballot of a random
>voter, and use it to construct a special ballot (what he calls a "TBRC", or
>"Tie-Breaking Ranking of Candidates").  Since an ordinary ballot may contain
>ties, or be truncated (which is equivalent), the TBRC is constructed by
>randomly choosing the order within those subsets of candidates on the ballot
>which are tied, to produce a complete ranking with no ties.
>
>I prefer this method to having a particular voter (president, etc.) prepare
>the tiebreaker, as it satisfies the Anonymity criterion.
>
I may not understand Tideman's suggestion, but it sounds as if it still violates GITC.
{A,B,C} are clones

{A,B,C} > D 1
{A,B,C} > F 2
D > E 1
D > F 3
E > {A,B,C} 1
E > F 4
A > B 1
B > C 1
C > A 1

So, all those F defeats are locked, and a tie develops. 
Someone reaches into the ballot box and pulls out a ballot marked, you guessed it, F.  All other candidates are unranked.  Anyway, if we decide the rest randomly, A,B,C,D and E have an equal chance of winning over all, but of course, because {A,B,C} are clones, they should have an equal chance all together to D and E.
I don't know if Schultz has the same problem in this example, but I suspect an example could be contrived for Schultz too.

This method might work, maybe it's what Tideman intended:
1.  Pick a random ballot and use its rankings, consider ties as unsorted with regard to each other.
2.  Continue picking ballots.  When you find one that orders previously unsorted candidates, use the ballot to sort them.  Do not change the order of the already sorted.
3.  If you go through all ballots, and some candidates are still not sorted, order them randomly.

This should be done at the same time as the ballots are counted to form the matrix.

I would explain this method by saying that it is very important that each voter can vote sincerely, as if he or she was the only person voting.  It is a natural tie-breaker, therefore, to select a single ballot and go by that person's preference.

I should point out that for the reasons stated in my previous posting, some sort of tie-breaker will be necessary in ANY pair-wise method to meet the GITC criterion.  In other words, no purely pair-wise method can meet the GITC criterion, and some addition, like my proposed tie-breaker, must be added that keeps it from being purely pair-wise.

Just how likely a tie is to happen depends on where the method is used.  In a public election, it may never happen.  In a Congressional vote it may very well happen.  On a small city council it might happen from time to time.  I do not think that EM should constrain itself to thinking of Condorcet only in public elections, but also as a parliamentary reform.


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