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?

Answer:

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

Leave a Reply Cancel reply

Welcome!

CV and more