## Arrow's "impossibility" theorem – how can range voting accomplish the impossible?

According to this voting tutorial by Prof. William R. Webb, (from which we now quote verbatim) Arrow's (1950) theorem states that no voting method can satisfy the following short list of conditions:

1. There is no dictator.
2. If every voter prefers A to B then so does the group.
3. The relative positions of A and B in the group ranking depend on their relative positions in the individual rankings, but do not depend on the individual rankings of any irrelevant alternative C.

Webb continues: "That's not just the voting methods we know of now, but any voting method anybody might think of in the future as well. This fact is known as Arrow's Impossibility Theorem. This discovery was a major factor in Arrow winning the Nobel Prize in Economics." (End of verbatim quoting.)

But... wait a minute. Range voting satisfies all three criteria, accomplishing the "impossible"! Huh? Let's check that in slow-mo:

1. There is no dictator – that is, there exists no single range voter ("Joe Stalin") who, no matter what the other voters say, always gets it his way. Check.
2. If every voter rates A above B, then A's summed-score (and hence average score) will be higher than B's. So the finish-order will rank A above B. Check.
3. Jane Voter's score for C in no way affects her scoring of A and B, which are totally independent scoring decisions made by that voter. Hence A's and B's averages (and hence finish-order) are in no way affected by how any and all voters rate C. Check.

And range voting is not the only voting system accomplishing the "impossible"; many others, such as trimmed-mean range voting which we recommend for judging figure-skating events, also do so.

How can this be? The explanation is simple. Arrow, when he made his theorem, made a definition of what a "voting system" was. His theorem only applies to voting systems that obey his definition. The trouble is that (in my opinion) Arrow made a silly definition. One reason it is silly is that, according to Arrow's definition, range voting is "not" a voting system at all. It sure looks and feels like a voting system. It inputs votes and it elects a winner. But according to Arrow's definition, it isn't a voting system. (It is pretty easy to prove voting systems "impossible" if, as step one, you define a lot of voting systems as not being voting systems.)

The true lesson of Arrow's theorem is (more than anything else, in my opinion) that you should stay away from voting systems based on rank-order ballots.

Analysis of why Arrow didn't like range voting.

#### Who first pointed this out?

Warren D. Smith pointed this out in 2000, and Claude Hillinger at about the same time. A few years later John C. Lawrence went further than them, making an especially strong criticism of Arrow: based on a close look at Arrow's words, Lawrence contends Arrow actually did briefly consider range voting, but dismissed it due to a mental mistake. Much earlier than any of these people, economist John C. Harsanyi had pointed it out in the 1950s shortly after Arrow's work appeared. Harsanyi later (1994) was awarded the Nobel Prize, but, despite that, his point about Arrow's theorem for some reason remained largely ignored and unknown. For example, you can read about how (also Nobel Laureate) Eric Maskin apparently remained ignorant of this as of 2007.

There also are many more papers and books about this, e.g. Kenneth J. Arrow: A Difficulty in the Concept of Social Welfare, Journal of Political Economy 58, 4 (August 1950) 328-346 is Arrow's original paper. K Akashi: A simplified derivation of Arrow's Impossibility Theorem Hitotsubashi Journal of Economics 46,2 (Dec 2005) 177-181; T.E.Armstrong: Arrow's theorem with restricted coalition algebras, J.Mathematical Economics 7 (1980) 55-75; John Geanakoplos: Three brief proofs of Arrow's impossibility theorem, Economic Theory 26,1 (July 2005) 211-215; P.Hansen: Another graphical proof of Arrow's Impossibility Theorem J. of Economic Education 33,3 (Summer 2002) 217-235; John C. Harsanyi: Cardinal utility in welfare economics and the theory of risk-taking, J. of Political Economy 61 (Oct. 1953) 434-435; John C. Harsanyi: Cardinal welfare, Individualistic ethics, and Interpersonal comparisons of utility, J. of the Political Economy 63 (Aug. 1955) 309-321; John C. Harsanyi: Rational behavior and Bargaining Equilibrium in games and social situations, Cambridge Univ. Press 1977; A.P.Kirman & D.Sondermann: Arrow's theorem, many agents, and invisible dictators, J. Economic Theory 5 (1972) 267-277; Luc Lauwers: Topological social choice, Mathematical Social Sciences 40,1 (2000) 1-39; H. Reiju Mihara: Arrow's theorem, countably many agents, and more visible invisible dictators, J. Mathematical Economics 32,3 (1999) 267-287; Klaus Nehring: Arrow's theorem as a corollary, Economics Letters 80,3 (Sept. 2003) 379-382; Yasuhito Tanaka: A topological approach to the Arrow impossibility theorem when individual preferences are weak orders, Applied Maths & Computation 174,2 (March 2006) 961-981; Yasuhito Tanaka: On the equivalence of the Arrow impossibility theorem and the Brouwer fixed point theorem, Applied Maths & Computation 172,2 (Jan 2006) 1303-1314; Yasuhito Tanaka: On the computability of binary social choice rules in an infinite society and the halting problem, Applied Maths & Computation (August 2007?); H.Terao: Chambers of arrangements of hyperplanes and Arrow's impossibility theorem, Advances in Maths 214,1 (Sept. 2007) 366-378; ...

