Condorcet winner criterion

From electowiki
(Redirected from Pairwise champion)
Wikipedia has an article on:

An electoral system satisfies the "Condorcet winner criterion", also known as the Condorcet criterion, if it always chooses the Condorcet winner when one exists. The "Condorcet winner" is sometimes referred to as the "Condorcet candidate", "pairwise champion" or "beats-all winner". The "Condorcet winner" of an election is the candidate who is preferred by more voters than any other candidate in pairwise matchups. This is determined by observing whether more voters rank or score the Condorcet winner higher than each of the other candidates than the other way around.

The Condorcet winner criterion for a voting system is that it chooses the beats-all winner when one exists. Any method conforming to the Condorcet criterion is known as a Condorcet method. Though Condorcet winner criterion is sometimes referred to as simply the "Condorcet criterion", it's important not to confuse the Condorcet winner criterion with the "Condorcet loser criterion" .

Mainly because of Condorcet's voting paradox, a beats-all winner will not always exist in a given set of votes. However, there will always be a smallest group of candidates such that more voters prefer anyone in the group over anyone outside of the group. If the beats-all winner exists, they will be the only candidate in this group, which is called the Smith set. Voting methods that always elect from the Smith set are known as "Smith-efficient".  

Example

As an example, if there are 3 candidates, with head-to-head matchups indicating a 51% majority prefers the second candidate over the first, and a 43% plurality prefer the second over 37% preferring the third (with 20% of voters having no preference), then the second candidate gets more votes than their competitors in all matchups and so they are the Condorcet winner.

Detailed example

Suppose the voters had been polled on their preferences among the candidates, and the following preferences in head-to-head matchups are produced between French Fries (FF), Hamburger (H), and Cookies (C) (FF>C shows the number of voters who prefer FF over C, for example):

FF>H:51, FF>C:60

H>FF:49, H>C:70

C>FF:40, C>H:20

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.

(Margins)

FF>H:2 (Win), FF>C:20 (Win)

H>FF:-2, H>C:20 (Win)

C>FF:-20, C>H:-50

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.

A more general wording of Condorcet criterion definition

