Peter Chng

Condorcet paradox and its implications

The Condorcet paradox is a counter-intuitive outcome that can happen in a ranked voting1 system with three or more candidates. It states that even if individual voter preferences are transitive (that is, voters provide a strict ordering of candidates that is non-cyclic), the aggregated preferences may be non-transitive or cyclical. When I first read about this, I was surprised and interested in its implications, since it implies in certain situations, under certain voting systems, that there might not be a “best” candidate that is pairwise-better than all others!

Conditions for the paradox

The paradox (which is also called a Condorcet cycle) can only happen if we have three or more candidates, so let’s explore this simplest situation.

Suppose we have three candidates, A, B, and C. Then the paradox will happen if:

  1. The fraction of voters who prefer $A > B$ is greater than $1/2$
  2. The fraction of voters who prefer $B > C$ is greater than $1/2$
  3. The fraction of voters who prefer $C > A$ is greater than $1/2$
    (Or equivalently: The fraction that prefer $A > C$ is less than $1/2$)

This creates a Condorcet cycle because there is not a transitive ordering to the candidates. In effect, we have $A > B > C > A \ldots$ which is akin to a game of Rock, Paper, Scissors: There is no candidate that is pairwise superior to all other candidates across the aggregated voter preferences.

Let’s explore some specific conditions that can lead to this2. Suppose we have the fraction of voters that adhere to a certain preference defined as:

Fraction of voter share Preference
a $A > B > C$
b $B > C > A$
c $C > A > B$

Each voter preference is transitive, and because there are only three preferences here, $a + b + c = 1$ by definition. (Note that for brevity this doesn’t cover all possible preferences since there are six possible permutations from three candidates, but only those that are necessary to create a cycle.)

Let’s also define the fraction of voters by pairwise preferences:

Fraction of voter share Preference
x $A > B$
y $B > C$
z $A > C$

By referencing the first table, we can determine the following:

$$ x = a + c $$ $$ y = a + b $$ $$ z = a $$

We can then do:

$$ x + y = (a + c) + (a + b) = a + (a + b + c) = a + 1 $$

$$ x + y - 1 = a = z $$

$$ z = x + y - 1 $$

In order for the cycle to exist, we need $z < 1/2$ so that most voters instead prefer $C > A$, so we have:

$$ x + y - 1 < {1\over2} $$ $$ x + y < {3\over2} $$

So the conditions for the cycle (paradox) to exist here are:

  • $x > 1/2$
  • $y > 1/2$
  • $x + y < {3\over2}$

Or in terms of a, b, and c:

  • $a < 1/2$
  • $b > 1/2 - a$
  • $c > 1/2 - a$

Note that the possible preferences must also be able to form a cycle. In this example, we defined the possible preferences as:

  1. $A > B > C$
  2. $B > C > A$
  3. $C > A > B$

These can form a cycle in aggregate because the permutations are drawn from the cycle $ A, B, C, A, B \ldots$ by picking any three consecutive candidates from that cycle.

Prevalence of the paradox in actual elections

Although the Condorcet paradox is possible, is it likely? Several studies have shown specific examples of its occurrence in real-world elections, but its “true” frequency is uncertain:

  • One meta-analysis by Van Deemen counted 25 occurrences of the paradox in 265 elections, a rate of 9.4%. (See pages 323-325) However this aggregation of multiple studies included some studies that looked at a specific incidence of the Condorcet paradox in a single election, which may have biased the frequency upward. (e.g. the study would not have been published if the paradox did not occur)
  • Estimations based on models produce different results based on the model’s assumptions. For example, the “impartial culture” (IC) model3 gives the result that as the number of votes (n) increases, the probability of a cycle converges to some fixed value, and that value is determined by the number of candidates (m). When m is low, this limiting probability is also low, and it increases as m increases. This seems to match the observation “that for small number of candidates and large number of votes” there will not be a paradox/cycle. (See Krishnamoorthy and Raghavachari (2005). Condorcet Winner Probabilities - A Statistical Perspective. 16-17)
  • On the other hand, the “normal spatial model”, which is a closer approximation to real voter behavior, shows that the probability of a paradox converges to 0% as the number of votes increases. (See pages 13-14 of the PhD thesis of Chang Geun Song)
  • Simulations based on election data also show a low probability of the Condorcet paradox. (Song (2021). Estimating the Probability of a Voting Cycle)

