Condorcet method

From Wikipedia, the free encyclopedia

You have new messages (last change).
The Voting series:

This series is part of the
Politics and the Election series
Politics Portal · edit

A Condorcet method is a single winner election method in which voters rank candidates in order of preference. A Condorcet method is a voting system that will always elect the Condorcet winner; this is the candidate whom voters prefer to each other candidate, when compared to them one at a time. This candidate can easily be found by conducting a series of pairwise comparisons, using the basic procedure described in this article. The family of Condorcet methods is also referred to collectively as Condorcet's method. A voting system that always elects the Condorcet winner when there is one is described by electoral scientists as a system that satisfies the Condorcet criterion.

In certain circumstances an election has no Condorcet winner. This occurs as a result of a kind of tie known as a 'majority rule cycle', described by Condorcet's paradox. The manner in which a winner is then chosen varies from one Condorcet method to another. Some Condorcet methods involve the basic procedure described below, coupled with a Condorcet completion method– a special method used to find a winner when there is no Condorcet winner. Other Condorcet methods involve an entirely different system of counting, but are classified as Condorcet methods because they will still elect the Condorcet winner if there is one.

Condorcet methods are named for the eighteenth century mathematician and philosopher Marie Jean Antoine Nicolas Caritat, the Marquis de Condorcet, but the Condorcet criterion was also discovered independently by Ramon Llull in 1299.[1] Sophisticated modern Condorcet methods include Ranked Pairs and the Schulze method. Condorcet methods are not currently in use in government elections anywhere in the world, but a Condorcet method known as Nanson's method was used in city elections in the U.S. town of Marquette, Michigan in the 1920s [2], and today Condorcet methods are used by a number of private organisations.

Not all single winner, preferential voting systems are Condorcet methods. For example, neither instant-runoff voting nor the Borda count satisfies the Condorcet criterion.

Contents

[edit] Basic procedure

[edit] Voting

In a Condorcet election the voter ranks the list of candidates in order of preference. So, for example, the voter gives a '1' to their first preference, a '2' to their second preference, and so on. In this respect it is the same as an election held under non-Condorcet methods such as instant-runoff voting or the Single Transferable Vote. Some Condorcet methods allow voters to rank more than one candidate equally, so that, for example, the voter might express two first preferences rather than just one.

Usually, when a voter does not give a full list of preferences they are assumed, for the purpose of the count, to prefer the candidates they have ranked over all other candidates. Some Condorcet elections permit write-in candidates but, because this can be difficult to implement, software designed for conducting Condorcet elections often does not allow this option.

[edit] Finding the winner

The count is conducted by pitting every candidate against every other candidate in a series of imaginary one-on-one contests. The winner of each pairing is the candidate preferred by a majority of voters. The candidate preferred by each voter is taken to be the one in the pair that the voter ranks highest on their ballot paper. For example, if Alice is paired against Bob it is necessary to count both the number of voters who have ranked Alice higher than Bob, and the number who have ranked Bob higher than Alice. If Alice is preferred by more voters then she is the winner of that pairing. When all possible pairings of candidates have been considered, if one candidate beats every other candidate in these contests then they are declared the Condorcet winner. As noted above, if there is no Condorcet winner a further method must be used to find the winner of the election, and this mechanism varies from one Condorcet method to another.

[edit] Counting with matrices

In a Condorcet election votes are often counted, and results illustrated, in the form of matrices such as those below. In these matrices each row represents each candidate as a 'runner', while each column represents each candidate as an 'opponent'. The cells at the intersection of rows and columns each show the result of a particular pairwise comparison. Certain cells are left blank because it is impossible for a candidate to be compared with herself.

Imagine there is an election between four candidates: A, B, C and D. The first matrix below records the preferences expressed on a single ballot paper, in which the voter's preferences are (B, C, A, D); that is, the voter ranked B first, C second, A third, and D fourth. In the matrix a '1' indicates that the runner is preferred over the 'opponent', while a '0' indicates that the runner is defeated.

Opponent
A B C D
R
u
n
n
e
r		 A — 0 0 1
B 1 — 1 1
C 1 0 — 1
D 0 0 0 —
A "1" indicates that the runner is
preferred over the opponent; a '0'
indicates that the runner is defeated.

