Part of the Politics series 
Electoral systems 


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 secondmost popular, which choice might be thirdmost popular, and so on down to which choice might be leastpopular. 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.
YouTube Encyclopedic

1/5Views:8312 6833 270673985

Kemeny Hall Dedication

Young Tableaux

Coombs Method of Voting

Ranking Web Pages  Intro to Computer Science

Bài 16: Ensemble methods  Voting
Transcription
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.^{[citation needed]} Unranked choices are usually interpreted as leastpreferred.
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.
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:
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:^{[citation needed]}
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.^{[clarification needed]}
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 equalpreference pairwise counts that appear in the tally table:^{[1]}
... 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 upperright, 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 upperright, triangular half. (If it did, that would be the overall ranking.)
In this summary matrix, the sum of the numbers in the lowerleft, triangular half of the matrix (shown here with a red background) are a minimum. The academic papers by John Kemeny and Peyton Young^{[2]}^{[3]} 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  Firstplace winner 

Kemeny–Young  Roland 
Condorcet  Roland 
Instant runoff voting  Elliot or Selden (depending on how the secondround tie is handled) 
Plurality  Selden 
Example
Imagine that Tennessee is having an election 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 these four cities and that everyone wants to live as near to the capital 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, near the center of the state
 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:
... 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 unitless 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 upperright, 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 mostpopular choice, secondmost 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:
 Nonimposition
 There are voter preferences that can yield every possible overall orderofpreference 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.
 Nondictatorship
 A single voter cannot control the outcome in all cases.
Additional satisfied criteria
The Kemeny–Young 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 lesspreferred 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 Smithdominated 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.^{[4]}
 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
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 alternatives
 Adding or withdrawing choice X does not change a result in which choice Y is identified as most popular.
 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.
 Participation
 Adding ballots that rank choice X over choice Y never cause choice Y, instead of choice X, to become most popular.
 Laternoharm
 Ranking an additional choice (that was otherwise unranked) cannot displace a choice from being identified as the most popular.
 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 the most popular when all the ballots are combined.
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 clones
 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.
 Invulnerability to pushover
 A voter cannot cause choice X to become the most popular by giving choice Y an insincerely high ranking.
 Schwartz
 The choice identified as most popular is a member of the Schwartz set.
 Polynomial runtime^{[5]}
 An algorithm is known to determine the winner using this method in a runtime that is polynomial in the number of choices.
Calculation methods and computational complexity
An algorithm for computing a KemenyYoung ranking in time polynomial in the number of candidates is not known, and unlikely to exist since the problem is NPhard^{[5]} even if there are just 4 voters (even)^{[6]}^{[7]} or 7 voters (odd).^{[8]}
It has been reported^{[9]} 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 40candidate 5voter Kemeny elections generated at random were not solvable on a 3 GHz Pentium computer in a useful time bound in 2006.^{[9]}
The Kemeny–Young method can be formulated as an instance of a more abstract problem, of finding weighted feedback arc sets in tournament graphs.^{[10]} As such, many methods for the computation of feedback arc sets can be applied to this problem, including a variant of the Held–Karp algorithm that can compute the Kemeny–Young ranking of candidates in time , significantly faster for many candidates than the factorial time of testing all rankings.^{[11]}^{[12]} There exists a polynomialtime approximation scheme for computing a KemenyYoung ranking,^{[13]} and there also exists a parameterized subexponentialtime algorithm with running time O^{*}(2^{O(√OPT)}) for computing such a ranking.^{[10]}
History
The Kemeny–Young method was developed by John Kemeny in 1959.^{[2]}
In 1978, Peyton Young and Arthur Levenglick axiomatically characterized the method, showing that it is the unique neutral method satisfying consistency and the socalled quasiCondorcet criterion.^{[3]} It can also be characterized using consistency and a monotonicity property.^{[14]} In other papers,^{[15]} ^{[16]} ^{[17]} ^{[18]} 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 KemenyYoung rule and its maximumlikelihood 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,^{[2]}^{[3]} 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.^{[19]}
Comparison table
The following table compares the KemenyYoung method with other preferential singlewinner election methods:
System  Monotonic  Condorcet winner  Majority  Condorcet loser  Majority loser  Mutual majority  Smith  ISDA  LIIA  Independence of clones  Reversal symmetry  Participation, consistency  Laternoharm  Laternohelp  Polynomial time  Resolvability 

