Arrow’s Impossibility Theorem: The Statement versus Its Proof
Ah! I love this stuff. In a bout of magnanimity I went back and re-read the comments in this Potpourri post, where Keshav and I couldn’t understand why Tel kept asking certain questions about Arrow’s Theorem. (Here’s my follow up which you should also read for more context.) And now I think I get what the problem is. Tel was looking at various proofs of the theorem (such as the one on Wikipedia) and then misunderstanding the definition of a dictator and also the applicability of the theorem.
Let me first make a contrived analogy, which is based on a true story. When I was a little kid, my dad did this trick: “Bob, think of a number. Now double it. Now add 8. Now cut the whole thing in half. Finally, subtract the original number you thought of. You’re thinking of 4.”
That absolutely blew my mind. After he did it a few times, I went and got paper and a calculator, and started picking enormous numbers and then trying negative decimals etc. I couldn’t understand what was going on. [EDITed to add: My dad would change the number that I added each time; I didn’t always end up thinking of 4. So it fueled the illusion that he was literally reading my mind.]
Of course, from my current vantage point, I could easily explain Pat’s Trick using algebraic notation. But suppose the following conversation occurred.
BOB: Ah, I can explain why Pat’s Trick works. Start with some number X. Then double it to get 2X. Now add 8, so you have 2X+8. Cut the whole thing in half–you’ve got X+4. Subtract the original number, you’ve got 4. And yep that’s the number Pat tells you you’re thinking of.
TEL: Sure maybe this works for Ivory Tower PhDs, but when Mark Dice approaches drunk college kids at the beach and says, “Think of a number,” they don’t think of X. They think of a number. Somebody tell me how X is a number? What is it? 1, 2, 3, 4, X? I don’t think so. We don’t count like that in Australia, that’s for sure.
KESHAV: No Tel you’re totally misunderstanding…
CRAW: Actually Tel has a point. According to Pat’s Theorem, it’s possible the person doesn’t know the actual number until the last step. But in the real world, when people think of a number and start manipulating it, at each stage they have a specific number in their minds. So I can see why Tel thinks Pat’s model doesn’t really apply to the world if you tried to have actual people do this trick.
Now to be sure, the above is a bit contrived, and obviously I don’t mean to suggest that Tel/Craw in the real world are being as obtuse as their hypothetical counterparts in the dialog. But I hope the analogy helps.
Specifically, when Landsburg in his proof of Arrow’s Theorem says something like, “But if Mushrooms had come out on top, I could have proved that Bob is an absolute dictator, and if Pepperoni had come out on top, I could have proved that Charlie is an absolute dictator. Regardless of what happened Tuesday, someone must be an absolute dictator,” he didn’t mean that people in society wouldn’t know if they had a dictator on their hands, or would need to see whose preferences get obeyed to figure it out ex post.
Rather, this phrasing is because Landsburg is proving the characteristics of an arbitrary social ranking. He’s assuming we have some rule that generates Social Rankings, and that the rule satisfies the other criteria of Arrow’s Theorem. Then Landsburg uses various considerations to paint it into a corner, and conclude that whatever the rule is, it must be anointing somebody as a dictator. We can’t say in general who the dictator is, because that choice would depend on the specific rule. (E.g. one rule could say, “Social Rankings always match Alice’s rankings,” and another rule could say “Social Rankings always match Charlie’s rankings.”) Landsburg is showing that for ANY rule (that obeys the other conditions), there must exist a dictator. Yes he has to be vague, because we haven’t spelled out the specific rule. Any specific rule would anoint one specific person as the dictator. All Landsburg is showing is that for any rule, there must be such a person.
This has to be like the ‘airplane on a treadmill’ problem, where groups of people adamantly defend the wrong answer over and over even after it is spelled out in very clear terms. The culprit in that problem is always that the mistaken group is interpreting the question in such a way as to include additional unstated (but perceived to be implied) conditions. In the airplane example, people hear ‘the treadmill moves backwards at the same rate the plane moves forwards’ it translate that into ‘the plane’s absolute position remains static’. Even after dozens or hundreds of replies explaining that the plane will move forward, this assumption continues to trip people up until eventually disloged, when the solution clicks immediately.
So my next question, if that is the case, is what assumption is being imported here that doesn’t belong but would explain the disagreement and confusion?
My best guess would involve some combination of time, multiple iterations of the social preference ranking rule, and changing preferences across iterations. That combined with the confusion between ‘every rule happens to create a dictator’ vs ‘only rules that create dictators satisfy the other criteria’.
Just a guess tho.
Michael,
Well in fairness to the people who were confused, Steve kinda muddied the waters by applying the rule on Monday, Tuesday, etc. I get why he did that, because that’s a more intuitive way to handle changing preferences among the people, but the problem is then people ask stuff like, “Why can’t we change the dictator each day?”
If the plane is moving forwards relative to the Earth as a whole, then by definition it must also be moving forwards FASTER relative to the treadmill than the treadmill is moving backwards, unless you are using some quite peculiar geometry.
Since the wheels of the plane are free spinning and low friction the treadmill can move at pretty much any speed and the movement of the plane is largely decoupled from that, but still the basic rules apply in terms of relative position.
I believe some interpet it to mean that the plane cannot move forward. This would cause the treadmill to accelerate to infinity and there is no physical way this could happen. Nevertheless, in this interpretation the plane is thought to be unable to move and no consideration is given to whether this makes sense. This allows people to continue arguing their interpretation by clinging to what they think the setup means. Sort of “yes, I know we cannot have a treadmill that moves that fast, but we are considering what would happen if we could.”
Most people expect that the answer to a problem should stay within the constraints posed by that problem. If no scenario can possibly fulfill all of these constraints simultaneously then maybe rethink what was being asked.
Since the whole idea of sticking a plane on a treadmill is unrealistic to begin with, everything after that is selective suspension of disbelief. If you do choose to believe in friction, the wheels on the aircraft would get hot and fail at some stage (nowhere close to infinity).
None of this has anything to do with voting of course. People really do vote, and it does have an effect on our lives and various mathematical models of elections capture some aspects of what happens during elections. The purpose of a model is to be simple while also giving some insight into the process and outcomes. The way I see it, creating a bunch of election criteria that don’t really represent what happens in an election in order to prove it’s impossible seems kind of self defeating. Anyway, I’ll try to get a proper explanation below.
“Have you not seen the Mythbuster’s one where they do exactly this? The plane, of course, takes off.
https://www.youtube.com/watch?v=YORCk1BN7QY
I agree with you that the conditions imposed in the setup make a lot more sense if they are based in physical reality and therefore the only sensible answer is that the plane will take off.
There’s two different kind of statements in mathematics regarding how constraints are imposed. This is basic set theory and it’s often simple assumed that the reader understands the context, but under the circumstances it seems worth spelling it out.
“True for all X” means it doesn’t matter which X you choose, it will always work. The symbol ∀ is sometimes used.
“There exists X” means that is really does matter which X you choose, but at least one of them works. The symbol ∃ is used for this purpose.
The equation would be: (2X + 8) / 2 – X = 4
This is a “True for all X” type of claim. You can use algebra to simplify it down and discover the X gets simplified out of the problem. Some equations work like that, but others do not. This has nothing to do with “ivory towers” but it’s just how math works. For example we have these simultaneous equations:
2X + 5Y = 13
3Y + 7Y = 19
Here we have a constraint that will not work “for all X” but it is possible to find at least one X where it will work. That’s the “existential quantification” or the ∃ symbol if you prefer. In this case the algebra will be unable to simplify X out of the problem completely, but it will be able to narrow down a specific value and thus solve the equation.
So here is a key part of the proof given by Amartya Sen, following Bob’s link from before:
Note that Sen uses the phrase “assume that everyone in G prefer …” and then goes on to explain his assumption. What this means is that the “Spread of Decisiveness” situation is a claim of the “there exists X” type scenario. Since Sen has used assumptions about certain situations, he has not attempted to “prove for all X” but instead merely found that sometimes, perhaps, maybe, under the right circumstances this Spread of Decisiveness can occur. It does not mean it always happens, it does not even mean it is likely to happen.
Now since the quest is to find a “perfect” voting system (where perfect is fulfilling all of Arrow’s conditions) then just showing that there exists any situations which fail the perfection criteria has already proven an imperfection exists. However it says nothing about whether real world voting is subject to this problem.
The Australian system is the “Instant Runoff” system which is described here:
https://en.wikipedia.org/wiki/Instant-runoff_voting
The well-known flaw of this system is the “Monotonicity criterion” and you can read more about that on Wikipedia, but the only situation this happens is where you are close to a three-way tie with one party somewhat in the lead, but not far enough ahead to win outright, and the preferences need to be set in just the right configuration. The question is entirely valid IMHO, whether this happens often in real elections, and whether voters can detect that it’s going to happen at the time of voting and further whether the voters can coordinate in secret to game the system and take advantage of non-Monotonicity. I happen to believe it’s basically a non-issue.
The Australian system handles extremely well the much more common configuration of voting where you get two major candidates who are close to each other in the primary round and then you get a trailing rabble of minor parties distributing preferences which often tip the balance between the majors (i.e. the Ralph Nader 2000 situation). That’s an important part of designing a system … to be able to work well under normal situations even if it works poorly under highly unusual situations.
Tel wrote: “Note that Sen uses the phrase “assume that everyone in G prefer …” and then goes on to explain his assumption. What this means is that the “Spread of Decisiveness” situation is a claim of the “there exists X” type scenario. Since Sen has used assumptions about certain situations, he has not attempted to “prove for all X” but instead merely found that sometimes, perhaps, maybe, under the right circumstances this Spread of Decisiveness can occur. It does not mean it always happens, it does not even mean it is likely to happen.”
Tel, I find this remarkable. It’s one thing to argue (as Craw did for example) that the term “dictator” could be overblown in certain cases, such as for example if we’re talking about 3 people picking pizza toppings.
Yet here, you are claiming that Kenneth Arrow, Amartya Sen, Steve Landsburg, me, and the hundreds (?) of academics contributing to the literature that Arrow’s proof spawned, have all mistaken a proof of “there exists” to mean “for all”?
Instead of arguing with some guy on his blog, why aren’t you writing up a “Note on a Popular Misconception Regarding Arrow’s Theorem” and send it to a prestigious journal? (You wouldn’t even need to waste time defining for the editor and referees what the symbols ∃ and ∀ mean, as you felt the need to do for me here.) That would be impressive to show your relatives next Thanksgiving, that you had unseated one of the most celebrated results in 20th century economics.
I’m being serious Tel, that is the implication of what you’re now claiming. Is this really how you walk around looking at the world?
Tel I have no reason to lie to you. You are misunderstanding that aspect of the proof. I’ll try walking through it.
So the claim here is an if/then. We get to assume group G is decisive over a particular x,y in the outcome set, and then we have to prove that this implies group G is decisive over any arbitrary elements a,b from the outcome set.
So Sen has us pick an arbitrary a,b that is different from the x,y that we already know (by assumption) G is decisive over. If we can show that G must be decisive over this arbitrary a,b as well, then we are done with the proof.
Now then, Sen is saying it could happen to be the case that everyone in G prefer a to x, that to y, and that to b. And further it could happen to be the case that all others (not in G) prefer a to x, and y to b (we do not impose any condition on the rest of their preferences). You’re right, at this point this is a very particular, possible case. Let’s see where Sen is taking this line of argument.
In this particular scenario with the preferences so arranged, we conclude that a is socially preferred to x, and y is socially preferred to b. This is because–with these assumed preferences–every single person (i.e. those in G and those outside G) prefer a to x, and prefer y to b. So far, so good.
Furthermore, because G by construction is decisive over {x,y}, then that alone is sufficient to conclude that x is socially preferred to y. Putting together what we’ve so far concluded about the social preferences (that is, a preferred to x, that to y, and that to b), we have, by transitivity of strict preference, the result that a is socially preferred to b. So far, so good (I hope).
Now here is where I think Sen had been losing you. By the Independence of Irrelevant Alternatives, the social ranking of a being preferred to b can *only* be a function of how individuals in society feel about a,b. Look again at what we assumed in the above. We said *nothing* about how the people outside of group G feel about a versus b. We came up with a particular set of circumstances in which group G preferred a to b, and in which members of non-G had some particular preferences that did not involve ranking a versus b. We concluded in that very particular scenario that society must prefer a to b. But now with the IIA condition, we are saying it must be the case that the social rule still says “a preferred to b” whenever we have the same rankings of a,b among each individual in society. Thus, it must be the case that whenever the people in group G think a is better than b, that that alone pins down the social rule as also saying is preferred to b.
But look at what we just said: Whenever the people in group G prefer a to b, so does the social rule, regardless of how the people in non-G feel about a,b. That is what it means for group G to be decisive over a,b.
And so, we’ve proven the if-then claim. We’ve shown that if group G is decisive over a particular x,y in the outcome set, that they must also be decisive over any other pair a,b chosen from the set.
What is tripping you up, Tel, is the IIA condition and how it is being used. Sen (like Arrow before him) finds a particular set of possible preferences under which we can conclude something, and then invokes IIA to make that conclusion more general than the original set of very specific assumptions.
I understand that the IIA cannot be guaranteed by any real voting system, the proof is demonstrating that it isn’t achievable.
My point is that Sen (and Arrow) do set up at least some specific circumstances. Yes, by the IIA those circumstances should be irrelevant, and it turns out those are not really as irrelevant as you had hoped because IIA turns out not to be achievable. This is sufficient to prove you cannot build a perfect voting system.
And we can easily see that’s not what happens in real elections. You don’t get a small group (especially not 1 person) able to just decide the outcome. It’s an absurd conclusion for the purpose of demonstrating that the axioms used to reach that conclusion are not achievable. Hence the “impossibility” theorem.
Hence the “dictator” is not a conventional dictator (every secret ballot system immediately removes the possibility of a conventional dictator). It’s a straw-man “dictator” for the purpose of showing the desirable axioms cannot be met. As a consequence we need to deal with those unavoidable situations where IIA does not hold, but those don’t happen as often as many people seem to think.
OK Tel, well I think I gave it the old college try. Arrow is showing that even in principle, just using logic alone, there is no way we can come up with a way of mapping from individual preferences into a “social” ordering, in a way that satisfies basic desirable properties. And then in the midst of that demonstration, you are raising practical objections.
It’s a bit like Einstein saying, “You can’t build a rocket ship that goes faster than light, even if you had a perfectly efficient engine,” and you saying, “That’s a silly statement. In the real world, rocket ships always suffer from friction.”
Or for another example, Mises says, “Even if a central planner had all the information about supplies and technology, he couldn’t rationally allocate resources,” and you say, “That’s a silly statement, in the real world nobody could possibly know where all the hammers are located.”
And so Arrow says, “Even in principle, you can’t get a sensible way to aggregate preferences. Suppose you had a rule, well I could pick a group G of citizens…” and you say, “That’s a silly statement, the people in non-G would start burning police cars.”
So I think I need to give up at this point. And by the same token, I guess you are throwing up your hands and saying, “I can’t get this guy Murphy to see my point.”
I’ll admit I’m not so great at explaining things, and also I’m not in a position to put long time into both collecting the research and putting together a good description.
If you find yourself with nothing better to do, then there’s some references at the bottom of the Wikipedia article talking about monotonicity (which is a common criticism of the Instant Runoff system).
https://en.wikipedia.org/wiki/Monotonicity_criterion
In particular Lepelley, Dominique; Chantreuil, Frédéric; Berg, Sven. “The likelihood of monotonicity paradoxes in run-off elections” is good, which you can download for free but I found I needed to use the Internet Archive to get an older page snapshot because the original site was playing up.
So what’s happening there is people are looking into statistical estimates of how often these known theoretical problems do actually come up in real world elections. Yeah, I know they are all fools because Arrow has already proven this all 100% impossible, but still we have elections, right? Means we still want to be able to gauge the quality of the real elections. Those guys come up with approx 3% to 4% chance based on their model of random voters (we know real voters are not random, but we need some kind of model for statistical purposes, this is not the only estimate out there, others have come up with larger values, depending on assumptions you make about voter behaviour).
I could also propose an alternative perspective. Let’s suppose some Hypothetical Austrian Free Market Economist (HAFME for short) was thinking about ways to collect large numbers of individual preferences and come up with an overall social outcome that seemed fair to all participants. Maybe HAFME would say, “Oh a marketplace gives a fair price based on the balance of individual desires to buy and sell. We can use that as a social decision making mechanism.”
So a marketplace and an election both have something in common, in as much as they are collective decision-making tools that process many small inputs into one final output (the election produces a winner, the marketplace produces a price, and a volume of trade).
Then perhaps someone might point out the theoretical possibility that one player can “corner the market” and thus drive prices in an unusual direction that fails to meet the desirable criteria of “fair” market prices. Maybe there’s even some mathematical outline of the type of conditions that allow this to happen.
HAFME says, “Oh but can that ever happen in practice? It would be extremely difficult for one participant to swing the whole market!”
https://www.npr.org/sections/money/2015/10/14/448718171/episode-657-the-tale-of-the-onion-king
Oh look at that, it really has happened in practice. There are documented real world cases where one individual has been able to “corner a market” and extract exceptional profits out of the situation. I thought that was a pretty interesting result, so do we abandon markets now that “fair market price” has been undermined?
Probably HAFME would argue that the exception proves there is a rule and market participants just have to keep their wits about them with knowledge that this sort of thing can happen now and then. Marketplaces work well enough most of the time, better than central planning, so we live with the imperfection.
One more point for Tel and others who think I might be being obtuse: I am obviously not saying, Tel, that Arrow et al. are such smart guys that no mere mortal can criticize. What I am saying is that it is very implausible that all of the economists who have looked at his proof missed something so elementary as, “Arrow proved the result for a very specific case, and yet claimed he had proved it in general.” It’s not even a long proof, it’s like 3 pages. It can’t possibly be that it rests on such a basic confusion as you are claiming here.
What does sen mean by the “that” in “a to x, that to y, and that to b” ? Does he just mean “a to x, a and x to y, and a, x, and y to b” or something else ?
“and assume that everyone in G prefer a to x, that to y, and that to b.” means a preferred to x, x preferred to y, and y preferred to b.
And then yes, by transitivity, what you wrote also would be implied.
and by
‘ But only the preferences of individuals in G have been specified. So G is decisive over {a,b}. Similarly for all other pairs. So G is indeed [globally] decisive.’
Does he mean that (for {a,b}) even if everyone outside of G had b}a then societal reference would still be a}b and this is what makes G decisive ?
Transformer wrote: Does he mean that (for {a,b}) even if everyone outside of G had b}a then societal reference would still be a}b and this is what makes G decisive ?
Well I think strictly speaking the definition of decisive is that it doesn’t matter what the non-G people think. So yes your condition is included, but that’s not enough. (I think that’s actually the definition of “almost decisive” as I spell out in my notes.) For G to be decisive over {a,b} we require that everyone in G preferring a to b implies that Society does too, end of story. I don’t need to know what non-G people think. So yeah, if they all happen to think b is preferred to a, then too bad for them, but that’s included in the general definition of decisive.
In fact when I said ‘even if everyone outside of G had b}a’ I was thinking that if that extreme case was true then that would be the same as saying ‘it doesn’t matter what the non-G people think’.
My understanding of the claim is that for all types of voting system there exists at least one situation where one of the desirable axioms of a quality voting system has been broken. Thus, there is no perfect voting system. I don’t believe the claim was ever made that all possible elections will violate those axioms every single time.
So the “general proof” was over the domain of systems of voting, but the specific example within a given system. If I was to attempt a proof “All diamonds have a flaw” then I only need to find one flaw in each particular diamond.
For all the well known voting systems (i.e. the ones being used) that axiom they fail to achieve is the “IIA” or independence from irrelevant alternatives. That is to say, there do exist some possible election outcomes where a “spoiler” candidate could manage to mess up the overall ranking. That does not prove that every single election has been spoiled. It’s easy to think of an example of an election where the winning candidate has a strong popular support and such a majority that regardless of which minor candidates you bring into the picture it makes no difference. So the “IIA” can be achieved in real elections at least some of the time, even if the system fails to guarantee it will be achieved 100% of the time.
What’s more, the voters do recognize where the key leverage points exist in the systems that they grew up with. Do you really think those people voting for Gary Johnson genuinely expected him to win? They fully understood they were throwing their votes away, but did so as a protest against the main candidates they were unhappy with.
“For all the well known voting systems (i.e. the ones being used) that axiom they fail to achieve is the “IIA” or independence from irrelevant alternatives….That does not prove that every single election has been spoiled.”
One could argue that every election in a first past the post system has been spoiled because it fails utterly to rank the actual preferences of the people. Many people vote for ‘least worst’ rather than prefered candidate since third party and minor party candidates will not get elected. We cannot know for certain that this is not simply because everyone is second guessing what everyone else will do, so they are inclined to do the same.
Whilst it is very likely that some elections would end up with the same winner, we cannot know this to be the case, so they are all to en extent spoiled.
Hi Tel,
I think the issue is not so narrow as voting and elections. This is about “public opinion” and to what extent we can actually aggregate and express societal preference. There are many possible “funnels” that take a bunch of individual preference rankings and crunch them into a single “social” output ranking.
The funnel does not have to be a traditional voting scheme, though many ideal voting schemes can adhere to simple mathematical functions.