Part of the Politics series |
Electoral systems |
---|
Politics portal |
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. This is a Condorcet method because if there is a Condorcet winner it is always the most popular choice.
The system was developed[1] by John Kemeny in 1959. In 1978, Peyton Young and Arthur Levenglick showed [2] that this method was the unique neutral and anonymous method satisfying Pareto efficiency, reinforcement, and local IIA. In 1991 Richard Fobes independently rediscovered the method, calling it "VoteFair popularity ranking".[3]
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, unmarked choices should be interpreted as least-preferred, and more than one preference level should be possible for the same choice, but only the highest-marked preference level (for each choice) should be used.
Kemeny-Young calculations are usually done in two steps. 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 variation, 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 original Kemeny method uses pairwise counts of voters who oppose each pairwise order, and the lowest sequence score is identified.
The following two paragraphs (from Ending The Hidden Unfairness In U.S. Elections[4], used with the author's permission, and available for public use) describe the Kemeny-Young method 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.
Example
Suppose that Tennessee is holding an election on the location of its capital. The population is concentrated around four major cities. All voters want the capital to be as close to them as possible. The options are:
- Memphis, the largest city, but far from the others (42% of voters)
- Nashville, near the center of the state (26% of voters)
- Chattanooga, somewhat east (15% of voters)
- Knoxville, far to the northeast (17% of voters)
The preferences of each region's voters are:
42% of voters Far-West |
26% of voters Center |
15% of voters Center-East |
17% of voters Far-East |
---|---|---|---|
|
|
|
|
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 Kemeny-Young 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% |
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 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.)
Characteristics
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.
The following table summarizes the fairness criteria achieved by the Kemeny-Young method.
Criterion | Description | Satisfied? |
Universality | Identifies the overall order of preference for all the choices. The method 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. | Yes |
Condorcet criterion | If there is a choice that wins all pairwise contests, then this choice wins. | Yes |
Majority criterion | If a majority of voters strictly prefer choice X to every other choice, then choice X is identified as the most popular. | Yes |
Pareto efficiency | Any pairwise preference expressed by every voter results in the preferred choice being ranked higher than the less-preferred choice. | Yes |
Non-imposition | There are voter preferences that can yield every possible overall order-of-preference result, including ties at any combination of preference levels. | Yes |
Monotonicity | If voters increase a choice's preference level, the ranking result either does not change or the promoted choice increases in overall popularity. | Yes |
Reinforcement | If all the ballots are divided into two separate races and the same complete ranking of choices is calculated for both races, the same complete ranking is also produced when all the ballots are combined. | Yes |
Consistency | If all the ballots are divided into separate races and choice X is identified as the most popular in every such race, then choice X is not necessarily the most popular when all the ballots are combined. | No |
Independence of irrelevant alternatives | Adding or withdrawing choice X does not change a result in which choice Y is identified as most popular.[1] | No |
Independence of clones | Offering a larger number of similar choices, instead of offering only a single such choice, decreases the probability that one of these choices is identified as most popular (fratricide). | No |
Invulnerability to burying | A voter can displace a choice from most popular by giving the choice an insincerely low ranking. | No |
Later-no-harm | Ranking an additional choice (that was otherwise unranked) can displace a choice from being identified as the most popular. | No |
Invulnerability to compromising | A voter can cause a choice to become the most popular by giving the choice an insincerely high ranking. | No |
Invulnerability to push-over | A voter can cause choice X to become the most popular by giving choice Y an insincerely high ranking. | No |
Participation | Adding ballots that rank choice X over choice Y can cause choice Y, instead of choice X, to become most popular. | No |
Schwartz | The choice identified as most popular may be outside the Schwartz set. | No |
Non-dictatorship | A single voter cannot control the outcome in all cases. | Yes |
Polynomial runtime[5] | The full calculation method can determine the most popular choice in a runtime that is polynomial in the number of choices. | No |
^ 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.
Calculation methods
Calculating all sequence scores requires time proportional to N!, where N is the number of choices. Although one need not compute scores to find the winner, any algorithm finding the winner requires superpolynomial time (unless P=NP). Nevertheless, fast calculation methods based on linear programming allow the computation of full rankings for votes with as many as 40 choices.[5]
References
- ^ John Kemeny, "Mathematics without numbers", Daedalus 88 (1959), pp. 577–591.
- ^ H. P. Young and A. Levenglick, "A Consistent Extension of Condorcet's Election Principle", SIAM Journal on Applied Mathematics 35, no. 2 (1978), pp. 285–300.
- ^ Richard Fobes, The Creative Problem Solver's Toolbox (1993), pp. 223-225.
- ^ Richard Fobes, Ending The Hidden Unfairness In U.S. Elections (2006)
- ^ a b Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam, "Improved bounds for computing Kemeny rankings" (2006).
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.