Requirements:

  1. The voting system must allow the voter to vote as many transitive pairwise preferences as desired. (Typically that's in the form of an unlimited ranking)
  2. If there are one or more unbeaten candidates, then the winner should be an unbeaten candidate. (Though usually this requirement is simply "If there is one candidate who beats all others, then they must win."; see the below section on Weak Condorcet winners for a critique of this definition)

Traditional definition of "beat":

X beats Y iff more voters vote X over Y than vote Y over X.

Majority Condorcet criterion

The majority Condorcet criterion is the same as the above, but with "beat" replaced by "majority-beat", defined to be "X majority-beats Y iff over 50% voters vote X over Y." Thus, a majority Condorcet winner is a Condorcet winner who majority-beats all other candidates.

Complying methods

Black, Condorcet//Approval, Smith/IRV, Copeland, Llull-Approval Voting, Minmax, Smith/Minmax, ranked pairs and variations (maximize affirmed majorities, maximum majority voting), and Schulze comply with the Condorcet criterion.

Approval voting, Range voting, Borda count, plurality voting, and instant-runoff voting do not comply with the Condorcet Criterion. However, any voting method that collects enough information to detect pairwise preferences (i.e. scoring or ranking methods) can be "forced" to comply with the Condorcet criterion by automatically electing the Condorcet winner if one exists (or alternatively, eliminating all candidates not in the Smith Set) before doing anything else.

Commentary

Compromise candidate

On a one-dimensional political spectrum, the beats-all winner will be at the position of the median voter. See the following example:

Supposing this is the voter distribution, with three candidates Left, Center, and Right, with voters concentrated in each area of the distribution as given, with the yellow voters preferring Left, the green preferring Center, and the blue preferring Right. Then the Condorcet winner is Center, because a majority - the Center voters plus the Left voters - prefers Center to Right, and another majority prefers Center to Left.

Instant-runoff voting, which does not pass the Condorcet criterion, fails to detect Center's support and thus Center is eliminated early. However, if the majority preferring Center to the IRV winner knew this in advance, they could have used compromising strategy to force Center to be elected anyway. See below.

Note that the "Center" candidate is only the center of the voters' distribution. If this were a conservative party primary, the center of the distribution would likely be a conservative candidate, not a centrist.

Equilibrium point for various voting methods

The Condorcet winner/Smith set is a common equilibrium point in many voting methods. This is because a majority/plurality of voters have no incentive to deviate towards another candidate. The Condorcet criterion can thus be considered a type of automatic strategy, which reduces the need for compromising strategy by electing candidates who could have won with majority-strength compromising.

An example for Approval voting:

35: A>B|>C

34: B>C|

31: C>B|>A

B is the CW. If voters approve everyone they ranked before the "|", then B is approved by all voters, and wins. If any of the three groups of voters here raises their approval threshold (only approves their 1st choice), then another group has an incentive to maintain their approval threshold where it is i.e. if C-top voters stop approving B, then the 69 voters who prefer B>C have an incentive to move their approval thresholds between B and C to ensure B is approved by a majority and C is not. Note that this requires both accurate polling and coordinated strategic voting.

Non-complying methods

Non-ranking methods such as plurality and approval cannot comply with the Condorcet criterion because they do not allow each voter to fully specify their preferences. But instant-runoff voting allows each voter to rank the candidates, yet it still does not comply. A simple example will prove that IRV fails to comply with the Condorcet criterion.

Consider, for example, the following vote count of preferences with three candidates {A,B,C}:

499:A>B>C
498:C>B>A
3:B>C>A

In this case, B is preferred to A by 501 votes to 499, and B is preferred to C by 502 to 498, hence B is preferred to both A and C. So according to the Condorcet criteria, B should win. By contrast, according to the rules of IRV, B is ranked first by the fewest voters and is eliminated, and C wins with the transferred voted from B; in plurality voting A wins with the most first choices. Note that B and C are a mutual majority, so most majority rule-based methods would rule A out of winning. If A drops out, then B becomes the majority's 1st choice; so this is an example of IRV failing independence of irrelevant alternatives.

See Score voting#Majority-related criteria to see how Score can fail the Condorcet criterion. In general however, it is expected that the Condorcet winner (and Smith Set candidates in general) will almost always be very high-utility when compared to the utilitarian winner.

Independence of Irrelevant Alternatives

Note that the Condorcet criterion also implies the following criterion which is somewhat related to Independence of Irrelevant Alternatives: removing losing candidates can't change the result of an election if there is a Condorcet winner.[1] In addition, adding candidates who are pairwise beaten by the Condorcet winner (when one exists) can't change the result of the election.

Weak Condorcet winners

Sometimes there is no Condorcet winner, but there may be candidate(s) who are preferred by at least as many voters as all other candidates (i.e. they beat or tie all other candidates; as many voters rank or score them higher or equally as each of the other candidates as the other way around), who are known as weak Condorcet winners. While it may thus seem reasonable that a Condorcet method should pass a condition of always electing solely from the set of weak Condorcet winners when no regular Condorcet winner exists and at least one weak Condorcet winner exists, this guaranteeably leads to failures of reversal symmetry and clone immunity, and so it may be better to say that the set of weak Condorcet winners should have some, but not total priority to win. Example (parentheses are used to indicate implied rankings):
3 A(>B1=B2=B3)

1 B1>B2>B3(>A)

1 B2>B3>B1(>A)

1 B3>B1>B2(>A)
A is the only weak Condorcet winner here, as they tie 3 to 3 when compared to B1, B2, and B3, and each of the latter 3 candidates suffer at least one pairwise defeat, and since there is no regular Condorcet winner (since every candidate has at least one pairwise tie or defeat), by the above-proposed condition A must win. To show a failure of reversal symmetry, suppose the ballots are reversed:
3 B1=B2=B3(>A)

1 A>B3>B2>B1

1 A>B1>B3>B2

1 A>B2>B1>B3
Again A is the only weak CW here, with there being no regular CW, so the same condition holds that A must still win. To show a failure of clone immunity, suppose B2 and B3 drop out of the race:
3 A(>B1)


3 B1(>A)
Now both of A and B1 are weak CWs, because they both pairwise tie each other. In this particular example, since there is nothing that distinguishes either candidate from the other, the neutrality criterion requires that both A and B1 must have an equal probability of winning i.e. both must have a 50% chance. This means that removing clones of B1 increased B1's chances of winning (which were originally at 0%, since A was guaranteed to win earlier i.e. had a 100% chance of winning.) [2]

Weak CWs have also been called Condorcet non-losers, with the requirement that they always win when they exist being called Exclusive-Condorcet. [3]

Multi-winner generalizations

Schulze has proposed a generalization of the Condorcet criterion for multi-winner methods:[4] Suppose all but M+1 candidates are eliminated from the ballots, and the remaining candidates include candidate b. If b is always a winner when electing M winners from the M+1 remaining candidates, no matter who the other M remaining candidates are, then b is an M-seat Condorcet winner.

A method passes the M-seat Condorcet criterion if its M-seat election outcome always contains such a b when he exists, and passes the multi-winner Condorcet criterion if it passes the M-seat Condorcet criterion for all M.

When M=1, and the method elects the candidate with the most first preferences when there are only two candidates, the generalization reduces to the ordinary Condorcet criterion.

Note that Bloc Ranked Pairs and Bloc Score voting (if scored methods are considered) would pass this criterion, though they are not proportional, and the latter is not a Condorcet method in the single-winner case. So it may make more sense to consider Schulze's criterion as one of several that a multi-winner method ought to pass to be considered a Condorcet multi-winner or Condorcet PR method, rather than the definitive one.

In addition to Schulze's generalization, Gehrein, and Aziz et al. have proposed different multi-winner generalizations, based on the concept of stability.[5]

Abstract Condorcet Criterion

See Self-referential Smith-efficient Condorcet method.

The Condorcet criterion can be abstractly modified to be "if the voting method would consider a candidate to be better than all other candidates when compared one-on-one, then it must consider that candidate better than all other candidates." Approval Voting and Score Voting, as well as traditional Condorcet methods pass this abstract version of the criterion, while IRV and STAR Voting don't (since they reduce to Plurality in the 2-candidate case and thus would need to always elect the traditional Condorcet winner in order to pass).[6]

One logical property (call it the "additive beatpath" property) that all traditional Condorcet methods fail, but which Approval and Score Voting pass is "if a voter with acyclic ranked preferences expresses a preference between two candidates (say A>Z), then the strength of that voter's preference between those two candidates (the amount of support they give to A to help beat Z) must equal the sum of the strengths of preference of all pairwise matchups of candidates that are in a beatpath from A to Z when sequentially going through each pair." In other words, if a voter's cardinally expressed preference is A5 B3 Z2, then under Score Voting the strength of A>Z (5-2=3 points, or 60% of the max score) will always equal the strength of preference of A>B (5-3=2 points/40% support) plus the strength of preference of B>Z (3-2=1 point/20% support), since that is just 3 = 2 + 1. With a traditional Condorcet method, this will fail because A>Z will be evaluated at 100% support, as will A>B and B>Z, and therefore the Condorcet method would give 100% = 100% + 100% which is incorrect. It would appear Borda methods pass this property, as a voter voting A>B>Z would have each candidate receive one point for every rank higher they are than another candidate, and thus a beatpath could be sequentially evaluated and strengths of preference added up to remain consistent. The failure of this property is the cause of Condorcet cycles in traditional Condorcet methods, and Condorcet cycles are the only time where traditional Condorcet methods can fail Favorite Betrayal and Independence of Irrelevant Alternatives, so in some sense, cardinal methods are a special case of Condorcet methods modified to pass the additive beatpath property, and on this basis cardinal methods pass and fail various properties that traditional Condorcet methods don't.

Approval Voting (and thus Score Voting when all voters use only the minimum or maximum score) is equivalent to a traditional Condorcet method where a voter must rank all candidates 1st or last. Score Voting where some voters give some candidates intermediate scores can be treated as Approval Voting using the KP transform, and thus treated as a traditional Condorcet method in the same way as Approval Voting.

Strategic implications

Every Condorcet method is susceptible to burial in at least some elections, and Condorcet is also incompatible with later-no-harm and later-no-help. However, if a method passes the informed majority coalition criterion so a coordinated majority can always force its outcome, then prefixing a Condorcet step to that method can never increase the proportion of elections where strategy pays off.[7][8]

Criticism

The Condorcet criterion and methods that pass it have been criticized for certain reasons. Some common arguments are:

Operational concerns

Susceptibility to strategy

Quality of winners

  • The weak centrist argument: Condorcet methods don't take strength of preference information into account, and thus can't distinguish between a strong consensus candidate and a bland centrist who is inoffensive enough to be everybody's second choice.
  • The Condorcet criterion's preference for consensus winners may lead centrists to win so often that they become near-monopolists, if the political contest takes place on a line (like a left-right spectrum).
    • Rebuttal: The problem vanishes with multidimensional politics, and thus Condorcet methods reward candidates who break politics out of its one-dimensional mold.[11]


FairVote critique

Here is one critique by FairVote, with some analysis/rebuttals:
If there is a Condorcet winner, it means that he or she is preferred to every other candidate – not necessarily liked more than other candidates and not necessarily ready to represent the constituents.

If one candidate is preferred over another, it necessarily means the voter likes that candidate more than the other.

Condorcet winners are centrist by nature, regardless of the preferences of the electorate.

Not necessarily. If an electorate is 55% liberal, the Condorcet winner will be liberal, whereas if the electorate is 55% conservative, the CW will be conservative. They may lean towards the center to some degree (if the minority prefers them more than other candidates supported by the majority), but they do shift with regards to the voters' preferences.

Consider an election with three candidates: a strong liberal who commands between 40% to 50% of the vote, a moderate with about 10% to 15%, and a strong conservative between 40% and 50%. By being everyone’s second choice, the moderate will certainly be the Condorcet winner as long as neither of the two more extreme candidates earns a majority of the vote. If the electorate is moderate, then great – the Condorcet winner makes sense. But if the electorate mostly wants something to the left or right of the center, is it still the case that the moderate should always win? Wouldn’t the 80% to 90% of voters who lean clearly to one side prefer that their candidate have a nonzero chance of winning, as opposed to the impossibility of victory under Condorcet methods?

The problem with this argument is that if most of the voters prefer something other than the centrist candidate, they are free to rank candidates on both sides above the moderate candidate, which would guarantee the moderate wouldn't be the CW. In other words, if voters indicate they prefer the moderate over the other side, then they shouldn't be surprised if this allows them to get the moderate instead of the one of the other side's candidates as a winner.

Looking to Burlington [...] The mayor was vulnerable, but Montroll only secured 22% of first choices and only 29% when the field was reduced to three, basically failing to make the case for his candidacy to enough people. If Montroll had won due to Condorcet voting being in place, the resulting controversy in Burlington would likely have been far louder than the outcry against Kiss’s IRV victory. Having a candidate win after being in last place when the field was reduced to three would have taken a lot of explaining to voters. They might have accepted the results; more likely, they would have challenged them, particularly if they understood that Democrats would suddenly be the dominant party in mayor’s race even when failing to finish in the top two.

This criticism can easily be averted if the voters on either side of the Democrats simply refuse to rank the Democrats above the other side..

Notes

It is rather common for pollsters to do head-to-head matchup polling to see who is likely to win in an FPTP general election. Condorcet polling can be done in a similar way, except more efficiently, by allowing polled voters to rank or rate the candidates.[13]

One strategy common to most Condorcet methods is to prevent a candidate from being a Condorcet winner by burying them (giving them a pairwise defeat against another candidate).

Alternative definitions

Alternative definition of "beat" that is claimed to be more consistent with the preferences, intent and wishes of equal-top-ranking voters:

(Argument supporting that claim can be found at the Symmetrical ICT article.)

(X>Y) means the number of ballots voting X over Y.

(Y>X) means the number of ballots voting Y over X.

(X=Y)T means the number of ballots voting X and Y at top

(a ballot votes a candidate at top if it doesn't vote anyone over him/her)

X beats Y iff (X>Y) > (Y>X) + (X=Y)T

With this alternative definition of "beat", FBC and the Condorcet Criterion are compatible.

It has been recently argued that the definition of the verb "beat" should be regarded as external to the Condorcet Criterion...and that "beat should be defined in a way that interprets equal-top ranking consistent with the actual preferences, intent and wishes of the equal-top-ranking voters. When such a definition of "beat" is used in the Condorcet Criterion definition, then the Condorcet Criterion is compatible with FBC, and there are Condorcet methods that pass FBC. Discussion and arguments on that matter can be found at the Symmetrical ICT article.

Outside of voting theory

Analogues to the Condorcet criterion have been proposed in non-voting contexts; it appears in many places when discussing how to aggregate ranked information. It has been used to discuss search engine rankings [14] and metasearch[15]. The concept of a Smith set ranking (which is sometimes referred to as the "extended/generalised Condorcet criterion") helps structure how the ranking of all options should be, rather than only the winner.

References

  1. Schulze, Markus (2018-03-15). "The Schulze Method of Voting". p. 351. arXiv:1804.02973 [cs.GT]. "The Condorcet criterion for single-winner elections (section 4.7) is important because, when there is a Condorcet winner b ∈ A, then it is still a Condorcet winner when alternatives a1,...,an ∈ A \ {b} are removed. So an alternative b ∈ A doesn’t owe his property of being a Condorcet winner to the presence of some other alternatives. Therefore, when we declare a Condorcet winner b ∈ A elected whenever a Condorcet winner exists, we know that no other alternatives a1,...,an ∈ A \ {b} have changed the result of the election without being elected."
  2. Schulze, Markus (2018-03-15). "The Schulze Method of Voting". p. 206–207. arXiv:1804.02973 [cs.GT].
  3. "Voting matters, Issue 3: pp 8-15". www.votingmatters.org.uk. Retrieved 2020-05-09. Exclusive-Condorcet (see Fishburn[2]). If there is a Condorcet non-loser, then at least one Condorcet non-loser should be elected.
  4. Schulze, Markus (2018-03-15). "The Schulze Method of Voting". p. 351. arXiv:1804.02973 [cs.GT].
  5. Aziz, Haris; Elkind, Edith; Faliszewski, Piotr; Lackner, Martin; Skowron, Piotr (2017-01-27). "The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality". arXiv:1701.08023 [cs.GT].
  6. The "official" and "unofficial" definitions of "Condorcet" - Warren D. Smith, August 2005
  7. Green-Armytage, James; Tideman, T. Nicolaus; Cosman, Rafael (2015-08-11). "Statistical evaluation of voting rules" (PDF). Social Choice and Welfare. Springer Science and Business Media LLC. 46 (1): 183–212. doi:10.1007/s00355-015-0909-0. ISSN 0176-1714.
  8. Durand, François; Mathieu, Fabien; Noirie, Ludovic (2014-06-17). "Making most voting systems meet the Condorcet criterion reduces their manipulability". Inria. Retrieved 2022-01-12.
  9. Woodall, Douglas R. (1996). "Monotonicity and single-seat election rules". Voting matters. 6: 9–14.
  10. Small, Alex (2002-11-17). "Sports and "The Condorcet Mindset"". Election-methods mailing list archives.
  11. Small, Alex (2003-08-07). "[EM] Condorcet 2 - The Sequel ( the same people say the same things)". Election-methods mailing list archives.
  12. "RangeVoting.org - How Condorcet voting can fail to elect Condorcet Winner". rangevoting.org. Retrieved 2020-05-14.
  13. Potthoff, Richard F. (2011-07-01). "Condorcet Polling". Public Choice. 148 (1): 67–86. doi:10.1007/s11127-010-9646-1. ISSN 1573-7101.
  14. Dwork, Cynthia; Kumar, Ravi; Naor, Moni; Sivakumar, D. (2001). Rank aggregation methods for the Web (PDF). New York, NY, USA: ACM. doi:10.1145/371920.372165.
  15. Montague, Mark; Aslam, Javed A. (2002-11-04). Condorcet fusion for improved retrieval (PDF). New York, NY, USA: ACM. doi:10.1145/584792.584881.
This page uses Creative Commons Licensed content from Wikipedia (view authors).