Jason (jcreed) wrote,

So here's a nice set of three proofs of Arrow's Impossibility Theorem. I only understand the first one, but hey, one's enough.

Here's a retelling of the first proof as I've understood it. A constitution is a thing that outputs a societal ranking of all candidates, given as input every citizen's ranking. A consitution has the property of unanimity if the societal ranking says X is strictly better than Y at least whenever every citizen believes this. A constitution hsa the property of irrelevance of independent alternatives if the societal ranking of X compared to Y can be determined solely from the individual citizens' X-vs.-Y feelings. Arrow's theorem says that if there are at least two voters and three candidates, the only constitutions that have both these properties possesses are dictatorships, i.e. have one fixed citizen whose rankings are output without considering anyone else's.

There is a lemma that says, for any b, if everybody is "polarized" on b, i.e. everyone thinks b is the best or worst (but society may still be split on whether b is the worst or best) then the constitution must output a societal ranking which has b being at the top or bottom. For suppose otherwise, i.e. that the constitution puts b between some other two elements a and c, so that a <= b <= c, for some b-polarized set of citizen rankings. Now here's where it starts being obvious that IIA is a really strong principle. What we can do is fudge around the a vs. c votes in all citizens by moving c above a everywhere. We take care, as we diddle each voter's brain, to leave b where it is, whether at the top or bottom. Because of this, nobody's a vs. b or b vs. c opinions have changed. Everyone still thinks "b is the greatest!!!" or has "anybody but b!!!" bumper stickers as they did before. Because of IIA, we still must have a <= b <= c, but everyone now prefers c to a. Contradiction! Classically (I don't know if there's a natural constructive proof... I don't see any infinities around, so I suppose it is probably still technically constructively true) we conclude that our original assumption was false, and therefore that b is societally considered to be the best or the worst.

Armed with this lemma we can do the following thought experiment. Consider any ol' set of citizen rankings. Change them by slamming b to the bottom in all of them. By unanimity, society now also thinks b is the worst. Proceed with the whole population, person by person, flipping b from "worst" to "best". By mean-value-theoremish reasoning, society must at some point change its mind from "b is shit candidate" to "b is the greatest". The citizen whose diddling effected this change is called the b-pivotal voter. Call the set of rankings just before we upped the BPV's opinion of b "ranking set I" and the set of rankings after "ranking set II".

For some candidate z, say a z-dictator is a citizen whose opinion on any pair xy perfectly determines the societal outcome, as long as z is neither x nor y. Here's a funny thing: the b-pivotal voter is actually a b-dictator. Why? Let a and c be given distinct from b. In ranking set II, both a and c are less than b. Create ranking set III, which looks just like II, except that we move a above b, such that a > b > c according to our wily b-pivotal voter, and where we let every other citizen say whatever the hell they want about a and c, as long as they leave b whereever it was in profiles I and II. (remember the only citizen that changes their mind between I and II is the BPV) We can show that the constitution pronounces a better than c in ranking set III. It must say a > b: this is because the a vs. b votes for everyone in III are the same as in set I, and the constitution said b was the worst for set I. It must say b > c: this is because the b vs. c votes for everyone in III are the same as in set II, and the constitution say b was the best for set II. By transitivity society says a beats c. By IIA, we can forget all about opinions about b. Only the a vs. c votes matter to societally rank a and c, and the BPV has absolute say.

So for every x there is an x-pivotal voter who is also an x-dictator, but these all must be the same person. For suppose we have at least candidates x, y, and z. Consider an x-pivotal voter, who is also an x-dictator. This voter can swing x from below all other candidates to above all other candidates. But if there were a different voter who was a y-dictator, they could affect the x-z rankings with absolute power, contradicting the x-pivotal voter's pivotality. So the y-dictator must be the same as the x-dictator, for any y. Thus we have a dictator, QED.

Now, I was trying to convince myself in the shower this morning that the general idea I had yesterday necessarily falls apart, i.e. that this argument should also apply to any reasonable generalization of citizen-rankings, because you can just strip away any information that isn't the order and come up with a dictatorship. But I thought of a counterexample pretty quickly, namely the easily gamed "bad abstraction" of yesterday's post. Let everyone assign real numbers to all candidates, and let the constitution take a simple sum. Setting aside that it's totally infeasible as a voting system, it does seem to paradoxically pass all of Arrow's criteria. It doesn't have dictators, it certainly has unanimity just because a < a' and b < b' implies a + b < a' + b', and it seems to have IIA, in that if you add new candidates with new valuations, that has no effect on the old candidates' valuations or rankings.

But, and this is the critical thing, it's not really IIA by the definition given above. We don't have that the societal rankings of a vs. b only depend on the citizen rankings of a vs. b. And in fact the first lemma fails. We can imagine a republican candidate R, a democrat D, and a centrist C. If all the republicans say 3 for R, 2 for C, and 0 for D, and all the democrats say 3 for D, 2 for C, and 0 for R, and there are 11 republicans and 10 democrats, then we get a score of 42 for C, 33 for R, and 30 for D. Every citizen's opinion on R is polarized, but society's isn't. This is because the "fudge everyone's a-preference just above their c-preference" step in the lemma actually can lead to a defeating b.

The thing is that we do have a nice IIA-like property, namely that society's valuation of a candidate only depends on the citizens' valuations. This gives me some hope that we maybe can actually satisfy a reasonable set of requirements that structurally look very much like Arrow's, just for an idealization of voting which extracts more information from the voter than rankings. (besides, say, Condorcet's weakening of the IIA criterion, which, although I think is not so bad, I hope we might be able improve)

  • (no subject)

    Something that's bugged me for a long time is this: How many paths, starting at the origin, taking N steps either up, down, left or right, end up at…

  • (no subject)

    Still sad that SAC seems to end up being as complicated as it is. Surely there's some deeper duality between…

  • (no subject)

    I had already been meaning to dig into JaneSt's "Incremental" library, which bills itself as a practical implementation (in ocaml) of the ideas in…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment