Arrow's impossibility theorem(en.wikipedia.org) |
Arrow's impossibility theorem(en.wikipedia.org) |
1. Arrow's theorem concerns the situation where your election procedure needs to deliver (not just a single winner, but) a ranking of all the candidates. You might hope that relaxing this condition will help, but ...
2. There's a closely related theorem with the magnificent name of Gibbard-Satterthwaite, which says that if you have more than two candidates, any procedure that takes in ranked preferences and spits out a single winner must (1) give all the power to one voter, or (2) leave at least one candidate unable to win whatever the voters' preferences, or (3) be susceptible to tactical voting, meaning that in some situations a voter does best to rank the candidates in an order that doesn't match his or her actual preferences.
3. However, there is a loophole "at the other end". For instance, if the input consists not of rankings but of scores (e.g., from 0 to 100), then the conditions of Arrow and Gibbard-Satterthwaite don't apply. And, in fact:
4. If there are only three candidates then "range voting" or "score voting" (each voter scores every candidate and the candidate with best average or total score wins) has the desirable properties Gibbard & Satterthwaite forbid for ranking-based voting systems. (Almost: sometimes optimal voting strategy might require you to give two candidates the same score even though you have a definite preference between them.) But, alas,
5. With more than three candidates no score-based system has those properties either.
(An interesting simplification of range voting is "approval voting", where the only possible scores are 0 and 1.)
Well, any social welfare function that can pick a single winner can also be used to form a complete ordering, by repeating the process with the previous winner eliminated. So any social welfare function is a social ordering function.
http://ScoreVoting.net/ArrowThm.html http://ScoreVoting.net/GibbSat.html
Last year, I got some books signed by Arrow at his Palo Alto retirement home. It was pretty cool.
After finishing dinner, Sidney Morgenbesser decides to order dessert. The waitress tells him he has two choices: apple pie and blueberry pie. Sidney orders the apple pie. After a few minutes the waitress returns and says that they also have cherry pie at which point Morgenbesser says "In that case I'll have the blueberry pie."
http://www.amazon.com/Gaming-Vote-Elections-Arent-About/dp/0...
1. Jay Sethuraman, Teo Chung Piaw, and Rakesh V. Vohra. Integer Programming and Arrovian Social Welfare Functions. Mathematics of Operations Research Vol. 28, No. 2, May 2003, pp. 309–326.
Where it really gets interesting is when you reinterpret the result into other contexts. For example, suppose you're trying to reconcile several different decision-making systems -- e.g., different moral codes. Those are like different voters in Arrow's system, and hence there may be no "rational" way to reconcile them other than simply adopting one of them (which would be the "dictator" in the theorem's terms).
That is to say that the issues solved by Quadratic Voting and those presented in Arrow's theorem are orthogonal.
https://en.wikipedia.org/wiki/Sonnenschein%E2%80%93Mantel%E2...
SMD: rational individuals do not sum up to a rational aggregate.
But Arrow's theorem is first and foremost an exercise in logic. It is grossly oversimplified, and therefore should not be treated as realistic simulation of real-world voting systems. We should be very careful when drawing political conclusions from logical proofs.
There are several reasons why most contemporary political theorists don't give a damn about Arrow's theorem, despite its logical plausibility.
1) Arrow's theorem assumes everyone's preferences to be fixed points, and only cares about finding a curve that fits all of those points. But people's preferences are not fixed. People are always changing their minds, often in response to the shifting preferences of others. Many political theorists in the "deliberative democracy" camp (the dominant model since the early 90s) argue that the whole point of a democratic discussion is to get people to reconsider their pre-existing preferences and find some sort of middle ground.
2) It's not even clear why an ideal procedure would need to satisfy all of the preferences, or even most of them. If making everybody happy were as simple as designing an election procedure, we would have gotten rid of politics a long time ago! You don't even need 3 or more preferences to arrive at a conflict. Two people with one preference each, that directly contradict each other, would be enough to produce a situation where no procedure can satisfy them all. In other words, there's nothing new here. Time to move on.
3) Arrow's theorem is somewhat effective in explaining how the actual share of seats in a lawmaking body can end up being very different from the number of votes that each party received in a first-past-the-post voting system with 3 or more major parties, such as UK and Canada. But there are much simpler, more intuitive ways to explain that.
All in all, Arrow's theorem was a neat response to the political theory of the mid-20th century, when people assumed democracy to be simply a matter of efficient curve-fitting. But political theory has come a long way since then, partly in response to problems like Arrow's theorem. In the new academic milieu, Arrow's theorem isn't as relevant as it used to be.
On the other hand, I can sort of imagine how Arrow's theorem might find a new use in designing distributed computer systems. Since computers aren't as fickle as human politicians, the logical conclusions of Arrow's theorem might be more relevant there. It's good to see that the HN thread so far focuses more on technical details than on grand, mostly irrelevant political narratives.
The most trivial example is that he simply changed his mind—but obviously this has nothing to do with IIA.
Another reason is that he might be dining with someone (who is, perhaps, away from the table). Say that he knows his partner's preferences are C>B>A. Say his own preferences are B>A>C, but that he also has a preference for being able to sample two distinct choices. Initially, he believes that his partner will order B, so he orders A to maximize his range of desserts. Upon learning that the "irrelevant" choice C is available, he will have to order his top choice, B, himself.
The same scenario could play out with himself as the second diner, in the sense that he knows he will have two opportunities to visit this restaurant (and that their dessert choices will remain constant). If his preferences are C>B>A, and for whatever reason he decides to order his second-most-preferred dessert first and his most-preferred dessert on the next visit, then his choice is logical.
Perhaps he's of the opinion that a kitchen which prepares cherry pie cannot prepare an adequate apple pie.
The point is, alternatives are rarely "irrelevant". In fact, including the word "irrelevant" in IIA is begging the question: we are tasked with determining whether dominated alternatives (for example) really are irrelevant, and our answer might be "no".
For the second case, you've made "good apple pie" and "bad apple pie" different elements of the choice set. And again, IIA implies that if "good apple pie" ≿ "cherry pie" that continues to hold when "bad apple pie" is an option. (And as an important aside, all cherry pie is of equal quality in this hypothetical.) Also note that it has nothing to do with the relative likelihood of different choices being delivered, so choosing to order something because you think another order is likely to be messed up is perfectly consistent with the IIA.
Arrow's impossibility theorem is a mathematical result, and IIA is a property of a mathematical representation of preferences. They have practical implications, but certainly don't imply that people in real life make transparently consistent choices.
Delving further down this tangent... If that's what happened, he would be unlikely to have said "In that case, ...". That usually means "I am incorporating this new information, and it has changed my decision." More likely he would have said, "On second thought..." or "Actually..." or "Y'know..."
Not, of course, that this has much relevance outside of considering English pragmatics.
Say there's an election between a moderate democrat "blueberry pie" and a third party liberal "apple pie". As a liberal, Sidney would rather vote for the third party ("Sidney orders the apple pie"). However, if you introduce a republican candidate "cherry pie", Sidney will probably vote for the democrat (blueberry pie) instead of the third party candidate, because he'd be worried about his vote costing the more moderate candidate the election.
IIA means that you won't vote differently than your preferences—but people do that all the time. And sure, a voting system where that wasn't necessary would be nice, but losing that condition isn't as nonsensical as it seems at first.
(with the caveat that it has been a long time since I've thought about these results.)
Ask your dinner party "Do we prefer Apple or Blueberry?", and a majority might reasonably answer Apple. Ask them "Blueberry or Cherry?", and a slightly different majority might reasonably answer Blueberry. Ask them "Cherry or Apple?" and a different majority would answer Cherry. You would get this situation, for instance, with the following voters: 2x A > B > C 2x B > C > A 1x C > A > B A beats B by 3:2, B beats C by 4:1, and C beats A by 3:2.
This is a rock paper scissors situation -- or a "condorcet cycle".
Now suppose instead of simple Sidney there were actually these 5 people ordering dessert. Is it really that unreasonable that the group as a whole might pick blueberry once cherry is on the table even though a majority prefers apple to blueberry?
What is IIA? Can't find anything relevant on Google.
(Except that it might -- e.g., imagine that making cherry pie is incredibly difficult and most kitchens can't manage it, and that the special skills and equipment required are also useful for making really good blueberry pies. Then knowing that cherry pie is on offer could actually be evidence that the blueberry pie will be good. This is maybe just a tiny bit similar to, e.g., changing your vote from A to B when you learn that C is standing, because C is a terrible candidate but might win, and in scenarios where C is close to winning B is C's main rival.)
The impossibility is the impossibility of ensuring rational (transitive) outcomes amongst ranked preferences and adhering to a set of fair and democratic norms.
A rational transitive outcomes is one in which votes result in option A being preferred over option B and option B being preferred over option C, such that A is preferred over C (eg, A > B > C). Option A is known as the Condorcet winner.
But there may be cases where the vote yields no Condorcet winner (eg, A > B > C > A). This is illustrated by the following table:
Preferences Voter 1 Choc Vanil Strwb Voter 2 Vanil Strwb Choc Voter 3 Strwb Choc Vanil
Two voters prefer C over V and two prefer V over S, but two also prefer S over C.
To ensure transitivity, we can introduce voting rules, but it is impossible to introduce rules that do not violate the fair and democratic norms (referred to as the pre-specified criteria in the Wikipedia article: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives).
Realistically, that kind of situation doesn't break a voting system. We can say "we don't care about that case -- just pick a random winner then", but it's no longer deterministic.
Is there a stronger version of the theorem that says there's no sane procedure even ignoring those cases?
For a voting system (ranking of some candidates based on preferences of voters), it would be nice if:
- A single voter cannot determine the ranking (as a dictator) - For every possible set of voter preferences, there is an outcome (not random) - If everyone likes candidate A over candidate B, then in the final ranking candidate A should be ranked higher than candidate B - If one prefers A over B when comparing just A and B, then one should also prefer A over B when an additional option C is offered
Sounds like some reasonable properties for a voting system, right?
Well, the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above.
> Well, the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above in the general case.
Nobel Laureate Amartya Sen[0] has demonstrated that, while there is no system that satisfies all four characteristics in the general case, there are systems that either satisfy all four conditions either probabilistically or satisfy all four conditions subject to some very weak assumptions.
The example I've heard him use is of the 2000 election in Florida, with Bush, Gore, and Nader (let's ignore Buchanan for simplicity). While technically there are 3! = 6 possible ways to rank the candidates, in practice, the ranking (Nader, Bush, Gore) is much less likely than (Nader, Gore, Bush) or (Gore, Nader, Bush). If we introduce one minor assumption about the relative frequencies of the rankings, we can prove that instant-runoff voting[1] does always satisfy all four of Arrow's criteria[2].
To use an analogy from computer science, the halting problem is undecidable in the general case, but that doesn't prevent static analysis tools from spotting many infinite loops; it just means it can't spot all infinite loops with 100% accuracy.
[0] https://en.wikipedia.org/wiki/Amartya_Sen
[1] https://en.wikipedia.org/wiki/Instant-runoff_voting
[2] A different example: instead of making assumptions about the relative frequencies, we could make assumptions about the number of axes that candidates may have and the way they cluster around them. This realistically depicts both two-party and multiparty elections in most parts of the world, since political positions are not uniformly distributed along n dimensions.
There is no rank order voting system that has all those properties. (Rank order means, that the voter puts the candidates in the the order of preference: 1., 2., 3. etc.)
But there are other voting systems, e.g. a system where you give each candidate points between 1-100 or whatever, and you can give the same amount of points to several candidates if you want.
Regarding Arrow's theorem, most voting systems regarded as better than first-past-the-post tend to choose to violate the third criteria, commonly called "independence of irrelevant alternatives": adding another candidate shouldn't change the preference order of existing candidates.
That assumption seems fishy to me if in a real life application, in particular because we assume offering new choices can't fundamentally change the agent/voter's preferences isn't exactly true to life. I'll give a real life, but slightly historically oversimplified example:
Say I am a poor serf living in pre-revolution Russia about a century ago. I am usually offered the following two choices:
A. serve the bourgeois royal family and live off of their scraps
B. die like a dog
Then, one day, Lenin (or similar revolutionary) comes along and offers me:
C. fight for glorious USSR communism
In real life, I would think the offered choice of C would absolutely change my preferences for A and B.
Granted this doesn't invalidate the Arrow paradox in any way, I'm just saying the paradox isn't true to life because one of its core tenants doesn't quite hold.
It's actually not that "simple", but it's overall less technical.
More accurately, it is a theorem about the properties of all possible voting systems where the input is voters preference rankings and the output is also a preference ranking.
In short, the theorem states that no rank-order voting system can be
designed that always satisfies these three "fairness" criteria:
1. If every voter prefers alternative X over alternative Y, then the
group prefers X over Y.
2. If every voter's preference between X and Y remains unchanged, then
the group's preference between X and Y will also remain unchanged
(even if voters' preferences between other pairs like X and Z, Y and
Z, or Z and W change).
3. There is no "dictator": no single voter possesses the power to
always determine the group's preference.
All of these requirements listed above seem like fairly simple requirements for a voting system to have; if there's unanimous agreement about the ordering of two of the choices, then the voting system should order them that way. If a voter changes preferences about one choice C (maybe changing between them being ranked above or below D, or above or below one of A or B), without changing their ordering between choices A and B, that shouldn't affect the outcome of the A/B ordering that the voting system gives you. And finally, there is not dictator; no single voter is able to always determine the group ordering unilaterally.
The first requirement seems pretty obvious; if everyone is unanimous that we should pick one option over another, then the group should pick that option.
The second is a little trickier; but it basically states that there shouldn't be able to be "spoiler"; someone whose ordering in people's preferences affects the ordering of to other choices. Think about, say, the 2000 election, with Bush and Gore and a couple of third party candidates; now, that used just single choices per voter rather than a ranking, but imagine it used a ranking. So let's say Bush and Gore are fairly close, but 51% of voters prefer Gore over Bush. Their preferences for other candidates should not affect the fact that Gore wins over Bush. If I rank candidates Nader > Gore > Bush, that should not change the Gore/Bush result compared to if I ranked the candidates Gore > Bush > Nader.
And the last is pretty trivially desirable; generally a democracy wants to democratically make a choice, in which everyone's vote has the same weight in affecting the final outcome.
The fact that these conditions are impossible to achieve together is fairly profound, and means that almost any voting system will have serious flaws under certain circumstances.
(2) It is abundantly clear why a "procedure" should satisfy all of the requirements of the related theorems: they are trivial, intuitive, and absolutely spot-on. There is a reason why these results are surprising, and not just some arbitrary theorems concerning uninteresting axioms.
(3) Arrow's theorem has nothing to do with explaining anything. It is an impossibility result in mathematics.
The rest of your post seems just dismissive of the problem, rather than directly critical of it. ("All in all.." -- as if these results were just passing fads and now we've got our sense back??)
There are two major factions within the deliberative democracy camp. One is indeed interested in consensus building and eventually-consistent rationality. This is the "Rawlsian" faction led by Gutmann and Thompson. The other faction, however, focuses more on actual practices of negotiation through which pre-existing preferences and power structures are transformed. This is the "critical theory" faction led by John Dryzek and the late Iris Marion Young. Personally, I think the latter remains closer to the original aims of deliberative democracy and presents a better contrast to the older models it was intended to transplant. The Rawlsians just took the opportunity to cram their own agenda into democratic theory, as they always do with everything they touch.
Your claims (2) and (3) seem to contradict each other. If it is so abundantly clear that a procedure that satisfies Arrow's conditions is desirable, why do you say that Arrow's theorem is just a mathematical result that doesn't explain anything IRL?
Arrow's theorem is surprising and troubling only if you believe in some sort of sacred relationship between the trinity of democracy, voting, and satisfaction of all pre-existing preference. To the contrary, I find it both trivial and intuitive that it is impossible to satisfy all of the preferences of all human beings, and I would be very surprised and troubled if someone claimed to be able to do so.
That's just strategic voting, not an actual change in your preferences. How you go about voting strategically depends on the voting system in use. In your hypothetical scenario you make the unstated assumption that the voting system in use would not allow for you to express a preference for A over B without hurting B's ability to beat C. The inability of that voting system to fully capture your preferences is forcing you to vote misleadingly based on your knowledge of how others will probably vote.
This criteria is called "independence of irrelevant alternatives". A common criticism of Arrow's theorems usefulness is that it is a bit of a stretch to call paper an "irrelevant alternative" when rock-paper-scissors forms a cycle of preferences like that.
If politics is one-dimensional ("single-peaked preferences" in the article), then you never get this situation.
It's also important to note that a much more reasonable criteria exists called "local independence of irrelevant alternatives". This is the idea that total losers joining the race don't affect the result, however someone who is in the top rock-paper-scissors cycle (the "Smith Set") can still affect the result even if they don't win themselves. This is far more reasonable, as it's fairly arbitrary which of the candidates in that top cycle should win.
When there is no top cycle, the Smith Set is a single person (the "Condorcet Winner"). When there is a Smith Set, most reasonable voting systems will pick their winner somewhat arbitrarily as a member of the Smith Set, since everyone in the Smith Set beats everyone outside the Smith Set.
Which particular problems occur, and the frequency with which they occur, depend on the particular voting system.
Plurality and majority/runoff (which are ranked preference voting systems with a vary narrow constraint on the preferences that are expressed on the input ballots, which is pretty much the same constraint as on the preferences reflected in the output of any single-winner voting system) hits problems fairly frequently in practice, but most of the common voting systems that most people think of as ranked-preference systems (IRV, etc.) still hit them in practice as well, though not generally as frequently and in ways which create as clear incentives to tactical voting.
I don't know what you mean by the "trinity" in which "satisfaction of all pre-existing preference" is a part.. That's obviously not relevant; we aren't interested in a system that satisfies preferences. What we are interested in is a system that (1) isn't a dictatorship, (2) is fair [i.e., everyone counts equally], (3) allows us to decide any kind of potential matter _as a group_.
If you look at the conditions this way it should be glaringly obvious what this has to do with the (possibility) of democracy..
The conditions, of course, sound obvious and intuitive. Of course we don't want a dictatorship, and of course we want everyone to count as equally as possible. But it takes a very specific interpretation of your third condition to bootstrap the rest of Arrow's theorem. You have to interpret it in a way that emphasizes translating fixed individual preferences into group preferences as straightforwardly as possible. If you care about that, then yes, you should be worried about Arrow's theorem. Otherwise, Arrow's theorem is just a cool thought experiment that helps explain why said interpretation is wrong.
Deliberative democracy currently happens to be the most popular model of democracy among political theorists, and they don't care about Arrow's theorem because whatever preferences people have before they enter the democratic "procedure" isn't worth jack shit to them. As a result, Arrow's theorem is much less relevant to the possibility and fate of democracy as currently understood than it was 60 years ago.
Non-forced rankings allow you to indicate ties, and quantitative indications of strength of preference are unlikely to have consistent meanings among voters, so treating them has having the same meaning (as, presumably, any voting system using them must) is inherently problematic.
You can arbitrarily change the 50/50 probability to e.g. 40/60 or what have you, to make it equally preferable to any guaranteed item.
But the question is whether a "score" given by a voter on a ballot indicates anything psychologically interesting, and, more importantly, whether it indicates anything relevant to the "judicious" selection of a candidate. It seems to me that, empirically, the only meaning we can _seriously_ assign to a "score" on a ballot is a relative-scoring-as-indicative-of-relative-preference. I don't know how "10 to A, 20 to B" could indicate anything beyond the simple fact that the voter prefers B to A. And surely my "10 to A, 20 to B" needn't have the same meaning as your "10 to A, 20 to B" -- I think all we can really say is that we both prefer B to A. What else?
Now, you might want to try to interpret these "scores" as something like a hypothetical question put to the voter about how much they might pay to have this-or-that person elected; but if you know anything about self-reports of this kind about hypothetical scenarios, you know that people are horribly inaccurate (either intentionally or not), and that the setup is contrived. Serious measures of preferences involve actual stakes, markets, etc. Good luck with that here.
This isn't the case (or even uniquely formalizable) in base (non-e.u.) utility theory which requires choice-order preservation under arbitrary monotonic transformations of the scoring function. Expectation ordering is not necessarily preserved under such transformations.
E.U. is a common paradigm because it is a useful approximation and allows numerical calculations but it is not all (or even, the core) of utility theory except in very limited circumstances (e.g. purely monetary payoffs and linear utility of money).
You're right that it was a smaller group, of course, but it wasn't an empty one.
Jello Biafra's endorsement of Nader plus Gore's attack on Twisted Sister for the Parents Music Resource Council means N-B-G was actually the order of preference for anyone where "the right to rock out" was their single voting issue.
(I was young, ok?)
Scores are actual utilities with added loss, from:
- ignorance
- normalization
- rounding error
- tactical voting
So those scores HAVE meaning. That meaning is muddied by the aforementioned loss, but it is lunacy to say it only "could indicate anything beyond the simple fact that the voter prefers B to A".
However, this plays rather fast and loose with the principles behind Arrow's theorem. First, you're violating the nondictatorial condition (you are the only person voting on your own choice), so it's kind of silly to apply the theorem here in the first place.
Secondly, you're saying that, as soon as Communism becomes an option (but only then), you'd rather die than serve the royal family.
I can see how this might be the case, but if so, you're fundamentally changing the meaning of choice B. It's no longer just the default state ("die of starvation"), but rather dying for a cause (Communism). It's not that the introduction of choice C suddenly means that you're now choosing B over A; it's that it also introduces choice D ("die as a martyr in the name of Communism", as contrasted with "die for no particular cause"). Your ranking is now C > D > A > B.
You have to understand that Arrow's theorem came about as the result of an effort to understand the way that firms make decisions, and the ways that voting structures of boards can influence corporations to make non-optimal decisions for the corporation. Your situation doesn't really apply to the definition of independence of irrelevant alternatives as implied by the context in which Arrow's theorem is applied (or the formal proof thereof).
Well, maybe. Supposing there's some information contained in option C, or the mere availability of option C, that reveals to you the futility of option A.
In other words, your preferences aren't necessarily transitive because the availability or unavailability of particular options are themselves a little information payload that could influence the decision.
This isn't an assumption. Organisms have specifically evolved to maximize the expected number of copies of their genes they make. Or rather, _genes_ have specifically survived in proportion to their expected impact on the number of copies of themselves they make, and therefore we are to a very close approximation utility maximizers.
> ..linear utility of money
Utility is approximately log(money).
A caveat here is that certain decisions themselves are costly (particularly in terms of the most precious resource: time) and hence we can sometimes make clearly "irrational" choices because the expected utility of spending more time choosing was lower than the expected utility of making the more optimal choice. This leads to apparent paradoxes like the Allais Paradox.
Here's some background on utility theory. http://scorevoting.net/UtilFoundns.html