## Condorcet Voting Explained
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: pairwise matrix for vote (B,D,C)
- | A | B | C |
D |
A | - | 0 | 0 |
0 |
B | 1 | - | 1 |
1 |
C | 1 | 0 | - |
0 |
D | 1 | 0 | 1 |
- |
Table 2: pairwise matrix for vote (D,B)
- | A | B | C |
D |
A | - | 0 | 0 |
0 |
B | 1 | - | 1 |
0 |
C | 0 | 0 | - |
0 |
D | 1 | 1 | 1 |
- |
Table 3: pairwise matrix sum for previous votes
- | A | B | C |
D |
A | - | 0 | 0 |
0 |
B | 2 | - | 2 |
1 |
C | 1 | 0 | - |
0 |
D | 2 | 1 | 2 |
- |
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.
Table 4: simple pairwise matrix
- | A | B | C |
D |
A | - | 63 | 89 |
57 |
B | 87 | - | 78 |
73 |
C | 69 | 72 | - |
74 |
D | 67 | 51 | 52 |
- |
Table 5: ambiguous pairwise matrix
- | A | B | C |
D |
A | - | 40 | 22 |
13 |
B | 37 | - | 50 |
50 |
C | 30 | 35 | - |
25 |
D | 20 | 60 | 20 |
- |
### 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:
- D/B (60)
- B/C (50)
- A/B (40)
- C/A (30)
- C/D (25)
- 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:
- An unbeaten set is a set of candidates of whom none are beaten by
any candidate ouside that set.
- An innermost unbeaten set is an unbeaten set that doesn't contain a
smaller unbeaten set.
- 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:
- D/B (60)
- B/C (50)
- A/B (40)
- C/A (30)
- C/D (25)
- 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.
We have programmed the Beatpath Winner algorithm in Python and made
it available for download. See also Eric
Gorr's handy Online
Condorcet Voting Calculator and Andrew Myers' Condorcet Internet Voting
Service.
ElectionMethods.org |