Matrices of this kind are useful because they can be easily added together to give the overall results of an election. The sum of all ballots in an election is called the sum matrix. Suppose that in the imaginary election there are two other voters. Their preferences are (D, A, C, B) and (A, C, B, D). Added to the first voter, these ballots would give the following sum matrix:

Opponent
A B C D
R
u
n
n
e
r		 A — 2 2 2
B 1 — 1 2
C 1 2 — 2
D 1 1 1 —

When the sum matrix is found, the contest between each pair of candidates is considered. The number of votes for runner over opponent (runner, opponent) is compared with the number of votes for opponent over runner (opponent,runner). It is then possible to find the Condorcet winner. In the sum matrix above it can be seen that A is the Condorcet winner because A beats every other candidate. When there is no Condorcet winner Condorcet completion methods, such as Ranked Pairs and the Schulze method, use the information contained in the sum matrix to choose a winner.

In strict mathematical terms the cells marked '–' in the matrices above should be '0', but in these examples a dash is used for clarity. The first matrix, that represents a single ballot, is inversely symmetric: (runner,opponent) is ¬(opponent,runner). Or (runner,opponent) + (opponent,runner) = 1. The sum matrix has this property: (runner,opponent) + (opponent,runner) = N for N voters, if all runners were fully ranked by each voter.

[edit] An example

Tennesee's four cities are spread throughout the state

Imagine that the population of Tennessee, a state in the United States, is voting 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 one of these four cities, and that they would like the capital to be established as close to their city 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
  • 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

To find the Condorcet winner every candidate must be matched against every other candidate in a series of imaginary one-on-one contests. In each pairing the winner is the candidate preferred by a majority of voters. When results for every possible pairing have been found they are as follows:

Pair Winner
Memphis (42%) vs. Nashville (58%) Nashville
Memphis (42%) vs. Chattanooga (58%) Chattanooga
Memphis (42%) vs. Knoxville (58%) Knoxville
Nashville (68%) vs. Chattanooga (32%) Nashville
Nashville (68%) vs. Knoxville (32%) Nashville
Chattanooga (83%) vs. Knoxville (17%) Chattanooga

The results can also be shown in the form of a matrix:

A
Memphis Nashville Chattanooga Knoxville
B Memphis [A] 58%
[B] 42%
 [A] 58%
[B] 42%
 [A] 58%
[B] 42%
Nashville [A] 42%
[B] 58%
 [A] 32%
[B] 68%
 [A] 32%
[B] 68%
Chattanooga [A] 42%
[B] 58%
 [A] 68%
[B] 32%
 [A] 17%
[B] 83%
Knoxville [A] 42%
[B] 58%
 [A] 68%
[B] 32%
 [A] 83%
