Condorcet paradox

Last updated

In social choice theory, Condorcet's voting paradox is a fundamental discovery by the Marquis de Condorcet that majority rule is inherently self-contradictory. The result implies that it is logically impossible for any voting system to guarantee a winner will have support from a majority of voters: in some situations, a majority of voters will prefer A to B, B to C, and also C to A, even if every voter's individual preferences are rational and avoid self-contradiction. Examples of Condorcet's paradox are called Condorcet cycles or cyclic ties.

Contents

In such a cycle, every possible choice is rejected by the electorate in favor of another alternative, who is preferred by more than half of all voters. Thus, any attempt to ground social decision-making in majoritarianism must accept such self-contradictions (commonly called spoiler effects). Systems that attempt to do so, while minimizing the rate of such self-contradictions, are called Condorcet methods.

Condorcet's paradox is a special case of Arrow's paradox, which shows that any kind of social decision-making process is either self-contradictory, a dictatorship, or incorporates information about the strength of different voters' preferences (e.g. cardinal utility or rated voting).

History

Condorcet's paradox was first discovered by Spanish philosopher and theologian Ramon Llull in the 13th century, during his investigations into church governance, but his work was lost until the 21st century. The mathematician and political philosopher Marquis de Condorcet rediscovered the paradox in the late 18th century. [1] [2] [3]

Condorcet's discovery means he arguably identified the key result of Arrow's impossibility theorem, albeit under stronger conditions than required by Arrow: Condorcet cycles create situations where any ranked voting system that respects majorities must have a spoiler effect.

Example

Suppose we have three candidates, A, B, and C, and that there are three voters with preferences as follows:

VoterFirst preferenceSecond preferenceThird preference
Voter 1ABC
Voter 2BCA
Voter 3CAB
Voters (blue) and candidates (red) plotted in a 2-dimensional preference space. Each voter prefers a closer candidate over a farther. Arrows show the order in which voters prefer the candidates. Voting Paradox example.png
Voters (blue) and candidates (red) plotted in a 2-dimensional preference space. Each voter prefers a closer candidate over a farther. Arrows show the order in which voters prefer the candidates.

If C is chosen as the winner, it can be argued that B should win instead, since two voters (1 and 2) prefer B to C and only one voter (3) prefers C to B. However, by the same argument A is preferred to B, and C is preferred to A, by a margin of two to one on each occasion. Thus the society's preferences show cycling: A is preferred over B which is preferred over C which is preferred over A.

As a result, any attempt to appeal to the principle of majority rule will lead to logical self-contradiction. Regardless of which alternative we select, we can find another alternative that would be preferred by most voters.

Likelihood of the paradox

It is possible to estimate the probability of the paradox by extrapolating from real election data, or using mathematical models of voter behavior, though the results depend strongly on which model is used.

Impartial culture model

We can calculate the probability of seeing the paradox for the special case where voter preferences are uniformly distributed among the candidates. (This is the "impartial culture" model, which is known to be a "worst-case scenario" [4] [5] :40 [6] :320 [7] —most models show substantially lower probabilities of Condorcet cycles.)

For voters providing a preference list of three candidates A, B, C, we write (resp. , ) the random variable equal to the number of voters who placed A in front of B (respectively B in front of C, C in front of A). The sought probability is (we double because there is also the symmetric case A> C> B> A). We show that, for odd , where which makes one need to know only the joint distribution of and .

If we put , we show the relation which makes it possible to compute this distribution by recurrence: .

The following results are then obtained:

3101201301401501601
5.556%8.690%8.732%8.746%8.753%8.757%8.760%

The sequence seems to be tending towards a finite limit.

Using the central limit theorem, we show that tends to where is a variable following a Cauchy distribution, which gives (constant quoted in the OEIS).

The asymptotic probability of encountering the Condorcet paradox is therefore which gives the value 8.77%. [8] [9]

Some results for the case of more than three candidates have been calculated [10] and simulated. [11] The simulated likelihood for an impartial culture model with 25 voters increases with the number of candidates: [11] :28

345710
8.4%16.6%24.2%35.7%47.5%

The likelihood of a Condorcet cycle for related models approach these values for three-candidate elections with large electorates: [9]

All of these models are unrealistic, but can be investigated to establish an upper bound on the likelihood of a cycle. [9]

Group coherence models

