Ranked pairs

Ranked pairs (sometimes abbreviated "RP") or the Tideman method is an electoral system developed in 1987 by Nicolaus Tideman that selects a single winner using votes that express preferences.^[1]^[2] The ranked-pairs procedure can also be used to create a sorted list of winners.

If there is a candidate who is preferred over the other candidates, when compared in turn with each of the others, the ranked-pairs procedure guarantees that candidate will win. Because of this property, the ranked-pairs procedure complies with the Condorcet winner criterion (and is a Condorcet method).^[3]

Procedure

The ranked-pairs procedure operates as follows:

Tally the vote count comparing each pair of candidates, and determine the winner of each pair (provided there is not a tie)
Sort (rank) each pair, by strength of victory, from largest first to smallest last.^{[vs 1]}
"Lock in" each pair, starting with the one with the largest strength of victory and, continuing through the sorted pairs, add each one in turn to a graph if it does not create a cycle in the graph with the existing locked in pairs. The completed graph shows the final ranking.

The procedure can be illustrated using a simple example. Suppose that there are 27 voters and 4 candidates $w$ , $x$ , $y$ and $z$ such that the votes are cast as shown in the table of ballots.

Ballots table
$w > x > z > y$	7 ballots
$w > y > x > z$	2 ballots
$x > y > z > w$	4 ballots
$x > z > w > y$	5 ballots
$y > w > x > z$	1 ballots
$y > z > w > x$	8 ballots

Tally

	$w$	$x$	$y$	$z$
$w$	0	9	1	–7
$x$	–9	0	5	11
$y$	–1	–5	0	3
$z$	7	–11	–3	0

The vote tally can be expressed as a table in which the $(w, x)$ entry is the number of ballots in which $w$ comes higher than $x$ minus the number in which $x$ comes higher than $w$ . In the example $w$ comes higher than $x$ in the first two rows and the last two rows of the ballot table (total 18 ballots) while $x$ comes higher than $w$ in the middle two rows (total 9), so the entry in the $(w, x)$ cell is 18–9 = 9.

Notice the skew symmetry of the table.

Sort

The positive majorities are then sorted in decreasing order of magnitude.

$\left(x,z\right)=11$
$\left(w,x\right)=9$
$\left(z,w\right)=7$
$\left(x,y\right)=5$
$\left(y,z\right)=3$
$\left(w,y\right)=1$

Lock

The next stage is to examine the majorities in turn to determine which pairs to "lock in". This can be done by building up a matrix in which the $(x, y)$ entry is initially 0, and is set to 1 if we decide that $x$ is preferred to $y$ and to –1 if we decide that $y$ is preferred to $x$ . These preferences are decided by the list of sorted majorities, simply skipping over any which are inconsistent with previous decisions.

The first two majorities tell us that $x$ is preferred to $z$ and $w$ to $x$ , from which it follows by transitivity that $w$ is preferred to $z$ . Once these facts have been incorporated into the table it takes the form as shown after two steps. Notice again the skew symmetry. The third majority tells us that $z$ is preferred to $w$ , but since we have already decided that $w$ is preferred to $z$ we ignore it, which is why our bank of knowledge looks the same after both 2 and 3 steps.

After 2-3 steps, $w$ > $x$ > $z$
	$w$	$x$	$z$
$w$	0	1	1
$x$	–1	0	1
$y$	0	0	0
$z$	–1	–1	0

After 4 steps, $w$ > $x$ > $z$ and $w$ > $x$ > $y$
	$w$	$x$	$y$	$z$
$w$	0	1	1	1
$x$	–1	0	1	1
$y$	–1	–1	0	0
$z$	–1	–1	0	0

After 5 steps, $w > x > y > z$
	$w$	$x$	$y$	$z$
$w$	0	1	1	1
$x$	–1	0	1	1
$y$	–1	–1	0	1
$z$	–1	–1	–1	0

