Tie-breakers

[Lowell Bruce Anderson]

Before I make a recommendation on tie-breakers, I want to repeat (and 
update) relevant aspects of my notation.

BACKGROUND

I am currently working on an "e-mailable" dictionary of single-winner, 
ranked-ballot voting methods, which I hope to send to the EM list when (& 
if) I finish.  The following is an extract from a partial draft that 
dictionary.

[[START OF EXTRACT
A Deterministic Uniform Single-winner Ranked-ballot Voting Method (DUSRVM) 
is defined here to be a rule (i.e., a function) that, given a finite set of 
candidates and a finite set of voter's ballots ranking those candidates, 
determines a non-empty subset of those candidates as being the possible 
winners of the vote being taken.  If this subset consists of a single 
candidate, then that candidate is the single winner.  If this subset 
consists of two or more candidates, then some method must be used to break 
this "tie" in order to determine the single winner.

One way to break such a tie is to randomly (i.e., uniformly) pick the winner 
from among the "tied" candidates.  Recognizing this, a Uniform Single-winner 
Ranked-ballot Voting Method (USRVM) is defined here to be either a DUSRVM or 
a DUSRVM with the addition that, if the DUSRVM results in two or more 
candidates remaining under consideration, then one of those candidates is 
picked as the single winner according to a uniform distribution over those 
remaining candidates.  Sometimes this is the only "inherent" way to break 
such ties.  For example, this is the case when there are two candidates, an 
even number of voters, and exactly half of those voters prefer each 
candidate over the other.

However, employing a random pick to break ties here can be considered as 
being a method of last resort.  It will always work, but it is not always 
needed.  Before resorting to a random pick, a "second" (not necessarily 
distinct) DUSRVM, along with the original set of voter's ballots but now 
restricted to the set of possible winners from the "first" DUSRVM, could be 
used either to break the tie or to reduce the number of tied candidates.  
Then, a "third" DUSRVM could be applied, and so on, with the random pick 
always being available when a particular sequence of DUSRVMs applied to a 
particular set of voter's ballots does not result in a single winner.  Since 
the original ballots are reused, each voter would only need to "go to the 
polls" once, to cast one ballot, in order to elect the (single) winner this 
way.  There are many different DUSRVMs that could be used, either initially 
or to break ties.  Some of the notation needed to describe how various 
DUSRVMs work is presented below.  Part 2[NOT INCLUDED HERE] then describes 
many common DUSRVMs (and some not-so-common ones) using this notation.

In contrast to DUSRVMs and their corresponding USRVMs, an Individual Single-
winner Ranked-ballot Voting Method (ISRVM) is defined here to be a rule 
(i.e., a function) that, given a finite set of candidates and a finite set 
of voter's ballots ranking those candidates, determines a probability 
distribution over those candidates, where this probability distribution has 
the property that it is not necessarily uniform over some subset of the 
candidates and zero outside of that subset.  The single winner is then 
picked according to this probability distribution.  Note that uniform 
distributions are allowed here; they're just not required.  In particular, 
an ISRVM can (and frequently does) result in a "degenerate" probability 
distribution that assigns probability 1 to a single candidate, and 
probability 0 to all others.  In that case, of course, that candidate is the 
single winner of the vote being taken, and no "random pick" is required.  
Part 3[NOT INCLUDED HERE] describes several ISRVMs (including commonly known 
ones) using the notation below[NOT INCLUDED HERE].

A Single-winner Ranked-ballot Voting Method (SRVM) is defined here to be 
either a USRVM or an ISRVM.

For any SRVM, voters are assumed to cast the following type of ballot.  Each 
voter casts a ballot by ranking (1st, 2nd, 3rd, etc.) as many of the 
candidates as he or she wishes, with ties allowed anywhere in this ranking
END OF EXTRACT]]

Four relevant DUSRVMs here are defined as follows.

For any two distinct candidates, say i and j, let p(i,j) be the number of 
voters who rank i ahead of j, and say that "i pairwise beats j" if:
p(i,j) > p(j,i).

Condorcet-M:  
For any candidate i, let
M(i) = 0  if p(i,j) >= p(j,i) for all other candidates j, and
M(i) = maximum of p(j,i) over those j for which p(j,i) > p(i,j)  otherwise.
Then Condorcet-M selects the candidate(s) with the minimum value of M(i).

Plurality:  selects the candidate(s) with largest number of first-place 
votes.  If two or more candidates are tied with the largest number of first-
place votes, then Plurality (by itself) does not attempt to break this tie.

Plurality-ext:  selects the candidate(s) with largest number of first-place 
votes, with ties broken by the largest number of second-place votes, and so 
on.

Smith:  A candidate is a Smith winner if it belongs to the smallest non-
empty set of candidates such that each candidate in that set pairwise beats 
each candidate not in that set.

If M1 and M2 are two (not necessarily distinct) DUSRVMs, define M1//M2 to be 
the DUSRVM that applies M2 to the set of winners according to M1 by 
restricting the rankings expressed on the voter's (original) ballots to that 
set of M1-winners.  For example, suppose that there were 6 candidates, say 
A, B, C, D, E, and F, before M1 was applied, that A, B, and C were the 
(tied) winners according to M1, and that a certain voter had voted:  
F>A=E>D>B=C.  Then the vote using M2 would consider (only) candidates A, B, 
and C, and that voter would be counted as having voted:  A>B=C.
Note that, if M1, M2, and M3 are three (not necessarily distinct) DUSRVMs,  
then M1//(M2//M3) is the same as (M1//M2)//M3, and so M1//M2//M3 is a 
uniquely defined DUSRVM.

If M is a DUSRVM, define [M] to be the DUSRVM given by:
[M] = M//M//...//M,
where //...//M means to continue to apply M until further applications of M 
produce no further changes.  Given a finite number of candidates, this 
process must converge in a finite number of steps.

Clearly, for any DUSRVM M, [[M]] = [M].  Also, [M] = M for some DUSRVMs.  
For example [Smith] = Smith, and [Schwartz] = Schwartz.  On the other hand, 
it is possible for some DUSRVMs, say M1 and M2, to have the property that 
the 8 DUSRVMs:
 M1//M2,    [M1]//M2,    M1//[M2],     [M1//M2],
[M1//M2],  [[M1]//M2],  [M1//[M2]],  [[M1]//[M2]]
are each different from each other.

If M is a DUSRVM, define M//Random to be the USRVM that selects the winner 
produced by M, if M produces a single winner, and selects one of the winners 
produced by M according to a uniform distribution over those M-winners, if M 
results in 2 or more (tied) winners.  Thus, M//Random always results in a 
single winner.

RECOMMENDATION

I used to like:
//[Plurality-ext]//Random
as a tie-breaker, but Mike's arguments have convinced me that
//[Plurality]//[Plurality-ext]//Random
is better.  Of course, it's also more complex.

I don't like
//Plurality//Random,
//[Plurality]//Random, or
//[Plurality]//Plurality-ext//Random,
because these invoke Random when it's still possible for
//[Plurality-ext] to break ties without resorting to a random pick.
After //[Plurality-ext] has been applied, any remaining ties are not 
breakable based solely on the voters' ballots.

I think that
Smith//[Condorcet-M]//[Plurality]//[Plurality-ext]//Random
may be slightly better (but is slightly more complex) than
Smith//Condorcet-M//[Plurality]//[Plurality-ext]//Random,
so I'm basically indifferent between these two ways of breaking ties that 
that can occur in Smith//Condorcet-M.

Bruce