Kemeny-Young method
From Wikipedia, the free encyclopedia
The Kemeny-Young method is a voting system that uses preferential ballots, pairwise comparison counts, and sequence scores to identify the most popular choice, and also identify the second-most popular choice, the third-most popular choice, and so on down to the least-popular choice.
The system was first developed by John Kemeny in 1959. Peyton Young later showed that this method was the unique neutral and anonymous method satisfying Pareto efficiency, reinforcement, and local IIA.
VoteFair ranking was created in 1991 without knowledge of the original Kemeny-Young method. Unlike Kemeny's original method, which calculates the number of voters opposing each pairwise comparison, VoteFair ranking calculates the number of voters who agree with each pairwise comparison. The two methods are equivalent because VoteFair ranking looks for the maximum instead of the minimum.
Contents |
[edit] Description
The Kemeny-Young method makes use of preferences expressed on order-of-preference ballots. A voter is allowed to rank more than one choice at the same preference level. A paper-based order-of-preference ballot looks like the type of preferential ballot in which ovals in different columns designate different preference levels. To minimize invalid hand-marked order-of-preference ballots, the VoteFair method interprets unmarked choices as least-preferred, and more than one preference level can be indicated for the same choice, but only the highest-marked preference level (for each choice) is used.
Kemeny-Young calculations are usually done in two steps. (Single-step methods are inefficient.) The first step is to create a matrix or table that counts pairwise voter preferences. The second step is to test all possible order-of-preference sequences, calculate a sequence score for each sequence, and compare the scores. In the VoteFair method each sequence score equals the sum of the pairwise counts that apply to the sequence, and the sequence with the highest score is identified as the overall ranking, from most popular to least popular.
The following two paragraphs (from Ending The Hidden Unfairness In U.S. Elections, used with the author's permission, and available for public use) describe VoteFair ranking in a way that can be used in legal documents for small organizations:
After the candidates for the offices have been nominated, the officers of this organization shall be elected as follows. Eligible members shall be given ballots that contain the names of the candidates grouped according to their desired office. To the right of each name shall be markable locations, such as empty ovals, arranged in columns labeled First choice, Second choice, Third choice, and so on, progressing from left to right. Each voter shall mark these locations on their ballot to indicate their first choice, second choice, third choice, and so on for each office. The left-most mark among multiple marks given to the same candidate shall be used as the voter’s preference level. More than one candidate can be marked at the same preference level. The absence of a mark for a candidate indicates the lowest preference. VoteFair ranking, as explained below, shall be used to identify the most popular candidate for each office, and the most popular candidate for each office shall win the election for that office. If there is a tie for first place, the counting of votes and the VoteFair ranking shall be repeated. If the recount also indicates a tie, the outgoing Treasurer (or some other designated official) shall choose how to resolve the tie.
VoteFair ranking shall be done using software (such as accessible at www.VoteFair.org) that performs the following calculations. The preferences indicated in the ballots are counted to produce a tally table in which all the possible pairs of candidates are listed, one number for each pair indicates the number of voters who prefer one candidate in the pair over the other candidate in the pair, another number for each pair indicates the number of voters who have the opposite preference for these two candidates, and a third number for each pair indicates the number of voters who express no preference between the two candidates. Using a computer, each possible sequence of candidates is considered, where a sequence consists of one of the candidates being regarded as the most popular candidate, another candidate being regarded as the second-most popular candidate, and so on. For each such sequence the numbers in the tally table that apply to that sequence are added together to produce a sequence score for this sequence. The sequence that has the highest sequence score indicates the overall order of preference for the candidates. If there is more than one sequence that has the same highest score, the sequences with this score shall be analyzed to identify one or more ties at one or more preference levels.
[edit] Example
Imagine that the population of Tennessee, a state in the United States, is voting on the location of its capital. The population of Tennessee is concentrated around its four major cities, which are spread throughout the state. For this example, suppose that the entire electorate lives in one of these four cities, and that they would like the capital to be established as close to their city as possible.
The candidates for the capital are:
- Memphis, the state's largest city, with 42% of the voters, but located far from the other cities
- Nashville, with 26% of the voters
- Knoxville, with 17% of the voters
- Chattanooga, with 15% of the voters
The preferences of the voters would be divided like this:
| 42% of voters (close to Memphis) |
26% of voters (close to Nashville) |
15% of voters (close to Chattanooga) |
17% of voters (close to Knoxville) |
|---|---|---|---|
|
|
|
|
This matrix summarizes the corresponding pairwise comparison counts:
| Memphis | Nashville | Chattanooga | Knoxville | |
|---|---|---|---|---|
| Memphis | - | 42% | 42% | 42% |
| Nashville | 58% | - | 68% | 68% |
| Chattanooga | 58% | 32% | - | 83% |
| Knoxville | 58% | 32% | 17% | - |
The VoteFair method arranges the pairwise comparison counts in the following tally table:
| All possible pairs of choice names |
Number of votes with indicated preference | ||
| Prefer X over Y | Equal preference | Prefer Y over X | |
| X = Memphis Y = Nashville |
42% | 0 | 58% |
| X = Memphis Y = Chattanooga |
42% | 0 | 58% |
| X = Memphis Y = Knoxville |
42% | 0 | 58% |
| X = Nashville Y = Chattanooga |
68% | 0 | 32% |
| X = Nashville Y = Knoxville |
68% | 0 | 32% |
| X = Chattanooga Y = Knoxville |
83% | 0 | 17% |
In the VoteFair method the sequence score for the sequence Memphis first, Nashville second, Chattanooga third, and Knoxville fourth equals (the unit-less number) 345, which is the sum of the following annotated numbers.
- 42% (of the voters) prefer Memphis over Nashville
- 42% prefer Memphis over Chattanooga
- 42% prefer Memphis over Knoxville
- 68% prefer Nashville over Chattanooga
- 68% prefer Nashville over Knoxville
- 83% prefer Chattanooga over Knoxville
The following table lists all the VoteFair sequence scores.
| First choice |
Second choice |
Third choice |
Fourth choice |
Sequence score |
| Memphis | Nashville | Chattanooga | Knoxville | 345 |
| Memphis | Nashville | Knoxville | Chattanooga | 279 |
| Memphis | Chattanooga | Nashville | Knoxville | 309 |
| Memphis | Chattanooga | Knoxville | Nashville | 273 |
| Memphis | Knoxville | Nashville | Chattanooga | 243 |
| Memphis | Knoxville | Chattanooga | Nashville | 207 |
| Nashville | Memphis | Chattanooga | Knoxville | 361 |
| Nashville | Memphis | Knoxville | Chattanooga | 295 |
| Nashville | Chattanooga | Memphis | Knoxville | 377 |
| Nashville | Chattanooga | Knoxville | Memphis | 393 |
| Nashville | Knoxville | Memphis | Chattanooga | 311 |
| Nashville | Knoxville | Chattanooga | Memphis | 327 |
| Chattanooga | Memphis | Nashville | Knoxville | 325 |
| Chattanooga | Memphis | Knoxville | Nashville | 289 |
| Chattanooga | Nashville | Memphis | Knoxville | 341 |
| Chattanooga | Nashville | Knoxville | Memphis | 357 |
| Chattanooga | Knoxville | Memphis | Nashville | 305 |
| Chattanooga | Knoxville | Nashville | Memphis | 321 |
| Knoxville | Memphis | Nashville | Chattanooga | 259 |
| Knoxville | Memphis | Chattanooga | Nashville | 223 |
| Knoxville | Nashville | Memphis | Chattanooga | 275 |
| Knoxville | Nashville | Chattanooga | Memphis | 291 |
| Knoxville | Chattanooga | Memphis | Nashville | 239 |
| Knoxville | Chattanooga | Nashville | Memphis | 255 |
The highest sequence score is 393, and this score is associated with the following sequence, so this is the winning preference order.
| Preference order |
Choice |
| First | Nashville |
| Second | Chattanooga |
| Third | Knoxville |
| Fourth | Memphis |
If a single winner is needed, the first choice, Nashville, is chosen. (In this example Nashville is the Condorcet winner.)
[edit] Characteristics
The Kemeny-Young method is a Condorcet method, and as such always chooses the Condorcet winner if there is one.
In all cases that do not result in an exact tie, the Kemeny-Young method identifies a most-popular choice, second-most popular choice, and so on.
A tie can occur at any preference level. Except in some cases where circular ambiguities are involved, the Kemeny-Young method only produces a tie at a preference level when the number of voters with one preference exactly matches the number of voters with the opposite preference.
In cases that do not involve circular ambiguity, the choice identified as most popular is the choice preferred by the majority of voters who express a preference between the most popular choice and each other choice.
The following table summarizes the desired criteria achieved by the Kemeny-Young method.
| Criterion | Satisfied? | Comments |
| Universality | Yes | The method identifies the overall order of preference for all the choices. It does this for all possible sets of voter preferences, involves no randomness, and always produces the same result for the same set of voter preferences. Universality is a significant advantage over voting systems that only attempt to identify a single winner. |
| Majority criterion | Yes | In almost all cases, the overall most popular choice is preferred by a majority of voters who express a preference between this choice and any other choice. In addition, in almost all cases, each successively ranked choice is preferred over lower-ranked choices by a majority of voters (who express a preference). |
| Monotonicity | Yes | If a voter increases a choice's preference level, the ranking result either does not change or the promoted choice increases in overall popularity. |
| Independence of irrelevant alternatives | No* | In all cases that do not involve circular ambiguity, adding or withdrawing a choice does not change the overall ranking of the other choices. (An example of a case involving both circular ambiguity and a dependence on irrelevant alternatives is when 5 voters prefer A then B then C, and 4 voters prefer B then C then A, and 2 voters prefer C then A then B, because withdrawing choice B causes C to win instead of A.) |
| Invulnerability to burying | No* | In all cases that do not involve circular ambiguity, if a voter moves a disliked choice to a lower preference level, this change cannot increase the overall preference for the choices preferred by that voter. The only consequence to burying is a possible overall preference increase for the choices that are ranked at preference levels between the buried choice's original and buried preference levels. |
| Invulnerability to push-over | No* | In all cases that do not involve circular ambiguity, ranking a weak choice higher does not increase the ranking of any other choice; it only increases the chances of the weak candidate being ranked at a higher preference level. |
| Invulnerability to compromising | No* | In all cases that do not involve circular ambiguity, moving a preferred choice to a lower level does not benefit the choices that result in being moved to a higher preference; it only increases the chances of the preferred choice being ranked at a lower preference level. |
| Non-imposition | Yes | There are voter preferences that can yield every possible overall order-of-preference result, including ties at any combination of preference levels. |
| Pareto efficiency | Yes | Any pairwise preference expressed by every voter results in the preferred choice being ranked higher than the less-preferred choice. |
| Non-dictatorship | Yes | A single voter cannot control the outcome beyond what can be achieved by any other voter. |
* This criterion is satisfied for all cases that do not involve a circular ambiguity, and in some cases that do.
[edit] References
- ↑ John Kemeny, "Mathematics without numbers", Daedalus, Vol. 88 (1959), pp. 571--591.
- ↑ H. Peyton Young, "Optimal voting rules", Journal of Economic Perspectives, Vol. 9 No. 1 (1995), pp. 51–64.
- ↑ Richard Fobes, Ending The Hidden Unfairness In U.S. Elections (2006) describes VoteFair ranking (and variations of it) in detail, provides illustrated examples that demonstrate its use, and argues that VoteFair ranking can be used to improve the fairness of government elections and other voting situations.
- Richard Fobes, The Creative Problem Solver's Toolbox (1993) contains the first published description of VoteFair ranking (on pages 223-225).
- Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam, "Improved bounds for computing Kemeny rankings, 2006.
[edit] External links
- www.VoteFair.org A website that provides free access to VoteFair ranking calculations. For comparison the calculations also identify the winning choice according to plurality, Condorcet, Borda-count, and other voting methods.
- www.FullRanking.com A free online tool for using VoteFair ranking to rank priorities, budget categories, and more.
