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.

Formally,

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

References:

[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
Russian)
[4] Taylor, A. D., Pacelli, A. M., Mathematics and Politics: Strategy, Voting, Power
and Proof, Springer, Second edition,2010.