#### The fine print

Actually, in his tutorial, Webb did not very carefully state a precise and complete statement of Arrow's theorem – he "dumbed it down" for a wide audience. If he had done so, then Range Voting would (with some theorem versions) disobey criterion #3 – but even in those versions, a system related to range, called "honest utility voting," still would "impossibly" obey all three Arrow criteria. The issue is that many voting system criteria were originally carelessly worded by people, such as Arrow, who simply did not conceive (or if he did he cavalierly dismissed them) that there might be other voting systems in the universe – such as range voting – besides ones employing rank-order ballots. When you try to employ the criteria to these more general voting systems, there often are several inequivalent ways to word criteria, all of which happen to be equivalent if we restrict attention to rank-order systems. That is the case for Arrow's IIA criterion, as well as the majority criterion and Condorcet's criterion. Thus, under some wordings of the criteria taken verbatim from the literature, range voting is a Condorcet method, approval voting obeys the Majority Criterion, and range obeys IIA. Under other wordings, none of these are true. Here, we are simply pointing out that with Webb's wording – which is perfectly valid for all rank-order voting systems, which is all Arrow was considering – Range Voting obeys all three of Arrow's "incompatible" criteria.

To explain: there are two natural ways to word the IIA criterion when you try to generalize Arrow to ratings-ballot voting systems:

1. When candidate C is removed from all ballots, the voting system's (output) relative ordering of A & B does not change.
2. When C is removed from the election and voters vote again in a new election knowing that C is now gone (and thus "renormalizing" their ballots), and re-vote in a way consistent with their original votes, then the voting system's (output) relative ordering of A & B does not change.
Both of these wordings are equivalent if we are talking about rank-order-ballot voting systems, and wording #1 seems simpler. But these wordings are not equivalent for ratings-ballot systems such as range voting. With wording #1, Range Voting accomplishes all three "impossible" Arrow desiderata. But with wording #2, RV fails the IIA criterion (elections demonstrating that failure arise from any Condorcet cycle situation). "Honest utility voting" satisfies all three criteria no matter which wording you use.

For a deeper and more precise look, we recommend W.D.Smith's survey paper #79 here and P.C.Fishburn: Arrow's Impossibility Theorem: Concise Proof and Infinite Voters, J. Economic Theory 2,1 (March 1970) 103-106. Fishburn proves a strictly stronger statement than Arrow's theorem in only 2 pages (whereas it took Arrow an entire, and rather badly written, book to prove a weaker statement).

#### Even stronger theorems than Arrow's!

A.Quesada: More on independent decisiveness and Arrow's theorem, Social Choice & Welfare 19,2 (April 2002) 449-454
is able to replace Arrow's third postulate with a weaker one.

Gil Kalai: A Fourier-theoretic perspective on Arrow's theorem and Condoret's paradox, Advances in Applied Mathematics 29,3 (Oct. 2002) 412-426
is able to prove quantitative versions of Arrow's theorem:

Kalai's Theorem 1.1:
For a symmetric social choice function with 3-candidates, the probability that the output-ranking is transitive is less than 0.9192.
Kalai's Theorem 1.2:
There exists an absolute constant K so that: for a neutral social choice function, if prob(Condorcet cycle exists)<ε, then prob(dictator fails to force his choice to be the winner)<Kε.
Kalai's Theorem 5.1 (& discussion on his p.419):
Prob(symmetric Social Choice Function on 3m candidates leads to a transitive output-ranking)<0.91m.

#### Wilson's impossibility theorem

Another famous impossibility theorem is Wilson's impossibility theorem [Robert B. Wilson: Social choice theory without the Pareto principle, J. Economic Theory 5 (1972) 478-496]. It is quite like Arrow's theorem, but avoids the test about unanimity. Specifically

