# ML Wiki

## May's Theorem

May's Theorem is a Voting Theory theorem

Desirable Properties

• Neutrality - we don't look at the names of candidates
• Anonymity - we just count the votes without looking at the names of voters
• Monotonicity

### Theorem

With two candidates ($A = \{a, b\}$) the only voting mechanism that satisfies all these three properties is Plurality Voting

Anonymity
• the only possible thing to do is to count the number of voters that prefer $a$ to $b$ and $b$ to $a$:
• let $N(a > b)$ denote the number of people who prefer $a$ to $b$ and $N(b > a)$ - $b$ to $a$
• by neutrality we can say without loss of generality that $N(a > b) > N(b > a)$

For the case when $N(a > b) > N(b > a)$ there are two possible outcomes:

1. $a$ is elected - this case is the Plurality Voting case
2. $b$ is elected - not Plurality Voting

Case 2

$N(a > b) > N(b > a)$ but $b$ wins over $a$ - let's show that this assumption leads to contradiction

• $N(a > b) > N(b > a) \Rightarrow N(a > b) = N(b > a) + k$ for some $k > 0$
• by applying the Monotonicity principle (we assume it's satisfied) we improve $b$'s position:
$N(a > b) = N(b > a) + 1$: $b$ still gets elected
• continue improving $b$'s positions
$N(a > b) = N(b > a) - k' \Rightarrow N(a > b) < N(b > a)$
• since the candidate with fewer votes gets elected, not $a$ wins
• thus Monotonicity is not satisfied: by improving his position $b$ no longer wins
• contradiction: by monotonicity $b$ should remain elected, but by the assumption - $a$

Therefore the only possible outcome under the assumed principles is $a$ wins - which is the Plurality Voting mechanism.

$\square$