Condorcet method: Difference between revisions

From electowiki
Content added Content deleted
VisualWikitext
No edit summary
(Add Marquette's use of Nanson)
Line 297: Line 297:
#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]

Nanson's method, which is a Condorcet method, was used in city elections in the U.S. town of Marquette, Michigan in the 1920s.<ref name="Mclean">{{cite conference | last=Mclean | first=Iain | title=Australian electoral reform and two concepts of representation | url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.362.5357 |date=October 2002|access-date=2020-04-02|conference=APSA Jubilee Conference}}</ref>

{{fromwikipedia}}
{{fromwikipedia}}


Line 313: Line 316:


[[Category:Condorcet methods]]
[[Category:Condorcet methods]]

==References==


<references />
<references />

Revision as of 11:13, 2 April 2020

Wikipedia has an article on:
Finding the Condorcet winner using pairwise counting.

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 (due to the Condorcet paradox).

Condorcet is sometimes used to refer to 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" 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.

Casting ballots

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.

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/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.

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

Each cell should be read as "number of votes preferring candidate on the left beat candidate on the top", so:

A B C D
A — A>B A>C A>D
B B>A — B>C B>D
C C>A C>B — C>D
D D>A D>B D>C —

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.

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

All of the candidates in 1st place (Andy, Brianna, Charles) are in the Smith set. See the Smith set ranking article for more information on this image.

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. 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.

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) 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).

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

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.

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):

  • 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 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 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

See also Score voting#Connection to Condorcet 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).

  • A Condorcet winner is found by algorithmizing Asset Voting and then using it to find the equilibrium winner.

    A Condorcet winner is found by algorithmizing Asset Voting and then using it to find the equilibrium winner.

  • The Smith Set found using an algorithmized version of Asset Voting.

    The Smith Set found using an algorithmized version of Asset Voting.

Notes

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. 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.

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. This mitigates one common utilitarian concern with Condorcet, that it might let a majority force its weak preference onto the minority, 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.

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.

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.

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, Software in the Public Interest (SPI) project, Gentoo Linux project, and UserLinux project use 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

Nanson's method, which is a Condorcet method, was used in city elections in the U.S. town of Marquette, Michigan in the 1920s.[2]

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

External links

References

  1. ↑ https://rangevoting.org/CondDQ.html
  2. ↑ Mclean, Iain (October 2002). Australian electoral reform and two concepts of representation. APSA Jubilee Conference. Retrieved 2020-04-02.
Retrieved from "https://electowiki.org/wiki/Condorcet_method?oldid=9911"