Kemeny-Young method
Encyclopedia
The Kemeny–Young method is a voting 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. (As explained below, ties can occur at any ranking level.)
The Kemeny–Young method is also known as the Kemeny rule, VoteFair popularity ranking, the maximum likelihood
method, and the median relation.
Another way to view the ordering is that it is the one which minimizes the sum of the Kendall tau distance
s (bubble sort
distance) 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. (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.)
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:
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.
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:
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.
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.
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.
counts:
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 (the unit-less number) 345, which is the sum of the following annotated numbers.
This table lists all the ranking scores.
The largest ranking score is 393, and this score is associated with the following possible ranking, so this ranking is also the overall ranking.
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).
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).
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.
A polynomial-time algorithm for computing the Kemeny-Young ranking is not known, and unlikely to exist since the problem is NP-hard
, even if there are just 4 voters. Nevertheless, fast calculation methods based on integer programming
can allow the computation of full rankings for votes with as many as 40 choices in seconds... but this same paper also states that for certain 40-candidate 5-voter Kemeny elections they generated using certain reasonable-sounding random processes, no algorithm known to them was able to find the Kemeny ordering in any reasonable amount of time. (They were using a 3GHz pentium computer in their testing.)
in 1959.
In 1978 Peyton Young
and Arthur Levenglick showed that this method was the unique neutral method satisfying reinforcement and 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 (cf. Condorcet's jury theorem
.) 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.
Voting system
A voting system or electoral system is a method by which voters make a choice between options, often in an election or on a policy referendum....
that uses preferential ballots and pairwise comparison
Pairwise comparison
Pairwise comparison generally refers to any process of comparing entities in pairs to judge which of each entity is preferred, or has a greater amount of some quantitative property. The method of pairwise comparison is used in the scientific study of preferences, attitudes, voting systems, social...
counts to identify the most popular choices in an election. It is a Condorcet method
Condorcet method
A Condorcet method is any single-winner election method that meets the Condorcet criterion, which means the method always selects the Condorcet winner if such a candidate exists. The Condorcet winner is the candidate who would beat each of the other candidates in a run-off election.In modern...
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–Young method is also known as the Kemeny rule, VoteFair popularity ranking, the maximum likelihood
Maximum likelihood
In statistics, maximum-likelihood estimation is a method of estimating the parameters of a statistical model. When applied to a data set and given a statistical model, maximum-likelihood estimation provides estimates for the model's parameters....
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 distance
Kendall tau distance
The Kendall tau distance is a metric that counts the number of pairwise disagreements between two lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort...
s (bubble sort
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
distance) 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
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, 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.)
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:
| Preference order | 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 pairs of choice names | Number of votes with indicated preference | ||
| Prefer X over Y | Equal preference | Prefer Y over X | |
| X = Selden Y = Meredith | 0 | +1 vote | 0 |
| X = Selden Y = Elliot | 0 | 0 | +1 vote |
| X = Selden Y = Roland | 0 | 0 | +1 vote |
| X = Meredith Y = Elliot | 0 | 0 | +1 vote |
| X = Meredith Y = Roland | 0 | 0 | +1 vote |
| X = Elliot Y = 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 pairs of choice names | Number of votes with indicated preference | ||
| Prefer X over Y | Equal preference | Prefer Y over X | |
| X = Selden Y = Meredith | 50 | 10 | 40 |
| X = Selden Y = Elliot | 40 | 0 | 60 |
| X = Selden Y = Roland | 40 | 0 | 60 |
| X = Meredith Y = Elliot | 40 | 0 | 60 |
| X = Meredith Y = Roland | 30 | 0 | 70 |
| X = Elliot Y = 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.| ... 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–Young | Roland |
| Condorcet Condorcet method A Condorcet method is any single-winner election method that meets the Condorcet criterion, which means the method always selects the Condorcet winner if such a candidate exists. The Condorcet winner is the candidate who would beat each of the other candidates in a run-off election.In modern... | Roland |
| Instant runoff voting | Elliot or Selden (depending on how the second-round tie is handled) |
| Plurality Plurality voting system The plurality voting system is a single-winner voting system often used to elect executive officers or to elect members of a legislative assembly which is based on single-member constituencies... | Selden |
Example
This matrix summarizes the corresponding pairwise comparisonPairwise comparison
Pairwise comparison generally refers to any process of comparing entities in pairs to judge which of each entity is preferred, or has a greater amount of some quantitative property. The method of pairwise comparison is used in the scientific study of preferences, attitudes, voting systems, social...
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:
| 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 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.
| First choice | Second choice | Third choice | Fourth choice | Ranking 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 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 |
| 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–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:-
- 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 criterionCondorcet criterionThe Condorcet candidate or Condorcet winner of an election is the candidate who, when compared with every other candidate, is preferred by more voters. Informally, the Condorcet winner is the person who would win a two-candidate election against each of the other candidates...
- If there is a choice that wins all pairwise contests, then this choice wins.
- Condorcet criterion
-
- Majority criterionMajority criterionThe majority criterion is a single-winner voting system criterion, used to compare such systems. The criterion states that "if one candidate is preferred by a majority of voters, then that candidate must win"....
- If a majority of voters strictly prefer choice X to every other choice, then choice X is identified as the most popular.
- Majority criterion
-
- Non-dictatorshipNon-dictatorshipIn voting theory, non-dictatorship is a property of social choice functions, where the results cannot simply mirror that of any ONE single person's preferences without consideration of the other voters. Fairness requires that the social welfare function take into account the desires of more than...
- A single voter cannot control the outcome in all cases.
- Non-dictatorship
Additional satisfied criteria
The Kemeny–Young method also satisfies these criteria:-
- Unrestricted domainUnrestricted domainIn social choice theory, unrestricted domain, or universality, is a property of social welfare functions in which all preferences of all voters are allowed...
- 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.
- Unrestricted domain
-
- Pareto efficiencyPareto efficiencyPareto efficiency, or Pareto optimality, is a concept in economics with applications in engineering and social sciences. The term is named after Vilfredo Pareto, an Italian economist who used the concept in his studies of economic efficiency and income distribution.Given an initial allocation of...
- Any pairwise preference expressed by every voter results in the preferred choice being ranked higher than the less-preferred choice.
- Pareto efficiency
-
- MonotonicityMonotonicity criterionThe monotonicity criterion is a voting system criterion used to analyze both single and multiple winner voting systems. A voting system is monotonic if it satisfies one of the definitions of the monotonicity criterion, given below.Douglas R...
- If voters increase a choice's preference level, the ranking result either does not change or the promoted choice increases in overall popularity.
- Monotonicity
-
- Smith criterionSmith criterionThe Smith criterion is a voting systems criterion defined such that its satisfaction by a voting system occurs when the system always picks the winner from the Smith set, the smallest set of candidates such that every member of the set is pairwise preferred to every candidate not in the set...
- The most popular choice is a member of the Smith setSmith setIn voting systems, the Smith set, named after John H. Smith, is the smallest non-empty set of candidates in a particular election such that each member beats every other candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome...
, 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.
- Smith criterion
-
- Independence of Smith-dominated alternatives
- If choice X is not in the Smith setSmith setIn voting systems, the Smith set, named after John H. Smith, is the smallest non-empty set of candidates in a particular election such that each member beats every other candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome...
, 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.
-
- Reversal symmetryReversal symmetryReversal symmetry is a voting system criterion which requires that if candidate A is the unique winner, and each voter's individual preferences are inverted, then A must not be elected. Methods that satisfy reversal symmetry include Borda count, the Kemeny-Young method, and the Schulze method...
- If the preferences on every ballot are inverted, then the previously most popular choice must not remain the most popular choice.
- Reversal symmetry
Failed criteria for all Condorcet methods
In common with all Condorcet methods, the Kemeny–Young method fails these criteria (which means the described criteria do not apply to the Kemeny–Young method):-
- Independence of irrelevant alternativesIndependence of irrelevant alternativesIndependence of irrelevant alternatives is an axiom of decision theory and various social sciences.The word is used in different meanings in different contexts....
- Adding or withdrawing choice X does not change a result in which choice Y is identified as most popular.
- Independence of irrelevant alternatives
-
- Invulnerability to burying
- A voter cannot displace a choice from most popular by giving the choice an insincerely low ranking.
-
- Invulnerability to compromising
- A voter cannot cause a choice to become the most popular by giving the choice an insincerely high ranking.
-
- ParticipationParticipation criterionThe participation criterion is a voting system criterion. It is also known as the "no show paradox". It has been defined as follows:* In a deterministic framework, the participation criterion says that the addition of a ballot, where candidate A is strictly preferred to candidate B, to an existing...
- Adding ballots that rank choice X over choice Y never cause choice Y, instead of choice X, to become most popular.
- Participation
-
- Later-no-harmLater-no-harm criterionThe later-no-harm criterion is a voting system criterion formulated by Douglas Woodall. The criterion is satisfied if, in any election, a voter giving an additional ranking or positive rating to a less preferred candidate cannot cause a more preferred candidate to lose.- Complying methods :Single...
- Ranking an additional choice (that was otherwise unranked) cannot displace a choice from being identified as the most popular.
- Later-no-harm
-
- ConsistencyConsistency criterionA voting system is consistent if, when the electorate is divided arbitrarily into two parts and separate elections in each part result in the same choice being selected, an election of the entire electorate also selects that alternative...
- 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 the most popular when all the ballots are combined.
- Consistency
Additional failed criteria
The Kemeny–Young method also fails these criteria (which means the described criteria do not apply to the Kemeny–Young method):-
- Independence of clonesIndependence of clones criterionIn voting systems theory, the independence of clones criterion measures an election method's robustness to strategic nomination. Nicolaus Tideman first formulated the criterion, which states that the addition of a candidate identical to one already present in an election will not cause the winner...
- Offering a larger number of similar choices, instead of offering only a single such choice, does not change the probability that one of these choices is identified as most popular.
- Independence of clones
-
- Invulnerability to push-over
- A voter cannot cause choice X to become the most popular by giving choice Y an insincerely high ranking.
-
- SchwartzSchwartz setIn voting systems, the Schwartz set is the union of all Schwartz set components. A Schwartz set component is any non-empty set S of candidates such that...
- The choice identified as most popular is a member of the Schwartz set.
- Schwartz
-
- Polynomial runtime
- An algorithm is known to determine the winner using this method in a runtime that is polynomial in the number of choices.
Calculation methods
A polynomial-time algorithm for computing the Kemeny-Young ranking is not known, and unlikely to exist since the problem is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, even if there are just 4 voters. Nevertheless, fast calculation methods based on integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
can allow the computation of full rankings for votes with as many as 40 choices in seconds... but this same paper also states that for certain 40-candidate 5-voter Kemeny elections they generated using certain reasonable-sounding random processes, no algorithm known to them was able to find the Kemeny ordering in any reasonable amount of time. (They were using a 3GHz pentium computer in their testing.)
History
The Kemeny–Young method was developed by John KemenyJohn George Kemeny
John George Kemeny was a Hungarian American mathematician, computer scientist, and educator best known for co-developing the BASIC programming language in 1964 with Thomas E. Kurtz. Kemeny served as the 13th President of Dartmouth College from 1970 to 1981 and pioneered the use of computers in...
in 1959.
In 1978 Peyton Young
Peyton Young
Hobart Peyton Young is an American game theorist known for his contributions to evolutionary game theory and its application to the study of institutional and technological change, as well as the theory of learning in games...
and Arthur Levenglick showed that this method was the unique neutral method satisfying reinforcement and 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 (cf. Condorcet's jury theorem
Condorcet's jury theorem
Condorcet's jury theorem is a political science theorem about the relative probability of a given group of individuals arriving at a correct decision...
.) 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
Marquis de Condorcet
Marie Jean Antoine Nicolas de Caritat, marquis de Condorcet , known as Nicolas de Condorcet, was a French philosopher, mathematician, and early political scientist whose Condorcet method in voting tally selects the candidate who would beat each of the other candidates in a run-off election...
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.
External links
- VoteFair.org — A website that calculates Kemeny–Young results. For comparison, it also calculates the winner according to plurality, Condorcet, Borda count, and other voting methods.