When modeled with more realistic voter preferences, Condorcet paradoxes in elections with a small number of candidates and a large number of voters become very rare. [5] :78

Spatial model

A study of three-candidate elections analyzed 12 different models of voter behavior, and found the spatial model of voting to be the most accurate to real-world ranked-ballot election data. Analyzing this spatial model, they found the likelihood of a cycle to decrease to zero as the number of voters increases, with likelihoods of 5% for 100 voters, 0.5% for 1000 voters, and 0.06% for 10,000 voters. [12]

Another spatial model found likelihoods of 2% or less in all simulations of 201 voters and 5 candidates, whether two or four-dimensional, with or without correlation between dimensions, and with two different dispersions of candidates. [11] :31

Empirical studies

Many attempts have been made at finding empirical examples of the paradox. [13] Empirical identification of a Condorcet paradox presupposes extensive data on the decision-makers' preferences over all alternatives—something that is only very rarely available.

While examples of the paradox seem to occur occasionally in small settings (e.g., parliaments) very few examples have been found in larger groups (e.g. electorates), although some have been identified. [14]

A summary of 37 individual studies, covering a total of 265 real-world elections, large and small, found 25 instances of a Condorcet paradox, for a total likelihood of 9.4% [6] :325 (and this may be a high estimate, since cases of the paradox are more likely to be reported on than cases without). [5] :47

An analysis of 883 three-candidate elections extracted from 84 real-world ranked-ballot elections of the Electoral Reform Society found a Condorcet cycle likelihood of 0.7%. These derived elections had between 350 and 1,957 voters. A similar analysis of data from the 1970–2004 American National Election Studies thermometer scale surveys found a Condorcet cycle likelihood of 0.4%. These derived elections had between 759 and 2,521 "voters". [12]

A database of 189 ranked United States elections from 2004 to 2022 contained only one Condorcet cycle: the 2021 Minneapolis Ward 2 city council election. [15] While this indicates a very low rate of Condorcet cycles (0.5%), it's possible that some of the effect is due to general two-party domination.

Andrew Myers, who operates the Condorcet Internet Voting Service, analyzed 10,354 nonpolitical CIVS elections and found cycles in 17% of elections with at least 10 votes, with the figure dropping to 2.1% for elections with at least 100 votes, and 1.2% for ≥300 votes. [16]

Implications

Three men portraying a Mexican standoff. Just as there is no winner in a Mexican standoff with certain combinations of gun-pointings, there is sometimes no majority-preferred winner in a ranked-ballot election. Mexican Standoff.jpg
Three men portraying a Mexican standoff. Just as there is no winner in a Mexican standoff with certain combinations of gun-pointings, there is sometimes no majority-preferred winner in a ranked-ballot election.

When a Condorcet method is used to determine an election, the voting paradox of cyclical societal preferences implies that the election has no Condorcet winner: no candidate who can win a one-on-one election against each other candidate. There will still be a smallest group of candidates, known as the Smith set, such that each candidate in the group can win a one-on-one election against each of the candidates outside the group. The several variants of the Condorcet method differ on how they resolve such ambiguities when they arise to determine a winner. [17] The Condorcet methods which always elect someone from the Smith set when there is no Condorcet winner are known as Smith-efficient. Note that using only rankings, there is no fair and deterministic resolution to the trivial example given earlier because each candidate is in an exactly symmetrical situation.

Situations having the voting paradox can cause voting mechanisms to violate the axiom of independence of irrelevant alternatives—the choice of winner by a voting mechanism could be influenced by whether or not a losing candidate is available to be voted for.

Two-stage voting processes

One important implication of the possible existence of the voting paradox in a practical situation is that in a paired voting process like those of standard parliamentary procedure, the eventual winner will depend on the way the majority votes are ordered. For example, say a popular bill is set to pass, before some other group offers an amendment; this amendment passes by majority vote. This may result in a majority of a legislature rejecting the bill as a whole, thus creating a paradox (where a popular amendment to a popular bill has made it unpopular). This logical inconsistency is the origin of the poison pill amendment, which deliberately engineers a false Condorcet cycle to kill a bill. Likewise, the order of votes in a legislature can be manipulated by the person arranging them to ensure their preferred outcome wins.

Despite frequent objections by social choice theorists about the logically incoherent results of such procedures, and the existence of better alternatives for choosing between multiple versions of a bill, the procedure of pairwise majority-rule is widely-used and is codified into the by-laws or parliamentary procedures of almost every kind of deliberative assembly.