THEOREM: Any social choice function satisfying these 2 conditions must be a dictatorship or reverse-dictatorship (in both cases a single voter, the "dictator," has total control over the voting system's output-ordering, either by always getting his vote as the output of the voting system, or by always getting the reverse of his vote as the output of the voting system):

1. The voting system does not always prefer some candidate A over some other B (regardless of the votes).
2. The relative positions of A and B in the group ranking depend on their relative positions in the individual rankings, but do not depend on the individual rankings of any irrelevant alternative C (this is the same last condition as Arrow's)

Again, range voting "accomplishes the impossible": it is not a dictatorship (reverse or not), it does not always prefer somebody A over B regardless of the votes, and it obeys the final condition. It can do that because hidden in the definition of "social choice function" is the requirement that the ballots must be rank-order ballots. Range voting uses rating ballots and hence can evade Wilson's theorem.

#### My own impossibility theorem

Is explained here. Range voting again evades it by not employing rank-order ballots.

#### Unified impossibility theorem via topology

It recently was realized there there is a unified theorem which combines both Arrow's and the Gibbard-Satterthwaite impossibility theorem into a single statement which may be proven by topological methods. The entire community of course went into ecstasy when they heard that, since it is just so amazingly cool-sounding (although I'm not sure there is any great benefit aside from sounding cool).
K. Eliaz: Social aggregators, Social Choice & Welfare 22 (2004) 317-330;
Yasuhito Tanaka: A topological proof of Eliaz's unified theorem of social choice theory, Applied Mathematics and Computation 176,1 (May 2006) 83-90.

THEOREM: Any social choice function satisfying these 4 conditions must be a dictatorship:

1. The voting system always outputs at least one winner.
2. If the voting system claims A>B and B≥C, then it does not claim C>A.
3. If all voters prefer A>B then the voting system does too.
4. If in election #1 the voting system says A>B, but in election #2 (with the same voters) it says B>A, then at least one voter must have reversed her preference relation about A and B.

I was all ready to say that once again, range voting "accomplishes the impossible" by satisfying every condition in this theorem without being a dictatorship – except it does not because it is possible for the range voting winner to change from A to B without any voter changing her opinion that A>B, A<B, or indifferent(A,B) [just changing strengths of preferences can suffice]. And I should have known that immediately because I already knew that range voting only partially evades the Gibbard-Satterthwaite impossibility theorem.

#### Tanaka's impossibility theorem

Tanaka devised an altered version of Wilson's impossibility theorem which now involves a "monotonicity" axiom instead of Arrow's final condition [Yasuhito Tanaka: A necessary and sufficient condition for Wilson's impossibility theorem with strict non-imposition, Economics Bulletin 4,17 (2003) 1-8]. However, you are warned that Tanaka's notion of "monotonicity" is nontraditional and probably not what you were expecting...

THEOREM: Any social choice function satisfying these 2 conditions must be a dictatorship or reverse-dictatorship:

1. The voting system does not always prefer some candidate A over some other B (regardless of the votes).
2. Either:
1. Whenever the voting system says X>Y and then the votes change in such a way that: every voter who was indifferent about X versus Y changes her vote to say X>Y and every voter who had voted X>Y still says X>Y in her (new) vote, then the voting system always still outputs the social preference X>Y ("monotonicity") OR
2. Whenever the voting system says Y>X and then the votes change in such a way that: every voter who was indifferent about X versus Y changes her vote to say X>Y and every voter who had voted X>Y still votes X>Y in her (new) vote, then the voting system still outputs the social preference Y>X ("reverse monotonicity").

Remark: One might have thought that Borda voting was a counterexample to this theorem. It isn't. Tanaka explains: while Borda is normally considered "monotonic," it is not under his (nontraditional) definition. A counterexample is

 Voter#1: X>Y>Z>W Voter#2: W>X>Y>Z Voter#3: W>X>Y>Z

Here X is the winner with 7=3+2+2 points, and W is the runner-up with 6=0+3+3 points. If Voter#1 changes her vote to "X>W>Y>Z" then W becomes the winner with 8=2+3+3 points, despite the fact that Voter#1 did not change her vote's preference X>W and no voter was indifferent. This contradicts Tanaka's definition 2a of monotonicity.

Does range voting "accomplish the impossible" by satisfying the assumptions of, while disobeying the conclusion of, Tanaka's theorem? No, because Range Voting also is "non-monotonic" under Tanaka's definition (although again normally considered monotone).

#### A 1-sentence (partial) proof of Arrow's Theorem

It is possible to prove Arrow's theorem for election methods which reduce to simple-majority in the 2-candidate case in only one sentence: Consider a Condorcet-cycle scenario such as this and note that removing a non-winning candidate changes the winner. Q.E.D.

Another famous theorem by Gibbard & Satterthwaite