I lean towards thinking the paradox is unlikely to occur in practice, at least for political elections. This is because we usually think of political candidates as existing along a left-right spectrum that is one-dimensional. If voters are also placed along this spectrum, and we assume that voters rank candidates by how close they are on this left-right spectrum, then by the Median Voter Theorem, the Condorcet paradox cannot exist.

For example, assume candidates A, B, and C are arranged on a line from left to right as follows: (This is an adaptation of the diagram seen in pages 16-17 here)

A ------------ B ------------ C

Now assume that voters' preferences are also points along this line,4 and that voters rank candidates by whomever is closest to them. There are then only four possible rankings, by looking at regions along the line:

  1. $A > B > C$
  2. $B > A > C$
  3. $B > C > A$
  4. $C > B > A$

These permutations cannot in aggregate form a cycle, unlike the example I gave earlier. That is because:

  • With the set ${A, B, C}$ there are only two unique directed cycles that can be formed: 
    (Assume clockwise cycle)

   (1)        (2)
    A          A
   / \        / \ 
  C - B      B - C
  • From (1), we can produce the following orderings:
    $A > B > C$
    $B > C > A$
    $C > A > B$
  • From (2), we can produce the following orderings:
    $A > C > B$
    $C > B > A$
    $B > A > C$
  • In order for a Condorcet cycle to happen with three candidates, all three orderings from one of the cycles must be present in voters' preferences. (That is the cycle that may form)
  • That doesn’t happen in this one-dimensional example, because two of the possible rankings are from one cycle, and two are from the other cycle.

So if candidates and voter preferences can be arrayed in a one-dimensional space (line) and voters rank candidates by order of closeness, the Condorcet paradox is not possible. Of course, candidate and voter preferences might be multidimensional, which is why the paradox is possible in the first place.

Does the Condorcet paradox exist other domains?

The meta-analysis I previously cited also opined that most of the focus had been on elections, and speculated that Condorcet cycles could occur in other settings - any decision making process where there are multiple options that can be ranked, and multiple stakeholders (“voters”) whose preferences must be considered in making a collective decision:

In practice, numerous collective decisions are made over and over again in business andpolitics; in boards, councils, management teams, cabinets, …—in sum in all kinds of com-mittees and elections. Many of these collective decisions may stem from underlying prefer-ence profiles with the properties of a Condorcet paradox

Recommender systems, which attempt to assign the “best” order to a set of items, could be seen as an example of this. In this scenario:

  • The “candidates” are the items being ranked.
  • The “voters” are the actions taken by users, which are transformed into training data, used to train a model5.
  • The model is then used to rank items.

As with real elections, Condorcet paradoxes are unlikely here. There are at least a few indications as to why:

  1. The models typically are not trying to find the global best ordering, but rather the optimal ordering for the given user. This level of personalization can be thought of as an “election” with one voter (the user), in which case a paradox/cycle is impossible, assuming the user’s preferences are transitive.
  2. A study using the Netflix Prize dataset (users and their ratings of movies on a scale from 1-5) simulated 3-way and 4-way elections based on this data using various models. Across these simulations, the probability of a Condorcet paradox (cycle) was typically low, much less than 1%. (Mattei (2011). Empirical Evaluation of Voting Rules with Strictly Ordered Preference Data, section 4.1)

So again, the paradox appears possible, but not probable.

Mitigating the Condorcet paradox

