Does IRV reduce the frequency of "spoiled" elections versus plain plurality? Yes for 3-canddt elections.

[Warren D Smith]

Does IRV reduce the frequency of "spoiled" 3-candidate elections
versus plain plurality?
==============Warren D Smith====Oct 2016===============================

IRV (instant runoff) proponents unfortunately often claim that
switching from plain plurality voting to IRV will "eliminate"
the "spoiler problem." That claim is false.
Not only can spoilers still occur with IRV, in some ways they
can actually be worse. For example, with IRV, an "obvious" spoiler
candidate can occur, meaning one that can be proven to be a spoiler by
simply examining the ballots. In contrast with plain plurality voting,
spoilers always are "non-obvious," meaning you need to know information
beyond that available on the ballots alone, in order to be sure he was
a spoiler. For example, in a distorted & oversimplified version of USA
presidential Florida 2000 race
#voters their preferences
23 Nader>Gore>Bush
28 Gore>Nader>Bush
49 Bush>Gore>Nader
both Nader and Gore are spoilers using plurality voting, but
this is due to the 2nd preferences of the voters, which simply are
not written on plurality ballots. Meanwhile, in an IRV-spoiler election
like
#voters their preferences
23 Nader>Bush>Gore
28 Gore>Nader>Bush
49 Bush>Gore>Nader
Gore would be a spoiler (if he dropped out, Nader would win,
but by running, he causes Bush, the most-hated candidate in the view
of Gore voters, to win) and this is knowable from the ballots alone.

But now let us focus on a lesser claim/hope. Is it the case that with
IRV, spoilers become less frequent?

Consider the general 3-candidate ranked ballot election
#voters their preferences
t A>B>C
u A>C>B
v B>A>C
w B>C>A
y C>A>B
z C>B>A
where t,u,v,w,y,z all are nonnegative not all zero.
An election is said to be "spoiled" if it contains at least one spoiler.
A "spoiler" is a nonwinner who, by dropping out, changes the winner.

Warning: with IRV we can have "nonmonotonicity" where
some voters can cause X to win by voting dishonestly against X.
This perhaps could be viewed as an additional kind of
"spoiler" (X "spoils himself"!) but for simplicity we will not take
that view here.
Also with IRV X can by losing some but not all votes, sometimes change
the winner,
e.g. to himself(!), but we for simplicity will not count those as
spoilers either.

Wlog the IRV winner is A, and C is eliminated first, meaning
y+z<v+w, y+z<t+u, y+t+u>v+w+z.
Then an IRV spoiler (who necessarily is B) occurs if and only if
w+y+z>t+u+v.
Meanwhile in this election, the plain plurality winner must be
either A or B. We have that
* A wins and C=spoiler iff: t+u>v+w and z+v+w>t+u+y
* A wins and B=spoiler iff: t+u>v+w and w+y+z>t+u+v
* B wins and A=spoiler iff: t+u<v+w and u+y+z>t+v+w
* B wins and C=spoiler iff: t+u<v+w and y+t+u>v+w+z.

So... trying it on a computer
(the three probability models described here:
http://rangevoting.org/IrvParadoxProbabilities.html )
two runs each model

Dirichlet model:
tried 10000000 elections; spoiled IRV=902896; spoiled Plur=4098732; ratio=4.54
tried 10000000 elections; spoiled IRV=902621; spoiled Plur=4096433; ratio=4.54

Random Election Model:
tried 1000000 elections; spoiled IRV=121881; spoiled Plur=309295; ratio=2.54
tried 1000000 elections; spoiled IRV=121953; spoiled Plur=309548; ratio=2.54

Quas1D model:
tried 100000000 elections; spoiled IRV=19442452; spoiled
Plur=38885241; ratio=2.00
tried 100000000 elections; spoiled IRV=19438229; spoiled
Plur=38886530; ratio=2.00

CONCLUSION:
YES, IRV does reduce "spoiled" 3-candidate elections versus plain
plurality, making spoiled elections 2.00 to 4.54 times rarer
depending on which of these three probability models we use.

If, however, there are a huge number of candidates (not 3), then in the REM
and Dirichlet models spoiled elections should happen (in the limit)
100% of the time for both voting methods. Not sure right now about
the Quas1D model but as a guess it probably is also 100% for both. If
so IRV is not an improvement (or at best is
a vanishingly small improvement) in this limit as far as spoilers concerned.

If I had included nonmonotone "self spoilers" and partial spoilers too,
then 3-candidate IRV would look a little (perhaps 10%)
worse, not enough to change the conclusion that 3-candidate IRV does
improve over
plain plurality about spoilers. (The reason this has little effect is
in the large majority of instances where these problems happen,
garden-variety spoilage also happens, so that election was already
counted.)


--
Warren D. Smith
http://RangeVoting.org <-- add your endorsement (by clicking
"endorse" as 1st step)

