[EM] Does IRV fail the Smith criterion?

[Instant Runoff Voting supporter]

- - - - - - - - - - - - - - - - - - - - 01/03/01
Source: Richard Moore  <rmoore4 at home.com>

Date: Sun, 31 Dec 2000
Some Thoughts on Instant Runoff Voting

I. Instant Runoff Voting -- How Well Does It Work?

Instant Runoff Voting (IRV) works well when only a few rounds of
elimination take place. The simplest case is if there is a majority
winner -- in this case, IRV only takes one round and produces the
obvious result. However, with each additional round that is required,
the results of IRV become more chaotic. Let's assume there are N
candidates, and the IRV evaluation requires M rounds. Then, in the
worst case, the winner could be the Mth best of N candidates. (The
problem of deciding how to calculate the winner's true rank is of
course generally not resolvable, but in this case I mean the the
winner would be capable of defeating N-M of the other candidates in
pairwise races). Nothing more can be guaranteed by IRV.

So, if IRV requires exhaustive elimination (M = N-1), then the IRV winner
can only be guaranteed to defeat one other candidate in a head-to-head
matchup.

For that reason, I could not feel comfortable with the result of an IRV
race that requires more than one or two rounds to resolve. In a race with,
say five candidates, I would hope that the IRV winner would be stronger
than at least three other candidates. This cannot be guaranteed if the race
requires more than two rounds. And with five candidates, three rounds is
not an unlikely scenario, especially if the voting population is closely
divided.

II. IRV and Aliasing

IRV belongs to a class of election methods that I like to call "aliasing
methods". An aliasing method is any election method in which candidates are
eliminated without considering all expressed rankings of that candidate.

This term originates from an analogy to the world of signal processing.
When an analog signal is sampled (as when converting it to a digital
signal) at too low a sample rate, the components of the signal at
the upper end of its spectrum are folded back into the lower part of
its spectrum, only with the frequencies reversed and shifted. This
"aliased" signal interferes with the original signal, making accurate
reconstruction of the original signal difficult or impossible. In an
election with an aliasing method, some of the information collected
from the voters, representing finer detail in the overall picture,
is ignored. This is analogous to undersampling the analog signal.

Interestingly, simply restricting the voting to first choices only
(the plurality method) does not cause aliasing at all. This is because
these first-choice votes represent very coarse information, comparable
to limiting the signal in my analogy to low frequencies only. In
signal processing this would be accomplished with an anti-aliasing
filter. The result is a picture that, while not having any aliasing
artifacts, nevertheless suffers from low resolution. If there is a
clear majority, even that low resolution is sufficient. But without
that majority, we start sampling the higher-order information. If
we limit the samples we look at, we begin to introduce the aliasing
effect. IRV eliminates one candidate based on the low-resolution image
of the first round, and then, based on that elimination, admits only
a portion of the samples of the more fine-grained ranking information.

I will not attempt to give aliasing methods a mathematical treatment.
I will make a conjecture: I believe aliasing methods are non-monotonic.

I do not believe aliasing methods would necessarily fail the Smith
criterion.  I will present two variations of IRV here. The first variation
is non-aliasing.  The second variation, while it is still an aliasing
method, passes the Smith criterion.


III. Improving IRV: RIRV

Consider an IRV election with 5 candidates that goes through 4 rounds. If,
after 3 rounds, B, C, and D are eliminated, and A then defeats E in the 4th
round, what can we conclude with certainty about these results (without
going back and peaking at the original bins)?

The only conclusion we can draw is that a majority of the voters expressed
a preference for A over E. "Expressed a preference" is different from "have
a preference", because they may have attempted (and failed) a strategy by
reversing their A-E preference (people will do this in a non-monotonic
system).  However, to simplify this case study, let's assume only sincere
voting takes place.

Nothing could be determined, just from the result, about the voting
population's preferences for B, C, and D over either A or E. Suppose E
would have lost to B, C, and D in head-to-head races -- that is, E was not
a viable candidate in the first place. So E played the role of spoiler in
this race.

After M rounds with N candidates, you can only say that the winner is
preferred by a majority over N-M other candidates.