Spoiler effects

Condorcet paradoxes imply majoritarian methods fail independence of irrelevant alternatives. Label the three candidates in a race Rock, Paper, and Scissors. In a one-on-one race, Rock loses to Paper, Paper to Scissors, etc.

Without loss of generality, say that Rock wins the election with a certain method. Then, Scissors is a spoiler candidate for Paper: if Scissors were to drop out, Paper would win the only one-on-one race (Paper defeats Rock). The same reasoning applies regardless of the winner.

This example also shows why Condorcet elections are rarely (if ever) spoiled: spoilers can only happen when there is no Condorcet winner. Condorcet cycles are rare in large elections, [18] [19] and the median voter theorem shows cycles are impossible whenever candidates are arrayed on a left-right spectrum.

See also

Related Research Articles

In social choice theory and politics, the spoiler effect refers to a situation where a large group of like-minded voters split their votes among multiple candidates, which can affect the result of an election by allowing a candidate with a smaller base of support to win with a plurality. If a major candidate is perceived to have lost an election because a more minor candidate pulled votes away from them, the minor candidate is called a spolier candidate and the major candidate is said to have been spoiled. This phenomenon is also called vote splitting.

<span class="mw-page-title-main">Condorcet method</span> Pairwise-comparison electoral system

A Condorcet method is an election method that elects the candidate who wins a majority of the vote in every head-to-head election against each of the other candidates, whenever there is such a candidate. A candidate with this property, the pairwise champion or beats-all winner, is formally called the Condorcet winner. The head-to-head elections need not be done separately; a voter's choice within any given pair can be determined from the ranking.

Arrow's impossibility theorem is a key result in social choice, discovered by Kenneth Arrow, showing that no ranked voting rule can behave rationally. Specifically, any such rule violates independence of irrelevant alternatives (IIA), the idea that a choice between and should not depend on the quality of a third, unrelated option . The result is most often cited in election science and voting theory, where is called a spoiler candidate. In this context, Arrow's theorem can be restated as showing that no ranked voting rule can eliminate the spoiler effect.

The Copeland or Llull method is a ranked-choice voting system based on counting each candidate's pairwise wins and losses.

Independence of irrelevant alternatives (IIA) is a major axiom of decision theory which codifies the intuition that a choice between and should not depend on the quality of a third, unrelated outcome . There are several different variations of this axiom, which are generally equivalent under mild conditions. As a result of its importance, the axiom has been independently rediscovered in various forms across a wide variety of fields, including economics, cognitive science, social choice, fair division, rational choice, artificial intelligence, probability, and game theory. It is closely tied to many of the most important theorems in these fields, including Arrow's impossibility theorem, the Balinski-Young theorem, and the money pump arguments.

In social choice theory, the majority rule (MR) is a social choice rule that says that, when comparing two options, the option preferred by more than half of the voters should win.

In an election, a candidate is called a majority winner or majority-preferred candidate if more than half of all voters would support them in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the majority-rule principle, because they extend the principle of majority rule to elections with multiple candidates.

The participation criterion, sometimes called votermonotonicity, is a voting system criterion that says candidates should never lose an election as a result of receiving too many votes in support. More formally, it says that adding more voters who prefer Alice to Bob should not cause Alice to lose the election to Bob.

Social choice theory is a branch of welfare economics that analyzes methods of combining individual opinions, beliefs, or preferences to reach a collective decision or create measures of social well-being. It contrasts with political science in that it is a normative field that studies how societies should make decisions, whereas political science is descriptive. Social choice incorporates insights from economics, mathematics, philosophy, political science, and game theory to find the best ways to combine individual preferences into a coherent whole, called a social welfare function.

A voting system satisfies join-consistency if combining two sets of votes, both electing A over B, always results in a combined electorate that ranks A over B. It is a stronger form of the participation criterion. Systems that fail the consistency criterion are susceptible to the multiple-district paradox, which allows for a particularly egregious kind of gerrymander: it is possible to draw boundaries in such a way that a candidate who wins the overall election fails to carry even a single electoral district.

The Kemeny–Young method is an electoral system that uses ranked ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.

The Borda method or order of merit is a positional voting rule which gives each candidate a number of points equal to the number of candidates ranked below them: the lowest-ranked candidate gets 0 points, the second-lowest gets 1 point, and so on. Once all votes have been counted, the option or candidate with the most points is the winner.

