29 May’s Theorem

Kenneth May’s groundbreaking 1952 paper provided a rigorous mathematical justification for majority rule (Definition 28.2) by showing it is the only voting method that satisfies certain fundamental principles of group decision-making.

Recall that we are restricting attention to group decisions involving exactly two candidates. When we have exactly two candidates, we write the set of candidates as \(X=\{a,b\}\). An example of a profile for this set of candidates is \(\mathbf{P}=(a\mathrel{P} b, b\mathrel{P} a, a\mathrel{P} b)\), where the first and third voters prefer \(a\) over \(b\) while the second voter prefers \(b\) over \(a\).

May’s Theorem will show that majority rule has a special status: it is the only voting method that satisfies certain fundamental properties of group decision-making. To appreciate these properties, let’s first look at some alternative voting methods that could be used to select winners.

Always Choose \(a\): This method ignores all votes and selects \(a\) as the winner in every profile. For example, in the profile \(\mathbf{P}=(b\mathrel{P} a, b\mathrel{P} a)\), \(a\) still wins despite both voters preferring \(b\).
First Voter’s Choice: This method selects whichever candidate is preferred by the first voter. For example, in the profile \(\mathbf{P}=(b\mathrel{P} a, a\mathrel{P} b, a\mathrel{P} b)\), \(b\) wins because the first voter prefers \(b\), even though more voters prefer \(a\).
Supermajority Rule: A candidate must receive strictly more than a specified threshold (say, two-thirds) of the votes to win. If no candidate reaches this threshold, both candidates win. For example, with a two-thirds threshold and profile \(\mathbf{P}=(a\mathrel{P} b, a\mathrel{P} b, b\mathrel{P} a)\), both \(a\) and \(b\) win since \(a\) has only two-thirds of the votes, not more.
Unanimous Consensus: A candidate wins only if every voter prefers them. If voters disagree, then both candidates are declared winners. For example, in \(\mathbf{P}=(a\mathrel{P} b, a\mathrel{P} b)\), \(a\) wins, but in \(\mathbf{P}=(a\mathrel{P} b, b\mathrel{P} a)\), both \(a\) and \(b\) win.
Minority Rule: The candidate with fewer votes wins. If there’s a tie, both candidates win. For example, in \(\mathbf{P}=(a\mathrel{P} b, a\mathrel{P} b, b\mathrel{P} a)\), \(b\) wins despite only one voter preferring it.

Each of these voting methods is well-defined - they give clear winners for any profile. However, they each have drawbacks that we’ll explore when we discuss the fundamental properties of voting methods.

29.1 May’s Axioms

May identified three fundamental properties that we want any voting method to satisfy.

The first principle is Anonymity. This says that the identities of the voters should not matter. The outcome should depend only on how many people voted each way, not on which specific voters voted which way. For example, if voters 1 and 2 swap their votes, this shouldn’t change the winner.

Definition 29.1 (Anonymity) A voting method \(F\) satisfies anonymity if rearranging the voters’ preferences in any way does not change the set of winners. In other words, if \(\mathbf{P}\) is a profile and \(\mathbf{P}'\) is another profile that is exactly like \(\mathbf{P}\) except that some of the voters have swapped their ballots, then \(F(\mathbf{P})=F(\mathbf{P}')\).

The voting method Always Choose \(a\) satisfies anonymity because the outcome is always \(a\), regardless of the voters’ preferences. The method First Voter’s Choice does not satisfy anonymity because the outcome depends on which ballot the first voter submitted.

The second principle is Neutrality. This says that the names of the candidates should not matter. The method should treat both options equally, without favoring either one. If we swap every voter’s preference between \(a\) and \(b\), the outcome should swap as well.

Definition 29.2 (Neutrality) A voting method \(F\) satisfies neutrality if swapping the candidates leads to an equivalent swap in winners. More precisely:

