minguo.info

In the Condorcet election method, voters rank the candidates in order of preference. The vote counting procedure then takes into account each preference of each voter for one candidate over another. It does so by conceptually breaking the election down into a series of separate races between each possible pairing of candidates, hence it is sometimes referred to as a "pairwise" method. If one of the candidates beats each of the other candidates in their one-on-one race, then that candidate wins. Otherwise, the result is ambiguous and a standard procedure is used to resolve the ambiguity. Unlike conventional plurality voting, Condorcet voting gives voters little incentive to falsify their true preferences.

Pairwise Matrices

The basics of Condorcet voting are best illustrated by example. Suppose an election has four candidates designated A, B, C, and D. Each voter ranks the candidates in order of preference. For example, the vote (B,D,C) ranks B first, D second, and C third. The last choice is implicit. Voters are not required to fully rank the entire list. For example, the vote (D,B) indicates that the voter has no preference between A and C. Each vote translates to a pairwise matrix showing the equivalent vote for each possible pairing of candidates, as illustrated in the tables below.

Table 1 shows the pairwise matrix for the vote (B,D,C). Since B is ranked first, the B row gets a 1 in each of the columns for the other three candidates. Since D is ranked above C and A, the D row gets a 1 in the C and A columns. Finally, since C is ranked above A, the C row gets a 1 in the A column. Since A is not ranked, the A row is filled with zeros. All cells that do not get a 1 get a 0 (the diagonal cells are always empty). As another example, Table 2 shows the pairwise matrix for the vote (D,B). The pairwise matrix for each vote are summed to get the pairwise matrix sum. Table 3 shows the sum for the two votes discussed here. Corresponding elements of the individual pairwise matrices are simply added together to get the pairwise matrix sum.

The final pairwise matrix sum is used to determine the winner. If one of the candidates wins his or her one-on-one race with each of the other candidates, that candidate wins. For example, consider the pairwise matrix sum shown in Table 4 below. In this example, B beats A by 87-63, B beats C by 78-72, and B beats D by 73-51. Because B beats each of the other candidates, B wins.

Cyclic Ambiguity Resolution

[Note: This section is currently undergoing revision and may not be entirely correct.]

Sometimes no candidate beats each of the other candidates. The result is then ambiguous, and the ambiguity must be resolved. Such cyclic ambiguities are true ambiguities in the preferences of the electorate, and the fact that Condorcet accurately reflects them is not a problem with the Condorcet method itself, as is often erroneously assumed. Several excellent methods exist for resolving ambiguities, each with minor advantages and disadvantages compared to the other methods. The determination of the preferable method is an ongoing area of research and discussion. Two of those methods will be discussed here.

The ambiguous pairwise matrix of Table 5 will be used as an example to show how cyclical ambiguities are resolved. In this example, none of the candidates is unbeaten: A is beaten by D and C; B is beaten by A and D; C is beaten by B; and D is beaten by C. The notation A/B ("A over B") will be used to denote the defeat of B by A. A cyclic ambiguity is a set of defeats that "wraps around" on itself. For example, the list of defeats A/B, B/C, C/A forms a cycle. A cycle always involves at least three and possibly more candidates. A cycle also involves at least three and possibly more defeats.

The magnitude of a defeat can be defined as either the margin of defeat or the number of votes cast against the defeated candidate. These are referred to as "margins" and "winning votes" (wv). For example, in Table 5, D defeated B by 60-50, so the margin of the defeat is 10 and the wv strength is 60. For purposes of this tutorial, the wv measure of defeats will be used.

The notation D/B (60) will be used to denote the defeat of B by D with a magnitude of 60 votes. Here are the defeats in Table 5, ordered by magnitude:

1. D/B (60)
2. B/C (50)
3. A/B (40)
4. C/A (30)
5. C/D (25)
6. D/A (20)

Two methods of cyclic ambiguity resolution will be discussed: Plain Condorcet (PC) and the Schulze Condorcet algorithm. Plain Condorcet is simpler, but the Schulze algorithm is the state of the art. Software that implements Schulze algorithm is provided through a link below. If the number of candidates is three or less, Plain Condorcet and Schulze give the same result, but for more than three candidates they can give different results.

Plain Condorcet (PC)

The Plain Condorcet method of ambiguity resolution is the original method proposed by Condorcet himself. It can be stated as follows: drop the weakest (smallest magnitude) defeat, repeating if necessary until one of the candidates is unbeaten.

The Plain Condorcet method works as follows for the example shown above. D/A is the weakest defeat, so it is dropped. Candidate A still has another defeat, so no candidate is unbeaten yet. Now C/D is the weakest defeat, so it is dropped. Candidate D is now unbeaten and wins.

Although it is superior to plurality and Instant Runoff Voting, Plain Condorcet suffers from some technical deficiencies compared to the Schulze method to be discussed below and is not recommended for use in actual public elections -- unless its simplicity makes the difference between public acceptance or lack thereof.

Schulze Condorcet Algorhthm

The Schulze procedure starts with the determinion of the Schwartz set, the definition of which depends on a couple of prerequisite definitions:

1. An unbeaten set is a set of candidates of whom none are beaten by any candidate ouside that set.
2. An innermost unbeaten set is an unbeaten set that doesn't contain a smaller unbeaten set.
3. The Schwartz set is the set of candidates who are in innermost unbeaten sets.

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). Otherwise, drop the weakest defeat among the Schwartz set, determine the new Schwartz set, and repeat the procedure.

The ordered list of defeats for the example is repeated here for convenience:

1. D/B (60)
2. B/C (50)
3. A/B (40)
4. C/A (30)
5. C/D (25)
6. D/A (20)

The Schulze method works as follows for this example. Initially the entire set of candidates constitutes the Schwartz set because it doesn't contain a smaller unbeaten set. The weakest defeat is D/A, so it is dropped. The innermost unbeaten set is now still the set of all the candidates, and the smallest defeat is now C/D, so it is dropped. Candidate D is now unbeaten and wins. Note that Plain Condorcet and Schulze produced the same winner in this case.

The Schulze method of resolving cyclic ambiguities has been found to be equivalent to another method called Beatpath Winner, which can be stated as follows:

• X has a beatpath to Y if X beats Y or if X beats another candidate that has a beatpath to Y.
• A sequence of defeats that makes it possible to say that X has a beatpath to Y is called a beatpath from X to Y.
• The strength of a beatpath is measured by the strength of its weakest defeat.
• X has a beatpath win against Y if the strongest beatpath from X to Y is stronger than the strongest beatpath from Y to X.
• The winner (or winners in the case of a tie) is the candidate against whom no candidate has a beatpath win.

See Eric Gorr's handy Online Condorcet Voting Calculator.