E can be eliminated from the race and the entire IRV procedure repeated for
the remaining candidates using the original ballots. Perhaps there is a
different winner this time; maybe the final round has C defeating A. Now we
know that neither A nor E are the top choices of the voters. You could have
another "big" round between B, C, and D. A picture of an IRV variant should
be emerging now: Four back-to-back full-depth IRV elections from the same
set of ballots, each with a smaller number of candidates than the previous
one, and each with a more accurate picture than the previous one. Each
"election" or "meta-round" eliminates the loser of its last "sub-round".
Finally, it comes down to the last two candidates (C and D, for example)
and the final victor is the pairwise winner of this race.

Since at least one of A and B has been tried directly against one or more
other candidates, there is a significant improvement of the quality of the
outcome.  If C is the "most tried" candidate, then if C wins he is still
the most tried.  If D beats C he wins by defeating the most tried
candidate.

This approach requires that a candidate be proven to be directly defeatable
(i.e., in a pairwise race) by at least one other candidate before the
candidate can be eliminated. This avoids the major IRV disadvantage of
eliminating candidates without first examining the full spectrum of their
strengths and weaknesses.

I thought of calling this approach "Meta-IRV" but considering the
inevitable acronym, I think "Recursive IRV" would be better.

IV. RIRV (detailed example)

        FIRST ELIMINATION:
        4:      ABCDE   AxCDE   AxCxE   AxxxE
        1:      BCADE   xCADE   xCAxE   xxAxE
        2:      CABED   CAxED   CAxEx   xAxEx
        1:      DACEB   DACEx   xACEx   xAxEx
        1:      DECAB   DECAx   xECAx   xExAx
        3:      ECABD   ECAxD   ECAxx   ExAxx

        A (8) beats E (4)
        E eliminated

NOTE: An "x" indicates an elimination in straight IRV. An "x" with a
candidate listed to the left of it indicates aliasing. B, C, and D are
subject to aliasing effects but A and E are not. B, C, and D will be
restored at the start of the next elimination, erasing the aliasing
effects.

NOTE: E is a spoiler in this race. E cannot win against any other candidate
in pairwise elections (assuming the rankings given by the voters are
sincere).

        SECOND ELIMINATION:
        4:      ABCD    AxCD    AxCx
        1:      BCAD    xCAD    xCAx
        5:      CABD    CAxD    CAxx
        1:      DACB    DACx    xACx
        1:      DCAB    DCAx    xCAx

        C (7) beats A (5)
        A eliminated


        THIRD ELIMINATION:
        5:      BCD     BCx
        5:      CBD     CBx
        2:      DCB     xCB

        C (7) beats B (5)
        B eliminated


        FOURTH AND FINAL ELIMINATION:
        10:     CD
        2:      DC

        C (10) beats D (2)
        C wins the election

Note that in this example, the winner is also the Condorcet winner. I
believe that is generally the case for RIRV; if there is a Condorcet
winner, that candidate will never be eliminated by this method. The
method also meets Smith (a Smith set member can only be eliminated by
another Smith set member). I do not know if this method is monotonic.
I believe this method is free of aliasing (since each elimination round
compares only two candidates and considers the complete rankings of both).


V. Improving IRV: SIRV

I stated earlier that aliasing in an election method does not preclude
meeting the Smith criterion. It is easy to show how an aliasing method
(IRV) can be modified to be Smith-compliant. I will call this modified
method Smith IRV.  I haven't seen this method discussed previously
but it is obvious enough that I suspect it, or some variation of it,
has probably already been proposed.

>From the ranked ballots, it is possible to determine the Smith
set and eliminate all non-members. This must be done in the first
round. The remaining candidates can then be selected based on normal
IRV procedures.  Since all candidates qualified by round one are
Smith set members, the winner will be from the Smith set.

While all the rankings must be considered in determining the Smith set
(a non-aliasing operation), once the initial elimination is complete,
elimination based on partial ranking information begins. Thus, the IRV
phase of SIRV introduces aliasing, but the interference from non-Smith
candidates is eliminated so the aliasing effect will be less severe.

This method has a few implications. First, for cases where there is
a Condorcet winner, this method selects that candidate. Second, the
minimum Smith set size when there is no Condorcet winner is three,
so for elections with only three candidates, this method will be
equivalent to simple IRV if there is not a Condorcet winner.  In cases
of more than three candidates, the Smith phase of SIRV amounts to an
insurance policy that non-viable candidates do not get unjustified
assistance from the IRV process.