The fourth majority tells us that $x$ is preferred to $y$ , and since we know that $w$ is preferred to $x$ we infer that $w$ is preferred to $y$ , giving us the table after 4 steps.

The fifth majority tells us that $y$ is preferred to $z$ , and this completes the table.

Winner

In the resulting graph for the locked pairs, the source corresponds to the winner. In this case $w$ is preferred to all other candidates and is therefore identified as the winner.

Tied majorities

In the example the majorities are all different, and this is what will usually happen when the number of voters is large. If ties are unlikely, then it does not matter much how they are resolved, so a random choice can be made. However this is not Tideman's procedure, which is considerably more complicated. See his paper for details.^[1]

An example

The situation

Suppose that Tennessee is holding an election on the location of its capital. The population is concentrated around four major cities. All voters want the capital to be as close to them as possible. The options are:

Memphis, the largest city, but far from the others (42% of voters)
Nashville, near the center of the state (26% of voters)
Chattanooga, somewhat east (15% of voters)
Knoxville, far to the northeast (17% of voters)

The preferences of each region's voters are:

42% of voters Far-West	26% of voters Center	15% of voters Center-East	17% of voters Far-East
Memphis Nashville Chattanooga Knoxville	Nashville Chattanooga Knoxville Memphis	Chattanooga Knoxville Nashville Memphis	Knoxville Chattanooga Nashville Memphis

The results would be tabulated as follows:

Pairwise election results
		A
		Memphis	Nashville	Chattanooga	Knoxville
B	Memphis		[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/A	68%	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

Tally

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 since it is the ratio of votes between two candidates that matters.

Sort

The votes are then sorted. The largest majority is "Chattanooga over Knoxville"; 83% of the voters prefer 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

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 away from the winner).

In this example, Nashville is the winner using the ranked-pairs procedure. Nashville is followed by Chattanooga, Knoxville, and Memphis in second, third, and fourth places respectively.

Summary

In the example election, the winner is Nashville. This would be true for any Condorcet method.

Using the First-past-the-post voting and some other systems, Memphis would have won the election by having the most people, even though Nashville won every simulated pairwise election outright. Using Instant-runoff voting in this example would result in Knoxville winning even though more people preferred Nashville over Knoxville.

Criteria

Of the formal voting criteria, the ranked pairs method passes the majority criterion, the monotonicity criterion, the Smith criterion (which implies the Condorcet criterion), the Condorcet loser criterion, and the independence of clones criterion. Ranked pairs fails the consistency criterion and the participation criterion. While ranked pairs is not fully independent of irrelevant alternatives, it still satisfies local independence of irrelevant alternatives.

Independence of irrelevant alternatives

Ranked pairs fails independence of irrelevant alternatives. However, the method adheres to a less strict property, sometimes called independence of Smith-dominated alternatives (ISDA). It says that if one candidate (X) wins an election, and a new alternative (Y) is added, X will win the election if Y is not in the Smith set. ISDA implies the Condorcet criterion.

Comparison table

The following table compares Ranked Pairs with other preferential single-winner election methods:

