Random Ballot Tiebreaker

[Norman Petry]

Blake,

You wrote:

>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.

In this example, there will be no ballot marked F, since F beats nothing, so
the first problem you identified would not occur.  This is a quibble,
however, since you could construct a similar example with majority
votes-against beat-paths of 2, rather than 1 (bump up all the numbers in the
above example) to produce the possibility of a ballot with F beats-all
equally (A..E truncated).  Still, F cannot win in this case under either
Tideman's or Schulze's rules, since F's defeat has been locked in by
Tideman, and Schulze's method would use the Smith set to eliminate F from
contention before even computing beat-path defeats.  Therefore, once F has
been discounted, this example reduces to a larger version of the one you
presented earlier, in which all candidates are tied (in the pairwise
matrix).

>I don't know if Schultz has the same problem in this example, but I suspect
an example could be contrived for Schultz too.

Yes, Schulze's method has the same problem here -- aside from F, all of the
beat-path defeats are 1, so the Schwartz set consists of {A..E}, and this
cannot be further reduced without using an additional tiebreaker.

>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 is an interesting idea, but definitely not what Tideman intended.  He
wrote:

"In this paper we introduce a way of breaking ties under the ranked pairs
rule, using the ranking of one voter (the tie-breaker).  If the tie-breaker
submits a ranking of the candidates that includes some ties, then a random
process is used to resolve these, so that a complete ranking is
produced." -- Tideman, "Complete Independence of Clones", p. 170


The reason Tideman's method never requires more than one ballot, even when
that ballot contains tied rankings, has to do with the definition of clone
sets.  Tideman's definition is:

"A proper subset of two or more candidates, S, is a set of clones if no
voter ranks any candidate outside of S as either tied with any element of S
or between any two elements of S." -- Tideman, "Independence of Clones", p.
186.


Therefore, if the tiebreaker ballot contains one or more subsets of
candidates that are tied, then either (a) all of the candidates in each
subset are members of a clone set, or (b) none of the candidates in each
subset are members of a clone set.  Therefore randomly ordering each tied
subset will still satisfy GITC.  For example, if a voter had ranked
E>{A,B,C,D}>F, in your example above, then either D is also a clone of
{A,B,C}, or {A,B,C} are _not_ clones.  Therefore choosing a random order for
{A,B,C,D} in preparing a TBRC is ok.

The problem is more complicated when truncation is allowed.  In your
example, if the randomly drawn tiebreaker ballot showed only F, then this
could be interpreted as: F>{A,B,C,D,E}, in which case picking any of {A..E}
with equal probability *does* satisfy GITC, since either {D,E} must also be
clones of {A,B,C} or {A,B,C} is not a clone subset, by definition, since D
and E are effectively _tied_ on this voter's ballot with the clones.  Since
this is how we interpret truncated ballots for the purposes of counting
votes, this seems reasonable for breaking ties as well.


It's also arguable though, that this voter doesn't necessarily consider
{A..E} to be equally bad, merely all inferior to his favourite, F.  In that
case, using additional randomly selected ballots to "fill in" the TBRC for
unranked candidates might be a good idea.  It's never necessary to use the
additional ballots to rank explicitly tied candidates, though, for reasons
given above (it probably wouldn't do any harm either, although GITC is
satisfied without it.)

***

You also wrote:

> [...]  I do not think that EM should constrain itself to thinking of
Condorcet only in public elections, but also as a parliamentary reform.

Absolutely.  Personally, I think the _best_ application of improved
single-winner methods is as a means of choosing policies, rather than
choosing "leaders".  I believe that public policy should be set by
representative _groups_ of people, rather than single individuals, using a
single-winner method that ensures that the policies are supported by a
genuine majority of voters.


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 25, 1998 2:33 PM
Subject: Re: Random Ballot Tiebreaker

[...]
>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
>