[B] 17%
Ranking: 4th 1st 2nd 3rd
  • [A] indicates voters who preferred the candidate listed in the column caption to the candidate listed in the row caption
  • [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption
  • "Ranking" is found by repeatedly removing the Condorcet winner (it is not necessary to find these rankings).


Result: As can be seen from both of the tables above, Nashville beats every other candidate. This means that Nashville is the Condorcet winner. Nashville will thus win an election held under any possible Condorcet method.

While any Condorcet method will elect Nashville as the winner, if instead an election based on the same votes were held using first-past-the-post or instant-runoff voting, these systems would select Memphis and Knoxville respectively; this would occur despite the fact that, compared to either of these candidates, most people would have preferred Nashville.

[edit] Circular ambiguities

As noted above, sometimes an election has no Condorcet winner because there is no candidate who is preferred by voters to all other candidates. When this occurs the situation is known as a 'majority rule cycle', 'circular ambiguity' or 'circular tie'. This situation emerges when, once all votes have been added up, the preferrences of voters with respect to some candidates form a circle in which every candidate is beaten by at least one other candidate. For example, if there are three candidates, Andrea, Carter and Delilah, there will be no Condorcet winner if voters prefer Andrea to Carter and Carter to Delilah, but also Delilah to Andrea. Depending on the context in which elections are held, circular ambiguities may or may not be a common occurrence. Nonetheless there is always the possibility of an ambiguity, and so every Condorcet method must be capable of determining a winner when this occurs. A mechanism for resolving an ambiguity is known as ambiguity resolution or Condorcet completion method.

Circular ambiguities arise as a result of the paradox of voting -- the result of an election can be intransitive (forming a circle) despite the fact that each individual voter expressed a transitive preference. In a Condorcet election it is impossible for the preferences of a single voter to be cyclical, because a voter must rank all candidates in order and can only rank each candidate once, but the paradox of voting means that it is still possible for a circular ambiguity to emerge.

In elections there is often a single axis political spectrum. This means that each candidate can be defined by her position along a straight line, such as a line that goes from the most right wing candidates to the most left wing, with centrist candidates occupying the middle. Where this kind of spectrum exists there will often be a Condorcet winner because voters will tend to elect a candidate who occupies the middle position on the spectrum.

In Condorcet methods, as in most electoral systems, there is also the possibility of an ordinary tie. This occurs when two or more candidates tie with each other but defeat every other candidate. As in other systems this can be resolved by a random method such as the drawing of lots.

[edit] Resolving circular ambiguities

The method by which they resolve circular ambiguities is what chiefly distinguishes Condorcet methods. Theoretically, there are countless ways in which this can be done. Every resolution method however, involves ignoring the majorities expressed by voters in at least some pairwise matchings.

[edit] Two method systems

One family of Condorcet methods consists of systems that first conduct a series of pairwise comparisons and then, if there is no Condorcet winner, fall back to an entirely different, non-Condorcet method to determine a winner. The simplest such methods involve entirely disregarding the results of pairwise comparisons. For example, Black is a method that involves finding the Condorcet winner if it exists, but using the Borda count instead if there is an ambiguity (it is named after Duncan Black).

A more sophisticated two-stage process is, in the event of an ambiguity, to use a separate voting system to find the winner but to restrict this second stage to a certain subset of candidates found by scrutinising the results of the pairwise comparisons. Sets used for this purpose are defined so that they will always contain only the Condorcet winner if there is one, and will always, in any case, contain at least one candidate. Such sets include the

  • Smith set: The smallest set of candidates in a particular election such that every candidate in the set can beat all candidates outside the set. It is easily shown that there is only one possible Smith set for each election.
  • Schwartz set: This is the innermost unbeaten set, and is usually the same as the Smith set. It is defined as the union of all possible sets of candidates such that for every set:
    1. Every candidate inside the set is pairwise unbeatable by any other candidate outside the set (i.e. ties are allowed).
    2. No proper (smaller) subset of the set fulfills the first property.
  • Landau set (or uncovered set or Fishburn set): the set of candidates, such that each member, for every other candidate (including those inside the set), either beats this candidate or beats a third candidate that itself beats the candidate that is unbeaten by the member.

One possible method is to apply instant-runoff voting to the candidates of the Smith set. This method has been described as 'Smith/IRV'.

[edit] Other systems

There are also various methods whose procedures do not fall back on an entirely different system. Most involve scrutinising the results of each pairwise contest and using this data to determine a winner of the overall election. These include:

  • Copeland's method: This simple method involves electing the candidate who wins the most pairwise matchings. However it often produces a tie.
  • Kemeny-Young method
  • Minimax: Also called 'Simpson' and 'Simpson-Kramer', this method chooses the candidate whose worst pairwise defeat is better than that of all other candidates. A refinement of this method involves restricting it to choosing a winner from among the Smith set; this has been called 'Smith/Minimax'.
  • Ranked Pairs: This method is also known as 'Tideman', after its inventor Nicolaus Tideman.
  • Schulze method: This method is also known as 'Schwartz sequential dropping' (SSD), 'cloneproof Schwartz sequential dropping' (CSSD), 'beatpath method', 'beatpath winner', 'path voting' and 'path winner'.

Ranked Pairs and Schulze are procedurally in some sense opposite approaches (although they very frequently give the same results):

  • Ranked Pairs (and its variants) starts with the strongest defeats and uses as much information as it can without creating ambiguity.
  • Schulze repeatedly removes the weakest defeat until ambiguity is removed.

Minimax could be considered as more "blunt" than either of these approaches, as instead of removing defeats it can be seen as immediately removing candidates by looking at the strongest defeats (although their victories are still considered for subsequent candidate eliminations).

[edit] Ranked Pairs

In the Ranked Pairs method, pairwise defeats are ranked (sorted) from strongest to weakest. Then each pairwise defeat is considered, starting with the strongest defeat. Defeats are "affirmed" (or "locked in") only if they do not create a cycle with the defeats already affirmed. Once completed, the affirmed defeats are followed to determine the winner of the overall election. In essence, Ranked Pairs treat each majority preference as evidence that the majority's more preferred alternative should finish over the majority's less preferred alternative, the weight of the evidence depending on the size of the majority.

[edit] Schulze method

The Schulze method resolves votes as follows:

  1. First, determine the Schwartz set (the innermost unbeaten set). If no defeats exist among the Schwartz set, then its members are the winners (plural only in the case of a tie, which must be resolved by another method).
  2. Otherwise, drop the weakest defeat information among the Schwartz set (i.e., where the number of votes favoring the defeat is the smallest). Determine the new Schwartz set, and repeat the procedure.

In other words, this procedure repeatedly throws away the weakest pairwise defeat within the top set, until finally the number of votes left over produce an unambiguous decision.

[edit] Defeat strength

Many pairwise methods (including minimax, Ranked Pairs, and the Schulze method) resolve circular ambiguities based on the relative strength of the defeats. There are different ways to measure the strength of each defeat, and these include considering "winning votes" and "margins":

  • Winning votes: The number of votes on the winning side of a defeat.
  • Margins: The number of votes on the winning side of the defeat, minus the number of votes on the losing side of the defeat.

Sometimes these two approaches can yield different results. Consider, for example, the following election:

45 voters 11 voters 15 voters 29 voters
1. A 1. B 1. B 1. C
2. C 2. B

The pairwise defeats are as follows:

  • B beats A, 55 to 45 (55 winning votes, a margin of 10 votes)
  • A beats C, 45 to 44 (45 winning votes, a margin of 1 vote)
  • C beats B, 29 to 26 (29 winning votes, a margin of 3 votes)

Using the winning votes definition of defeat strength, the defeat of B by C is the weakest, and the defeat of A by B is the strongest. Using the margins definition of defeat strength, the defeat of C by A is the weakest, and the defeat of A by B is the strongest.

Using winning votes as the definition of defeat strength, candidate B would win under minimax, Ranked Pairs and the Schulze method, but, using margins as the definition of defeat strength, candidate C would win in the same methods.

If all voters give complete rankings of the candidates, then winning votes and margins will always produce the same result. The difference between them can only come into play when some voters declare equal preferences amongst candidates, as occurs implicitly if they do not rank all candidates, as in the example above.

The choice between margins and winning votes is the subject of scholarly debate. Because all Condorcet methods always choose the Condorcet winner when one exists, the difference between methods only appears when cyclic ambiguity resolution is required. The argument for using winning votes follows from this: Because cycle resolution involves disenfranchising a selection of votes, then the selection should disenfranchise the fewest possible number of votes. When margins are used, the difference between the number of two candidates' votes may be small, but the number of votes may be very large—or not. Only methods employing winning votes satisfy Woodall's plurality criterion.

An argument in favour of using margins is the fact that the result of a pairwise comparison is decided by the presence of more votes for one side than the other and thus that it follows naturally to assess the strength of a comparison by this "surplus" for the winning side. Otherwise, changing only a few votes from the winner to the loser could cause a sudden large change from a large score for one side to a large score for the other. In other words, one could consider losing votes being in fact disenfranchised when it comes to ambiguity resolution with winning votes. Also, using winning votes, a vote containing ties (possibly implicitly in the case of an incompletely ranked ballot) doesn't have the same effect as a number of equally weighted votes with total weight equaling one vote, such that the ties are broken in every possible way (a violation of Woodall's symmetric-completion criterion), as opposed to margins. Many see margins as more appealing from an intuitive point of view.

