Random Ballot Tiebreaker

[Norman Petry]

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.
Tideman gave this example:

Candidates: {A,B,B',C,D,E,F}

Clones: {B,B'}

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

If this is processed as:

lock A>D 3; (A>D)
lock B>D 3; (A>D, B>D)
lock C>D 3; (A>D, B>D, C>D)
lock D>E 3; (A>D>E, B>D>E, C>D>E)
skip E>B 3;
lock E>B' 3; (A>D>E>B', B>D>E>B', C>D>E>B')
lock B'>F 3; (A>D>E>B'>F, B>D>E>B'>F, C>D>E>B'>F)
lock B>F 3; (A>D>E>B'>F, B>D>E>B'>F, C>D>E>B'>F)
skip F>A 3; (A>D>E>B'>F, B>D>E>B'>F, C>D>E>B'>F)
lock A>B 1; (A>B>D>E>B'>F, C>D>E>B'>F)
lock B>C 1; (A>B>C>D>E>B'>F)
skip (all others)

Final Ranking: A>B>C>D>E>B'>F
Winner: A

If the clone B' is removed from the above example, then C wins, therefore
Tideman's original method is not fully clone-independent.  However, if a
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.



Norm Petry


-----Original Message-----
From: Blake Cretney <bcretney at my-dejanews.com>
To: election-methods-list at eskimo.com <election-methods-list at eskimo.com>
Date: August 24, 1998 8:50 PM
Subject: Re: Goldfish (single-winner method)


>
>--
>
>On Sun, 23 Aug 1998 18:08:29   Norman Petry wrote:
>
>>As far as I know, the only decisive, pairwise methods which fully satisfy
>>GITC are: (1) Schulze's method, and (2) Tideman's _improved_ method, which
>>uses a tiebreaker ballot, probably in the manner you describe (see
"Complete
>>Independence of Clones in the Ranked Pairs Rule", Soc Choice Welfare
(1989)
>>6:167-173).  Schulze's method seems to be better in this respect, since a
>>special tiebreaker isn't required under any circumstances we've yet
>>discovered.  This seems to me to be a definite advantage of Schulze, since
>>adding special tiebreaker-ballot rules to other methods increases
>>complexity, and may be unintuitive to voters.  At first glance, it might
>>seem unfair to allow one particular voter to affect the election outcome.
>>If you've discovered any GITC violations for Schulze that we don't know
>>about, I'd be interested in seeing them!
>
>Here is my argument for why any pair-wise method, even if it uses a random
selection procedure between some alternatives will fail GITC unless
augmented somehow.
>
>Balloting 1:  No clones
>1 A B
>2 A B
>3 A B
>4 B A
>5 B A
>6 B A
>  A  B
>A X  3
>B 3  X
>So, based only on the matrix, a random tie-breaker would give
>P(A)=.5 P(B)=.5
>
>Balloting 2:  B has a clone named C
>
>1 A C B
>2 A C B
>3 A B C - C cannot be a clone of A
>4 C B A
>5 B C A
>6 B C A
>
>  A B C
>A X 3 3
>B 3 X 3
>C 3 3 X
>
>Judging by this matrix we would have to give
>A B and C equal chance P(A) = 1/3 P(B)=1/3 P(C)=1/3
>but to avoid rich party P(A) = P(B)+P(C)
>
>That is, the pair-wise matrix does not provide enough information to avoid
GITC in this case.
>
>So, any pair-wise system will have to be augmented with something, like a
tie-breaker ballot, in order to avoid GITC, although perhaps only in very
rare circumstances.
>
>
>-----== Sent via Deja News, The Discussion Network ==-----
>http://www.dejanews.com/  Easy access to 50,000+ discussion forums
>