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.

 

Advertisements

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 https://www.ndsu.edu/pubweb/~novozhil/
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:

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s