Under winning votes, if two more of the "B" voters decided to vote "BC", the A->C arm of the cycle would be overturned and Condorcet would pick C instead of B. This is an example of "Unburying" or "Later does harm". The margin method would pick C anyway.

Under the margin method, if three more "BC" voters decided to "bury" C by just voting "B", the A->C arm of the cycle would be strengthened and the resolution strategies would end up breaking the C->B arm and giving the win to B. This is an example of "Burying". The winning votes method would pick B anyway.

[edit] Related terms

Other terms related to the Condorcet method are:

  • Condorcet loser: the candidate who is less preferred than every other candidate in a pairwise matchup.
  • Weak Condorcet winner: a candidate who beats or ties with every other candidate in a pairwise matchup. There can be more than one weak Condorcet winner.
  • Weak Condorcet loser: a candidate who is defeated by or ties with every other candidate in a pair wise matchup. Similarly, there can be more than one weak Condorcet loser.

[edit] Comparison with instant runoff and first-past-the-post

There are circumstances, as in the example above, when both instant-runoff voting (IRV) and the 'first-past-the-post' plurality system will fail to pick the Condorcet winner. Proponents of the Condorcet criterion see it as a principal issue in selecting an electoral system. They see the Condorcet criterion as a natural extension of majority rule. Condorcet methods tend to encourage the selection of centrist candidates who appeal to the median voter. Here is an example that is designed to support IRV at the expense of Condorcet:

