Partially prompted by Terry’s buzz, I decided to take a look at Arrow’s Impossibility Theorem. The name I have heard before, since I participated in CollegeBowl as an undergraduate, and questions about Arrow’s theorem are perennial favourites. The theorem’s most famous interpretation is in voting theory:
- Given a set of electors and a finite set of candidates , a preference assigns to each elector an ordering of the set . In particular, we can write for the statement “the elector prefers candidate to candidate “. The set of all possible preferences is denoted .
- A voting system assigns to each preference an ordering of the set .
- Given a preference and two candidates , a bloc biased toward is defined as the subset
- The voting system is said to be
- unanimous if, whenever all electors prefer candidate to , the voting system will return as such. In other words, ““.
- independent if the voting results comparing candidates and only depend on the individual preferences between them. In particular, whether only depends on . An independent system is said to be monotonic if, in addition, a strictly larger biased bloc will give the same voting result: if and , then necessarily.
- dictator-free if there isn’t one elector whose vote always coincides with the end-result. In other words, we define a dictator to be an elector such that for any .
- A voting system is said to be fair if it is unanimous, independent and monotonic, and has no dictators.
And the theorem states
Arrow’s Impossibility Theorem
In an election consisting of a finite set of electors with at least three candidates , there can be no fair voting system.
As we shall see, finiteness of the set of electors and the lower-bound on the number of candidates are crucial. In the case where there are only two candidates, the simple-majority test is a fair voting system. (Finiteness is more subtle.) It is also easy to see that if we allow dictators, i.e. force the voting results to align with the preference of a particular predetermined individual, then unanimity, independence, and monotonicity are all trivially satisfied.
What’s wrong with the simple majority test in more than three candidates? The problem is that it is not, by definition, a proper voting system: it can create loops! Imagine we have three electors and three candidates . The simple majority test says that if and only if two or more of the electors prefer to . But this causes a problem in the following scenario:
then the voting result will have , , and , a circular situation which implies that the “result” is not an ordering of the candidates! (An ordering of the set requires the comparisons to be transitive.) So the simple-majority test is, in fact, not a valid voting system.
From this first example, we see already that, in the situation of more than 2 candidates, designing a voting system is a non-trivial problem. Making them fair, as we shall see, will be impossible. Read the rest of this entry »