Instant-runoff voting (IRV), also known as ranked-choice voting (RCV), preferential voting (PV), or the alternative vote (AV), is a multi-round elimination method where the loser of each round is determined by the first-past-the-post method. In academic contexts, the term instant-runoff voting is generally preferred as it does not run the risk of conflating the method with methods of ranked voting in general.

In game theory and political science, Poisson games are a class of games often used to model the behavior of large populations. One common application is determining the strategic behavior of voters with imperfect information about each others' preferences. Poisson games are most often used to model strategic voting in large electorates with secret and simultaneous voting.

<span class="mw-page-title-main">Ranked voting</span> Voting systems that use ranked ballots

Ranked voting is any voting system that uses voters' orderings (rankings) of candidates to choose a single winner or multiple winners. More formally, a ranked rule is one that depends only on which of two candidates is preferred by a voter, and as such does not incorporate any information about intensity of preferences. Ranked voting systems vary dramatically in how preferences are tabulated and counted, which gives them very different properties.

Maximal lotteries refers to a probabilistic voting rule. The method uses preferential ballots and returns a probability distribution of candidates that a majority of voters would weakly prefer to any other.

A major branch of social choice theory is devoted to the comparison of electoral systems, otherwise known as social choice functions. Viewed from the perspective of political science, electoral systems are rules for conducting elections and determining winners from the ballots cast. From the perspective of economics, mathematics, and philosophy, a social choice function is a mathematical function that determines how a society should make choices, given a collection of individual preferences.

Impartial culture (IC) or the culture of indifference is a probabilistic model used in social choice theory for analyzing ranked voting method rules.

<span class="mw-page-title-main">Condorcet efficiency</span>

Condorcet efficiency is a measurement of the performance of voting methods. It is defined as the percentage of elections for which the Condorcet winner is elected, provided there is one.

<span class="mw-page-title-main">Center squeeze</span> Bias of some electoral systems that favors extremists

In social choice, a center squeeze is a kind of spoiler effect common to plurality-based voting rules like the two-round system, plurality-with-primaries, and ranked-choice voting (RCV). In a center squeeze, a majority-preferred and socially-optimal candidate is eliminated in favor of a more extreme alternative. Extreme or polarizing candidates who focus on appealing to a small political base can thus "squeeze" broadly-popular candidates who are trapped between them, starving them of the first preferences they need to survive early rounds.