499 voters 3 voters 498 voters
1. A 1. B 1. C
2. B 2. C 2. B
3. C 3. A 3. A

B is preferred by a 501-499 majority to A, and by a 502-498 majority to C. So, according to the Condorcet criterion, B should win, despite the fact that very few voters rank B in first place. By contrast, IRV elects C and plurality elects A. Here is an example that is designed to support Condorcet at the expense of IRV:

33 voters 16 voters 16 voters 35 voters
1. A 1. B 1. B 1. C
2. B 2. A 2. C 2. B
3. C 3. C 3. A 3. A

B would win against either A or C by more than a 65-35 margin in a one-on-one election, but IRV eliminates B first, leaving a contest between the more "polar" candidates, A and C. Proponents of plurality voting state that their system is simpler than any other and more easily understood. All three systems are susceptible to tactical voting, but the types of tactics used and the frequency of strategic incentive differ in each method.

[edit] Potential for tactical voting

Like most voting methods, Condorcet methods are vulnerable to compromising. That is, voters can help avoid the election of a less-preferred candidate by insincerely raising the position of a more-preferred candidate on their ballot.

However, Condorcet methods are only vulnerable to compromising when there is a majority rule cycle. By contrast, instant runoff voting has compromising incentive when there is a majority rule cycle, but it may also have compromising incentive under other circumstances, i.e. when the Condorcet winner is eliminated before the final round.

Unlike IRV, Condorcet methods are vulnerable to burying. That is, voters can help a more-preferred candidate by insincerely lowering the position of a less-preferred candidate on their ballot. In general, this can be done by creating a false majority rule cycle that overrules a genuine pairwise defeat. Some Condorcet methods may be less vulnerable to the burying strategy than others.

[edit] Evaluation by criteria

Scholars of electoral systems often compare them using mathematically defined voting system criteria. The criteria which Condorcet methods satisfy vary from one Condorcet method to another. All Condorcet methods satisfy the Condorcet criterion and the majority criterion by definition; no Condorcet method satisfies participation or IIA.

Majority Monotonic Consistent Participation Condorcet loser IA independence Clone independence
Schulze Yes Yes No No Yes No
(see local IIA note)		 Yes
Ranked Pairs Yes Yes No No Yes No
(see local IIA note)		 Yes
Minimax Yes Yes No No No No No
Nanson Yes No No No Yes No No

[edit] Use of Condorcet voting

Condorcet voting is not currently used in government elections. However, it is starting to receive support in some public organizations. Organizations which currently use some variant of the Condorcet method are:

  1. The Debian project uses the Schulze method for internal referendums and to elect its leader.
  2. The Software in the Public Interest corporation uses the Schulze method to elect members of its board of directors.
  3. The Gentoo Linux project uses the Schulze method.
  4. The UserLinux project uses the Schulze method.
  5. The Free State Project used Minimax for choosing its target state.
  6. The voting procedure for the uk.* hierarchy of Usenet
  7. Five-Second Crossword Competition
  8. Kingman Hall, a student housing co-operative, uses the Schulze method for its elections.

See also: Use of the Schulze method

[edit] References

  1. ^ G. Hägele and F. Pukelsheim (2001). "Llull's writings on electoral systems". Studia Lulliana 3: 3-38.
  2. ^ See: Australian electoral reform and two concepts of representation

[edit] See also

[edit] External resources

Retrieved from "http://en.wikipedia.org../../../c/o/n/Condorcet_method.html"