Condorcet ranking

From electowiki
(Redirected from Smith set ranking)

A Condorcet ranking is an ordering of candidates such that every candidate at a given rank pairwise beats every lower-ranked candidate. In other words:

  • The Condorcet winner, if one exists, is ranked first.
  • The secondary Condorcet winner (the new Condorcet winner if the Condorcet winner is eliminated), if one exists, is ranked second.
  • The tertiary Condorcet winner (the new Condorcet winner if the Condorcet winner and the secondary Condorcet winner are eliminated), if one exists, is ranked third.
  • etc.

and

  • The Condorcet loser, if one exists, is ranked last.
  • The secondary Condorcet loser (the new Condorcet loser if the Condorcet loser is eliminated), if one exists, is ranked next-to-last.
  • 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 ties with each other are ranked equally i.e:
2 A

2 B

1 C
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 cycles, there won't be a Condorcet ranking (though it may still be possible to fill in certain parts of the 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

An example of finding the generalized Smith set ranking using the 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.

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 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.[1] 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 ranking (the ranking of all candidates such that the candidates with the most (pairwise victories minus pairwise defeats) are ranked first, the candidates with the second-most (pairwise victories minus pairwise defeats) are ranked second, etc.)

The generalized Smith ranking is a Smith ranking where all candidates in each consecutively ranked Smith set are equally ranked and the same holds for each consecutively ranked Smith loser set; for example:

2 A

2 B

1 C

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:
1 A>B>C

1 B>C>A

1 C>A>B

1 D>E

1 E>D

