Kemeny–Young method


The Kemeny–Young method is an electoral system that uses preferential 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.
The Kemeny–Young method is also known as the Kemeny rule, VoteFair popularity ranking, the maximum likelihood method, and the median relation.

Description

The Kemeny–Young 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.
Another way to view the ordering is that it is the one which minimizes the sum of the Kendall tau distances to the voters' lists.
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 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.
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 and has the following preference order:
Preference
order		Choice
FirstElliot
SecondRoland
ThirdMeredith or Selden

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 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:
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:


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:
  1. Elliot
  2. Roland
  3. Meredith
  4. 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
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:
  1. Roland
  2. Elliot
  3. Selden
  4. 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 to least popular. This matrix layout does not include the equal-preference pairwise counts that appear in the tally table:
... over Roland... over Elliot... over Selden... over Meredith
Prefer Roland...-706070
Prefer Elliot...30-6060
Prefer Selden...4040-50
Prefer Meredith...304040-

In this summary matrix, the largest ranking score equals the sum of the counts in the upper-right, triangular half of the matrix. No other possible ranking can have a summary matrix that yields a higher sum of numbers in the upper-right, triangular half.
In this summary matrix, the sum of the numbers in the lower-left, triangular half of the matrix 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 each pairwise order:
MethodFirst-place winner
Kemeny–YoungRoland
CondorcetRoland
Instant runoff votingElliot or Selden
PluralitySelden

Example

This matrix summarizes the corresponding pairwise comparison counts:
... over
Memphis		... over
Nashville		... over
Chattanooga		... over
Knoxville
Prefer
Memphis...		-42%42%42%
Prefer
Nashville...		58%-68%68%
Prefer
Chattanooga...		58%32%-83%
Prefer
Knoxville...		58%32%17%-



The Kemeny–Young method arranges the pairwise comparison counts in the following tally table:


The ranking score for the possible ranking of Memphis first, Nashville second, Chattanooga third, and Knoxville fourth equals 345, which is the sum of the following annotated numbers.


This table lists all the ranking scores:
First
choice		Second
choice		Third
choice		Fourth
choice		Ranking
score
MemphisNashvilleChattanoogaKnoxville345
MemphisNashvilleKnoxvilleChattanooga279
MemphisChattanoogaNashvilleKnoxville309
MemphisChattanoogaKnoxvilleNashville273
MemphisKnoxvilleNashvilleChattanooga243
MemphisKnoxvilleChattanoogaNashville207
NashvilleMemphisChattanoogaKnoxville361
NashvilleMemphisKnoxvilleChattanooga295
NashvilleChattanoogaMemphisKnoxville377
NashvilleChattanoogaKnoxvilleMemphis393
NashvilleKnoxvilleMemphisChattanooga311
NashvilleKnoxvilleChattanoogaMemphis327
ChattanoogaMemphisNashvilleKnoxville325
ChattanoogaMemphisKnoxvilleNashville289
ChattanoogaNashvilleMemphisKnoxville341
ChattanoogaNashvilleKnoxvilleMemphis357
ChattanoogaKnoxvilleMemphisNashville305
ChattanoogaKnoxvilleNashvilleMemphis321
KnoxvilleMemphisNashvilleChattanooga259
KnoxvilleMemphisChattanoogaNashville223
KnoxvilleNashvilleMemphisChattanooga275
KnoxvilleNashvilleChattanoogaMemphis291
KnoxvilleChattanoogaMemphisNashville239
KnoxvilleChattanoogaNashvilleMemphis255



The largest ranking score is 393, and this score is associated with the following possible ranking, so this ranking is also the overall ranking:
Preference
order		Choice
FirstNashville
SecondChattanooga
ThirdKnoxville
FourthMemphis



If a single winner is needed, the first choice, Nashville, is chosen.
The summary matrix below arranges the pairwise counts in order from most popular to least popular :
... 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 equals the sum of the counts in bold, which are in the upper-right, triangular half of the matrix.

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.

Satisfied criteria for all Condorcet methods

All Condorcet methods, including the Kemeny–Young method, satisfy these criteria:

Additional satisfied criteria

The Kemeny–Young method also satisfies these criteria:

Failed criteria for all Condorcet methods

In common with all Condorcet methods, the Kemeny–Young method fails these criteria :

Additional failed criteria

The Kemeny–Young method also fails these criteria :

Calculation methods and computational complexity

An algorithm for computing a Kemeny-Young ranking in time polynomial in the number of candidates is not known, and unlikely to exist since the problem is NP-hard even if there are just 4 voters.
It has been reported that calculation methods based on integer programming sometimes allowed the computation of full rankings for votes on as many as 40 candidates in seconds. However, certain 40-candidate 5-voter Kemeny elections generated at random were not solvable on a 3 GHz Pentium computer in a useful time bound in 2006.
Note that the complexity of computation scales linearly to the number of voters so the time needed to process a given set of votes is dominated by the number of candidates rather than the number of votes, limiting the importance of this constraint to elections where voters are able to effectively consider significantly more than the common seven items of working memory.
There exists a polynomial-time approximation scheme for computing a Kemeny-Young ranking, and there also exists a parameterized subexponential-time algorithm with running time O* for computing such a ranking.

History

The Kemeny–Young method was developed by John Kemeny in 1959.
In 1978 Peyton Young and Arthur Levenglick showed that this method was the unique neutral method satisfying reinforcement and a version of the Condorcet criterion. In other papers,
Young adopted an epistemic approach to preference-aggregation: he supposed that there was an objectively 'correct', but unknown preference order over the alternatives, and voters receive noisy signals of this true preference order Using a simple probabilistic model for these noisy signals, Young showed that the Kemeny–Young method was the maximum likelihood estimator of the true preference order. Young further argues that Condorcet himself was aware of the Kemeny-Young rule and its maximum-likelihood interpretation, but was unable to clearly express his ideas.
In the papers by John Kemeny and Peyton Young, the Kemeny scores use counts of how many voters oppose, rather than support, each pairwise preference, but the smallest such score identifies the same overall ranking.
Since 1991 the method has been promoted under the name "VoteFair popularity ranking" by Richard Fobes.

Comparison table

The following table compares the Kemeny-Young method with other preferential single-winner election methods: