Tie-breakers

Lowell Bruce Anderson landerso at ida.org
Sat Oct 26 21:36:41 PDT 1996

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

```