[EM] Tideman sort tie-breaker proposal

Steve Eppley SEppley at alumni.caltech.edu
Wed Jul 5 15:10:35 PDT 2017


On 07/01/2017 11:44 PM, Lucas Dailey wrote:
>> I’m working with some talented software 
>> developers to build an open
>> source, multi-winner implementation of 
>> Ranked Pair/Tideman tailored
>> toward budgeting to enable legislators to 
>> collectively and fairly rank
>> their budget priorities to arrive at a 
>> democratic budget.
-snip-
>> While building our open source software we 
>> quickly discovered the sort
>> tie problem. I prefer Tideman/RP for 
>> public elections because it’s
>> relatively conceptually simple compared to 
>> its criterion-meeting peers
>> (I’m still a fan, Markus Schulze!). I can 
>> explain it to voters and
>> politicians. However none of the Tideman 
>> tie-breaking procedures I’ve
>> heard of meet that same criterion of 
>> explainability and grounding in
>> democracy.
>>
>> I have a procedure that I believe meets 
>> those criteria, which I
>> paraphrase as the “Lost worst: locked-in 
>> first” procedure. I like it,
>> and I’d love to get feedback on it. I also 
>> imagine others have thought
>> of it before so any research that’s been 
>> done would be helpful. Also the
>> procedure wouldn’t work in every scenario 
>> so I proposed a secondary
>> procedure that is less inspiring but still 
>> better than many alternatives
>> (and also unlikely to work in every scenario).
-snip-
On 7/4/2017 7:40 PM, Kristofer Munsterhjelm 
replied:
> From looking at it briefly, I suspect that 
> the secondary tiebreak will fail clone 
> independence.
-snip-

I would bet Kristofer is correct.  It looks 
like the same problem with clones that Borda 
has, although Borda's problem is much more 
terrible because with Borda the problem isn't 
confined to tied scenarios.  Consider an 
example: A large majority, say 66%, prefer X 
over Y.  Given Borda, a person who prefers Y 
has an incentive to nominate extra 
alternatives that are similar to Y but 
slightly inferior.  Then the votes would be 
something like:
    66:   X > Y > [some inferior clones of Y]
    34:  Y > [some inferior clones of Y] > X
Let N denote the number of inferior clones.
Y's Borda score is (66 x N) + (34 x N+1) = 
100N + 34.
X's Borda score is (66 x N+1) + (34 x 0) = 
66N + 66.
Y wins when 34N > 32.  In other words, Y wins 
when N > 0. With Borda, a large majority can 
be overturned by simply nominating a similar 
alternative.

Each faction has an incentive to nominate as 
many inferior clones of their preferred 
alternative as possible, like an arms race, 
which is farcical.  Given Borda, the voters' 
preferences won't matter much; what matters 
is the number of inferior clones nominated, 
which is an even greater farce. (Call it a 
Type 2 farce.)  Unfortunately, the incentive 
will exist even if clones only make a 
difference when tiebreaking same-size 
majorities, because the chance that such a 
tie will occur is greater than zero, and 
savvy nominators would know that nominating 
clones would help later in case of a tie and 
would never hurt.  So, every faction would 
always have an incentive to nominate as many 
clones as possible.  Thus Lucas' second 
tiebreak could make such farces commonplace. 
(But not the Type 2 kind.)

Lucas is proposing his first tiebreak to 
reduce the need for another tiebreaking that 
he considers less democratic, which involves 
constructing a tiebreak ordering of the 
candidates by randomly picking one voter's 
order of preference (or more than one if the 
first one picked expresses indifference on 
the pairings relevant to the tiebreaking).  
In my webpages at 
http://alumnus.caltech.edu/~seppley/ I call 
the construction Random Voter Hierarchy, or 
RVH.  Because there can be cases where Lucas' 
first and second tiebreaks both fail to 
resolve the ties, he presumably intends to 
use something like RVH anyway as a third 
tiebreak. (Note: RVH is a generalization of 
Tideman's Random Dictator tiebreak, 
generalized to handle the cases where votes 
may include indifference between some 
candidates.  Random Dictator is insufficient 
because it's important to allow voters to 
express indifference, in order to satisfy 
Mike Ossipoff's "strong defensive strategy 
criterion," from which I derived the "minimal 
defense" criterion described in my 
webpages.)  Clearly Lucas' system with RVH as 
its third tiebreak (or second, if he decides 
to eliminate his second tiebreak due to its 
clones nomination incentive) is more complex 
than simply using RVH, and I think that makes 
it harder to explain.