Schulze  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  No  Yes  Yes  No  No  No  Yes  Yes 
Ranked pairs  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  No  No  No  Yes  Yes 
Tideman's Alternative  No  Yes  Yes  Yes  Yes  Yes  Yes  Yes  No  Yes  No  No  No  No  Yes  Yes 
Kemeny–Young  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  No  Yes  No  No  No  No  Yes 
Copeland  Yes  Yes  Yes  Yes  Yes  Yes  Yes  Yes  No  No  Yes  No  No  No  Yes  No 
Nanson  No  Yes  Yes  Yes  Yes  Yes  Yes  No  No  No  Yes  No  No  No  Yes  Yes 
Black  Yes  Yes  Yes  Yes  Yes  No  No  No  No  No  Yes  No  No  No  Yes  Yes 
Instantrunoff voting  No  No  Yes  Yes  Yes  Yes  No  No  No  Yes  No  No  Yes  Yes  Yes  Yes 
Smith/IRV  No  Yes  Yes  Yes  Yes  Yes  Yes  Yes  No  Yes  No  No  No  No  Yes  Yes 
Borda  Yes  No  No  Yes  Yes  No  No  No  No  No  Yes  Yes  No  Yes  Yes  Yes 
Baldwin  No  Yes  Yes  Yes  Yes  Yes  Yes  No  No  No  No  No  No  No  Yes  Yes 
Bucklin  Yes  No  Yes  No  Yes  Yes  No  No  No  No  No  No  No  Yes  Yes  Yes 
Plurality  Yes  No  Yes  No  No  No  No  No  No  No  No  Yes  Yes  Yes  Yes  Yes 
Contingent voting  No  No  Yes  Yes  Yes  No  No  No  No  No  No  No  Yes  Yes  Yes  Yes 
Coombs^{[20]}  No  No  Yes  Yes  Yes  Yes  No  No  No  No  No  No  No  No  Yes  Yes 
MiniMax^{[specify]}  Yes  Yes  Yes  No  No  No  No  No  No  No  No  No  No  No  Yes  Yes 
Antiplurality^{[20]}  Yes  No  No  No  Yes  No  No  No  No  No  No  Yes  No  No  Yes  Yes 
Sri Lankan contingent voting  No  No  Yes  No  No  No  No  No  No  No  No  No  Yes  Yes  Yes  Yes 
Supplementary voting  No  No  Yes  No  No  No  No  No  No  No  No  No  Yes  Yes  Yes  Yes 
Dodgson^{[20]}  No  Yes  Yes  No  No  No  No  No  No  No  No  No  No  No  No  Yes 
Notes
 ^ The numbers in this example are adapted from Sample election used in Wikipedia Archived 20170330 at the Wayback Machine.
 ^ ^{a} ^{b} ^{c} John Kemeny, "Mathematics without numbers", Daedalus 88 (1959), pp. 577–591.
 ^ ^{a} ^{b} ^{c} H. P. Young and A. Levenglick, "A Consistent Extension of Condorcet's Election Principle^{[permanent dead link]}", SIAM Journal on Applied Mathematics 35, no. 2 (1978), pp. 285–300.
 ^ Giuseppe Munda, "Social multicriteria evaluation for a sustainable economy", p. 124.
 ^ ^{a} ^{b} J. Bartholdi III, C. A. Tovey, and M. A. Trick, "Voting schemes for which it can be difficult to tell who won the election", Social Choice and Welfare, Vol. 6, No. 2 (1989), pp. 157–165.
 ^ C. Dwork, R. Kumar, M. Naor, D. Sivakumar. Rank Aggregation Methods for the Web, WWW10, 2001
 ^ Biedl, Therese; Brandenburg, Franz J.; Deng, Xiaotie (20050912). Healy, Patrick; Nikolov, Nikola S. (eds.). Crossings and Permutations. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–12. doi:10.1007/11618058_1. ISBN 9783540314257. S2CID 11189107.
 ^ Bachmeier, Georg; Brandt, Felix; Geist, Christian; Harrenstein, Paul; Kardel, Keyvan; Peters, Dominik; Seedig, Hans Georg (20191101). "kMajority digraphs and the hardness of voting with a constant number of voters". Journal of Computer and System Sciences. 105: 130–157. arXiv:1704.06304. doi:10.1016/j.jcss.2019.04.005. ISSN 00220000. S2CID 2357131.
 ^ ^{a} ^{b} Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam, "Improved bounds for computing Kemeny rankings" (2006).
 ^ ^{a} ^{b} Karpinski, M. and Schudy, W., "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament", in: Cheong, O., Chwa, K.Y., and Park, K. (Eds.): ISAAC 2010, Part I, LNCS 6506, pp. 314.
 ^ Lawler, E. (1964), "A comment on minimum feedback arc sets", IEEE Transactions on Circuit Theory, 11 (2): 296–297, doi:10.1109/tct.1964.1082291
 ^ Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "A note on exact algorithms for vertex ordering problems on graphs", Theory of Computing Systems, 50 (3): 420–432, doi:10.1007/s0022401193120, hdl:1956/4556, MR 2885638, S2CID 253742611
 ^ "How to Rank with Few Errors". http://cs.brown.edu/~claire/stoc07.pdf
 ^ Can, Burak; Storcken, Ton (20130301). "Update monotone preference rules". Mathematical Social Sciences. 65 (2): 136–149. doi:10.1016/j.mathsocsci.2012.10.004. ISSN 01654896.
 ^ H. P. Young, "Condorcet's Theory of Voting", American Political Science Review 82, no. 2 (1988), pp. 1231–1244.
 ^ H. P. Young, "Optimal ranking and choice from pairwise comparisons", in Information pooling and group decision making edited by B. Grofman and G. Owen (1986), JAI Press, pp. 113–122.
 ^ H. P. Young, "Optimal Voting Rules", Journal of Economic Perspectives 9, no.1 (1995), pp. 51–64.
 ^ H. P. Young, "Group choice and individual judgements", Chapter 9 of Perspectives on public choice: a handbook, edited by Dennis Mueller (1997) Cambridge UP., pp.181 –200.
 ^ Richard Fobes, "The Creative Problem Solver's Toolbox", (ISBN 0963222104), 1993, pp. 223–225.
 ^ ^{a} ^{b} ^{c} Antiplurality, Coombs and Dodgson are assumed to receive truncated preferences by apportioning possible rankings of unlisted alternatives equally; for example, ballot A > B = C is counted as 1/2 A > B > C and 1/2 A > C > B. If these methods are assumed not to receive truncated preferences, then laternoharm and laternohelp are not applicable.
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.
 VoteFair_Ranking.cpp — C++ program, available on GitHub under the MIT license, that calculates VoteFair ranking results, which include CondorcetKemeny calculations.
 Condorcet Class PHP library supporting multiple Condorcet methods, including Kemeny–Young method.
 C++ Program for KemenyYoung Preference Aggregation — Commandline program for fast calculation of KemenyYoung results, as source code and compiled binaries for Windows and Linux. Open source, except uses Numerical Recipes.
 C Program for KemenyYoung Preference Aggregation — Implements Davenport's algorithm with no other library dependencies. Open source, LGPL licensed. A Ruby binding to the library is also open source, LPGL licensed.
 KemenyYoung Optimal Rank Aggregation in Python — Tutorial that uses a simple formulation as integer program and is adaptable to other languages with bindings to lpsolve.
 QuickVote — A website that calculates Kemeny–Young results, and gives further explanation and examples of the concept. It also calculates the winner according to plurality, Borda count, instantrunoff and other voting methods.