Condorcet ranking: Difference between revisions
no edit summary
(→Notes) |
No edit summary |
||
| (10 intermediate revisions by the same user not shown) | |||
Line 1:
A '''Condorcet ranking''' is an ordering of candidates such that every candidate at a given rank [[pairwise beat]]<nowiki/>s every lower-ranked candidate. In other words:
* The [[Condorcet method | Condorcet]] winner, if one exists, is ranked first.
Line 12:
* The tertiary Condorcet loser (the new Condorcet loser if the Condorcet loser and secondary Condorcet loser are eliminated), if one exists, is ranked third-to-last.
* etc.
Often the definition of a Condorcet ranking is generalized so that candidates with [[Pairwise counting#Terminology|pairwise ties]] with each other are ranked equally i.e:<blockquote>2 A
2 B
1 C</blockquote>A and B pairwise tie (2 vs. 2), but both beat C (2 vs. 1), so a generalized (or perhaps "weak") Condorcet ranking would be A=B>C.
When there are [[Condorcet cycle|Condorcet cycles]], there won't be a Condorcet ranking (though it may still be possible to fill in certain parts of the [[Order of finish|order of finish]] i.e. if 5 candidates pairwise beat all others, with 3 candidates in a cycle and pairwise beaten by the 5, but otherwise pairwise beating all others, and 2 candidates pairwise beaten by all others except pairwise tied with each other, then the 5 candidates are in the first 5 places of the Condorcet ranking, with the 2 candidates both in 9th place, with the 3 candidates in the cycle guaranteed to be ranked either 6th, 7th, or 8th, depending on which [[Condorcet completion method]] is used).
The most direct generalization of the Condorcet ranking to handle Condorcet cycles is the Smith set ranking, which is meant to ensure that anytime the candidates can be divided into two groups such that everyone in the first group beats everyone in the second group, then everyone in the first group is ranked higher.
The fastest way to find the Condorcet (and Smith) ranking is to find the [[Copeland]] ranking. If every candidate at a given rank has only one more pairwise victory than all candidates at the next-lowest rank (i.e. the number of pairwise victories per candidates incrementally decreases as you go down the order), then there is a Condorcet ranking, otherwise there is only a Smith ranking.
== Smith set ranking ==
[[File:Finding smith set ranking.png|thumb|543x543px|An example of finding the generalized Smith set ranking using the [[Pairwise counting|pairwise matrix]]. One way to better visualize it is to imagine the arrow starting from the top left and traveling down one cell at at a time, creating a box around a group of candidates any time there are only pairwise victories to the right of the cells that are enclosed by the arrow. For further visual clarity, imagine a green background on the cells with pairwise victories; the arrow tries to cover the fewest cells necessary for there to be an all-green background to the right. ]]
[[File:Alternative way to find Smith set ranking.png|thumb|633x633px]]
A '''Smith ranking''' ('''Smith set ranking''') is the same as a Condorcet ranking, except instead of being defined in terms of the Condorcet winner and Condorcet loser, it is defined in terms of the [[Smith set]] and [[Smith set#Smith loser set|Smith loser set]]. When there is a multi-member Smith set, the candidates in the Smith set may be ranked in any order so long as they are all ranked above non-Smith set candidates, with the same applying for the Smith loser set candidates with regards to being ranked lower than non-Smith loser set candidates.<ref>{{Cite web|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.200.8245&rep=rep1&type=pdf|title=AN EXTENSION OF THE CONDORCET CRITERION AND KEMENY ORDERS|last=|first=|date=|website=|url-status=live|archive-url=|archive-date=|access-date=|quote=A first objective of this paper is to propose a formalization of this idea, called the Extended
Condorcet Criterion (XCC). In essence, it says that if the set of alternatives can be partitioned in such a
way that all members of a subset of this partition defeat all alternatives belonging to subsets with a higher
index, then the former should obtain a better rank than the latter.}}</ref> Each consecutive Smith set can be referred to as the 1st, 2nd, 3rd, etc. or the primary, secondary, tertiary, etc. Smith set.
When there is a Condorcet ranking (one doesn't always exist), the Smith ranking will be the same as the Condorcet ranking. There will always be at least one Smith ranking, and it is possible to have more than one (each of which will differ only on the order in which Smith or Smith loser candidates are ranked). The simplest way to find a Smith ranking is to find the [[Copeland's method|Copeland]] ranking (the ranking of all candidates such that the candidates with the most ([[Pairwise counting#Terminology|pairwise victories]] minus pairwise defeats) are ranked first, the candidates with the second-most (pairwise victories minus pairwise defeats) are ranked second, etc.)
Line 27 ⟶ 43:
1 C</blockquote>
The generalized Smith ranking is A=B>C, meaning A and B are tied for 1st place, and C is in 2nd place. Note that any of A>B=C, B>A=C, or A=B>C would be valid Smith rankings, but only the third is a generalized Smith ranking; this is because the generalized Smith ranking assumes neutrality as to who is superior within the Smith and Smith loser sets. This may make it an appropriate tool to demonstrate how various groups of candidates would compare across all Smith-efficient methods. There will always be one and only one generalized Smith set ranking. There is an ambiguity to consider in that if, for example, there are five candidates, with three in the 1st Smith set and two in the 2nd Smith set, then the two 2nd Smith set candidates can be considered to either be in 2nd place (because they are worse than all the 1st place candidates but better than all other candidates) or 4th place (because in order for them to be the best candidates in the election i.e. 1st place, at least 3 candidates considered better than them must be removed from the election).
Another example: <blockquote>1 A>B>C
Line 234 ⟶ 250:
== Notes ==
Smith set rankings can be given additional context by showing for each Smith set the weakest pairwise victory anyone in that Smith set has against anyone in a lower-ranked Smith set; one generalized way to show strength of victory is by % of votes earned in the matchup, which will always be over 50% for the pairwise winner. So, for example, if there are 4 candidates, with 3 of them in a cycle and each of them having a 65%, 60%, and 55% victory respectively against the fourth candidate, then 55% could be used to describe the minimum strength of all of the candidates in the set against the lower-ranked candidate.
The generalized Smith ranking can also be found by finding all candidates in the Smith set, equally ranking each of them, then eliminating all of them and finding the secondary Smith set (the Smith set now that the original Smith set has been eliminated) and equally ranking each of them lower than the candidates in the Smith set, and repeating until all candidates are ranked.
Line 338 ⟶ 356:
!Sp, Pa, Sa
| colspan="3" |SpongeBob, Patrick, Sandy (2-0)
|
|-
!
Line 345 ⟶ 363:
|3 Losses →
1 Win ↓
|Minimum of
51% margin
|-
!
Line 353 ⟶ 373:
|10 (Sq) –
9 (Pl)
|Minimum of
62% margin
|}
Line 361 ⟶ 383:
#
This makes it more ambiguous as to how to record the exact margins of some [[Pairwise counting#Terminology|pairwise matchups]] where groups of candidates are involved, as even if all candidates in a group of candidates pairwise beat all candidates not in the group, they may each do so with different margins. One way to do so is to show the minimum % of votes each candidate gets in the head-to-head matchups against all lower/worse Smith set candidates i.e. if A, B and C are in the Smith set, with D in the 2nd Smith set, and C has the smallest-size majority by %, say, 54%, then 54% can be used to indicate the minimum quality of all the 1st Smith set candidates against D.
Once the Smith set ranking is found, a number of [[Smith-efficient]] [[Condorcet methods]]' rankings can be computed from it:
* Several [[:Category:Defeat-dropping Condorcet methods|defeat-dropping Condorcet methods]]' rankings can be computed. For example, [[Schulze]] works by looking for a Schwartz set ranking. Within each Schwartz set, the weakest defeat (as measured using [[defeat strength]]) is turned into a pairwise tie, a smaller Schwartz set is found if possible, and repeat until all remaining candidates pairwise tie. These candidates are sorted to the top of the original Schwartz set, and the process repeated to find the ranking for any other candidates.
*[[Smith//Score]] and [[Smith//Approval]] order the candidates in each Smith set by number of points/approvals. This can be easily done by showing each candidate's points in the cell comparing them to themselves.
*[[Kemeny-Young]]
Theoretical note:
Line 373 ⟶ 402:
A [[Pairwise counting#Terminology|pairwise beats]] B pairwise beats C pairwise beats D pairwise beats A, so all candidates here are in the Smith set. However, C is unanimously preferred to D, so the Pareto-satisfying generalized Smith ranking would acknowledge that D must be at a lower rank than C, whereas the regular generalized Smith ranking would simply be A=B=C=D.
[[Category:Voting theory]]
[[Category:Condorcet-related concepts]]
| |||