How likely are Condorcet cycles in supermajorities?

You can use a supermajority rule to eliminate the possibility of Condorcet cycles. e.g. if you require a \(\frac{2}{3}\) supermajority there is no possibility of creating a Condorcet triple with the majority strictly preferring A to B, B to C and C to A.

Unfortunately that’s only the three candidate case. If you consider the \(N\) candidate case you need a supermajority of \(1 – \frac{1}{N}\) to achieve the same result (just consider the \(N\) cyclic permutations of the candidates and you get a generalisation of the Condorcet example where every candidate beats every other this fraction of the time).

So there is no supermajority rule that in general prevents Condorcet cycles.

In “The Probability of Condorcet Cycles and Super Majority Rules”, Yves Balasko and Hervé Crès show the following asymptotic result: If you consider a profile of votes chosen uniformly at random on the set \(\{p \in \mathbb{R}^{n!}: p \geq 0, \sum p = 1\}\), then the probability of there being a Condorcet cycle in that set with a supermajority of \(\tau\) is bounded above by \(n! \left( \frac{1 –  \tau}{0.4714}\right)^{n!}\).

From this they conclude that the critical threshold for a supermajority is around 54%, because this goes very rapidly towards zero.  e.g. with the 54% threshold the probability of a cycle in \(7\) candidates is \(< 10^{-52}\), which we can probably treat as adequately safe.

They also say “Within our setup, this makes the Condorcet cycles a theoretical curiosity without any practical bearing for super majority rules that exceed the threshold value of 53%”.

Unfortunately this conclusion is totally wrong (the bound is probably correct, but I’ll confess to not having fully followed the rather complicated calculations), because it neglects the fact that \(n\) can be small as well as large.

e.g. for \(n=3\), their upper bound isn’t even smaller than \(1\). It’s about 5.18. It then grows before dropping – at 4 it’s 13.34, at 5 it’s 6.36, and then finally at 6 is becomes small and is 1.6e-5.

So in order to find what the appropriate super majority threshold is for making the probability of a cycle adequately small (say under 1 in 1000) we need to manually check the cases of 3, 4 and 5.

Fortunately it’s easy to do that by direct simulation, so I wrote some code, and the 54% threshold is indeed the wrong one and fails to handle the three candidate case well.

About 6% of elections on three candidates have majority cycles, and of those about a quarter would still have a cycle with a 54% supermajority. The 99.9% mark is a 59% supermajority: Above that, fewer than one in a thousand profiles have a cycle. For four candidates, the 99.9% mark is 57%.

If we take the higher requirement of one in a million (which is well into the region where my simulation does not have sufficient fidelity to actually give a good answer) the thresholds become 64% and 61%.

That leaves the n=5 case. My simulation is a bit too inefficient (it has an O(n!) componetn in it) to run in reasonable time for n=5, but fortunately it doesn’t have to. The upper bound for the supermajorities the lower n required is now adequately low: For a 59% supermajority it’s 6e-6, for a 60% supermajority it’s 3e-7, so goes below the one in a million mark too.

So, in conclusion, if you require a 60% supermajority, and not just a 54% one, you are probably free of Condorcet cycles. If you go for the full 2/3 supermajority (which probably makes a lot of sense for serious cases) you’re almost certainly safe – you’re provably safe at n=3 and, provably have vanishingly low probability for n >= 5, and for n=4 a simulation says there’s well under a one in a million chance of getting a cycle.

Unless of course your population is drawn from a model that isn’t well represented by a uniform distribution (i.e. all populations ever) or the candidates are adversarially chosen to manipulate the electorate (i.e. all candidates ever). In those edge cases you might still have some problems.

This entry was posted in voting on by .