Instant Pairwise Elimination

From electowiki

Instant Pairwise Elimination (abbreviated as IPE) is an election vote-counting method that uses pairwise counting to identify a winning candidate based on successively eliminating the pairwise loser (Condorcet loser) in each round of elimination. When there is an elimination round that does not have a pairwise loser, pairwise count sums (explained below) for the not-yet-eliminated candidates are used to select which candidate is eliminated in that round.

Description

Instant Pairwise Elimination eliminates one candidate at a time. During each elimination round the candidate who loses every pairwise contest against every other not-yet-eliminated candidate is eliminated. The last remaining candidate wins.

If an elimination round has no pairwise-losing candidate, then the method eliminates the candidate with the largest pairwise opposition count, which is determined by counting on each ballot the number of not-yet-eliminated candidates who are ranked above that candidate, and adding those numbers across all the ballots. If there is a tie for the largest pairwise opposition count, the method eliminates the candidate with the smallest pairwise support count, which similarly counts support rather than opposition. If there is also a tie for the smallest pairwise support count, then those candidates are tied and all those tied candidates are eliminated in the same elimination round.

Ballots

Voters rank the candidates using as many ranking levels as there are candidates, or at least 5 ranking levels if ovals are marked on a paper ballot and space is limited and lots of the candidates are unlikely to win.

Multiple candidates can be ranked at the same ranking level.

If the voter marks more than one oval for a candidate, then the highest marked ranking level is used. If the voter does not mark any ovals for a candidate, that candidate is ranked at the lowest ranking level, as if the voter marked the oval for the lowest ranking level.

Example

Tennessee's four cities are spread throughout the state
Tennessee's four cities are spread throughout the state

Imagine that Tennessee is having an election on the location of its capital. The population of Tennessee is concentrated around its four major cities, which are spread throughout the state. For this example, suppose that the entire electorate lives in these four cities, and that everyone wants to live as near the capital as possible.

The candidates for the capital are:

  • Memphis, the state's largest city, with 42% of the voters, but located far from the other cities
  • Nashville, with 26% of the voters, near the center of Tennessee
  • Knoxville, with 17% of the voters
  • Chattanooga, with 15% of the voters

The preferences of the voters would be divided like this:

42% of voters
(close to Memphis)
26% of voters
(close to Nashville)
15% of voters
(close to Chattanooga)
17% of voters
(close to Knoxville)
  1. Memphis
  2. Nashville
  3. Chattanooga
  4. Knoxville
  1. Nashville
  2. Chattanooga
  3. Knoxville
  4. Memphis
  1. Chattanooga
  2. Knoxville
  3. Nashville
  4. Memphis
  1. Knoxville
  2. Chattanooga
  3. Nashville
  4. Memphis

These ballot preferences are converted into pairwise counts and displayed in the following tally table.

All possible pairs
of choice names
Number of votes with indicated preference
Prefer X over Y Equal preference Prefer Y over X
X = Memphis
Y = Nashville
42% 0 58%
X = Memphis
Y = Chattanooga
42% 0 58%
X = Memphis
Y = Knoxville
42% 0 58%
X = Nashville
Y = Chattanooga
68% 0 32%
X = Nashville
Y = Knoxville
68% 0 32%
X = Chattanooga
Y = Knoxville
83% 0 17%

These pairwise counts are rearranged into the following square table.

... over Memphis ... over Nashville ... over Chattanooga ... over Knoxville
Prefer Memphis ... - 42% 42% 42%
Prefer Nashville ... 58% - 68% 68%
Prefer Chattanooga ... 58% 32% - 83%
Prefer Knoxville ... 58% 32% 17% -

In the first elimination round, Memphis is eliminated because it is the pairwise loser, which means it lost every pairwise contest with every other choice.

If there had not been a Condorcet loser, Knoxville would have been eliminated (instead of Memphis) because the column labeled over Knoxville has the largest sum (193%). If there had been a tie for the largest column sum, then Knoxville would have been eliminated because the row labeled Prefer Knoxville has the smallest sum (107%).

The following table displays the pairwise counts for the remaining candidates.

... over Nashville ... over Chattanooga ... over Knoxville
Prefer Nashville ... - 68% 68%
Prefer Chattanooga ... 32% - 83%
Prefer Knoxville ... 32% 17% -

In the second elimination round, Knoxville is eliminated because it is the pairwise loser.

If there had not been a Condorcet loser, Knoxville still would have been eliminated because the column labeled over Knoxville has the largest sum (151%). If there had been a tie for the largest column sum, then Knoxville still would have been eliminated because the row labeled Prefer Knoxville has the smallest sum of (49%).

The following table displays the pairwise counts for the remaining candidates.

... over Nashville ... over Chattanooga
Prefer Nashville ... - 68%
Prefer Chattanooga ... 32% -

In the third and final elimination round, Chattanooga is eliminated because it is the pairwise loser.

The only remaining candidate is Nashville, so it is declared the winner.

Mathematical criteria

The frequency with which this method passes or fails each of the following criteria have not been estimated. The frequencies are likely to be similar to those of the Condorcet-Kemeny method because the two methods use pairwise counts in similar ways.

This method always passes the following criteria.

This method sometimes fails the following criteria.

  • Condorcet: fail
  • Majority: fail
  • Majority loser: fail
  • Mutual majority: fail
  • Smith/ISDA: fail
  • LIIA: fail
  • IIA: fail
  • Cloneproof: fail
  • Monotone: fail
  • Consistency: fail
  • Reversal symmetry: fail
  • Later no harm: fail
  • Later no help: fail
  • Burying: fail
  • Participation: fail
  • No favorite betrayal: fail

It is summable with O(N2).

History

The first version of IPE was created and named by Richard Fobes and described in an article at Democracy Chronicles. In that version the elimination method used when there was no Condorcet loser was an "upside-down" version of Instant-Runoff Voting. Later, in response to a suggestion on Reddit to improve the alternate elimination method, Fobes revised the alternate elimination method to use pairwise counts in a way that approximates the Condorcet-Kemeny method.

Notes

IPE is a Smith-efficient Condorcet method whenever a Condorcet ranking can be created for all candidates not in the Smith set i.e. when there are no Condorcet cycles among candidates not in the Smith set.