References

  1. Marquis de Condorcet (1785). Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix (PNG) (in French). Retrieved 2008-03-10.
  2. Condorcet, Jean-Antoine-Nicolas de Caritat; Sommerlad, Fiona; McLean, Iain (1989-01-01). The political theory of Condorcet. Oxford: University of Oxford, Faculty of Social Studies. pp. 69–80, 152–166. OCLC   20408445. Clearly, if anyone's vote was self-contradictory (having cyclic preferences), it would have to be discounted, and we should therefore establish a form of voting which makes such absurdities impossible
  3. Gehrlein, William V. (2002). "Condorcet's paradox and the likelihood of its occurrence: different perspectives on balanced preferences*". Theory and Decision. 52 (2): 171–199. doi:10.1023/A:1015551010381. ISSN   0040-5833. S2CID   118143928. Here, Condorcet notes that we have a 'contradictory system' that represents what has come to be known as Condorcet's Paradox.
  4. Tsetlin, Ilia; Regenwetter, Michel; Grofman, Bernard (2003-12-01). "The impartial culture maximizes the probability of majority cycles". Social Choice and Welfare. 21 (3): 387–398. doi:10.1007/s00355-003-0269-z. ISSN   0176-1714. S2CID   15488300. it is widely acknowledged that the impartial culture is unrealistic ... the impartial culture is the worst case scenario
  5. 1 2 3 Gehrlein, William V.; Lepelley, Dominique (2011). Voting paradoxes and group coherence : the condorcet efficiency of voting rules. Berlin: Springer. doi:10.1007/978-3-642-03107-6. ISBN   9783642031076. OCLC   695387286. most election results do not correspond to anything like any of DC, IC, IAC or MC ... empirical studies ... indicate that some of the most common paradoxes are relatively unlikely to be observed in actual elections. ... it is easily concluded that Condorcet's Paradox should very rarely be observed in any real elections on a small number of candidates with large electorates, as long as voters' preferences reflect any reasonable degree of group mutual coherence
  6. 1 2 Van Deemen, Adrian (2014). "On the empirical relevance of Condorcet's paradox". Public Choice. 158 (3–4): 311–330. doi:10.1007/s11127-013-0133-3. ISSN   0048-5829. S2CID   154862595. small departures of the impartial culture assumption may lead to large changes in the probability of the paradox. It may lead to huge declines or, just the opposite, to huge increases.
  7. May, Robert M. (1971). "Some mathematical remarks on the paradox of voting". Behavioral Science. 16 (2): 143–151. doi:10.1002/bs.3830160204. ISSN   0005-7940.
  8. Guilbaud, Georges-Théodule (2012). "Les théories de l'intérêt général et le problème logique de l'agrégation". Revue économique. 63 (4): 659. doi: 10.3917/reco.634.0659 . ISSN   0035-2764.
  9. 1 2 3 Gehrlein, William V. (2002-03-01). "Condorcet's paradox and the likelihood of its occurrence: different perspectives on balanced preferences*". Theory and Decision. 52 (2): 171–199. doi:10.1023/A:1015551010381. ISSN   1573-7187. S2CID   118143928. to have a PMRW with probability approaching 15/16 = 0.9375 with IAC and UC, and approaching 109/120 = 0.9083 for MC. … these cases represent situations in which the probability that a PMRW exists would tend to be at a minimum … intended to give us some idea of the lower bound on the likelihood that a PMRW exists.
  10. Gehrlein, William V. (1997). "Condorcet's paradox and the Condorcet efficiency of voting rules". Mathematica Japonica. 45: 173–199.
  11. 1 2 3 Merrill, Samuel (1984). "A Comparison of Efficiency of Multicandidate Electoral Systems". American Journal of Political Science. 28 (1): 23–48. doi:10.2307/2110786. ISSN   0092-5853. JSTOR   2110786.
  12. 1 2 Tideman, T. Nicolaus; Plassmann, Florenz (2012), Felsenthal, Dan S.; Machover, Moshé (eds.), "Modeling the Outcomes of Vote-Casting in Actual Elections", Electoral Systems, Berlin, Heidelberg: Springer Berlin Heidelberg, Table 9.6 Shares of strict pairwise majority rule winners (SPMRWs) in observed and simulated elections, doi:10.1007/978-3-642-20441-8_9, ISBN   978-3-642-20440-1 , retrieved 2021-11-12, Mean number of voters: 1000 … Spatial model: 99.47% [0.5% cycle likelihood] … 716.4 [ERS data] … Observed elections: 99.32% … 1,566.7 [ANES data] … 99.56%
  13. Kurrild-Klitgaard, Peter (2014). "Empirical social choice: An introduction". Public Choice. 158 (3–4): 297–310. doi:10.1007/s11127-014-0164-4. ISSN   0048-5829. S2CID   148982833.
  14. Kurrild-Klitgaard, Peter (2001). "An empirical example of the Condorcet paradox of voting in a large electorate". Public Choice. 107: 135–145. doi:10.1023/A:1010304729545. ISSN   0048-5829. S2CID   152300013.
  15. Graham-Squire, Adam; McCune, David (2023-01-28). "An Examination of Ranked Choice Voting in the United States, 2004-2022". arXiv: 2301.12075v2 [econ.GN].
  16. Myers, A. C. (March 2024). The Frequency of Condorcet Winners in Real Non-Political Elections. 61st Public Choice Society Conference. p. 5. 83.1% … 97.9% … 98.8% … Figure 2: Frequency of CWs and weak CWs with an increasing number of voters
  17. Lippman, David (2014). "Voting Theory". Math in society. ISBN   978-1479276530. OCLC   913874268. There are many Condorcet methods, which vary primarily in how they deal with ties, which are very common when a Condorcet winner does not exist.
  18. Gehrlein, William V. (2002-03-01). "Condorcet's paradox and the likelihood of its occurrence: different perspectives on balanced preferences*". Theory and Decision. 52 (2): 171–199. doi:10.1023/A:1015551010381. ISSN   1573-7187.
  19. Van Deemen, Adrian (2014-03-01). "On the empirical relevance of Condorcet's paradox". Public Choice. 158 (3): 311–330. doi:10.1007/s11127-013-0133-3. ISSN   1573-7101.

Further reading