Difference between revisions of "Condorcet method"

From Electowiki
Jump to navigation Jump to search
imported>Araucaria
(→‎Simple Explanation: Corrected and simplified grammar, added link for Condorcet Winner)
(39 intermediate revisions by 13 users not shown)
Line 1: Line 1:
Any election method conforming to the [[Condorcet criterion]] is known as a '''Condorcet method'''. The name comes from the 18th century mathematician and philosopher [[Marquis de Condorcet]], although the method was previously described by [[Ramon Llull]] in the 13th century.
+
{{Wikipedia}}
  
'''Condorcet''' is sometimes used to indicate the family of Condorcet methods as a whole.
+
Any election method conforming to the [[Condorcet criterion]] - that is, one which always elects the [[beats-all winner]] if one exists - is known as a '''Condorcet method'''. The name comes from the 18th century mathematician and philosopher [[Marquis de Condorcet]], although the method was previously described by [[Ramon Llull]] in the 13th century.
  
===Simple Explanation===
+
At present, the synonymous phrase '''"[[Instant-Round-Robin Voting|Instant Round Robin Voting]]" (IRRV)''' is being coined to leverage the public's greater familiarity with [[IRV |Instant Runoff Voting]] (IRV). This phrase is currently being used in a [http://groups.yahoo.com/group/Condorcet legislative effort] to implement a Condorcet variant ([[CSSD]]) in the state of Washington.
  
If a candidate defeats all other candidates head-to-head, that candidate is the [[Condorcet Criterion|Condorcet Winner]].  This can be determined through use of ranked ballots.  In rare occasions, each candidate is defeated by at least one other, so there is no Condorcet Winner.  In that case it is necessary to use some tiebreaking procedure.
+
'''Condorcet''' is sometimes used to indicate the family of Condorcet methods as a whole.
 
