In a couple of days I am giving a presentation at Math Club. For my talk I decided to choose the social choice theory and plan to give a proof of the famous Arrow’s impossibility theorem, that states, loosely speaking, that the only social choice procedure that satisfies a very reasonable list of axioms is the so-called dictatorship, i.e., when one voter (somehow chosen from the list of voters) decides who is the winner of the election. What follows are the notes I prepared for my talk. In these notes I follow mostly this article from Kvant . At the end of the post there are some additional references, including textbook , written for undergraduates with limited mathematical background.
1. Social choice procedures
Assume that we have voters and candidates. Each voter arranges the list of candidates with respect to her preferences; e.g., for three candidates it could be
which means that for this particular voter candidate is preferable to candidate , and is preferable to candidate . This is called an individual’s preference list (or ballot). The set of all the preference lists is called a profile.
|Number of votes||5||3||5||4|
Definition 1 A social choice procedure is a function from the set of all the profiles to the set of possible ballots.
where is the preference list of the th voter, and is the collective opinion (social choice).
Exercise 1 What is the total number of social choice procedures?
Possible social choice procedures exist. Probably the simplest is the so-called plurality voting, which states that the winner is the candidate that gets majority of the first-ranking places. In Example 1, we have gets 8 first rank votes, gets 5 votes, gets 4 votes, gets no votes; hence the winner is .
In the case of two candidates this social choice procedure is termed majority rule, which states that the winner is the candidate that receives over 50% of votes. For the list of three or more candidates the condition of getting over 50% often implies that there is no winner (as in the case of Example 1), therefore a modification was suggested.
Absolute majority rule is the rule that states that if no one gets over 50%, then two candidates with most votes are kept, and a second round of voting is fulfilled, thus yielding the winner. In Example 1 and are elected to the second round, and wins the election.
The Borda Count is the social choice procedure when each voter assigns points to the th candidate in her preference list (the first one gets points, the last — zero). All the points are added, and the winner is the candidate that has most points. In Example 1 gets 24 points, gets 22, gets 27 points, and gets 29 points, hence is the winner.
Condorset’s method makes a candidate the winner if this candidate wins all the pairwise duels in the profile. In Example 1 because 8 people put over and 9 voters put over . In the same vein, we have . The winner is (note that sometimes this procedure does not have a winner).
There is a temptation to generalize the Borda Count, assigning to candidates points. The Borda count is given by , and the plurality voting is given by . Can other rules be generalized in this way?
Exercise 3 Prove Lemma 3. Hint: Check the following profile:
3 6 4 4 c a b b a b a c 0 b c c a
Exercise 4 In Example 1 candidate that loses to by the absolute majority rule decides to withdraw herself from the election. Show that in this case the absolute majority rule implies that the winner will be .
Exercise 5 Consider the profile
2 1 4 b d 3 a c 2 d e 1 c b 0 e a
The Borda count implies that the winner is with 9 points. Show that if withdraws, the winner is .
Exercise 6 Consider the profile
6 5 4 2 a c b b b a c a c b a c
Show that if the two voters from the last column change their preference lists for , the absolute majority rule, which yields as the winner for the original profile, implies that now is the winner.
Concluding this section, it is worth mentioning that there is another social choice procedure — the dictatorship, which means that a chosen voter, say, number , alone decides who is the winner:
What are the natural requirements for a good social choice procedure?
Here is a reasonable list of axioms:
- is well defined. That is, for any candidates and the collective opinion implies either or .
- Transitivity: if and then .
- Pareto condition: if everyone prefers to then .
- Independence: The positions of any two candidates and in the collective choice depend only on their mutual positions on the preference lists and do not depend on other candidates positioning.
Exercise 7 Show that the dictatorship satisfies axioms (A1)—(A4).
The following theorem is the main result of this post.
To prove Arrow’s theorem, first set the terminology. Subset (a coalition) of the set of voters is called -decisive for against if and only if from the fact that all the members of have and all the members of have follows that . If coalition -decisive for any candidates, then we shall call it simply -decisive. A trivial example of -decisive coalition is (due to (A3)). An empty set cannot be -decisive for any candidates.
Proof: There is always -decisive coalition for any two candidates and (e.g., ). Choose the one that has minimal number of voters, we denote it , which is not empty, therefore it has at least one voter . Consider the sets , , . Due to the assumption there is always another candidate . Consider the profile
Since is -decisive for against then . If then is -decisive for against , it is smaller than , contradiction. This means, by , that , and, by (A2), . This means that is -decisive for against , which also contradicts the fact that is minimal. This means that cannot be split into two non-empty sets, hence .
Lemma 6 Coalition from Lemma 5 is -decisive.
Proof: Let be an arbitrary candidate. Consider the profile in which ‘s preference list for these three candidates is , and ‘s preference list is . We also have and (due to ), which means that and, due to we have that has and has independent of the position of (hence taking care of the case for ). Now we can assume that there is another candidate , and ‘s preference list is , ‘s list is . This implies that is -decisive for any arbitrary and .
At this point we know that dictates her opinion for any pair and for which it is -decisive. However, some pairs and can be such that has both and . The last step is to make sure that in this case the choice of coincides with the social choice.
Proof: Consider a profile where the preference list of is , and all the other voters have over both and (and we do not specify the order of and ). Since is -decisive, then . Due to the Pareto condition . Transitivity gives us , or , which means that — dictator.
Theorem~4 is due to Arrow and often called Arrow’s impossibility theorem. Why “impossibility”? Because an equivalent formulation adds one more axiom:
- (A5) The social choice procedure is not the dictatorship.
Then we have
Theorem 8 (Arrow, 1950) There is no social choice procedure satisfying (A1)—(A5).
 Arrow, K. J., A Difficulty in the Concept of Social Welfare, Journal of Political
Economy 58(4), 1950, 328-346
 Ning Neil Yu, A One-shot Proof of Arrow’s Impossibility Theorem, 2012
 Pakhomov, V., Democracy from a Mathematical Viewpoint, Kvant, 9, 10, 1992 (in
 Taylor, A. D., Pacelli, A. M., Mathematics and Politics: Strategy, Voting, Power
and Proof, Springer, Second edition,2010.