Ranked Pairs

From electowiki
(Redirected from RP)
Wikipedia has an article on:

The "Ranked Pairs" method (sometimes abbreviated as "RP") was created in 1987 by Nicolaus Tideman. It is a voting system that selects a single winner using votes that express preferences. The ranked-pairs method can also be used to create a sorted list of winners. Ranked Pairs passes the Smith criterion and the Condorcet winner criterion (thus making it a "Condorcet method"). The ranked-pairs method has many variations such as the "Maximize Affirmed Majorities" (or "MAM") and "Maximum Majority Voting" (or "MMV") voting methods.

Procedure[edit | edit source]

The ranked-pairs procedure works as follows:

  1. Tally the vote count comparing each pair of candidates, and determine the winner of each pair (provided there is not a tie)
  2. Sort (rank) each pair, by the largest margin of victory first to smallest last.
  3. "Lock in" each pair, starting with the one with the largest number of winning votes, and add one in turn to a graph as long as they do not create a cycle (which would create an ambiguity). The completed graph shows the winner.

See the Notes section for information on finding the Ranked Pairs winner without constructing a graph.

Ranked Pairs can also be used to create a sorted list of preferred candidates. To create a sorted list, repeatedly use the procedure to do the following:

  • select a winner,
  • remove that winner from the list of candidates,
  • ...and repeat (to find the next runner up, and so forth)

A simpler way to create the sorted list is simply to run Ranked Pairs once, and then use the resulting Condorcet ranking (when ignoring the defeats that were ignored by the ranked-pairs procedure) as the ranked-pairs ranking.

Tally[edit | edit source]

To tally the votes, consider each voters' preferences. For example, if a voter states "A > B > C" (A is better than B, and B is better than C), the tally should add one for A in A vs. B, one for A in A vs. C, and one for B in B vs. C. Voters may also express indifference (e.g., A = B), and unstated candidates are assumed to be equally worse than the stated candidates.

Once tallied, the majorities can be determined. If "Vxy" is the number of Votes that rank x over y, then "x" wins if Vxy > Vyx, and "y" wins if Vyx > Vxy.

Sort[edit | edit source]

The pairs of winners, called the "majorities", are then sorted from the largest majority to the smallest majority. A majority for x over y precedes a majority for z over w if and only if at least one of the following conditions holds:

  1. Vxy > Vzw. In other words, the majority having more support for its alternative is ranked first.
  2. Vxy = Vzw and Vwz > Vyx. Where the majorities are equal, the majority with the smaller minority opposition is ranked first.

Lock[edit | edit source]

The next step is to examine each pair in turn to determine which pairs to "lock in". Using the sorted list above, lock in each pair in turn unless the pair will create a circularity in a graph (e.g., where A is more than B, B is more than C, but C is more than A).

An Example[edit | edit source]

The Situation[edit | edit source]

Imagine an election for the capital of Tennessee, a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south. Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga). Here's the population breakdown by metro area (surrounding county):

  • Memphis (Shelby County): 826,330
  • Nashville (Davidson County): 510,784
  • Chattanooga (Hamilton County): 285,536
  • Knoxville (Knox County): 335,749

Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:

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

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

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

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

The results would be tabulated as follows:

