Ranked Pairs: Difference between revisions
Cleaned up Smith compliance proof, and elaborated on what tiebreaker is most commonly associated with RP.
imported>WikipediaBot m (importing text from Wikipedia) |
(Cleaned up Smith compliance proof, and elaborated on what tiebreaker is most commonly associated with RP.) |
||
| (33 intermediate revisions by 13 users not shown) | |||
Line 1:
{{Wikipedia|Ranked pairs}}
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 ==
The
# 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 the largest margin of victory first to smallest last.
# "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 [[Ranked pairs#Notes|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 ===
Line 32 ⟶ 29:
candidates are assumed to be equally worse than the stated candidates.
Once
If "Vxy" is the number of Votes that rank x over y, then
"x" wins if Vxy > Vyx, and "y" wins if Vyx > Vxy.
Line 69 ⟶ 66:
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:
<table class="wikitable" border="1">
<tr>
<td>
Line 133 ⟶ 130:
First, list every pair, and determine the winner:
{| class="wikitable" border="1"
!Pair!!Winner
|-
Line 167 ⟶ 164:
Thus, the pairs from above would be sorted this way:
{| class="wikitable" border="1"
!Pair!!Winner
|-
Line 204 ⟶ 201:
the winner).
[[Image:Tennessee-vote.
In this example, Nashville is the winner using RP.
Line 210 ⟶ 207:
=== Ambiguity Resolution Example ===
Let's say there was an ambiguity. For a simple situation involving
* A > B 68%
Line 223 ⟶ 220:
Therefore, A is the winner.
=== A Limit case ===
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.
== Advantages and disadvantages ==
Ranked Pairs is [[Smith-efficient]], because every Smith set member pairwise beats everybody outside the set. As a result, every defeat by a Smith set member over a non-Smith candidate is locked before any opposite-direction defeat, so a non-Smith candidate can never win.
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.
While Ranked Pairs behaves similarly to [[Schulze]], Ranked Pairs passes [[local independence of irrelevant alternatives]] whereas Schulze does not. Some authors argue that the Ranked Pairs method is more intuitive and easier to understand than Schulze as well.<ref name="Munger 2023 pp. 434–444">{{cite journal | last=Munger | first=Charles T. | title=The best Condorcet-compatible election method: Ranked Pairs | journal=Constitutional Political Economy | volume=34 | issue=3 | date=2023 | issn=1043-4062 | doi=10.1007/s10602-022-09382-w | pages=434–444}}</ref>
One disadvantage of Ranked Pairs is there's no easy way to detect ties for first place, as determining whether there exists a way to break ties between pairwise victories so that a given candidate wins is NP-complete.<ref name="Brill">{{cite journal | last=Brill | first=Markus | last2=Fischer | first2=Felix | title=The Price of Neutrality for the Ranked Pairs Method | journal=Proceedings of the AAAI Conference on Artificial Intelligence | publisher=Association for the Advancement of Artificial Intelligence (AAAI) | volume=26 | issue=1 | date=2012-07-26 | issn=2374-3468 | doi=10.1609/aaai.v26i1.8250 | pages=1299–1305}}</ref> However, ties can still be broken fairly and efficiently using some secondary method that doesn't compromise Ranked Pairs' properties. The most common such tiebreaker is [[random voter hierarchy]], a generalization of [[random ballot]]. Cardinal methods like [[Graduated Majority Judgment|highest medians]] can also be used, at the cost of slightly weakening properties like ranked [[clone independence]].
== Notes ==
The RP winner can be found using only a pairwise comparison table. Example: <blockquote>4 A>B>C
3 B>C>A
5 C>A>B </blockquote>The pairwise comparison table looks like this (victories are bolded, defeats are underlined):
{| class="wikitable"
|+
!
!A
!B
!C
|-
|A
| -
|'''9'''
|<u>4</u>
|-
|B
|<u>3</u>
| -
|'''7'''
|-
|C
|'''8'''
|<u>5</u>
| -
|}
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:
{| class="wikitable"
!
!C
!A
!B
|-
|C
| -
|'''8'''
|<u><s><small>5</small></s></u>
|-
|A
|<u>4</u>
| -
|'''9'''
|-
|B
|'''<s>7</s>'''
|<u>3</u>
| -
|}
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).
== References ==
<references />
== External Resources ==
* [http://condorcet.org/rp Ranked Pairs]
* [http://www.alumni.caltech.edu/~seppley The Maximize Affirmed Majorities voting procedure (MAM)]
* [http://radicalcentrism.org/majority_voting.html Maximum Majority Voting]
* [
* [http://fc.antioch.edu/~
[[Category:Single-winner voting methods]]
[[Category:Smith-efficient Condorcet methods]]
[[Category:Defeat-dropping Condorcet methods]]
[[Category:Monotonic_electoral_systems]]
[[Category:Ranked voting methods]]
[[Category:Condorcet methods]]
[[Category:Clone-independent electoral systems]]
{{fromwikipedia}}
| |||