Comparison of single-winner voting systems
Criterion Method	Majority	Majority loser	Mutual majority	Condorcet winner^{[Tn 1]}	Condorcet loser	Smith^{[Tn 1]}	Smith-IIA^{[Tn 1]}	IIA/LIIA^{[Tn 1]}	Cloneproof	Monotone	Participation	Later-no-harm^{[Tn 1]}	Later-no-help^{[Tn 1]}	No favorite betrayal^{[Tn 1]}	Ballot type
Anti-plurality	No	Yes	No	No	No	No	No	No	No	Yes	Yes	No	No	Yes	Single mark
Approval	Yes	No	No	No	No	No	No	Yes^{[Tn 2]}	Yes	Yes	Yes	No	Yes	Yes	Approvals
Baldwin	Yes	Yes	Yes	Yes	Yes	Yes	No	No	No	No	No	No	No	No	Ranking
Black	Yes	Yes	No	Yes	Yes	No	No	No	No	Yes	No	No	No	No	Ranking
Borda	No	Yes	No	No	Yes	No	No	No	No	Yes	Yes	No	Yes	No	Ranking
Bucklin	Yes	Yes	Yes	No	No	No	No	No	No	Yes	No	No	Yes	No	Ranking
Coombs	Yes	Yes	Yes	No	Yes	No	No	No	No	No	No	No	No	Yes	Ranking
Copeland	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No	No	Yes	No	No	No	No	Ranking
Dodgson	Yes	No	No	Yes	No	No	No	No	No	No	No	No	No	No	Ranking
Highest median	Yes	Yes^{[Tn 3]}	No^{[Tn 4]}	No	No	No	No	Yes^{[Tn 2]}	Yes	Yes	No^{[Tn 5]}	No	Yes	Yes	Scores
Instant-runoff	Yes	Yes	Yes	No	Yes	No	No	No	Yes	No	No	Yes	Yes	No	Ranking
Kemeny–Young	Yes	Yes	Yes	Yes	Yes	Yes	Yes	LIIA Only	No	Yes	No	No	No	No	Ranking
Minimax	Yes	No	No	Yes^{[Tn 6]}	No	No	No	No	No	Yes	No	No^{[Tn 6]}	No	No	Ranking
Nanson	Yes	Yes	Yes	Yes	Yes	Yes	No	No	No	No	No	No	No	No	Ranking
Plurality	Yes	No	No	No	No	No	No	No	No	Yes	Yes	Yes	Yes	No	Single mark
Random ballot^{[Tn 7]}	No	No	No	No	No	No	No	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Single mark
Ranked pairs	Yes	Yes	Yes	Yes	Yes	Yes	Yes	LIIA Only	Yes	Yes	No^{[Tn 5]}	No	No	No	Ranking
Runoff	Yes	Yes	No	No	Yes	No	No	No	No	No	No	Yes	Yes	No	Single mark
Schulze	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No	Yes	Yes	No^{[Tn 5]}	No	No	No	Ranking
Score	No	No	No	No	No	No	No	Yes^{[Tn 2]}	Yes	Yes	Yes	No	Yes	Yes	Scores
Sortition^{[Tn 8]}	No	No	No	No	No	No	No	Yes	No	Yes	Yes	Yes	Yes	Yes	None
STAR	No	Yes	No	No	Yes	No	No	No	No	Yes	No	No	No	No	Scores
Tideman alternative	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No	Yes	No	No	No	No	No	Ranking
Table Notes	^ ^a ^b ^c ^d ^e ^f ^g Condorcet's criterion is incompatible with the consistency, participation, later-no-harm, later-no-help, and sincere favorite criteria. ^ ^a ^b ^c Approval voting, score voting, and majority judgment satisfy IIA if it is assumed that voters rate candidates independently using their own absolute scale. For this to hold, in some elections, some voters must use less than their full voting power despite having meaningful preferences among viable candidates. ^ Majority Judgment may elect a candidate uniquely least-preferred by over half of voters, but it never elects the candidate uniquely bottom-rated by over half of voters. ^ Majority Judgment fails the mutual majority criterion, but satisfies the criterion if the majority ranks the mutually favored set above a given absolute grade and all others below that grade. ^ ^a ^b ^c In Highest median, Ranked Pairs, and Schulze voting, there is always a regret-free, semi-honest ballot for any voter, holding all other ballots constant and assuming they know enough about how others will vote. Under such circumstances, there is always at least one way for a voter to participate without grading any less-preferred candidate above any more-preferred one. ^ ^a ^b A variant of Minimax that counts only pairwise opposition, not opposition minus support, fails the Condorcet criterion and meets later-no-harm. ^ A randomly chosen ballot determines winner. This and closely related methods are of mathematical interest and included here to demonstrate that even unreasonable methods can pass voting method criteria. ^ Where a winner is randomly chosen from the candidates, sortition is included to demonstrate that even non-voting methods can pass some criteria.

