Ranked Pairs: Difference between revisions
Content added Content deleted
(Cleaned up Smith compliance proof, and elaborated on what tiebreaker is most commonly associated with RP.) |
|||
| Line 226: | Line 226: | ||
== Advantages and disadvantages == |
== Advantages and disadvantages == |
||
Ranked Pairs is [[Smith-efficient]], because |
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. |
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. |
||
| Line 232: | Line 232: | ||
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> |
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 |
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 == |
== Notes == |
||