[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