Notes

^ In fact, there are different ways how the strength of a victory is measured. This article uses Tideman's original method based on margins of victory.

References

^ ^a ^b Tideman, T. N. (1987-09-01). "Independence of clones as a criterion for voting rules". Social Choice and Welfare. 4 (3): 185–206. doi:10.1007/BF00433944. ISSN 1432-217X. S2CID 122758840.
^ Schulze, Markus (October 2003). "A New Monotonic and Clone-Independent Single-Winner Election Method". Voting matters (www.votingmatters.org.uk). 17. McDougall Trust. Archived from the original on 2020-07-11. Retrieved 2021-02-02.
^ Munger, Charles T. (2022). "The best Condorcet-compatible election method: Ranked Pairs". Constitutional Political Economy. doi:10.1007/s10602-022-09382-w.

External links

Descriptions of ranked-ballot voting methods by Rob LeGrand
Example JS implementation by Asaf Haddad
Pair Ranking Ruby Gem by Bala Paranj
A margin-based PHP Implementation of Tideman's Ranked Pairs
Rust implementation of Ranked Pairs by Cory Dickson

[condorcet-iia-incompatibility-5] ^ ^a ^b ^c ^d ^e ^f ^g Condorcet's criterion is incompatible with the consistency, participation, later-no-harm, later-no-help, and sincere favorite criteria.

[IIA_rating_methods-6] Approval voting, score voting, and majority judgment satisfy IIA if it is assumed that voters rate candidates independently using their own absolute scale. For this to hold, in some elections, some voters must use less than their full voting power despite having meaningful preferences among viable candidates.

[7] Majority Judgment may elect a candidate uniquely least-preferred by over half of voters, but it never elects the candidate uniquely bottom-rated by over half of voters.

[mjmmc-8] Majority Judgment fails the mutual majority criterion, but satisfies the criterion if the majority ranks the mutually favored set above a given absolute grade and all others below that grade.

[semipc-9] In Highest median, Ranked Pairs, and Schulze voting, there is always a regret-free, semi-honest ballot for any voter, holding all other ballots constant and assuming they know enough about how others will vote. Under such circumstances, there is always at least one way for a voter to participate without grading any less-preferred candidate above any more-preferred one.

[MinimaxVarient-10] A variant of Minimax that counts only pairwise opposition, not opposition minus support, fails the Condorcet criterion and meets later-no-harm.

[11] A randomly chosen ballot determines winner. This and closely related methods are of mathematical interest and included here to demonstrate that even unreasonable methods can pass voting method criteria.

[12] Where a winner is randomly chosen from the candidates, sortition is included to demonstrate that even non-voting methods can pass some criteria.

[victorystrength-4] In fact, there are different ways how the strength of a victory is measured. This article uses Tideman's original method based on margins of victory.

[Tideman-1] Tideman, T. N. (1987-09-01). "Independence of clones as a criterion for voting rules". Social Choice and Welfare. 4 (3): 185–206. doi:10.1007/BF00433944. ISSN 1432-217X. S2CID 122758840.

[2] Schulze, Markus (October 2003). "A New Monotonic and Clone-Independent Single-Winner Election Method". Voting matters (www.votingmatters.org.uk). 17. McDougall Trust. Archived from the original on 2020-07-11. Retrieved 2021-02-02.

[3] Munger, Charles T. (2022). "The best Condorcet-compatible election method: Ranked Pairs". Constitutional Political Economy. doi:10.1007/s10602-022-09382-w.

[1]

[2]

[3]

[vs 1]

[Tn 1]

[Tn 2]

[Tn 3]

[Tn 4]

[Tn 5]

[Tn 6]

[Tn 7]

[Tn 8]