Kleinblog: The proof I head heard of for Arrow's Impossibility theorem was alluded to at the very end of class --- what preceded it was (in my opinion) a much slicker proof, even though it might be considered less elegant (but not less true) from a constructivist point of view.
So the theorem says this: define a voting system to be a mapping f from a set S of rankings of candidates or options or something, one ranking per every member of some society to a consensus ranking f(S). If a voting system f has the following three perhaps desirable properties
- Unanimity: if everyone prefers A to B in their ranking, then so does the consensus ranking
- Monotonicty: let ranking sets S and S' be given. Fix some candidate A. Suppose for all B, if S prefers A to B, then S' prefers A to B. Then if f(S) prefers A to B, then f(S') prefers A to B. In plain english, if we go in to people's brains and only improve their opinion of A, then the voting system should only reveal an improvement in A's consensus ranking.
- Independence of Irrelevant Alternatives: f on a ranking set restricted to a smaller set of candidates is equal to the output of f on the original set, subsequently restricted to the smaller set. In plain english, there is no "tactial voting"; the introduction of a ralph nader or ross perot should not change the relative ranking obtained for other candidates.
and there are at least three candidates, then f is a dictatorship. That is, there exists some member of society whose ranking function f returns directly.
Proof: Say a set of voters I is (A,B)-decisive if whenever everyone in I prefers A to B, then so too does the consensus ranking. Let J be a smallest set for which there exists A, B such that J is (A,B)-decisive. (Unanimity guarantees there is some decisive set.) Let j be some member of J. Consider the following scenario, made possible by our assumption that there are at least three candidates.
j J-j complement of J
C > A > B A > B > C B > C > A
Since J is decisive for (A,B) and we suppose everyone in J prefers A to B, the consensus ranking prefers A to B. Only the members of the set J-j prefer A to C --- everyone else thinks C > A. So the consensus ranking must say C > A, or else J-j (A smaller set than J!) would be (A,C)-decisive, violating our minimality requirement for J. By transitivity, C > A > B means the consensus ranking puts C preferred to B. But j is the only voter that prefers C to B! Hence the minimal decisive set is of size one, and we have shown that if this one voter is (A,B)-decisive, then they are (C,B)-decisive for any C not equal to B.
Let (D,E) be given with D not equal to B. Consider
j complement of {j}
D > B > E B > E > D
Here j is (D,B)-decisive, so consensus says D > B. Also by unanimity, consensus says B > E. Yet j is the only voter that says D > E, so j is (D,E) decisive for any D not equal to B, and any E.
Finally we must show that j is (B,F)-decisive for any F. Let some G not equal to B,F be given and consider
j complement of {j}
B > G > F F > B > G
Since j is (G,F)-decisive, consensus says G > F. Also by unanimity, consensus says B > G. So consensus says B > F, though only j thinks this. So j is (B,F) decisive for any F. In other words, we have shown j is a dictator.
---
In other news, my copy of Faŭsto came in the mail.
El fruaj tempoj sentas mi reveni
Al mia vid', figuroj svagaj, vin.
Ĉu provu mi ĉifoje vin firmteni?
Ĉu restis al vi kora la inklin'?
Vi alpremiĝas! Do, bonvolu veni
El la nebulo ĉirkaŭanta min;
Junece mia sino jam ekskuas
pro sorĉa sprio, kiu vin trafluas. |
