Difference between revisions of "Condorcet method"
m (Inserting newlines around the Template:Image frame in hopes that the diff is more readable. It doesn't appear that I was successful, but oh well.)
|Line 1:||Line 1:|
(FF>C shows the number of voters who prefer FF over C, for example):
(FF>C shows the number of voters who prefer FF over C, for example):
|Line 21:||Line 23:|
FF (French Fries) is the CW here.
FF (French Fries) is the CW here.
|caption=Example of finding the Condorcet winner|border=|max-width=}}
Any election method conforming to the [[Condorcet criterion]] - that is, one which always elects the [[beats-all winner]], a candidate who can beat any other candidate in a runoff, 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. Many Condorcet advocates agree that a further criterion that Condorcet methods should pass is the [[Smith criterion]], which means the Condorcet method will always elect someone from the [[Smith set]] when there is no beats-all winner (usually due to the [[Condorcet paradox]]).
'''Condorcet''' is sometimes used to refer to the family of Condorcet methods as a whole.
'''Condorcet''' is sometimes used to refer to the family of Condorcet methods as a whole.
Revision as of 20:30, 26 November 2021
(FF>C shows the number of voters who prefer FF over C, for example):
If for each pair of candidates, we subtract the number of votes preferring the second candidate over the first from the number of votes preferring the first to the second, then we'll know which one won the head-to-head matchup.
H>FF:-2, H>C:20 (Win)
The Condorcet winner (if one exists) will be the candidate who got a majority of votes (as indicated by the positive margin) in all of their head-to-head matchups.FF (French Fries) is the CW here.
Any election method conforming to the Condorcet criterion - that is, one which always elects the beats-all winner, a candidate who can beat any other candidate in a runoff, 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. Many Condorcet advocates agree that a further criterion that Condorcet methods should pass is the Smith criterion, which means the Condorcet method will always elect someone from the Smith set when there is no beats-all winner (usually due to the Condorcet paradox).
Condorcet is sometimes used to refer to the family of Condorcet methods as a whole.
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" or cycle resolution/completion procedure; a very common 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.
- See also: Ballot
Each voter fills out a ranked ballot or rated ballot (i.e. they rank the candidates 1st, 2nd, 3rd, or they rate the candidates, for example, a 0 out of 5, a 3 out of 5, etc.) 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, with the voter considered to have no preference between any of them. 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.
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/matchup wins the matchup.
If a candidate is preferred over all other candidates i.e. wins all of their matchups, 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 in each head-to-head matchup simultaneously. This is called a majority rule cycle or Condorcet cycle, and it must be resolved by some other mechanism (usually either by using another voting method, or "dropping" weak defeats in order to end the cycle).
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.
Each cell should be read as "number of votes preferring candidate on the left beat candidate on the top", so:
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. Note that the voter's ranked preference among the candidates can actually be reconstructed from the matrix made for their own vote: the candidate that the voter preferred in the most matchups is their 1st choice, the next-most-preferred candidate their 2nd choice, etc. Ties can be represented by two candidates each being preferred in the most matchups yet not preferred over each other.
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 in defeat-dropping Condorcet methods, and can be used to find the Condorcet winner and Smith set in any Condorcet method.
Finding the Condorcet winner
There are various ways to find the Condorcet winner from the pairwise matrix. The simplest is to look for a single candidate who has a positive margin of votes against all other candidates in each matchup (i.e. if they got 5 votes and another candidate 4 votes in the pair's matchup, then the margin is 1 vote in favor of the first candidate, indicating they won the matchup), if one exists. Copeland more generally can help find the Smith set by looking for a smallest group of candidates that have victories against all others, by starting from the candidates with the most victories in their head-to-head matchups.
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
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:
- 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
- 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. Useful when deciding which defeats to "drop" in defeat-dropping Condorcet 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. Indeed, it can be argued that the large number of different competing Condorcet methods has made the adoption of any single method extremely difficult.
Condorcet methods can generally be categorized into methods that can be computed with only the head-to-head matchups (Copeland, defeat-droppers), those that require also some ranked information (Condorcet-IRV/Borda methods), or those that also use rated information (Condorcet-cardinal). Some of them use either ranked or rated information (Category:Pairwise sorted methods).
Examples of Condorcet methods include:
- 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.
- Condorcet-IRV hybrid methods:
- Defeat-dropping Condorcet methods:
- Minimax (also called Simpson or Simpson-Kramer) chooses the candidate whose worst pairwise defeat is less bad than that of all other candidates.1
- Ranked Pairs (RP) or Tideman (named after Nicolaus Tideman) with variations such as Maximize Affirmed Majorities (MAM) and Maximum Majority Voting (MMV).1
- Schulze with several reformulations/variations, including Schwartz Sequential Dropping (SSD) and Cloneproof Schwartz Sequential Dropping (CSSD)1. Also see its Smith set-based variant.
- 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.
- Smith//Score chooses the candidate with the highest summed or average score in the Smith Set. Condorcet//Score chooses the 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:
Defeat-dropping Condorcet methods
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) the defeat-dropping 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).
The Schulze 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).
- 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.
See also Pairwise counting#Terminology
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. Because of Condorcet cycles, it is possible for the Smith set to, for example, have one weak Condorcet winner, and three candidates that pairwise beat each other but pairwise tie with the WCW; for this reason, it is not always best to elect the weak Condorcet winner over the candidates that tie with them.
- weak Condorcet loser: a candidate who is defeated by or ties with every other candidate in a pairwise matchup. Similarly, there can be more than one weak Condorcet loser.
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):
- 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)
26% of voters (close to Nashville)
15% of voters (close to Chattanooga)
17% of voters (close to Knoxville)
The results would be tabulated as follows:
|B||Memphis||[A] 58% |
|[A] 58% |
|[A] 58% |
|Nashville||[A] 42% |
|[A] 32% |
|[A] 32% |
|Chattanooga||[A] 42% |
|[A] 68% |
|[A] 17% |
|Knoxville||[A] 42% |
|[A] 68% |
|[A] 83% |
|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 mutual 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 (shows the margins in each matchup by subtracting number of votes for one candidate from the votes for the other):
|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.
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 beat-or-tie path from the first candidate of the pair to the second; see Ranked voting#Strength of preference for an example. 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.
Approval voting can be thought of as a Condorcet method where voters must rank every candidate either 1st or last. This can most clearly be seen by observing that, when voters are limited to ranking candidates in this way in a Condorcet method, then Condorcet methods can be counted in exactly the same way as Approval using the Pairwise counting#Negative vote-counting approach, with the candidate being marked on the most ballots getting the most voters backing them in head-to-head matchups, and thus being the CW.
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).
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.
Comparison to other extensions of majority rule
The fundamental argument for Condorcet over other extensions of majority rule is that it explicitly monitors for the Condorcet paradox. This is what makes it vulnerable to Favorite Betrayal, however, since voters can make their lesser evil become the CW by preventing their favorite from pairwise beating them. See the Tied at the top rule for a way out of this. Another possible argument is that it may be the best way to avoid the center squeeze effect.
Making any voting method Condorcet-efficient
Any voting method can be made a Condorcet method by simply adding a condition that a Condorcet winner will win if one exists before running the voting method. It is possible to further make a voting method Smith-efficient by taking various approaches, such as eliminating candidates one by one until there is a Condorcet winner (like in Benham's method) or eliminating all candidates not in the Smith set before running the voting method's procedure (i.e. Smith//IRV), or taking a more complex approach of repeatedly eliminating all candidates not in a particular set and eliminating the loser of another voting method Tideman's Alternative methods).
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 is Score voting modified to elect a CW. The Condorcet methods that start by eliminating all candidates not in a given set of candidates and then run 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.
It is possible to do a first round where the Smith set of candidates is identified, and then a second round where another voting method is used to select among the Smith set (or any set). For example, Smith//Approval is the automatic form of doing this with Approval voting.
Connection to Asset voting negotiations
Condorcet methods can be seen as highly related to Asset voting: the voters indicate their preferences on how they'd negotiate and form majority coalitions for their favorite candidates, and when those candidates aren't viable or aren't in consideration, would intervene to help elect some candidates they prefer more than others. In this sense, extending Condorcet to PR (Condorcet PR) is not too difficult: Droop proportionality must be met, because Droop quotas can force their preference in any negotiation where each person can only maximally support up to a candidate, and certain other constraints must be met, such as allowing B to win in the following example:
because while A does pairwise beat B, C would always have 49 votes and thus actually win overall if the A-top voters try to only support A and not shift towards B, because A would have 26 votes, B 25, but C 49. In general, this type of "semi-solid coalition" where a group of voters are almost a solid coalition except that some in the group prefer another candidate over the solid coalition's candidates, with no voters outside of the coalition having preferences between the semi-solid coalition's candidates, has to always elect the candidate that everyone in the coalition supports to be related to Asset. In addition, the Condorcet PR method must be based on D'Hondt, because Asset voting allows voters to split their votes to obtain more seats (similar to free riding).
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. And in fact, if every voter ranks a candidate either 1st or last with a probability proportional to their cardinal utility for that candidate, then you get a Smith set ranking mirroring the Score voting ranking with probability approaching 1 when there are many voters. This is because if 100 voters consider a candidate a 3 out of 10, then if they use a 30% probability of ranking that candidate 1st, otherwise ranking them last, then it is very likely the candidate will end up ranked 1st on 30 of their ballots and last on 70, similar to being approved by only 30 of them. This mitigates one common utilitarian concern with Condorcet, that it might let a majority force its weak preference onto the minority; this is because voters with weak preferences may be willing to equally rank candidates in order to allow voters with stronger preferences to have the deciding vote. See also the KP transform, which can be used to model transforming cardinal utilities into ranked ballots by making Score ballots into Approval ballots, and then Approval ballots into ranked ballots.
Difficulty of vote-counting
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. An alternative solution if using a Condorcet-cardinal hybrid method is to count the ballots twice, first only recording the cardinal information, and then use this to select the 5 to 10 best candidates who qualify to win, between whom the pairwise matchups will also be recorded. Also see Condorcet criterion#Criticisms.
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:
- The Debian project, Software in the Public Interest (SPI) project, Gentoo Linux project, and UserLinux project use the Schulze method.
- The Free State Project used a Condorcet method for choosing its target state
- The voting procedure for the uk.* hierarchy of Usenet
- Five-Second Crossword Competition
Nanson's method, which is a Condorcet method, was used in city elections in the U.S. town of Marquette, Michigan in the 1920s.
At one point, the synonymous phrase (to Condorcet voting) "Instant Round Robin Voting" (IRRV) was being coined to leverage the public's greater familiarity with Instant Runoff Voting (IRV). This phrase was being used in a legislative effort to implement a Condorcet variant (CSSD) in the state of Washington.
|This page uses Creative Commons Licensed content from Wikipedia (view authors).|
- Condorcet Voting Calculator by Eric Gorr (includes Ranked Pairs, and Schulze)
- Condorcet's Method by Rob Lanphier
- Accurate Democracy by Rob Loring
- Voting methods resource page by James Green-Armytage
- Maximum Majority Voting by Ernest Prabhakar
- A New Monotonic and Clone-Independent Single-Winner Election Method (PDF) by Markus Schulze (mirror1, mirror2) (Schulze method)
- OpenSTV — Software for computing Condorcet methods and STV by Jeffrey O'Neill
- CIVS, a free web poll service using the Condorcet method by Andrew Myers
- Voting and Social Choice Demonstration and commentary on Condorcet method. (PDF) By Herve Moulin
- Yahoo work group Helping a WA state legislator to draft Condorcet election rules to replace recently nullified statute. Moderated by Jeffry R. Fisher
- ""Condorcet" definition quibble". RangeVoting.org. Retrieved 2020-04-06.
- Mclean, Iain (October 2002). Australian electoral reform and two concepts of representation. APSA Jubilee Conference. Retrieved 2020-04-02.