Given any profile \(\mathbf{P}\),
Create a new profile \(\mathbf{P}'\) by swapping \(a\) and \(b\) in every voter’s ballot,
Then \(F(\mathbf{P}')\) must be the same as \(F(\mathbf{P})\) with \(a\) and \(b\) swapped.

For example, if \(a\) wins in \(\mathbf{P}\) according to \(F\) (i.e., \(a\in F(\mathbf{P})\)), then if \(\mathbf{P}'\) is the profile \(\mathbf{P}\) where \(a\) and \(b\) are swapped in everyone’s ballots, then \(b\) must win in \(\mathbf{P}'\) according to \(F\) (i.e., \(b\in F(\mathbf{P}')\)). Furthermore, if both candidates win in \(\mathbf{P}\), then both must win in \(\mathbf{P}'\) as well.

To see that Always Choose \(a\) violates Neutrality, consider the profile \(\mathbf{P}=(a\mathrel{P} b, b\mathrel{P} a)\). Under this method, \(a\) is the unique winner in \(\mathbf{P}\). Now, swap \(a\) and \(b\) in every voter’s ballot to get profile \(\mathbf{P}'=(b\mathrel{P} a, a\mathrel{P} b)\). By Neutrality, since \(a\) was the unique winner in \(\mathbf{P}\), \(b\) should be the unique winner in \(\mathbf{P}'\). However, Always Choose \(a\) still selects \(a\) as the winner in \(\mathbf{P}'\), violating Neutrality.

An important consequence of Anonymity and Neutrality is that in any profile \(\mathbf{P}\), if the same number of voters prefer \(a\) over \(b\) as prefer \(b\) over \(a\) in \(\mathbf{P}\), then \(a\) and \(b\) must be tied for the win.

To see why, suppose that \(F\) satisfies Anonymity and Neutrality and consider the profile \(\mathbf{P}=(a\mathrel{P} b, b\mathrel{P} a, a\mathrel{P} b, b\mathrel{P} a)\). We will explain why it is impossible to have \(a\) be the unique winner in \(\mathbf{P}\) according to \(F\) (i.e., \(F(\mathbf{P})={a}\)). Consider the profile \(\mathbf{P}'=(b\mathrel{P} a, a\mathrel{P} b, b\mathrel{P} a, a\mathrel{P} b)\). Since \(\mathbf{P}'\) is a profile obtained by swapping \(a\) and \(b\) in every voter’s ballot in \(\mathbf{P}\), by Neutrality, if \(F(\mathbf{P})={a}\), we must have \(F(\mathbf{P}')={b}\).

Now, notice that \(\mathbf{P}\) can be obtained from \(\mathbf{P}'\) by swapping the first and second voters’ ballots and swapping the third and fourth voters’ ballots. By Anonymity, we must have that \(F(\mathbf{P})=F(\mathbf{P}')\). But this is impossible since we showed that \(F(\mathbf{P})=\{a\}\) and \(F(\mathbf{P}')=\{b\}\). This contradiction shows that \(a\) cannot be the unique winner in \(\mathbf{P}\).

By the same argument, \(b\) cannot be the unique winner either. Therefore, in any profile where equal numbers of voters prefer each candidate, both candidates must tie for the win.

The third principle is Weak Positive Responsiveness. This principle captures the idea that if a candidate is winning (or tied for winning) and then receives more support, they should become the unique winner. For instance, if \(a\) is tied with \(b\), and one voter changes from preferring \(b\) to preferring \(a\), then \(a\) should win outright.

Definition 29.3 (Weak Positive Responsiveness) A voting method \(F\) satisfies Weak Positive Responsiveness if the following holds: Consider any two profiles \(\mathbf{P}\) and \(\mathbf{P}'\) where:

\(a\) is a winner in profile \(\mathbf{P}\) (that is, \(a \in F(\mathbf{P})\)), and
\(\mathbf{P}'\) is obtained from \(\mathbf{P}\) by having one voter who ranked \(a\) last switch to ranking \(a\) first (while all other votes stay the same).

Then \(a\) must be the unique winner in \(\mathbf{P}'\) (that is, \(F(\mathbf{P}') = \{a\}\)).

\(a\) is the winner since it has the fewest number of first place votes.

29.2 The Theorem

Anonymity, Neutrality, and Weak Positive Responsiveness capture basic intuitions about fair group decision-making:

Anonymity ensures equal treatment of voters;
Neutrality ensures equal treatment of alternatives; and
Weak Positive Responsiveness ensures that gaining support helps a candidate win outright.

May’s Theorem shows that Majority Rule not only satisfies all these properties, but it is the only voting method that does.

Theorem 29.1 (May’s Theorem) Let \(F\) be a voting method on the domain of two-alternative profiles. Then the following are equivalent:

\(F\) satisfies Anonymity, Neutrality, and Weak Positive Responsiveness;
\(F\) is majority voting.

A proceduralist justification focuses on the fairness and reasonableness of the decision-making procedure itself, rather than on the outcomes it produces. May’s Theorem provides this type of justification for Majority Rule by showing it is the only voting method that satisfies basic principles of fair decision-making: treating all voters equally (Anonymity), treating all alternatives equally (Neutrality), and responding appropriately to voter preferences (Weak Positive Responsiveness).

However, this is not the only way to justify Majority Rule. In the next chapter, we discuss an epistemic justification of Majority Rule showing that is good at discovering truth - it has a high probability of identifying the correct answer to a question.