Random Dictator sounds much less democratic 
than Random Chairperson, but they refer to 
the same idea. (That is, when a committee 
vote is tied, the tie is broken by the vote 
of the chairperson.)  It might help if 
election reformers would use the latter 
name.  Perhaps it would help change Lucas' 
opinion about the democratic-ness of tiebreak 
schemes he's been trying to avoid.  The 
legislators who Lucas hopes to persuade 
already use voting methods that break ties 
using the preference of a single person, 
typically a chairperson, and I presume they 
don't believe it's undemocratic.  I don't see 
why anyone should consider RVH less 
democratic than using the preferences of a 
chairperson.  However, in the event that 
Lucas' legislators do consider randomness 
less democratic, my hunch is that they'd 
prefer to construct the tiebreak ordering 
using the preferences of a (non-random) 
seniority hierarchy (starting with the order 
of preference of the chairperson or "speaker 
of the house" or most senior member), and 
their familiarity with the concept may make 
it easier to explain to them than the 
tiebreak Lucas described.

Assuming the voting method permits voters to 
express indifference, the minorities that 
oppose same-size majorities might not be the 
same size.  So it's reasonable that the first 
tiebreak should instead compare the sizes of 
the opposing minorities, if it's desired to 
reduce the scenarios where randomness is a 
factor. (This is done by the Maximize 
Affirmed Majorities voting method, 
abbreviated MAM, which some people--but not 
me--call Ranked Pairs.) Example:
    60 voters rank X over Y, 39 rank Y over 
X, and 1 ranks X=Y.
    60 voters rank Z over W, and 40 rank W 
over Z.
Because the 39 who oppose the X>Y majority 
are fewer than the 40 who oppose the Z>W 
majority, MAM gives the X>Y majority 
precedence over the Z>W majority. (Note: 
Another way to describe the sorting of all 
the majorities is to say that the primary 
sort key is size of majority, descending, and 
the secondary sort key is size of opposing 
minority, ascending.  Given this notation, 
Lucas' first tiebreak would be the tertiary 
sort key, assuming he were to use opposing 
minorities as the secondary sort key.)

I expect that much more common than scenarios 
with three same-size majorities (as in the 
example linked by Lucas) will be scenarios 
that have two same-size majorities.  Here's a 
simple Rock-Paper-Scissors example:
    55:  R>S
    51:  S>P
    51:  P>R
In this scenario, Lucas' first tiebreak would 
simply be the head-to-head pairing of the two 
pairlosers, P versus R, and the tiebreak 
ordering of candidates would be P>R.  Since R 
is behind P in the tiebreak ordering, the 
primary tiebreak gives the P>R majority 
(which is "lost" by R) precedence over the 
S>P majority (which is "lost" by P).  Thus, 
after R has been placed ahead of S in the 
order of finish due to the 55% majority, the 
P>R majority is considered and P is placed 
ahead of R in the order of finish.  So P 
wins.  It's been a long time since I looked 
at this scenario, but my recollection is that 
this tiebreak scheme has a significant 
negative consequence.  Unfortunately I don't 
recall the details, and it's possible I'm 
mixing in a memory of a different tiebreak. 
(Somewhere among my old emails is a 
discussion I had with Mike Ossipoff about 
this tiebreak or something similar, in which 
we agreed there was a negative consequence.  
Maybe I'll find time to hunt for it, if it's 
important.)

Lucas' example seems unclear about what his 
first tiebreak will do in the case where some 
of the same-size majorities have the same 
candidate as pairloser, like B in the following:
     ...
    60:  A>B
    60:  C>D
    60:  E>B
     ...
I'll guess that Lucas would resolve the 
precedence of the A>B and E>B majorities by 
comparing their pairwinners, A&E.  In other 
words, if E is ahead of A in the tiebreak 
ordering, then give the E>B majority 
precedence over the A>B majority. (That's 
what MAM does in such cases.  When two 
same-size majorities' pairlosers are 
different candidates, MAM compares the two 
pairlosers' positions in the RVH tiebreak 
ordering.  But when the two pairlosers are 
the same candidate, MAM compares the two 
pairwinners' positions in the RVH tiebreak 
ordering.)

I should note, for the sake of anyone 
planning to implement Ranked Pairs, that 
there's an unnecessary flaw in the way 
Tideman & Zavist use Random Chairperson to 
break ties.  The flaw is irrelevant if voters 
are forced to vote strict orders of 
preference (no indifferences) and/or if the 
voting method method pays attention to 
"pairwise margins of difference" instead of 
"sizes of majorities." But the flaw is a 
concern, since satisfaction of Mike 
Ossipoff's SDSC (a.k.a. minimal defense) 
requires allowing voters to express 
indifference and requires paying attention to 
sizes of majorities instead of margins of 
difference. (MAM does both and satisfies 
minimal defense, but Tideman-Zavist Ranked 
Pairs does neither and fails minimal 
defense.)  Specifically, the Strong Pareto 
criterion is failed by the variation of 
Ranked Pairs that allows voters to express 
indifference and pays attention to 
majorities' sizes, if it uses Zavist's 
tiebreak scheme. (Strong Pareto: "If no 
voters rank x over y and at least one voter 
ranks y over x, then x must not finish ahead 
of y.")  When I proved MAM completely 
satisfies Strong Pareto, I noticed the proof 
would not have worked if Zavist's scheme were 
used (unless I made a mistake).  MAM 
tiebreaks same-size majorities by comparing 
the same-size majorities' pairlosers' 
positions in the tiebreak ordering (and when 
the pairlosers are the same candidate, it 
compares pairwinners' positions), whereas 
Zavist uses a mixture of pairwinners & 
pairlosers.  Lucas apparently has an 
intuition for this already, since his first 
and second tiebreakers compare pairlosers' 
positions in tiebreaking orderings.

(Equally good, I believe, would be to compare 
pairwinners' positions in the tiebreak 
ordering, instead of pairlosers' positions.  
For example, in the "two same-size 
majorities" example above, the pairwinners of 
the same-size majorities are S & P.  If S is 
ahead of P in the tiebreak ordering, a 
pairwinners scheme would give precedence to 
the majority in which S is pairwinner (the 
S>P majority) over the majority in which P is 
the pairwinner (the P>R majority).  As I 
wrote above, MAM's tiebreak compares 
pairlosers, so MAM compares the positions of 
the pairlosers P & R in the RVH ordering, and 
if P is behind R then MAM gives precedence to 
the majority in which P is pairloser.  When I 
defined MAM about 15 years ago, based on 
conversations in the EM maillist I believed 
pairwise defeats were more significant than 
pairwise wins.  I later decided they're 
equally significant and the choice to compare 
pairlosers is arbitrary.  By then I'd already 
defined MAM and already constructed a large 
number of proofs and documents, and I know no 
compelling reason to change MAM's tiebreaker 
to use pairwinners.  I think the choice 
between pairwinners or pairlosers is just a 
matter of taste.)

I agree with Lucas that Ranked Pairs and MAM 
are simpler to explain than Schulze' method.  
MAM also satisfies some criteria that 
Schulze's method fails: Local IIA, 
Multiwinner Resolvability, Immunity from 
Majority Complaints, and Immunity from 2nd 
Place Complaints.  Also, since Markus doesn't 
specify a tiebreaker in his Wikipedia page 
(the last time I looked, which was several 
years ago), it means Schulze's method doesn't 
clearly satisfy several other criteria, such 
as Independence of Clones.

An free online engine to tally elections 
using MAM is available for groups to use (or 
for anyone to experiment with):
      http://MAM.hostei.com/
To use it, a group's secretary types or 
pastes their votes into the box, and then 
clicks the button underneath.

Perhaps I can find some time to help Lucas' 
team develop their software, or help minimize 
the jargon when they pitch it to legislators 
and other groups, if he'd like me to consult.

Cheers,
Steve


More information about the Election-Methods mailing list