Can you find the probability of it being impossible to decide a winner in an election where there are 3 candidates A, B and C, and 3 voters, who place the candidates in order of preference?
This was another tough nut which took 8 months to crack and then yielded simultaneously to the application of minds at opposite points of the globe. Well done Justin from Skyview High School, Billings, USA and again to Ling Xiang Ning from Tao Nan School, Singapore for the solution which follows.
As each voter can choose any one of the six orders ABC, ACB, BAC, BCA, CAB and CBA, there are altogether (6*6*6 = 216) different combinations of votes that could be cast. We say the results are intransitive if, for example, A beats B and B beats C but A loses to C so that it is impossible to decide on a winner.
We have to find the total number of intransitive combinations of votes over the total number of combinations of votes (216) to get the probability of the paradox arising. So, we have to find the total number of intransitive combinations of votes.
First, we have to prove that the results are intransitive if and only if no two voters agree on their first choice, nor on their second, nor on their third.
I just take one combination of votes which two voters agree on their first choice, which is let us say A.
| First voter | Second Voter | Third voter |
| ABC | ACB | ABC or ACB or BAC, BCA, CAB, CBA |
If two or more voters agree on their second choice, then either they also agree on the first, which we have just shown to be transitive or if not (for example ABC and CBA) then the 3 candidates are all exactly equal as a result of these two votes. The outcome will be decided by the order chosen by the third voter and the result is transitive.
If two or more voters agree on the third choice, suppose B is placed third by two voters, then A beats B and C beats B by at least 2 choices to 1. The result is transitive whether A beats C (when A beats C, C beats B and A beats B) or alternatively C beats A (when C beats A, A beats B and C beats B).
This means that the results are intransitive if and only if no two voters agree on their first choice, nor on their second, nor on their third.
Now, we have to find the total number of intransitive combinations of votes.
If the first voter votes ABC, the second voter has to vote either BCA or CAB for the results to be intransitive. If the second voter votes BCA, then CAB is the only order for the third voter which makes the results intransitive. If the second voter votes CAB, then BCA is the only order for the third voter which makes the results intransitive. So, if the first voter votes ABC, there would be 2 possible combinations of votes making the results intransitive. As the first voter can vote 6 possible votes (ABC, ACB, BAC, BCA, CAB, CBA), the total number of intransitive combinations of votes possible is (6*2 = 12).
So, the probability of this paradox of collective choice arising is 12/216, that is 1/18.