+
== Simple explanation ==
=== Casting ballots ===
 
  
Each voter fills out a [[preferential voting|ranked ballot]]. The voter can include less than all candidates under consideration.   Usually when a candidate ''is not listed'' on the voter's ballot they are considered less preferred than listed candidates, and ranked accordingly. However, some variations allow a "no opinion" default option where no for- or against- preference is counted for that candidate.  Write-ins are possible, but are somewhat more difficult to implement for automatic counting than in other election methods.  This is a counting issue, but results in the frequent omission of the write-in option in ballot software.
+
If one candidate is preferred by more voters than all other candidates (when [[pairwise counting|compared one-on-one]]), that candidate is the [[Condorcet Criterion|Condorcet Winner]], abbreviated as CW. This can be determined through use of ranked or rated ballots (i.e. if a voter ranks or rates one candidate higher than another). On rare occasions, there is no Condorcet winner (because of either [[pairwise counting#Terminology|ties]] in the head-to-head matchups or the [[Condorcet paradox]]. In that case it is necessary to use some tiebreaking procedure; the most common minimum standard for a Condorcet method's tiebreaking procedure is that it should be [[Smith-efficient]], that is, always elect someone from the [[Smith set]], the smallest group of candidates that win all their [[head-to-head matchup|head-to-head matchups]] against all candidates not in the group.
  
=== Counting ballots ===
+
== Casting ballots ==
 +
:''See also: [[Ballot]]''
  
Ballots are counted by considering all possible sets of two-candidate elections from all available candidates.  That is, each candidate is considered against each and every other candidateA candidate is considered to "win" against another on a single ballot if they are ranked higher than their opponentAll the votes for candidate Alice over candidate Bob are counted, as are all of the votes for Bob over AliceWhoever has the most votes in each one-on-one election wins.
+
Each voter fills out a [[preferential voting|ranked ballot]] or [[Cardinal voting|rated ballot]]. The voter can include less than all candidates under considerationUsually when a candidate ''is not listed'' on the voter's ballot they are considered less preferred than listed candidates, and ranked accordinglyHowever, some variations allow a "no opinion" default option where no for- or against- preference is counted for that candidateWrite-ins are possible, but are somewhat more difficult to implement for automatic counting than in other election methodsThis is a counting issue, but results in the frequent omission of the write-in option in ballot software.
 +
== Counting ballots ==
  
If a candidate is preferred over all other candidates, that candidate is the [[Condorcet Criterion|Condorcet candidate]]However, a Condorcet candidate may not exist, due to a fundamental [[Voting paradox|paradox]]: It is possible for the electorate to prefer A over B, B over C, and C over A simultaneously. This is called a circular tie, and it must be resolved by some other mechanism.
+
Ballots are counted by considering all possible sets of two-candidate elections from all available candidates. That is, each candidate is considered against each and every other candidate.  A candidate is considered to "win" against another on a single ballot and receive that ballot's vote in the matchup against their opponent if they are ranked or rated higher than their opponent. All the votes for candidate Alice over candidate Bob are counted, as are all of the votes for Bob over Alice. Whoever has the most votes in each one-on-one election wins.
  
==== Counting with matrices ====
+
If a candidate is preferred over all other candidates, that candidate is the [[Condorcet winner|Condorcet candidate]] (Condorcet winner).  However, a Condorcet candidate may not exist, due to a fundamental [[Voting paradox|paradox]]: It is possible for the electorate to prefer A over B, B over C, and C over A simultaneously.  This is called a majority rule cycle or Condorcet cycle, and it must be resolved by some other mechanism.
 +
=== Counting with matrices ===
 +
:''Main article: [[Pairwise counting]]''
  
 
A frequent implementation of this method will illustrate the basic counting method.  Consider an election between A, B, and C, and a ballot (B, C, A, D).  That is, a ballot ranking B first, C second, A third, and D forth.  This can be represented as a matrix, where the row is the runner under consideration, and the column is the opponent.  The cell at (runner,opponent) has a one if runner is preferred, and a zero if not.
 
A frequent implementation of this method will illustrate the basic counting method.  Consider an election between A, B, and C, and a ballot (B, C, A, D).  That is, a ballot ranking B first, C second, A third, and D forth.  This can be represented as a matrix, where the row is the runner under consideration, and the column is the opponent.  The cell at (runner,opponent) has a one if runner is preferred, and a zero if not.
  
{| border="1"
+
{| class="wikitable" border="1"
 
! !! A !! B !! C !! D
 
! !! A !! B !! C !! D
 
|-
 
|-
! A || — || 0 || 0 || 1
+
! A  
 +
|—|| 0 || 0 || 1
 
|-
 
|-
! B || 1 || — || 1 || 1
+
! B  
 +
| 1 ||—|| 1 || 1
 
|-
 
|-
! C || 1 || 0 || — || 1
+
! C  
 +
| 1 || 0 ||—|| 1
 
|-
 
|-
! D || 0 || 0 || 0 || —
+
! D  
 +
| 0 || 0 || 0 ||—
 
|}
 
|}
  
Line 37: Line 44:
 
When the sum matrix is found, the contest between each candidate is considered.  The number of votes for runner over opponent (runner,opponent) is compared the number of votes for opponent over runner (opponent,runner).  The one-on-one winner has the most votes.  If one candidate wins against all other candidates, that candidate wins the election.
 
When the sum matrix is found, the contest between each candidate is considered.  The number of votes for runner over opponent (runner,opponent) is compared the number of votes for opponent over runner (opponent,runner).  The one-on-one winner has the most votes.  If one candidate wins against all other candidates, that candidate wins the election.
  
The sum of all ballot matrices, the '''Condorcet pairwise matrix''', is the primary piece of data used to resolve circular ties (also called circular ambiguities).
+
The sum of all ballot matrices, the '''Condorcet pairwise matrix''', is the primary piece of data used to resolve majority rule cycles.
  
=== Key terms in ambiguity resolution ===
+
There are various ways to find the Condorcet winner from the pairwise matrix. [[:Category:Sequential comparison Condorcet methods|Sequential comparison]] is one such way: order all of the candidates in any manner desired, pairwise compare the first two, eliminate the loser of the matchup, and repeat until only one candidate remains. This requires ((number of candidates) - 1) pairwise comparisons, since for each comparison one candidate is eliminated, and all but one candidate must be eliminated. To check whether a Condorcet winner exists in a given election, do the previous procedure and then check whether the remaining candidate wins all of their pairwise matchups; this requires ((number of candidates) - 2) pairwise comparisons in the worst case, though if the ordering of the candidates in the procedure is done in such a way as to put candidates more likely to be Condorcet winners higher in the ordering, then in the best case 0 pairwise comparisons are required, since if the first candidate in the ordering turns out to be the Condorcet winner, all of their pairwise comparisons have already been done. Condorcet winners may often have a lot of 1st choice votes, especially in less contested elections, so it may be best to order the candidates descending by order of 1st choice votes, then 2nd choice votes, etc. These procedures can be used even for Condorcet PR methods by considering each winner set to be a candidate. 
 +
== Key terms in ambiguity resolution ==
  
 
Handling cases where there is not a single Condorcet winner is called ambiguity resolution in this article, though other phrases such as "cyclic ambiguity resolution" and "Condorcet completion" are used as well.
 
Handling cases where there is not a single Condorcet winner is called ambiguity resolution in this article, though other phrases such as "cyclic ambiguity resolution" and "Condorcet completion" are used as well.
Line 48: Line 56:
 
*# every candidate inside the set is pairwise unbeatable by any other candidate outside the set, i.e., ties are allowed
 
*# every candidate inside the set is pairwise unbeatable by any other candidate outside the set, i.e., ties are allowed
 
*# no proper (smaller) subset of the set fulfills the first property  
 
*# no proper (smaller) subset of the set fulfills the first property  
* '''Cloneproof''': a method that is immune to the presence of '''clones''' (candidates which are essentially identical to each other).  In some voting methods, a party can increase its odds of selection if it provides a large number of "identical" options.  A cloneproof voting method prevents this attack. See [[strategic nomination]].
+
* '''[[Independence of clone alternatives|Cloneproof]]''': a method that is immune to the presence of '''clones''' (candidates which are essentially identical to each other).  In some voting methods, a party can increase its odds of selection if it provides a large number of "identical" options.  A cloneproof voting method prevents this attack. See [[strategic nomination]]
 +
*[[Defeat strength]]: Different ways of measuring how strong a pairwise defeat is.  
  
=== Different ambiguity resolution methods ===
+
== Different ambiguity resolution methods ==
  
 
There are a countless number of "Condorcet methods" possible that resolve such ambiguities. The fact that Marquis de Condorcet himself already spearheaded the debate of which particular Condorcet method to promote has made the term "Condorcet's method" ambiguous.
 
There are a countless number of "Condorcet methods" possible that resolve such ambiguities. The fact that Marquis de Condorcet himself already spearheaded the debate of which particular Condorcet method to promote has made the term "Condorcet's method" ambiguous.
Line 56: Line 65:
  
 
Examples of Condorcet methods include:
 
Examples of Condorcet methods include:
* '''[[Black]]''' chooses the Condorcet winner when it exists and otherwise the [[Borda count|Borda winner]]. It is named after Duncan Black.
+
*'''[[Copeland's method|Copeland]]''' selects the candidate that wins the most pairwise matchups minus the number of matchups it loses (or simply, wins the most matchups).  Note that if there is no Condorcet winner, Copeland will often still result in a tie.
* '''[[Smith/IRV]]''' is [[instant-runoff voting]] with the candidates restricted to the Smith set.
+
*[[:Category:Condorcet-IRV hybrid methods|'''Condorcet-IRV hybrid methods''']]:
* '''[[Copeland's method|Copeland]]''' selects the candidate that wins the most pairwise matchups.  Note that if there is no Condorcet winner, Copeland will often still result in a tie.
+
**'''[[Smith/IRV]]''' is [[instant-runoff voting]] with the candidates restricted to the Smith set.
* '''[[Minmax|Minimax]]''' (also called '''Simpson''') chooses the candidate whose worst pairwise defeat is less bad than that of all other candidates.<sup>1</sup>
+
*[[:Category:Defeat-dropping Condorcet methods|'''Defeat-dropping Condorcet methods''']]:
* '''Smith/Minimax''' restricts the Minimax algorithm to the Smith set.<sup>1</sup>
+
**'''[[Minmax|Minimax]]''' (also called '''Simpson''' or '''Simpson-Kramer''') chooses the candidate whose worst pairwise defeat is less bad than that of all other candidates.<sup>1</sup>
* '''[[Ranked Pairs]]''' (RP) or '''Tideman''' (named after [[Nicolaus Tideman]]) with variations such as '''[[Maximize Affirmed Majorities]]''' (MAM) and  '''[[Maximum Majority Voting]]''' (MMV)<sup>1</sup>
+
***'''[[Smith//Minimax|Smith/Minimax]]''' restricts the Minimax algorithm to the [[Smith set]].<sup>1</sup>
* '''Schulze''' with several reformulations/variations, including '''Schwartz Sequential Dropping (SSD)''' and '''[[Cloneproof Schwartz Sequential Dropping]] (CSSD)'''<sup>1</sup>
+
**'''[[Ranked Pairs]]''' (RP) or '''Tideman''' (named after [[w:Nicolaus Tideman|Nicolaus Tideman]]) with variations such as '''[[Maximize Affirmed Majorities]]''' (MAM) and  '''[[Maximum Majority Voting]]''' (MMV).<sup>1</sup>
* '''[[Approval-Condorcet Hybrids]]''', such as '''[[Definite Majority Choice]]''', use an [[Approval Cutoff]] to augment the Condorcet pair wise array.  Many believe that such a method would make a good first-round public proposal.
+
**'''[[Schulze method|Schulze]]''' with several reformulations/variations, including '''Schwartz Sequential Dropping (SSD)''' and '''Cloneproof Schwartz Sequential Dropping (CSSD)'''<sup>1</sup>. Also see its [[Schulze method#Smith set-based variant|Smith set-based variant]].
 +
*[[:Category:Condorcet-cardinal hybrid methods|'''Condorcet-cardinal hybrid methods''']]:
 +
**'''[[Approval-Condorcet Hybrids]]''', such as '''[[Definite Majority Choice]]''', use an [[Approval Cutoff]] to augment the Condorcet pair wise array.  Many believe that such a method would make a good first-round public proposal.
 +
***'''[[Llull-Approval Voting]]'''- Elects the member of the [[Schwartz set]] with the greatest number of approvals.
 +
**'''[[Smith//Score]]''' chooses the candidate with the highest summed or average score in the Smith Set. '''[[Condorcet//Score]]''' chooses the [[Utilitarian winner|Score winner]] when no Condorcet winner exists. (These can only be done with rated ballots, or with ranked/rated ballots modified to include approval thresholds).
 +
*'''Condorcet-Borda hybrids''':
 +
**'''[[Black]]''' chooses the Condorcet winner when it exists and otherwise the [[Borda count|Borda winner]]. It is named after Duncan Black.
 +
**'''[[Baldwin]]''' computes the [[Borda count]] for all candidates, then iteratively deletes (eliminates) the candidate with the lowest count.
  
<sup>1</sup> There are different ways to measure the strength of each defeat in some methods.  Some use the margin of defeat (the difference between votes for and votes against), while others use winning votes (the votes favoring the defeat in question).
+
<sup>1</sup> There are different ways to measure the strength of each defeat in some methods; see the [[Defeat strength|defeat strength]] article.  Some use the margin of defeat (the difference between votes for and votes against), while others use winning votes (the votes favoring the defeat in question).
 
Electionmethods.org argues that there are several disadvantages of systems that use margins instead of winning votes.
 
Electionmethods.org argues that there are several disadvantages of systems that use margins instead of winning votes.
 
The website argues that using margins "destroys" some information about majorities, so that the method can no longer honor information about what majorities have determined and that consequently margin-based systems cannot support a number of desirable voting properties.
 
The website argues that using margins "destroys" some information about majorities, so that the method can no longer honor information about what majorities have determined and that consequently margin-based systems cannot support a number of desirable voting properties.
Line 75: Line 91:
 
The text below describes (variants of) these methods in more detail.
 
The text below describes (variants of) these methods in more detail.
  
=== Ranked Pairs, Maximize Affirmed Majorities (MAM), and Maximum Majority Voting (MMV) ===
+
== Ranked Pairs, Maximize Affirmed Majorities (MAM), and Maximum Majority Voting (MMV) ==
  
In the Ranked Pairs (RP) voting method, as well as the variations Maximize Affirmed Majorities (MAM)
+
In the Ranked Pairs (RP) voting method, as well as the variations Maximize Affirmed Majorities (MAM) and Maximum Majority Voting (MMV), pairs of defeats are ranked (sorted) from largest majority to smallest majority. Then each pair is considered, starting with the defeat supported by the largest majority. Pairs are "affirmed" only if they do not create a cycle with the pairs already affirmed. Once completed, the affirmed pairs are followed to determine the winner.
and Maximum Majority Voting (MMV), pairs of defeats are ranked (sorted)
 
from largest majority to smallest majority.
 
Then each pair is considered, starting with the defeat supported by the largest majority.
 
Pairs are "affirmed" only if they do not create a cycle with the pairs already affirmed.
 
Once completed, the affirmed pairs are followed to determine the winner.
 
  
In essence, RP and its variants (such as MAM and MMV)
+
In essence, RP and its variants (such as MAM and MMV) 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.
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.
 
  
The difference betweeen RP and its variants is in the details of the ranking approach.
+
The difference between RP and its variants is in the details of the ranking approach. Some definitions of RP use margins, while other definitions use winning votes (not margins). Both MAM and MMV are explicitly defined in terms of winning votes, not winning margins. In MAM and MMV, if two defeat pairs have the same number of votes for a victory, the defeat with the smaller defeat is ranked higher. If this still doesn't disambiguate between the two, MAM and MMV perform slightly differently. In MAM, information from a "tiebreaker" vote is used (which could be a distinguished vote such as the vote of a "speaker", but unless there is a distinguished vote, a randomly-chosen vote is used). In MMV all such conflicting matchups are ignored (though any non-conflicting matchups of that size are still included).
Some definitions of RP use margins, while other definitions use winning votes (not margins).
+
== Schulze method ==
Both MAM and MMV are explicitly defined in terms of winning votes, not winning margins.
 
In MAM and MMV, if two defeat pairs have the same number of votes for a victory, the defeat with
 
the smaller defeat is ranked higher.
 
If this still doesn't disambiguate between the two, MAM and MMV perform slightly differently.
 
In MAM, information from a "tiebreaker" vote is used
 
(which could be a distinguished vote such as the vote of a "speaker",
 
but unless there is a distinguished vote, a randomly-chosen vote is used).
 
In MMV all such conflicting matchups are ignored (though any non-conflicting matchups of that size are still included).
 
  
=== Cloneproof Schwartz Sequential Dropping (CSSD) ===
+
The [[Schulze method]] resolves votes as follows:
 
 
The "[[Cloneproof Schwartz Sequential Dropping]]" (CSSD) method resolves votes as follows:
 
  
 
# 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).
 
# 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).
Line 108: Line 106:
  
 
In other words, this procedure repeatedly throws away the narrowest defeats, until finally the largest number of votes left over produce an unambiguous decision.
 
In other words, this procedure repeatedly throws away the narrowest defeats, until finally the largest number of votes left over produce an unambiguous decision.
 
The "Beatpath Winner" algorithm produces equivalent results.
 
 
 
== Related terms ==
 
== Related terms ==
  
 
Other terms related to the Condorcet method are:
 
Other terms related to the Condorcet method are:
* '''Condorcet loser''': the candidate who is less preferred than every other candidate in a pair wise matchup.
+
* '''[[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 pair wise matchup. There can be more than one weak Condorcet winner.
+
* '''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.
 
* '''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.
  
 
== An example ==
 
== An example ==
 +
 +
See also: [[Pairwise_counting#Example_with_numbers]] 
  
 
Imagine an election for the capital of Tennessee, a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south.  Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga).    Here's the population breakdown by metro area (surrounding county):  
 
Imagine an election for the capital of Tennessee, a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south.  Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga).    Here's the population breakdown by metro area (surrounding county):  
Line 131: Line 128:
 
Let's say that in the vote, the voters vote based on geographic proximity.  Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:
 
Let's say that in the vote, the voters vote based on geographic proximity.  Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:
  
<table border=1>
+
<table class="wikitable" border="1">
 
<tr>
 
<tr>
 
<td>
 
<td>
Line 190: Line 187:
 
* [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption
 
* [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption
  
In this election, Nashville is the Condorcet winner and thus the winner under all possible Condorcet methods.  
+
In this election, Nashville is the Condorcet winner (Nashville beats Memphis 58 to 42, and Chattanooga and Knoxville 68 to 32) and thus the winner under all possible Condorcet methods.
 +
 
 +
An alternative way of demonstrating this (using [[ISDA]]-based logic) is that a majority of voters prefer any city other than Memphis, so that knocks Memphis out of contention. When looking at Memphis voter's new 1st choice among the candidates, it is Nashville, resulting in Nashville having a 68% majority of 1st choices and thus pairwise beating all others. 
 +
 
 +
Alternative formatting of the pairwise matrix: 
 +
{| class="wikitable"
 +
|+
 +
!
 +
!Memphis
 +
!Nashville
 +
!Chattanooga
 +
!Knoxville
 +
|-
 +
|Memphis
 +
| ---
 +
|42 (-16 Loss)
 +
|42 (-16 Loss)
 +
|42 (-16 Loss)
 +
|-
 +
|Nashville
 +
|58 (+16 Win)
 +
| ---
 +
|68 (+36 Win)
 +
|68 (+36 Win)
 +
|-
 +
|Chattanooga
 +
|58 (+16 Win)
 +
|32 (-36 Loss)
 +
| ---
 +
|83 (+66 Win)
 +
|-
 +
|Knoxville
 +
|58 (+16 Win)
 +
|32 (-36 Loss)
 +
|17 (-66 Loss)
 +
| ---
 +
|}
 +
 
 +
== Connection to cardinal methods ==
 +
 
 +
Score Voting can be thought of as a Condorcet method where a voter is allowed to give a fraction of a vote to a candidate in a pairwise matchup against other candidates, rather than a full vote or nothing. Further, the amount of a vote the voter gives in one runoff directly alters the amount they give in another; if they arrange their scores such that they give 0.4 of a vote to help one candidate beat another, this automatically means they can at best arrange their scores such that they give up to 0.6 of their vote to help the second candidate beat someone else. Assuming a voter would vote the exact same way in a Score Voting runoff between all possible pairs of candidates as they did in the original Score election, Score elects the Condorcet winner using this modified definition.<ref>https://rangevoting.org/CondDQ.html</ref> 
 +
 
 +
It's possible to modify Score to be more like a traditional Condorcet method by allowing voters to write the scores they would give to every possible pair of candidates in a Score runoff, and then using a Condorcet method to process this, treating a score of, say, A5 B3 (where the max score is 5) as 0.4 votes for A>B. As this would be utterly infeasible with just a few candidates running however, one way to accomplish most of the same objective is to allow voters to mark on their ballots that they want their vote strategically optimized, meaning that if their cardinally expressed preferences are A5 B3 Z2, instead of having their vote considered as B3 Z2 in an B vs. Z runoff, it would be considered as B5 Z0 (if the max score is 5), which is functionally equivalent to the Plurality voting runoffs that are used for the traditional Condorcet winner definition. This strategic optimization can be done fractionally to allow a voter to customize how much optimization they want to be done with their scores in each runoff. It is also possible for voters to indicate an approval threshold, meaning that for all approved candidates, no strategic optimization is applied to pairwise matchups between them, but all pairwise matchups between approved and disapproved candidates are strategically optimized. With this modification, if all voters use strategic optimization, Score becomes a traditional Condorcet method (which will need a cycle resolution method to be applied at times), but if no voters strategically optimize, it remains Score (which never needs cycle resolution methods to be applied). 
 +
 
 +
Note that the above schemes can make Score fail the logical property that a voter's strength of preference between any pair of candidates must equal the sum of the strengths of preference between all sequential pairs of candidates in a beatpath from the first candidate of the pair to the second. The failure of this property seems to be the major reason traditional Condorcet methods can have Condorcet cycles and one major reason for why they fail certain properties such as Favorite Betrayal and Independence of Irrelevant Alternatives.
 +
 
 +
See also [[Pairwise counting#Cardinal methods]] and [[Order theory#Strength of preference]].
 +
 
 +
== Demonstrating pairwise counting ==
 +
Also see: [[Pairwise counting]]
 +
 
 +
Condorcet winners and the Smith Set in general are often the equilibrium outcomes of iterated voting methods. The CW in particular is the Nash Equilibrium of Score Voting. Here are demonstrations of equilibrium convergence using Asset Voting (in the sidebar to the right).
 +
 
 +
<gallery widths="500px" heights="400px" mode="packed">
 +
File:Asset Condorcet Winner example modified.png|A Condorcet winner is found by algorithmizing Asset Voting and then using it to find the equilibrium winner.
 +
File:Asset Smith Set example.png|The Smith Set found using an algorithmized version of Asset Voting.
 +
</gallery>
  
 
== Use of Condorcet voting ==
 
== Use of Condorcet voting ==
Line 196: Line 249:
 
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:
 
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:
  
# The Debian project uses Cloneproof Schwartz Sequential Dropping.
+
# The [http://www.debian.org/ Debian] project uses the [[Schulze method]].
# The Software in the Public Interest project uses Cloneproof Schwartz Sequential Dropping.
+
# The [http://www.spi-inc.org/ Software in the Public Interest (SPI)] project uses the [[Schulze method]].
# The UserLinux project uses Cloneproof Schwartz Sequential Dropping.
+
# The [http://www.gentoo.org/ Gentoo Linux] project uses the [[Schulze method]].
# The Free State Project uses a Condorcet method for choosing its target state
+
# The [http://www.userlinux.com/ UserLinux] project uses the [[Schulze method]].
 +
# The [[W:Free State Project|Free State Project]] used a Condorcet method for choosing its target state
 
# The voting procedure for the uk.* hierarchy of Usenet
 
# The voting procedure for the uk.* hierarchy of Usenet
 
#[http://www.rsabey.pwp.blueyonder.co.uk/rpc/fscc/ Five-Second Crossword Competition]
 
#[http://www.rsabey.pwp.blueyonder.co.uk/rpc/fscc/ Five-Second Crossword Competition]
{{fromwikipedia}}
+
 
 +
== Notes ==
 +
All Condorcet methods pass the [[Mutual majority criterion|mutual majority criterion]] when there is a Condorcet winner. This is because the CW is guaranteed to be a member of any set of candidates that can pairwise beat all candidates not in the set, and the mutual majority set is such a set, because all candidates in it are ranked by a majority over all candidates not in the set. [[Smith-efficient]] Condorcet methods always pass the [[Mutual majority criterion|mutual majority criterion]].
 +
 
 +
Most Condorcet methods allow for equal-ranking. Because of this, it is possible to vote [[Approval voting]]-style. In fact, if all voters vote Approval-style, the Smith set will only have candidates who pairwise tie, rather than who have [[Condorcet cycle|Condorcet cycles]]. 
 +
 
 +
It is common terminology for Condorcet methods that start by electing the Condorcet winner if there is one, but otherwise run some other voting method, to be named as "Condorcet//voting method". For example, [[Condorcet//Score]]. The Condorcet methods that start by eliminating all candidates not in a given set of candidates and then running some other voting method are named as "Given set//voting method" (sometimes with only one "/"). For example, [[Smith//IRV]] is [[IRV]] run on the [[Smith set]].
 +
 
 +
One concern with Condorcet methods is that it is very difficult to do [[pairwise counting]] for elections with 10 of more candidates, since that is at least (0.5*10*((10-1)=9))=45 pairwise matchups to record the details of. Allowing write-in candidates makes things even more complex. One possible solution would be to have a primary beforehand using a voting method better than [[FPTP]] to pick 5 top candidates, and then only allow voters to rank those top 5. For all other candidates, they'd be able to approve or score each of them. The rated information could then be used to elect someone other than one of the top 5 when the non-top 5 candidates have significantly higher ratings, but otherwise only elect one of the top 5. The primary itself could be made slightly semi-proportional as well. {{fromwikipedia}}
 +
 
 +
== External links ==
 +
 
 +
* [http://condorcet.ericgorr.net Condorcet Voting Calculator] by Eric Gorr
 +
* [http://robla.net/1996/politics/condorcet.html Condorcet's Method] by Rob Lanphier
 +
* [http://accuratedemocracy.com/ Accurate Democracy] by Rob Loring
 +
* [http://fc.antioch.edu/~james_green-armytage/voting.htm Voting methods resource page] by James Green-Armytage
 +
* [http://radicalcentrism.org/majority_voting.html Maximum Majority Voting] by Ernest Prabhakar
 +
* [http://www.mcs.vuw.ac.nz/~ncj/comp303/schulze.pdf A New Monotonic and Clone-Independent Single-Winner Election Method] ([[Portable Document Format|PDF]]) by Markus Schulze ([http://www.citizensassembly.bc.ca/resources/submissions/csharman-10_0409201706-143.pdf mirror1], [http://lists.gnu.org/archive/html/demexp-dev/2003-09/pdflQW7IlpAfC.pdf mirror2])
 +
* [http://www.OpenSTV.org/ OpenSTV] — Software for computing Condorcet methods and STV by Jeffrey O'Neill
 +
* [http://www5.cs.cornell.edu/~andru/civs/ CIVS, a free web poll service using the Condorcet method] by Andrew Myers
 +
* [http://www1.fee.uva.nl/creed/pdffiles/MoulinCh4Elferink.pdf Voting and Social Choice] Demonstration and commentary on Condorcet method. ([[Portable Document Format|PDF]]) By Herve Moulin
 +
* [http://groups.yahoo.com/group/Condorcet Yahoo work group] Helping a WA state legislator to draft Condorcet election rules to replace recently nullified statute. Moderated by Jeffry R. Fisher
 +
[[Category:Condorcet methods]]

Revision as of 08:49, 28 March 2020

Wikipedia has an article on:

Any election method conforming to the Condorcet criterion - that is, one which always elects the beats-all winner if one exists - is known as a Condorcet method. The name comes from the 18th century mathematician and philosopher Marquis de Condorcet, although the method was previously described by Ramon Llull in the 13th century.

At present, the synonymous phrase "Instant Round Robin Voting" (IRRV) is being coined to leverage the public's greater familiarity with Instant Runoff Voting (IRV). This phrase is currently being used in a legislative effort to implement a Condorcet variant (CSSD) in the state of Washington.

Condorcet is sometimes used to indicate the family of Condorcet methods as a whole.

Simple explanation

If one candidate is preferred by more voters than all other candidates (when compared one-on-one), that candidate is the Condorcet Winner, abbreviated as CW. This can be determined through use of ranked or rated ballots (i.e. if a voter ranks or rates one candidate higher than another). On rare occasions, there is no Condorcet winner (because of either ties in the head-to-head matchups or the Condorcet paradox. In that case it is necessary to use some tiebreaking procedure; the most common minimum standard for a Condorcet method's tiebreaking procedure is that it should be Smith-efficient, that is, always elect someone from the Smith set, the smallest group of candidates that win all their head-to-head matchups against all candidates not in the group.

Casting ballots

See also: Ballot

Each voter fills out a ranked ballot or rated ballot. The voter can include less than all candidates under consideration. Usually when a candidate is not listed on the voter's ballot they are considered less preferred than listed candidates, and ranked accordingly. However, some variations allow a "no opinion" default option where no for- or against- preference is counted for that candidate. Write-ins are possible, but are somewhat more difficult to implement for automatic counting than in other election methods. This is a counting issue, but results in the frequent omission of the write-in option in ballot software.

Counting ballots

Ballots are counted by considering all possible sets of two-candidate elections from all available candidates. That is, each candidate is considered against each and every other candidate. A candidate is considered to "win" against another on a single ballot and receive that ballot's vote in the matchup against their opponent if they are ranked or rated higher than their opponent. All the votes for candidate Alice over candidate Bob are counted, as are all of the votes for Bob over Alice. Whoever has the most votes in each one-on-one election wins.

If a candidate is preferred over all other candidates, that candidate is the Condorcet candidate (Condorcet winner). However, a Condorcet candidate may not exist, due to a fundamental paradox: It is possible for the electorate to prefer A over B, B over C, and C over A simultaneously. This is called a majority rule cycle or Condorcet cycle, and it must be resolved by some other mechanism.

Counting with matrices

Main article: Pairwise counting

A frequent implementation of this method will illustrate the basic counting method. Consider an election between A, B, and C, and a ballot (B, C, A, D). That is, a ballot ranking B first, C second, A third, and D forth. This can be represented as a matrix, where the row is the runner under consideration, and the column is the opponent. The cell at (runner,opponent) has a one if runner is preferred, and a zero if not.

A B C D
A 0 0 1
B 1 1 1
C 1 0 1
D 0 0 0

Cells marked "—" are logically zero, but are blank for clarity—they are not considered, as a candidate can not be defeated by himself. This binary matrix is inversely symmetric: (runner,opponent) is ¬(opponent,runner). The utility of this structure is that it may be easily added to other ballots represented the same way, to give us the number of ballots which prefer each candidate. The sum of all ballot matrixes is called the sum matrix—it is not symmetric.

When the sum matrix is found, the contest between each candidate is considered. The number of votes for runner over opponent (runner,opponent) is compared the number of votes for opponent over runner (opponent,runner). The one-on-one winner has the most votes. If one candidate wins against all other candidates, that candidate wins the election.

The sum of all ballot matrices, the Condorcet pairwise matrix, is the primary piece of data used to resolve majority rule cycles.

There are various ways to find the Condorcet winner from the pairwise matrix. Sequential comparison is one such way: order all of the candidates in any manner desired, pairwise compare the first two, eliminate the loser of the matchup, and repeat until only one candidate remains. This requires ((number of candidates) - 1) pairwise comparisons, since for each comparison one candidate is eliminated, and all but one candidate must be eliminated. To check whether a Condorcet winner exists in a given election, do the previous procedure and then check whether the remaining candidate wins all of their pairwise matchups; this requires ((number of candidates) - 2) pairwise comparisons in the worst case, though if the ordering of the candidates in the procedure is done in such a way as to put candidates more likely to be Condorcet winners higher in the ordering, then in the best case 0 pairwise comparisons are required, since if the first candidate in the ordering turns out to be the Condorcet winner, all of their pairwise comparisons have already been done. Condorcet winners may often have a lot of 1st choice votes, especially in less contested elections, so it may be best to order the candidates descending by order of 1st choice votes, then 2nd choice votes, etc. These procedures can be used even for Condorcet PR methods by considering each winner set to be a candidate.

Key terms in ambiguity resolution

Handling cases where there is not a single Condorcet winner is called ambiguity resolution in this article, though other phrases such as "cyclic ambiguity resolution" and "Condorcet completion" are used as well.

The following are key terms when discussing ambiguity resolution methods:

  • Smith set: the smallest set of candidates in a particular election who, when paired off in pairwise elections, can beat all other candidates outside the set.
  • Schwartz set: 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
  • Cloneproof: a method that is immune to the presence of clones (candidates which are essentially identical to each other). In some voting methods, a party can increase its odds of selection if it provides a large number of "identical" options. A cloneproof voting method prevents this attack. See strategic nomination
  • Defeat strength: Different ways of measuring how strong a pairwise defeat is.

Different ambiguity resolution methods

There are a countless number of "Condorcet methods" possible that resolve such ambiguities. The fact that Marquis de Condorcet himself already spearheaded the debate of which particular Condorcet method to promote has made the term "Condorcet's method" ambiguous. Indeed, it can be argued that the large number of different competing Condorcet methods has made the adoption of any single method extremely difficult.

Examples of Condorcet methods include:

1 There are different ways to measure the strength of each defeat in some methods; see the defeat strength article. Some use the margin of defeat (the difference between votes for and votes against), while others use winning votes (the votes favoring the defeat in question). Electionmethods.org argues that there are several disadvantages of systems that use margins instead of winning votes. The website argues that using margins "destroys" some information about majorities, so that the method can no longer honor information about what majorities have determined and that consequently margin-based systems cannot support a number of desirable voting properties.

Ranked Pairs and Schulze are procedurally in some sense opposite approaches:

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

The text below describes (variants of) these methods in more detail.

Ranked Pairs, Maximize Affirmed Majorities (MAM), and Maximum Majority Voting (MMV)

In the Ranked Pairs (RP) voting method, as well as the variations Maximize Affirmed Majorities (MAM) and Maximum Majority Voting (MMV), pairs of defeats are ranked (sorted) from largest majority to smallest majority. Then each pair is considered, starting with the defeat supported by the largest majority. Pairs are "affirmed" only if they do not create a cycle with the pairs already affirmed. Once completed, the affirmed pairs are followed to determine the winner.

In essence, RP and its variants (such as MAM and MMV) 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.

The difference between RP and its variants is in the details of the ranking approach. Some definitions of RP use margins, while other definitions use winning votes (not margins). Both MAM and MMV are explicitly defined in terms of winning votes, not winning margins. In MAM and MMV, if two defeat pairs have the same number of votes for a victory, the defeat with the smaller defeat is ranked higher. If this still doesn't disambiguate between the two, MAM and MMV perform slightly differently. In MAM, information from a "tiebreaker" vote is used (which could be a distinguished vote such as the vote of a "speaker", but unless there is a distinguished vote, a randomly-chosen vote is used). In MMV all such conflicting matchups are ignored (though any non-conflicting matchups of that size are still included).

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 narrowest defeats, until finally the largest number of votes left over produce an unambiguous decision.

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.

An example

See also: Pairwise_counting#Example_with_numbers

Imagine an election for the capital of Tennessee, a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south. Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga). Here's the population breakdown by metro area (surrounding county):

Condorcet Tennessee.png
  • Memphis (Shelby County): 826,330
  • Nashville (Davidson County): 510,784
  • Chattanooga (Hamilton County): 285,536
  • Knoxville (Knox County): 335,749

Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:

42% of voters (close to Memphis)
1. Memphis
2. Nashville
3. Chattanooga
4. Knoxville

26% of voters (close to Nashville)
1. Nashville
2. Chattanooga
3. Knoxville
4. Memphis

15% of voters (close to Chattanooga)
1. Chattanooga
2. Knoxville
3. Nashville
4. Memphis

17% of voters (close to Knoxville)
1. Knoxville
2. Chattanooga
3. Nashville
4. Memphis

The results would be tabulated as follows:

Pairwise Election Results
A
Memphis Nashville Chattanooga Knoxville
BMemphis[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 (by repeatedly removing Condorcet winner): 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

In this election, Nashville is the Condorcet winner (Nashville beats Memphis 58 to 42, and Chattanooga and Knoxville 68 to 32) and thus the winner under all possible Condorcet methods.

An alternative way of demonstrating this (using ISDA-based logic) is that a majority of voters prefer any city other than Memphis, so that knocks Memphis out of contention. When looking at Memphis voter's new 1st choice among the candidates, it is Nashville, resulting in Nashville having a 68% majority of 1st choices and thus pairwise beating all others.

Alternative formatting of the pairwise matrix:

Memphis Nashville Chattanooga Knoxville
Memphis --- 42 (-16 Loss) 42 (-16 Loss) 42 (-16 Loss)
Nashville 58 (+16 Win) --- 68 (+36 Win) 68 (+36 Win)
Chattanooga 58 (+16 Win) 32 (-36 Loss) --- 83 (+66 Win)
Knoxville 58 (+16 Win) 32 (-36 Loss) 17 (-66 Loss) ---

Connection to cardinal methods

Score Voting can be thought of as a Condorcet method where a voter is allowed to give a fraction of a vote to a candidate in a pairwise matchup against other candidates, rather than a full vote or nothing. Further, the amount of a vote the voter gives in one runoff directly alters the amount they give in another; if they arrange their scores such that they give 0.4 of a vote to help one candidate beat another, this automatically means they can at best arrange their scores such that they give up to 0.6 of their vote to help the second candidate beat someone else. Assuming a voter would vote the exact same way in a Score Voting runoff between all possible pairs of candidates as they did in the original Score election, Score elects the Condorcet winner using this modified definition.[1]

It's possible to modify Score to be more like a traditional Condorcet method by allowing voters to write the scores they would give to every possible pair of candidates in a Score runoff, and then using a Condorcet method to process this, treating a score of, say, A5 B3 (where the max score is 5) as 0.4 votes for A>B. As this would be utterly infeasible with just a few candidates running however, one way to accomplish most of the same objective is to allow voters to mark on their ballots that they want their vote strategically optimized, meaning that if their cardinally expressed preferences are A5 B3 Z2, instead of having their vote considered as B3 Z2 in an B vs. Z runoff, it would be considered as B5 Z0 (if the max score is 5), which is functionally equivalent to the Plurality voting runoffs that are used for the traditional Condorcet winner definition. This strategic optimization can be done fractionally to allow a voter to customize how much optimization they want to be done with their scores in each runoff. It is also possible for voters to indicate an approval threshold, meaning that for all approved candidates, no strategic optimization is applied to pairwise matchups between them, but all pairwise matchups between approved and disapproved candidates are strategically optimized. With this modification, if all voters use strategic optimization, Score becomes a traditional Condorcet method (which will need a cycle resolution method to be applied at times), but if no voters strategically optimize, it remains Score (which never needs cycle resolution methods to be applied).

Note that the above schemes can make Score fail the logical property that a voter's strength of preference between any pair of candidates must equal the sum of the strengths of preference between all sequential pairs of candidates in a beatpath from the first candidate of the pair to the second. The failure of this property seems to be the major reason traditional Condorcet methods can have Condorcet cycles and one major reason for why they fail certain properties such as Favorite Betrayal and Independence of Irrelevant Alternatives.

See also Pairwise counting#Cardinal methods and Order theory#Strength of preference.

Demonstrating pairwise counting

Also see: Pairwise counting

Condorcet winners and the Smith Set in general are often the equilibrium outcomes of iterated voting methods. The CW in particular is the Nash Equilibrium of Score Voting. Here are demonstrations of equilibrium convergence using Asset Voting (in the sidebar to the right).

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.
  2. The Software in the Public Interest (SPI) project uses the Schulze method.
  3. The Gentoo Linux project uses the Schulze method.
  4. The UserLinux project uses the Schulze method.
  5. The Free State Project used a Condorcet method for choosing its target state
  6. The voting procedure for the uk.* hierarchy of Usenet
  7. Five-Second Crossword Competition

Notes

All Condorcet methods pass the mutual majority criterion when there is a Condorcet winner. This is because the CW is guaranteed to be a member of any set of candidates that can pairwise beat all candidates not in the set, and the mutual majority set is such a set, because all candidates in it are ranked by a majority over all candidates not in the set. Smith-efficient Condorcet methods always pass the mutual majority criterion.

Most Condorcet methods allow for equal-ranking. Because of this, it is possible to vote Approval voting-style. In fact, if all voters vote Approval-style, the Smith set will only have candidates who pairwise tie, rather than who have Condorcet cycles.

It is common terminology for Condorcet methods that start by electing the Condorcet winner if there is one, but otherwise run some other voting method, to be named as "Condorcet//voting method". For example, Condorcet//Score. The Condorcet methods that start by eliminating all candidates not in a given set of candidates and then running some other voting method are named as "Given set//voting method" (sometimes with only one "/"). For example, Smith//IRV is IRV run on the Smith set.

One concern with Condorcet methods is that it is very difficult to do pairwise counting for elections with 10 of more candidates, since that is at least (0.5*10*((10-1)=9))=45 pairwise matchups to record the details of. Allowing write-in candidates makes things even more complex. One possible solution would be to have a primary beforehand using a voting method better than FPTP to pick 5 top candidates, and then only allow voters to rank those top 5. For all other candidates, they'd be able to approve or score each of them. The rated information could then be used to elect someone other than one of the top 5 when the non-top 5 candidates have significantly higher ratings, but otherwise only elect one of the top 5. The primary itself could be made slightly semi-proportional as well.

This page uses Creative Commons Licensed content from Wikipedia (view authors).

External links

  • https://rangevoting.org/CondDQ.html