Pairwise Election Results
Memphis Nashville Chattanooga Knoxville
BMemphis[A] 58%
[B] 42%
[A] 58%
[B] 42%
[A] 58%
[B] 42%
Nashville[A] 42%
[B] 58%
[A] 32%
[B] 68%
[A] 32%
[B] 68%
Chattanooga[A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 17%
[B] 83%
Knoxville[A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 83%
[B] 17%
Pairwise election results (won-lost-tied): 0-3-0 3-0-0 2-1-0 1-2-0
Votes against in worst pairwise defeat: 58%N/A68%83%
  • [A] indicates voters who preferred the candidate listed in the column caption to the candidate listed in the row caption
  • [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption
  • [NP] indicates voters who expressed no preference between either candidate

Tally[edit | edit source]

First, list every pair, and determine the winner:

Pair Winner
Memphis (42%) vs. Nashville (58%) Nashville 58%
Memphis (42%) vs. Chattanooga (58%) Chattanooga 58%
Memphis (42%) vs. Knoxville (58%) Knoxville 58%
Nashville (68%) vs. Chattanooga (32%) Nashville 68%
Nashville (68%) vs. Knoxville (32%) Nashville 68%
Chattanooga (83%) vs. Knoxville (17%) Chattanooga: 83%

Note that absolute counts of votes can be used, or percentages of the total number of votes; it makes no difference.

Sort[edit | edit source]

The votes are then sorted. The largest majority is "Chattanooga over Knoxville"; 83% of the voters prefer Chattanooga. Nashville (68%) beats both Chattanooga and Knoxville by a score of 68% over 32% (an exact tie, which is unlikely in real life for this many voters). Since Chattanooga > Knoxville, and they're the losers, Nashville vs. Knoxville will be added first, followed by Nashville vs. Chattanooga.

Thus, the pairs from above would be sorted this way:

Pair Winner
Chattanooga (83%) vs. Knoxville (17%) Chattanooga 83%
Nashville (68%) vs. Knoxville (32%) Nashville 68%
Nashville (68%) vs. Chattanooga (32%) Nashville 68%
Memphis (42%) vs. Nashville (58%) Nashville 58%
Memphis (42%) vs. Chattanooga (58%) Chattanooga 58%
Memphis (42%) vs. Knoxville (58%) Knoxville 58%

Lock[edit | edit source]

The pairs are then locked in order, skipping any pairs that would create a cycle:

  • Lock Chattanooga over Knoxville.
  • Lock Nashville over Knoxville.
  • Lock Nashville over Chattanooga.
  • Lock Nashville over Memphis.
  • Lock Chattanooga over Memphis.
  • Lock Knoxville over Memphis.

In this case, no cycles are created by any of the pairs, so every single one is locked in.

Every "lock in" would add another arrow to the graph showing the relationship between the candidates. Here is the final graph (where arrows point from the winner).


In this example, Nashville is the winner using RP.

Ambiguity Resolution Example[edit | edit source]

Let's say there was an ambiguity. For a simple situation involving candidates A, B, and C.

  • A > B 68%
  • B > C 72%
  • C > A 52%

In this situation we "lock in" the majorities starting with the greatest one first.

  • Lock B > C
  • Lock A > B
  • We don't lock in the final C > A as it creates an ambiguity or cycle.

Therefore, A is the winner.

A Limit case[edit | edit source]

We assume 48% of voters vote A>B>C, 3% votes B>C>A, 49% votes C>A>B. A>B in 97% (locked), C>A in 52% (locked) and B>C in 51% (not locked since there is a cycle). Thus, we have C>A>B and C is the winner. However, if we make a Borda count (2 points for first place 1 point for second place) A has 145 points and C has only 101 points and thus one could think that A deserves more to win.

Notes[edit | edit source]

The RP winner can be found using only a pairwise comparison table. Example:
4 A>B>C

3 B>C>A

5 C>A>B
The pairwise comparison table looks like this (victories are bolded, defeats are underlined):
A - 9 4
B 3 - 7
C 8 5 -

All candidates suffer at least one pairwise defeat, so the RP procedure must be done. The pairwise victories can be ordered from largest to smallest as A > B 9, C > A 8, and B > C 7. The first two victories are locked in (A>B creates no cycle, since it's the first defeat added, and C>A also creates no cycle, since for A, it shows C>A>B), and then the third defeat is thrown away (because adding B>C would result in, for C, a C>A>B>C beatpath cycle), resulting in the following pairwise comparison table:

C - 8 5
A 4 - 9
B 7 3 -

When ignoring struckthrough (non-locked in) pairwise victories, C is the only candidate with no pairwise defeats, and thus is the RP winner. The RP ranking is C>A>B, since C pairwise beats all others, A pairwise beats everyone except C, and B pairwise loses to everyone (when ignoring the defeats ignored by the RP procedure).

Ranked Pairs is Smith-efficient, because no Smith set member can be beaten by a candidate not in the Smith set, and therefore any candidate not in the Smith set can't have their defeats to Smith set members discarded during the RP procedure, so they can't become the Condorcet winner.

Ranked Pairs passes the Independence of Smith-dominated Alternatives criterion, because the only cycles for RP to potentially resolve will always be between Smith set members. Because of this, all candidates not in the Smith set can be eliminated before starting the procedure, reducing the number of operations needed to be done to find the winner. In addition, Ranked Pairs, like Schulze, is equivalent to Minimax when there are 3 or fewer candidates with no pairwise ties between them, so if the Smith set has 3 or fewer candidates in it with no pairwise ties between them, Smith//Minimax can be run instead to find/demonstrate the RP winner.

One disadvantage of Ranked Pairs is that there's no easy way to detect ties for first place: determining whether there exists a way to break ties between pairwise victories so that a given candidate wins is NP-complete.[1]. While it is possible to break pairwise ties fairly, doing so leads Ranked Pairs to declare one of the winners the sole winner, without giving information about whether other candidates could have won were the ties broken differently.

References[edit | edit source]

  1. Brill, Markus; Fischer, Felix (2012-07-26). "The Price of Neutrality for the Ranked Pairs Method". Proceedings of the AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence (AAAI). 26 (1): 1299–1305. doi:10.1609/aaai.v26i1.8250. ISSN 2374-3468.

External Resources[edit | edit source]

This page uses Creative Commons Licensed content from Wikipedia (view authors).