There are some ways to mitigate the paradox. For example, the Schulze method of evaluating voters' ranked preferences in a way that reduces the likelihood of the Condorcet paradox happening. It does this by creating a directed graph where the nodes are candidates, and the edge weights are the number of voters who prefer the source candidate over the destination candidate. It then identifies through pairwise comparisons if there is a candidate who wins against all other candidates, and also considers by how much they win. In this way, even if there is a cycle, the method will return an ordering (winner) that is the strongest because more information from voters is incorporated during the process of determining the winner. However, this method of determining the winner is quite complicated, and involves use of shortest path graph traversal algorithms.

Other methods like cardinal voting (where voters assign a numerical score to each candidate, not just a ranking), can also mitigate the paradox because they allow voters to provide more information than just a ranking of candidates would.

However, mitigation of the Condorcet paradox is only one criteria that voting systems can be evaluated on. (There are many, see the comparison table at the Schulze method Wikipedia article) For example, FairVote advocates for the Instant-runoff Ranked Choice Voting (RCV) system specifically because it’s one of the few to satisfy the later-no-harm criterion: In most RCV systems, you aren’t required to rank every candidate, and later-no-harm ensures that once you rank a candidate, adding or ranking more candidates behind them should not decrease the likelihood of higher-ranked candidates from being elected. This reduces the likelihood of strategic voting.6

Conclusion

The Condorcet paradox, while having been demonstrated to have occurred at least a few times, seems to be more of an intellectual curiousity rather than something which has had pervasive negative consequences. At least when it comes to elections, it appears that other criteria for voting systems overshadow the practical relevance of this paradox.

  1. A ranked voting (ordinal) system is one where voters provide a ranked order to all candidates on a ballot. Different implementations (rules) then use different methods to determine the winner. Plurality voting (where you simply vote for one candidate) may be considered a form of this where only the top-ranked candidate is given a point. This contrasts with cardinal voting where the voter themselves assigns points to each candidate on the ballot, e.g. “rank each candidate between 1 and 10”. Note that different implementations may not require a strict ordering and may allow candidates to be left unranked. ↩︎

  2. The Wikipedia article provides a succinct explanation under “Necessary condition for the paradox”, but cites pages 387-399 from a 1992 issue of The Mathematical Gazette that I wasn’t able to fully access. The derivation is apparently covered on page 388, but I could only preview page 387 of the issue, so I decided to go through the straightforward derivation here. ↩︎

  3. The impartial culture (IC) model assumes that there is a uniform distribution over all possible permutations of candidates, and that voter’s preferences are drawn from this distribution. This is obviously unrealistic, but seems to give an upper bound (worst case) on the likelihood of the Condorcet paradox. ↩︎

  4. Such a model, where candidates and voter preferences can be arranged on a line, and voters rank candidates in order of closeness, is called a one-dimensional spatial model where voters have single-peaked preferences. ↩︎

  5. The model might be trained on a simple classification task (e.g. predict whether the user interacts with the item or not), or it might be trained to produce the ordering more directly using a listwise approach like Learning to Rank. ↩︎

  6. A full discussion about strategic voting is beyond the scope of this article and my expertise. However, my understanding is that the Gibbard–Satterthwaite theorem shows that any ranked/ordinal voting system is susceptible to strategic voting: That is, voters cannot simply vote their “honest” opinion, but must instead alter their strategy to consider what other voters may do in order to avoid an undesirable outcome. The easiest of these situations to understand is the effect of a “third candidate” in the typical American two-party system: If a third candidate becomes strong enough, they threaten to “split the vote” of one of the candidates, thus causing the other to win. This probably happened in the 1992 US Presidental election, where the third candidate (Ross Perot) probably reduced George H.W. Bush’s votes because people who would vote for Perot would probably not have voted for Clinton. My interpretation of this is that with more “complex” voting systems like RCV, the potential for strategies is only mitigated (or made more complext), but does not disappear completely. ↩︎