Democracy from a mathematical viewpoint

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 [3]. At the end of the post there are some additional references, including  textbook [4], written for undergraduates with  limited mathematical background.

1. Social choice procedures

Assume that we have {n} voters and {m} candidates. Each voter arranges the list of candidates with respect to her preferences; e.g., for three candidates {a,b,c} it could be

\displaystyle a\succ b\succ c,

which means that for this particular voter candidate {a} is preferable to candidate {b}, and {b} is preferable to candidate {c}. This is called an individual’s preference list (or ballot). The set of all the preference lists is called a profile.

Example 1 Assume {n=17,\,m=4}. Five voters order candidates as {a\succ d\succ c\succ b}, three — {a\succ d\succ b\succ c}, five — {b\succ c\succ d\succ a}, last four — {c\succ d\succ b\succ a}. Summarizing, we have the following profile:

Number of votes 5 3 5 4
a a b c
Candidates d d c d
c b d b
b c a a

Definition 1 A social choice procedure is a function from the set of all the profiles to the set of possible ballots.


\displaystyle \stackrel{s}\succ\,=\,f(\stackrel{1}\succ,\stackrel{2}\succ,\ldots,\stackrel{n}\succ),

where {\stackrel{i}\succ} is the preference list of the {i}th voter, and {\stackrel{s}\succ} is the collective opinion (social choice).

Exercise 1 What is the total number of social choice procedures?


\displaystyle m!^{(n!^m)}

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 {a} gets 8 first rank votes, {b} gets 5 votes, {c} gets 4 votes, {d} gets no votes; hence the winner is {a}.

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 {a} and {b} are elected to the second round, and {b} wins the election.

The Borda Count is the social choice procedure when each voter assigns {m-i} points to the {i}th candidate in her preference list (the first one gets {m-1} points, the last — zero). All the points are added, and the winner is the candidate that has most points. In Example 1 {a} gets 24 points, {b} gets 22, {c} gets 27 points, and {d} gets 29 points, hence {d} 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 {d\succ a} because 8 people put {a} over {d} and 9 voters put {d} over {a}. In the same vein, we have {b\succ a,\, c\succ a,\,c\succ b, \, c\succ d}. The winner is {c} (note that sometimes this procedure does not have a winner).

There is a temptation to generalize the Borda Count, assigning to candidates {s_m\geq s_{m-1}\geq \ldots \geq s_2\geq s_1=0} points. The Borda count is given by {s_1=0,\,s_2=1,\ldots, s_m=m-1}, and the plurality voting is given by {s_m=1,s_{m-1}=\ldots=s_1=0}. Can other rules be generalized in this way?

Lemma 2 There exit such profiles that the winner by the absolute majority rule cannot be a winner for any point count.

Exercise 2 Prove Lemma 2. Hint: Check profile in Example 1.

Lemma 3 There exit such profiles that the winner by Condorset’s method cannot be a winner for any point count.

Exercise 3 Prove Lemma 3. Hint: Check the following profile:

3 6 4 4
{s_3} c a b b
{s_2} a b a c
0 b c c a

Exercise 4 In Example 1 candidate {a} that loses to {b} 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 {d}.

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 {b} with 9 points. Show that if {a} withdraws, the winner is {d}.

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 {a\succ b\succ c}, the absolute majority rule, which yields {a} as the winner for the original profile, implies that now {c} 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 {i}, alone decides who is the winner:

\displaystyle \stackrel{s}\succ\,=\,f(\stackrel{1}\succ,\stackrel{2}\succ,\ldots,\stackrel{n}\succ)= \stackrel{i}\succ

2. Arrow’s impossibility theorem

What are the natural requirements for a good social choice procedure?

Here is a reasonable list of axioms:

  • {\textbf{(A1)}} {f} is well defined. That is, for any candidates {a} and {b} the collective opinion implies either {a\succ b} or {b\succ a}.
  • {\textbf{(A2)}} Transitivity: if {a\succ b} and {b\succ c} then {a\succ c}.
  • {\textbf{(A3)}} Pareto condition: if everyone prefers {a} to {b} then {a\stackrel{s}\succ b}.
  • {\textbf{(A4)}} Independence: The positions of any two candidates {a} and {b} 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.