1 F=G
Pairwise comparison table (candidate on left is preferred by # of voters in their cell over candidate on top) Pairwise victories are bolded, defeats are underlined, ties are struck through Groups of candidates who pairwise beat all other lower groups are italicized; every odd group's numbers are made bigger and even group's numbers smaller
A B C D E F G
A - 2 1 3 3 3 3
B 1 - 2 3 3 3 3
C 2 1 - 3 3 3 3
D 2 2 2 - 1 2 2
E 2 2 2 1 - 2 2
F 1 1 1 1 1 - 0
G 1 1 1 1 1 0 -

The generalized Smith set ranking can be found by sorting the candidates in the pairwise comparison table based on their Copeland scores (or in any way that follows a Smith ranking), and then starting at the top left cell comparing two candidates, checking if all the cells to the right of the cell that is being looked at show pairwise victories; if so, the candidate to the left of the cell being looked at is in the Smith set, if not, repeatedly go one cell down and one cell to the right until at the cell directly below the cell furthest to the right in the top row with a pairwise tie or defeat, covering all cells from the top left cell to the bottom right cell, and checking again. Once all the cells to the right of the cells being looked at (the "covered" cells) show pairwise victories, all candidates to the left of the covered cells are in the Smith set. Go one cell down and one cell to the right, ignore all of the previously covered cells, and repeat the process to find the secondary Smith set, then repeat for the tertiary Smith set, etc. Then rank all candidates in the Smith set 1st, all candidates in the secondary Smith set 2nd, etc.

As an example, here, starting at the top left pairwise comparison cell (the A>A cell), we see a pairwise defeat or tie furthest to the right in the 3rd cell in the top pairwise comparison row (the A>C cell), so we cover all cells from the top left cell to the 3rd cell down and 3rd cell from the left:

A B C D E F G
A - 2 1 3 3 3 3
B 1 - 2 3 3 3 3
C 2 1 - 3 3 3 3

and we now see only pairwise victories to the right of all the covered cells (all the cells from A>A to C>C, here shown in larger font), so A, B, and C are in the Smith set. Going one cell down and one cell to the right, we ignore all previously covered cells and so now the top left cell of the covered cells is the D>D cell. We see a pairwise defeat or tie furthest to the right of this cell in the D>E cell, so we go one cell down and one cell to the right, making the E>E cell the bottom right cell of the covered cells.

D 2 2 2 - 1 2 2
E 2 2 2 1 - 2 2

Now, all cells to the right of the covered cells (the covered cells are all cells from the D>D cell to the E>E cell, which are the cells from the 5th cell in the top row to the 6th cell in the bottom row) show pairwise victories, so D and E are in the secondary Smith set. Going one cell down and one cell to the right, and again ignoring all previously covered cells, the top left cell of the now-covered cells is F>F. The only cell to its right shows a pairwise tie, so we automatically know that whichever candidate is in the row below F is also in the tertiary Smith set with F.

F 1 1 1 1 1 - 0
G 1 1 1 1 1 0 -

F and G are in the tertiary Smith set.

Thus, the generalized Smith set ranking is A=B=C>D=E>F=G, or (A, B, C) tied for 1st, (D, E) tied for 2nd, and (F, G) tied for 3rd place. In terms of pairwise comparisons, this is because 3 voters prefer (A, B, C) over all others (and at most 2 voters prefer any other candidates over (A, B, C)) but no smaller subset of (A, B, C) can say the same, 2 voters prefer (D, E) above all others when ignoring (A, B, C) (and at most 1 voter prefers other unignored candidates over (D, E)) but no smaller subset of (D, E) can say the same, and 1 voter prefers (F, G) above all others when ignoring (A, B, C, D, E) (and no voters prefer any other unignored candidates over (F, G)) but no smaller subset of (F, G) can say the same. Notice that when looking at the pairwise comparison table for the generalized Smith ranking that the consecutive Smith sets can essentially be seen by looking at which groups of candidates have pairwise victories over all other candidates when ignoring the pairwise matchups between candidates in the group.

One way to design the pairwise comparison table to show the generalized Smith set ranking would be to put all candidates in each consecutive Smith set on their own line, like so:

A, B, C D, E F, G
A, B, C - Win Win
D, E Loss - Win
F, G Loss Loss -

Another way to find the generalized Smith set ranking is to find the Copeland ranking, put all candidates ranked 1st by Copeland in the Smith set and thus equally rank them 1st in the generalized Smith set ranking, and then check if any other candidates can pairwise beat or tie any of the candidates in the Smith set; if any of them can, then all candidates ranked at the lowest rank of any of them based on the Copeland ranking or above is also in the Smith set, and the process repeats until at some point, none of them can, then the candidates at the next Copeland ranking after the lowest-Copeland-ranked Smith set candidate are all part of the secondary Smith set and thus equally ranked 2nd in the generalized Smith set ranking. Repeat until all candidates are equally ranked within their consecutive Smith set.

So for example, if 3 candidates are ranked 1st in Copeland, they are part of the Smith set, and if there are several candidates ranked lower than them by Copeland who pairwise beat or tie any of them, take the lowest ranked of them based on Copeland (suppose that candidate was ranked 5th by Copeland) and add all candidates ranked 5th or above by Copeland into the Smith set. Supposing no candidates pairwise beat or tie any of the candidates newly added into the Smith set, all candidates ranked 6th by Copeland are part of the secondary Smith set, and the process repeats to see who is part of the secondary Smith set, then tertiary Smith set, etc.

Notes

Condorcet methods that always produce Condorcet rankings (and also Smith rankings) include Copeland's method, Pairwise Sorted Methods, Schulze, Ranked Pairs, and Kemeny-Young. Instant Pairwise Elimination is a non-Condorcet method that always produces a Condorcet ranking when one exists.

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.

Smith or Condorcet rankings can be visualized in the following form:

             
wi JS DS KW BK AM
  AM Andy

Montroll (5–0)

5 Wins ↓
  BK Bob

Kiss (4–1)

1 Loss →

↓ 4 Wins

4067 (AM) –

3477 (BK)

  KW Kurt

Wright (3–2)

2 Losses →

3 Wins ↓

4314 (BK) –

4064 (KW)

4597 (AM) –

3668 (KW)

  DS Dan

Smith (2–3)

3 Losses →

2 Wins ↓

3975 (KW) –

3793 (DS)

3946 (BK) –

3577 (DS)

4573 (AM) –

2998 (DS)

  JS James

Simpson (1–4)

4 Losses →

1 Win ↓

5573 (DS) –

721 (JS)

5274 (KW) –

1309 (JS)

5517 (BK) –

845 (JS)

6267 (AM) –

591 (JS)

  wi Write-in (0–5) 5 Losses → 3338 (JS) –

165 (wi)

6057 (DS) –

117 (wi)

6063 (KW) –

163 (wi)

6149 (BK) –

116 (wi)

6658 (AM) –

104 (wi)

With generalized Smith rankings in particular, some rows would have to be groups of candidates, rather than solely individual candidates. Hypothetical example:

       
Pl Sq Sp, Pa, Sa
  Sp, Pa, Sa SpongeBob, Patrick, Sandy (2-0) 2 Wins ↓
  Sq Squidward (1-3) 3 Losses →

1 Win ↓

Minimum of

51% margin

  Pl Plankton (0-4) 5 Losses → 10 (Sq) –

9 (Pl)

Minimum of

62% margin

This makes it more ambiguous as to how to record the exact margins of some 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 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:

Note that a variant of generalized Smith rankings can be created to address the unanimity/Pareto criterion. For example:
34 A>B>C>D

33 B>C>D>A

33 C>D>A>B

A 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.

  1. "AN EXTENSION OF THE CONDORCET CRITERION AND KEMENY ORDERS". 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. line feed character in |quote= at position 96 (help)