The Kemeny method is an electoral system that uses ranked ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.
This method assigns a score for each possible sequence, where each sequence considers which choice might be most popular, which choice might be second-most popular, which choice might be third-most popular, and so on down to which choice might be least-popular. The sequence that has the highest score is the winning sequence, and the first choice in the winning sequence is the most popular choice. (As explained below, ties can occur at any ranking level.)
The Kemeny method is also known as the Kemeny-Young rule, VoteFair popularity ranking, the maximum likelihood method, and the median relation.
Description The Kemeny method uses preferential ballots on which voters rank choices according to their order of preference. A voter is allowed to rank more than one choice at the same preference level. Unranked choices are usually interpreted as least-preferred.
Kemeny 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 rankings, calculate a score for each such ranking, and compare the scores. Each ranking score equals the sum of the pairwise counts that apply to that ranking.
The ranking that has the largest score is identified as the overall ranking. (If more than one ranking has the same largest score, all these possible rankings are tied, and typically the overall ranking involves one or more ties.)
Another way to view the ordering is that it is the one which minimizes the sum of the Kendall tau distances (bubble sort distance) to the voters' lists.
In order to demonstrate how an individual preference order is converted into a tally table, it is worth considering the following example. Suppose that a single voter has a choice among four candidates (i.e. Elliot, Meredith, Roland, and Selden) and has the following preference order: Preferenceorder Choice First Elliot Second Roland Third Meredith or Selden(equal preference)
These preferences can be expressed in a tally table. A tally table, which arranges all the pairwise counts in three columns, is useful for counting (tallying) ballot preferences and calculating ranking scores. The center column tracks when a voter indicates more than one choice at the same preference level. The above preference order can be expressed as the following tally table: All possible pairsof choice names Number of votes with indicated preference Prefer X over Y Equal preference Prefer Y over X X = SeldenY = Meredith 0 +1 vote 0 X = SeldenY = Elliot 0 0 +1 vote X = SeldenY = Roland 0 0 +1 vote X = MeredithY = Elliot 0 0 +1 vote X = MeredithY = Roland 0 0 +1 vote X = ElliotY = Roland +1 vote 0 0
Now suppose that multiple voters had voted on those four candidates. After all ballots have been counted, the same type of tally table can be used to summarize all the preferences of all the voters. Here is an example for a case that has 100 voters: All possible pairsof choice names Number of votes with indicated preference Prefer X over Y Equal preference Prefer Y over X X = SeldenY = Meredith 50 10 40 X = SeldenY = Elliot 40 0 60 X = SeldenY = Roland 40 0 60 X = MeredithY = Elliot 40 0 60 X = MeredithY = Roland 30 0 70 X = ElliotY = Roland 30 0 70
The sum of the counts in each row must equal the total number of votes.
After the tally table has been completed, each possible ranking of choices is examined in turn, and its ranking score is calculated by adding the appropriate number from each row of the tally table. For example, the possible ranking: Elliot Roland Meredith Selden satisfies the preferences Elliot > Roland, Elliot > Meredith, Elliot > Selden, Roland > Meredith, Roland > Selden, and Meredith > Selden. The respective scores, taken from the table, are Elliot > Roland: 30 Elliot > Meredith: 60 Elliot > Selden: 60 Roland > Meredith: 70 Roland > Selden: 60 Meredith > Selden: 40 giving a total ranking score of 30 + 60 + 60 + 70 + 60 + 40 = 320.
Calculating the overall ranking After the scores for every possible ranking have been calculated, the ranking that has the largest score can be identified, and becomes the overall ranking. In this case, the overall ranking is: Roland Elliot Selden Meredith with a ranking score of 370.
If there are cycles or ties, more than one possible ranking can have the same largest score. Cycles are resolved by producing a single overall ranking where some of the choices are tied.
Summary matrix After the overall ranking has been calculated, the pairwise comparison counts can be arranged in a summary matrix, as shown below, in which the choices appear in the winning order from most popular (top and left) to least popular (bottom and right). This matrix layout does not include the equal-preference pairwise counts that appear in the tally table:The numbers in this example are adapted from Sample election used in Wikipedia . ... over Roland ... over Elliot ... over Selden ... over Meredith Prefer Roland ... - 70 60 70 Prefer Elliot ... 30 - 60 60 Prefer Selden ... 40 40 - 50 Prefer Meredith ... 30 40 40 -
In this summary matrix, the largest ranking score equals the sum of the counts in the upper-right, triangular half of the matrix (shown here in bold, with a green background). No other possible ranking can have a summary matrix that yields a higher sum of numbers in the upper-right, triangular half. (If it did, that would be the overall ranking.)
In this summary matrix, the sum of the numbers in the lower-left, triangular half of the matrix (shown here with a red background) are a minimum. The academic papers by John Kemeny and Peyton Young refer to finding this minimum sum, which is called the Kemeny score, and which is based on how many voters oppose (rather than support) each pairwise order: Method First-place winner Kemeny Roland Condorcet Roland Instant runoff voting Elliot or Selden(depending on how the second-round tie is handled) Plurality Selden
Example
This matrix summarizes the corresponding pairwise comparison counts: ... overMemphis ... overNashville ... overChattanooga ... overKnoxville PreferMemphis ... - 42% 42% 42% PreferNashville ... 58% - 68% 68% PreferChattanooga ... 58% 32% - 83% PreferKnoxville ... 58% 32% 17% -
The Kemeny method arranges the pairwise comparison counts in the following tally table: All possible pairsof choice names Number of votes with indicated preference Prefer X over Y Equal preference Prefer Y over X X = MemphisY = Nashville 42% 0 58% X = MemphisY = Chattanooga 42% 0 58% X = MemphisY = Knoxville 42% 0 58% X = NashvilleY = Chattanooga 68% 0 32% X = NashvilleY = Knoxville 68% 0 32% X = ChattanoogaY = Knoxville 83% 0 17%
The ranking score for the possible ranking of 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
This table lists all the ranking scores: Firstchoice Secondchoice Thirdchoice Fourthchoice Rankingscore 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 largest ranking score is 393, and this score is associated with the following possible ranking, so this ranking is also the overall ranking: Preferenceorder 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.)
The summary matrix below arranges the pairwise counts in order from most popular (top and left) to least popular (bottom and right): ... over Nashville ... ... over Chattanooga ... ... over Knoxville ... ... over Memphis ... Prefer Nashville ... - 68% 68% 58% Prefer Chattanooga ... 32% - 83% 58% Prefer Knoxville ... 32% 17% - 58% Prefer Memphis ... 42% 42% 42% -
In this arrangement the largest ranking score (393) equals the sum of the counts in bold, which are in the upper-right, triangular half of the matrix (with a green background).
Characteristics In all cases that do not result in an exact tie, the Kemeny 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 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.
Satisfied criteria for all Condorcet methods
All Condorcet methods, including the Kemeny method, satisfy these criteria:
Non-imposition There are voter preferences that can yield every possible overall order-of-preference result, including ties at any combination of preference levels.
Condorcet criterion If there is a choice that wins all pairwise contests, then this choice wins.
Majority criterion If a majority of voters strictly prefer choice X to every other choice, then choice X is identified as the most popular.
Non-dictatorship A single voter cannot control the outcome in all cases.
Additional satisfied criteria
The Kemeny method also satisfies these criteria:
Unrestricted domain Identifies the overall order of preference for all the choices. The method does this for all possible sets of voter preferences and always produces the same result for the same set of voter preferences.
Pareto efficiency Any pairwise preference expressed by every voter results in the preferred choice being ranked higher than the less-preferred choice.
Monotonicity If voters increase a choice's preference level, the ranking result either does not change or the promoted choice increases in overall popularity.
Smith criterion The most popular choice is a member of the Smith set, which is the smallest nonempty set of choices such that every member of the set is pairwise preferred to every choice not in the Smith set.
Independence of Smith-dominated alternatives If choice X is not in the Smith set, adding or withdrawing choice X does not change a result in which choice Y is identified as most popular.
Reinforcement If all the ballots are divided into separate races and the overall ranking for the separate races are the same, then the same ranking occurs when all the ballots are combined.Giuseppe Munda, "Social multi-criteria evaluation for a sustainable economy", p. 124.
Reversal symmetry If the preferences on every ballot are inverted, then the previously most popular choice must not remain the most popular choice.
Failed criteria for all Condorcet methods