Suppose that you have two candidates Peter and Liz running for senior student body president. How should the winner of the election be decided?
Jason, the current student body president, suggest that all 101 will be seniors vote. We have several options for how to determine the winner of this election.
- Whoever Jason votes for should automatically be declared the winner. This is called a dictatorship, not exactly so fair.
- No matter how anyone votes Liz will be named the winner. This is imposed rule, where the winner is decided before the election takes place.
- Every student votes for whoever they want to win the election and which ever candidate receives the fewest votes will be declared the winner. This method of choosing the winner is called (not suprisingly) minority rule.
All of these are legitimate voting systems, i.e. the way in which the winner of an election is determined from the individual ballots. However, most would not call these systems "fair". In order for us to objectively determine what a "fair" voting system is let's list some properties that a fair voting system should have.
- A voting system should treat all of the voters equally. So if any two voters trade ballots, the outcome of the election should remain the same. This is an anonymous voting system.
- A voting system should treat the candidates the same. So if every voter switched there vote, the outcome would change accordingly (or remain the same in the event of a tie). This is a nuetral voting system.
- A voting system should be monotone. Meaning, it is impossible for a winning candidate to become a losing candidate by gaining votes (and not losing others), and also for a losing candidate to become a winning candidate by losing votes (and gaining no others).
Problem Set 1 : Look at the three voting systems we have considered and decide if they do, or do not, have each of these properties.
Anonymous Neutral Monotone Dictatorship Imposed Rule Minority Rule
End of Problem Set 1
Notice something about your solution to activity 1? None of those voting systems have all three properties. What about using majority rule for the election? Does majority rule have those three properties? Well indeed it does. These observations lead us to the title of the section.
May's Theorem (Kenneth May, 1952) In a two-candidate election with an odd number of voters, majority rule is the only voting system that is anonymous, neutral, and monotone, and that avoids the possibilites of ties.
Now, to be able to prove this theorem we will need to develop some terminalogy and make a few observations.
A voting system is called a quota system if there is some number q, called the quota, such that a candidate will be declared the winner if and only if they receive at least q votes. Note that in a quota system there could be two winners in an election or two losers, also that the quota could depend on the number of voters in the election (i.e. the quota could mean that a candidate must get 75% of the votes cast to become the winner).
Lemma: If a voting system (call it V) for an election with two candidates is anonymous, neutral, and monotone, then it is a quota system.
First, we will prove this lemma. Then, we will see how it implies May's Theorem.
Problem Set 2 : In an election with two candidates A and B, and n voters (labeled v1, v2, v3, ...,vn-1, vn). Using the voting system V answer the following serious of questions
- If no one votes for A, does V determine A to be a winner?
- If v1 votes for A, does V determine A to be a winner?
- If v1 and v2 vote for A, does V determine A to be a winner?
- If v1, v2, and v3 vote for A, does V determine A to be a winner?
- ...
- If all of the voters voted for A, does V determine A to be the winner?
Now, explain how you can use the answers to these questions to find a value that might work as a quota for V. Also, why can we label the voters in any order we want to? (Hint: what properties does V have?)
Now, with this potential quota q for V, using the three properties of V, cleary explain why the following statements are true.
Now, using the answers you have so far from Activity 2, explain why the Lemma is true.
- If exactly q voters (no matter which ones they were) voted for A, then V would choose A as a winner.
- If more than q voters (no matter which ones they were) voted for A, then V would choose A as a winner.
- If exactly q-1 voters (no matter which ones they were) voted for A, then V would not choose A as a winner.
- If fewer than q-1 voters (no matter which ones they were) voted for A, then V would not choose A as a winner.
- All of the above conditions also apply to candidate B.
End of Problem Set 2
So, now that we have shown the validity of the Lemma, how do we show that the Lemma gives us May's Theorem? Back to the statement of May's theorem, since our voting system is anonymous, neutral, and monotone, by the Lemma it is a quota system. Also, we have an odd number of voters n. All that remains to show is that the quota q is not (n+1)/2 (this is the quota that gives us majority rules), then there is a possibility for ties.
- If q>(n+1)/2, then there is a tie (both lose) when there are(n-1)/2 votes for A and (n+1)/2 votes for B.
- If q<(n+1)/2, then there is a tie (both win) when there are(n-1)/2 votes for A and (n+1)/2 votes for B.
- Hence to avoid ties we must have that q=(n+1)/2, i.e. V is majority rules.
Note: Using the same line of reasoning, you could show that there exist no voting system for two candidates, when there are an even number of voters, that is anonymous, neutral, and monotone, and that avoids the possibility of ties!
References and Further Reading:
[1]Jonathan K. Hodge and Richard E. Klima.The Mathematics of Voting and Elections: A Hands-On Approach. American Mathematical Society, Providence, R.I., 2005.