Theorem 4 The only social choice procedure {f} for {m\geq 3} choices, satisfying {\emph{\textbf{(A1)}}}{\emph{\textbf{(A4)}}}, is the dictatorship.

To prove Arrow’s theorem, first set the terminology. Subset {A} (a coalition) of the set of voters {S} is called {f}-decisive for {a} against {b} if and only if from the fact that all the members of {A} have {a\succ b} and all the members of {S\backslash A} have {b\succ a} follows that {a\stackrel{s}\succ b}. If coalition {A} {f}-decisive for any candidates, then we shall call it simply {f}-decisive. A trivial example of {f}-decisive coalition is {S} (due to (A3)). An empty set cannot be {f}-decisive for any candidates.

Lemma 5 There exist two candidates {a} and {b} for which it is possible to find an {f}-decisive coalition {D}, consisting of only one voter {\{d\}}.

Proof: There is always {f}-decisive coalition for any two candidates {a} and {b} (e.g., {S}). Choose the one that has minimal number of voters, we denote it {M}, which is not empty, therefore it has at least one voter {d}. Consider the sets {D=\{d\}}, {M\backslash D}, {S\backslash M}. Due to the assumption there is always another candidate {c}. Consider the profile

{D} {M\backslash D} {S\backslash M}
a c b
b a c
c b a

Since {M} is {f}-decisive for {a} against {b} then {a \stackrel{s}\succ b}. If {c \stackrel{s}\succ b} then {M\backslash D} is {f}-decisive for {c} against {b}, it is smaller than {M}, contradiction. This means, by {\textbf{(A1)}}, that {b \stackrel{s}\succ c}, and, by (A2), {a \stackrel{s}\succ c}. This means that {D} is {f}-decisive for {a} against {c}, which also contradicts the fact that {M} is minimal. This means that {M} cannot be split into two non-empty sets, hence {M=D=\{d\}}. \Box

Lemma 6 Coalition {D} from Lemma 5 is {f}-decisive.

Proof: Let {c} be an arbitrary candidate. Consider the profile in which {D}‘s preference list for these three candidates is {a\succ b\succ c}, and {S\backslash D}‘s preference list is {b\succ c\succ a}. We also have {a \stackrel{s}\succ b} and {b \stackrel{s}\succ c} (due to {\textbf{(A3)}}), which means that {a \stackrel{s}\succ c,} and, due to {\textbf{(A4)}} we have that {D} has {a\succ c} and {S\backslash D} has {c\succ a} independent of the position of {b} (hence taking care of the case {a\succ c\succ b} for {D}). Now we can assume that there is another candidate {e}, and {D}‘s preference list is {e\succ a\succ c}, {S\backslash D}‘s list is {c\succ e\succ a}. This implies that {D} is {f}-decisive for any arbitrary {e} and {c}. \Box

At this point we know that {d} dictates her opinion for any pair {a} and {b} for which it is {f}-decisive. However, some pairs {a} and {b} can be such that {S\backslash D} has both {a\succ b} and {b\succ a}. The last step is to make sure that in this case the choice of {d} coincides with the social choice.

Lemma 7 {d} is the dictator.

Proof: Consider a profile where the preference list of {D} is {a\succ c\succ b}, and all the other voters have {c} over both {a} and {b} (and we do not specify the order of {a} and {b}). Since {D} is {f}-decisive, then {a\stackrel{s}\succ c}. Due to the Pareto condition {c\stackrel{s}\succ b}. Transitivity gives us {a\stackrel{s}\succ b}, or {a\stackrel{d}\succ b\Longrightarrow a\stackrel{s}\succ b}, which means that {d} — dictator. \Box

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).


[1] Arrow, K. J., A Difficulty in the Concept of Social Welfare, Journal of Political
Economy 58(4), 1950, 328-346
[2] Ning Neil Yu, A One-shot Proof of Arrow’s Impossibility Theorem, 2012
[3] Pakhomov, V., Democracy from a Mathematical Viewpoint, Kvant, 9, 10, 1992 (in
[4] Taylor, A. D., Pacelli, A. M., Mathematics and Politics: Strategy, Voting, Power
and Proof, Springer, Second edition,2010.



About Artem Novozhilov

I am an applied mathematician interested in studying various evolutionary processes by means of mathematical models. More on my professional activities can be found on my page
This entry was posted in Teaching, Uncategorized and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s