Kemeny–Young method: Wikis

Advertisements
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

The Kemeny–Young method is a voting system that uses preferential ballots, pairwise comparison counts, and sequence scores to identify the most popular choice, and also identify the second-most popular choice, the third-most popular choice, and so on down to the least-popular choice.

This is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.

The Kemeny–Young method is also known as VoteFair popularity ranking, the linear ordering problem, the maximum likelihood method, and the median relation.

Contents

Description

The Kemeny–Young method uses preferential ballots on which a voter ranks the 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 order-of-preference sequences, calculate a sequence score for each sequence, and compare the scores. Each sequence score equals the sum of the pairwise counts that apply to the sequence. The sequence with the highest score is identified as the overall ranking, from most popular to least popular.

Advertisements

Tally table

A tally table, which arranges all the pairwise counts in three columns, is useful for counting (tallying) ballot preferences and calculating Kemeny scores. The center column tracks voters who indicate more than one choice at the same preference level.

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


The above tally table summarizes the following preferences in which a voter has ranked two choices at the same preference level.

Preference
order
Choice
First Elliot
Second Roland
Third Meredith or Selden
(equal preference)


After all ballots have been counted, the same tally table is used to summarize all the preferences of all the voters. Here is an example for a case that has 100 voters. (It includes 10 ballots marked as above.)

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.

Calculating a Kemeny score for a specified sequence is done by adding one count from each row of this tally table. The counts in the center column do not contribute to the score, so they are ignored in the score calculations. The choice between using the count in the left (Prefer X over Y) or right (Prefer Y over X) column depends on which choice name appears first in the specified sequence.

Summary matrix

After the sequence with the highest Kemeny score has been identified, the pairwise comparison counts can be arranged in a summary matrix, as shown below, in which the choices appear in the winning sequence 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 winning Kemeny 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 sequence 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 winning sequence.)

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[1][2] refer to finding this minimum sum, which is based on how many voters oppose each pairwise order.

The numbers in the above example refer to a case[1] in which different voting methods identify different first-place winners.

Method First-place winner
Kemeny–Young Roland
Condorcet Roland
Instant runoff voting Elliot or Selden
(depending on how the second-round tie is handled)
Plurality Selden

Example

Tennessee's four cities are spread throughout the state

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 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 Tennessee
  • 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)
  1. Memphis
  2. Nashville
  3. Chattanooga
  4. Knoxville
  1. Nashville
  2. Chattanooga
  3. Knoxville
  4. Memphis
  1. Chattanooga
  2. Knoxville
  3. Nashville
  4. Memphis
  1. Knoxville
  2. Chattanooga
  3. Nashville
  4. Memphis

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 Kemeny sequence score for the sequence 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 sequence scores.

First
choice
Second
choice
Third
choice
Fourth
choice
Sequence
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 highest sequence score is 393, and this score is associated with the following sequence, so this is the winning preference order.

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 sequence 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 winning Kemeny 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 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–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 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 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.
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.
Later-no-harm
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 push-over
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[3]
An algorithm is known to determine the winner using this method in a runtime that is polynomial in the number of choices.

Calculation methods

Calculating all sequence scores requires time proportional to N!, where N is the number of choices. Although one need not compute scores to find the winner, any algorithm finding the winner requires superpolynomial time (unless P = NP). Nevertheless, fast calculation methods based on integer programming allow the computation of full rankings for votes with as many as 40 choices in seconds.[4]

History

The Kemeny–Young method was developed by John Kemeny in 1959.[1]

In 1978 Peyton Young and Arthur Levenglick showed[2] that this method was the unique neutral method satisfying reinforcement and the Condorcet criterion. In another paper[5], Young argued that the Kemeny–Young method was a possible interpretation of one of Condorcet's proposals.

In the papers by John Kemeny and Peyton Young, the Kemeny sequence scores use counts of how many voters oppose, rather than support, each pairwise preference,[1][2] but the smallest such sequence score identifies the same overall ranking.

Since 1991 the method has been promoted under the name "VoteFair popularity ranking" by Richard Fobes.[6]

Notes

  1. ^ a b c John Kemeny, "Mathematics without numbers", Daedalus 88 (1959), pp. 577–591.
  2. ^ a b c H. P. Young and A. Levenglick, "A Consistent Extension of Condorcet's Election Principle", SIAM Journal on Applied Mathematics 35, no. 2 (1978), pp. 285–300.
  3. ^ 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.
  4. ^ Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam, "Improved bounds for computing Kemeny rankings" (2006).
  5. ^ H. P. Young, "Condorcet's Theory of Voting", American Political Science Review 82, no. 2 (1988), pp. 1231–1244.
  6. ^ Richard Fobes, "The Creative Problem Solver's Toolbox", (ISBN 0-9632-2210-4), 1993, pp. 223–225.

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.

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message