[Warren D. Smith (CRV cofounder, http://RangeVoting.org)]

On reconsideration, it is not obvious to me what happens to the percentages

of "spoiled" IRV & plurality elections in the limit of a large number C of candidates.

[Clay Shentrup]

Someone needs to correct wikipedia's article on spoilers.

The spoiler effect is the effect of vote splitting between candidates or ballot questions[n 1] with similar ideologies. One spoiler candidate's presence in the election draws votes from a major candidate with similar politics thereby causing a strong opponent of both or several to win. The minor candidate causing this effect is referred to as a spoiler.[n 2] However, short of any electoral fraud, this presents no grounds for a legal challenge. The spoiler effect is a problem in plurality voting systems because they enable a candidate to win with less than half of the vote. The problem does not exist in preferential voting or ranked ballot voting systems because voters are allowed to rank their candidate choices, with their vote transferring to their second choice if their first choice does not win, and to their third choice if their second choice does not win, and so on.

[Warren D Smith]

In this post I will attempt to examine the frequency of spoilers in
elections in the limit which the number C of candidates becomes large
(and the number of voters is assumed to tend to infinity much faster).
I will use "extreme value statistics" without much explanation or care.
However, I claim the amount of care & precision I use, is sufficient
to see the results.
The 3 probability models are described here:
http://www.rangevoting.org/IrvParadoxProbabilities.html

The results of the present analysis are:
WITH PLURALITY VOTING:
in Random elections, Dirichlet, and Quas1D models (all three)
the chance a spoiler exists goes to 100%.

Now for the analyses.

ANALYSIS FOR PLURALITY VOTING:
In the random elections model, the total number of votes for each candidate
is (or rather can equivalently be regarded as, after appropriate rescale
and translate) i.i.d. standard normal deviates:

Density(x) = exp(-x^2 / 2) / sqrt(2*pi)
Cumulative(x) = [1+erf(x/sqrt(2))]/2
=asymptotic= 1 - exp(-x^2 / 2) / (x*sqrt(2*pi)) when x-->+infinity

Hence the candidate with the most votes among C candidates is almost surely
going to get about
sqrt(2*ln(C))
votes, and the runner-up is almost surely going to get about
sqrt(2*ln(C-1))
with the difference being about
1/(C*sqrt(2*ln(C))).
Meanwhile, the second-preference vote-totals among the fraction 1/C
voters for any
particular candidate S (who is not either the winner or runner-up) are going to
be normally distributed with variance=1/C not 1.
The difference between the two frontrunners' vote-totals among this fraction
is thus normally distributed with variance=2/C.
The chance S is a spoiler is the chance a normal random variable with
variance=2/C i.e. StdDeviation=sqrt(2/C) is going to exceed 1/(C*sqrt(2*ln(C))).
That is the same as the chance a standard normal (with unit variance) is
going to exceed 1/(2*sqrt(C*ln(C))). But this chance in the limit C-->+infinity
is 1/2. So each non-frontrunner candidate is a spoiler with chance-->50%
in the limit, so the likelihood a spoiler exists should go to 100%.

This same reasoning also works in the alternative "Dirichlet model" of
random elections
(since central limit theorem can be used to see normalities for
appropriate vote-total
quantities).

Now in the Quas1D model, the number of votes a candidate gets is the
area of his 1D
Voronoi region on the real interval [0,1]. These areas have mean about 1/C but
are distributed (in the limit) like the sum of two i.i.d. exponential deviates.
(This is a consequence of limit Poisson statistics.) Without loss of generality
(after scaling vote-counts by C) we may regard these as the sum of two
standard exponential deviates, i.e. having
Density(x) = x*exp(x) for x>0
Cumulative(x) = 1-exp(-x)*(1+x)
The winning candidate will almost surely have about ln(C) votes,
and runner-up ln(C-1), the difference being about 1/C.
If a candidate neighboring the runner-up is eliminated, then the
runner-up's Voronoi
region will expand, i.e. he will get more votes, in fact typically (on
this scale)
order 1 more votes. Hence the chance-->100% that each neighbor of
the runner-up
will be a spoiler.

Q.E.D.


You may ask how quickly the chance of a spoiled plurality election
goes to 100% as C-->infinity.
The answer seems to be (more precisely) about 1-2^(2-C)
for the R.E.M. and Dirichlet models, and about 1-k/C for some
positive constant k, for the Quas1D model.

[Warren D Smith]

In this post I will attempt to examine the frequency of spoilers in
elections in the limit which the number C of candidates becomes large
(and the number of voters is assumed to tend to infinity much faster).

I will use a "mass deletion" trick which looks valid but I
have not proven that, so you might wnat to regard this as an
imperfectly-rigorous, but still pretty convincing, proof.

The 3 probability models are described here:
http://www.rangevoting.org/IrvParadoxProbabilities.html

The results of the present analysis are:

WITH INSTANT RUNOFF VOTING (IRV):

in Random elections, Dirichlet, and Quas1D models (all three)

the chance a spoiler exists goes to 100% in th elimit
where the number C of candidates becomes large (and the number of
voters is assumed far larger).

Now for the analyses.

ANALYSIS FOR INSTANT RUNOFF VOTING:
The "mass deletion trick" is this. Let there be C candidates
with C large. Delete all but sqrt(C) of them at random.
Then claim that the winner of the resulting much-smaller IRV election
is essentially random among those sqrt(C) candidates.
More precisely, claim that if those sqrt(C) included the IRV-winner of
the original
(all C candidates) IRV election, then the chance he still wins, goes to 0
as C-->infinity.

This claim is supposed to be pretty obvious in all three models -- so I'm
not going to prove it here, I'm just going to claim/hope it is pretty
obvious to those
familiar with behaviors... and ASSUME it as the starting point of our
main argument.

Now this claim does not directly prove the existence of a single "spoiler"
candidate; it merely proves there exists a LARGE SET of candidates
whose collective
deletion changes the winner, and indeed claims in our limit that almost every
candidate-subset of cardinality C-sqrt(C) (which does not
include the IRV-winner of the original election) is such a "collective spoiler."

But what this tells us is: as we delete those candidates one by one, there will
come a time (maybe many times) when the winner changes. In that
particular reduced
election, that candidate was a (genuine) spoiler. The total number of
(reduced and partly reduced) elections we are talking about is
sum(for M=0...sqrt(C)-1) of (C-1 choose M)
which sum is dominated by middle terms, with M=C/2 and nearby.
The other terms, even combined, are relatively
negligible in the limit C-->infinity.
And the total number of genuine "spoiler events", meaning a time when
a single candidate is deleted from one of those elections to change its winner,
in aggregate over all those elections, is at least 1-o(1) per "deletion path."
But note the total number of "deletion PATHS" in "election space"
is far greater than the number of elections themselves, indeed
in each election with K candidates we have K-1 choices about who to delete next
so the total number of paths is C!/sqrt(C)!.
Indeed, this number of paths also in our limit,
is far greater than the SQUARE (or any fixed power)
of the number of elections themselves.

But now comes the trick: all these reduced and intermediate
elections actually are statistically
speaking the SAME as the original election
(maybe with different but always-large C, but sampled from the exactly correct
distribution for that C; this works in all 3 probability models).
Therefore the chance an IRV spoiler-event is available in a randomly chosen
election in our set of elections goes to 100%.

Therefore, the chance should go to 100% in all three models
that a C-candidate IRV election contains an IRV-spoiler.

[Warren D Smith]

http://rangevoting.org/SpoilerChance.html

now summarizes my findings about spoiled-election frequency
in IRV and plurality voting.