Part of the Politics series
Electoral systems
Single-winner/majoritarian Plurality First-past-the-post Plurality at-large (plurality block voting) General ticket (party block voting) Multi-round voting Two-round Exhaustive ballot Primary election Nonpartisan unified top-four Majority at-large (two-round block voting) Ranked / preferential systems Instant-runoff (alternative vote) Contingent vote Coombs' method Condorcet methods (Copeland's, Dodgson's, Kemeny–Young, Minimax, Nanson's, ranked pairs, Schulze, Alternative Smith) Positional voting (Borda count, Nauru/Dowdall method) Bucklin voting Oklahoma primary electoral system Preferential block voting Cardinal / graded systems Score voting Approval voting Combined approval voting Unified primary Usual judgment Satisfaction approval voting Majority judgment STAR voting
Proportional representation Party-list Electoral list open list closed list local lists Apportionment Sainte-Laguë D'Hondt Huntington–Hill Hare Droop Imperiali Hagenbach-Bischoff National remnant Highest averages Largest remainder Proportional forms of ranked voting Single transferable vote Gregory Wright Schulze STV CPO-STV Ranked party list PR Spare vote Proportional forms of cardinal voting Proportional approval voting Sequential proportional approval voting Method of Equal Shares Phragmen's voting rules Biproportional apportionment Fair majority voting Weighted voting Direct representation Interactive representation Liquid democracy
Mixed systems By type of representation Mixed-member majoritarian Mixed-member proportional Non-compensatory mixed systems Parallel voting Majority bonus Compensatory mixed systems Additional member system Mixed single vote (positive vote transfer) Scorporo (negative vote transfer) Mixed ballot transferable vote Alternative Vote Plus Dual-member proportional Rural–urban proportional
Other systems and related theory Semi-proportional representation Single non-transferable vote Limited voting Cumulative voting Binomial voting Other systems Multiple non-transferable vote Double simultaneous vote Proxy voting Delegated voting Indirect STV Liquid democracy Random selection (sortition, random ballot) Supermajority Social choice theory Arrow's theorem Gibbard–Satterthwaite theorem Public choice theory Veto Players List of electoral systems List of electoral systems by country Comparison of electoral systems Effects of electoral systems Political fragmentation Political efficacy Voter turnout
Politics portal

The Kemeny–Young 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–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.

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.)

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:

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:

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

• 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.

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:

This matrix summarizes the corresponding pairwise comparison 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.

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:

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).

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.

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^[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 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.^[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 ${\displaystyle n}$ candidates in time ${\displaystyle O(n2^{n})}$, significantly faster for many candidates than the factorial time of testing all rankings.^[11][12] There exists a polynomial-time approximation scheme for computing a Kemeny-Young ranking,^[13] and there also exists a parameterized subexponential-time 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 so-called quasi-Condorcet 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 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,^[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 Kemeny-Young method with other preferential single-winner election methods:

Notes

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 Condorcet-Kemeny calculations.
• Condorcet Class PHP library supporting multiple Condorcet methods, including Kemeny–Young method.
• C++ Program for Kemeny-Young Preference Aggregation — Command-line program for fast calculation of Kemeny-Young results, as source code and compiled binaries for Windows and Linux. Open source, except uses Numerical Recipes.
• C Program for Kemeny-Young 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.
• Kemeny-Young 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, instant-runoff and other voting methods.