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. |