In politics and machine learning, we often run elections where n candidates are ranked and one candidate is chosen. However, it is possible that the majority of voters ranked an alternative candidate higher than the chosen candidate. This scenario is known as Condorcet's paradox. The intuitive question is whether we can select a group of potential candidates where the majority of voters chose one of the winning candidates over the rest of the candidates (Condorcet's winning set). Moreover, what is the upper bound on the size of the winning set? Surprisingly, Charikar et al. proved that the answer is a constant number 6 [1]!
Let's start with a basic example of a ranked election result where n=4.
1234234134124123
We can see that candidate 1 is ranked first by only one voter and all other voters ranked a candidate higher than candidate 1. This is the worst case scenario. From this example we can see that as n→∞ the percentage of voters who choose an alternative candidate approaches 100%.
So what about a committee candidates to choose from?
Citations
[1] Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang. Six Candidates Suffice to Win a Voter Majority. https://arxiv.org/pdf/2411.03390