Hacker News new | past | comments | ask | show | jobs | submit login
Arrow's impossibility theorem (wikipedia.org)
97 points by Gray0Ed on June 3, 2015 | hide | past | favorite | 84 comments

A few remarks:

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

For #2, what if you relax the "no tactical voting" requirement to say that voters cannot predict how to vote tactically unless they have an impractically large quantity of information about other voters?

This is the insight. Proving "tactical voting is always theoretically possible" sounds bad, until you realize that there exist systems where tactical voting requires not only nearly perfect information about every other voters exact preferences ahead of time, but also solving cryptographically hard problems

I think I'd be satisfied with that. Or ideally, "given attainable information, an honest vote is the most likely to make the output most agree with me."

I don't follow this "loophole" you mention. Afaik there are proofs of Gibbard-Satterthwaite that allow indifference in the rankings, and this "distinction" between rankings and scores is methodologically dubious: Arrow himself was sensitive about the meaningfulness of quantitative reports of preference, and I don't see any reason to believe that a "score" issued by a voter is any better or more meaningful than a simple ranking (including rankings of indifference). This approach has always struck me as an unmotivated anti-empirical gimmick to get around this-or-that condition in the theorem(s).

Scoring lets you indicate ties, and strong preferences.

> Scoring lets you indicate ties, and strong preferences.

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.

indifferent rankings already indicate ties, and what does a 'strong preference' value amount to here? I'd suggest that it only makes sense if you try to understand the "score" as being a relative ranking of N imaginary alternative candidates in addition to the actual candidates.. So a 1 to A and 99 to B only indicates 'strength' in that it suggests if there were 96 other candidates you'd put them above A and below B.. but now we are back to orderings over candidates. At any rate, you ought to be suspicious of quantitative assignments of preference..

No. Utility is not about ordering. E.g. suppose you prefer X over Y over Z, and can have a guarantee of Y, or a 50/50 probability of X or Z. If your preference for Y is greater than the average of X and Z, then you would want to take Y. If Y is less than that average, then you want the lottery.

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.

Yes, we know that preference involves more than ordering and that "strengths" are relevant to decision making. We know this because it explains an obvious empirical matter, that there are scenarios like the one you cite where we prefer X over Y, but end up choosing Y over X. Not a puzzle; not a paradox; how it is. And of course the way we tease out the "strength" of your preference involves, e.g., looking at how your choice varies between counterfactual scenarios involving different probabilities.

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.

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

Scores are actual utilities with added loss, from:

  - ignorance    
  - normalization    
  - rounding error    
  - tactical voting
The way you measure the combined impact of that loss is with Bayesian regret. http://ScoreVoting.net/BayRegsFig.html

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

You are implicitly presuming an expected utility framework (more generally, that people rank outcome distributions based solely on their long run central tendencies).

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 are implicitly presuming an expected utility framework

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

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

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.

Some useful links.

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.

An amusing anecdote which illustrates why independence of irrelevant alternatives is desirable:

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

I hate to be that guy but there are plenty of reasons why this might be logical behavior. (I say "that guy" because I'm not prepared to argue for their relevance to voting.)

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

No, you're combining a few different things that aren't related to IIA. For your first dining example, you've changed the relevant set of options to (A,A), (A,B), (A,C), (B,A), etc... where the first element is the diner's desert and the second is the partner's desert. IIA means that if (B,A) ≿ (A,B) in the original choice set, then it continues to hold when we add (Z,Z) as an option.

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.

"The most trivial example is that he simply changed his mind—but obviously this has nothing to do with IIA."

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.

When you say it like that, IIA does sound pretty obvious. But if you change the terms a little bit, you can see why the IIA doesn't match up with how people actually vote:

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.

Arrow's impossibility theorem, and the IIA criterion, is about preferences not about uncertain actions. In particular, IIA doesn't mean that you'll vote differently than your preferences in some sort of election, it means that your preferences themselves don't change when you introduce other irrelevant options. In your example, it wouldn't be about how Sidney would vote in an election given the different menu of candidates, it's about who Sidney would prefer win the election.

(with the caveat that it has been a long time since I've thought about these results.)

In the context of voting, all IIA represents is the requirement that we only take into account the information on the ballots..

I don't see this. Could you elaborate?

I recall that Bordes and Tideman were a good source on this issue; I believe the (relevant) paper is "Independence of Irrelevant Alternatives in the Theory of Voting." -- The upshot is that the condition known as IIA (I think it is sometimes known as Sen's condition-alpha, and the condition that many people harp on, including Michael Dummett) is in fact a stronger condition than is needed for the result; roughly, that instead of needed a condition about consistency among selections over possible ballots (like: if y were selected in ballot [xyz], y should be selected among yz on ballot [yz]..) we simply need a requirement that the selection only involves information on the ballots (and that the relative rankings of candidates not on the ballot are irrelevant to the selection).

Ah, I think your phrasing was confusing. "IIA" is considering an attribute of the ballots, but including IIA is stronger than necessary for the theorem to hold - it can be replaced with the much weaker "nothing but the ballots".

While amusing, the anecdote is off in a very important way: it is not a single person ordering dessert, but an entire party of people who represent different conflicting majorities. In such a real situation you can get whatever "absurd" result you want by just asking questions in the right order.

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?

That explains why something like IIA is a reasonable intuition about how individual preferences should behave, not why IIA is a reasonable criterion for how systems of aggregating preferences should behave. (Unless you introduce the premise that "a social preference aggregation system should make society operate in a way that would match intuitions of a single actor".)

Morgenbesser is always great, but a defense against criticisms of IIA is much simpler to mount in the context of voting: it simply amounts to the requirement that our voting procedure only takes into account information from the ballots.

This is a comment directed to the various replies...

What is IIA? Can't find anything relevant on Google.

It's pretty early in the "story" page.

I don't see why that anecdote makes it desirable -- can you explain?

The anecdote illustrates why it's desirable: Morgenbesser's change of mind doesn't make any sense, and the reason why it doesn't make any sense is that it violates IIA: whether they have cherry pie shouldn't make any difference to his preference between apple pie and blueberry pie.

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

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

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.

in that case.. i thought about it and, if i can still change my order, i think i want the blueberry

Because if that anecdote is true, Morgenbesser is clearly insane. Drill down on your intuition about why he's insane and you arrive at "he's violating IIA".

The criteria considered by the theorem concern how democratic a voting system is. I'd argue that 'democraticness' is secondary to two other criteria: accountability and government-effectiveness. Accountability means that bad rulers can get voted out of office when enough people are displeased. Government-effectiveness means that the resulting government can practice good governance. When considering these criteria, I think plurality/first-past-the-post voting systems are superior. Unpopular leaders are voted out and elections usually result in single-party majorities that can govern effectively.

It seems to me that concern over the dictatorship criterion is ill founded. Its failure merely implies that for any given set of alternatives there will always be one voter whose preferences, whatever they may be, determine the outcome. Now if everyone's preferences were known and constant then in theory you could find that person and they would be able to decide the outcome. In practice preferences don't stay constant and no-one knows them all, so as long as you have secret ballots the dictatorship criterion doesn't matter. So you can have the other two criteria which are far more important.

Can I get a simple wikipedia explanation? That was the most challenging wikipedia article I've ever read.

This is how I was taught it (or understood I was taught it) - at law school, so it might have been dumbed down.

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

Yeah, but that takes the punch out of the theorem. It's saying, "hey, sometimes you have really screwy preferences, too bad."

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?

No, of course not. It's really easy to come up with a system that always comes up with "good" results if you rule out "screwy" voter preferences, with a sufficiently restrictive value of "screwy".

"Screwy" in this context means the sort of intransitive situations referred to in the parent of my last comment.

That is all the punch he theorem has. Arrows theorem shows that aggregate preferences have ties even when individuals don't, and strategic voting can tip the results in those cases.

You should update the wikipedia page with this explanation.

In short:

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.

This is correct, with one addition:

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

> (Nader, Bush, Gore) is much less likely

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?)

In college I was part of a club that had an elaborate election procedure for officers. I'm pretty sure it violates Arrow's Theorem, but it was also nonterminating!

That sounds very interesting! How did your nonterminating election procedure work?

Oh, god. I don't remember the details, but it involved crossing off the bottom third of candidates every round until there was only one left. But somehow, this didn't always get rid of everyone, and you could get stuck in a state where there was no bottom third.

Did work? It is still working to this day...

> the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above.

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.

Also see http://en.wikipedia.org/wiki/Category:Voting_system_criteria for other potentially desirable criteria for voting systems.

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.

>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

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.

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

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

>Secondly, you're saying that, as soon as Communism becomes an option (but only then), you'd rather die than serve the royal family.

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.

Are the counterexamples offered by the theorem pathological, in the sense that they are unlikely to occur in practice but are theoretically possible? Or would they arise in practice frequently using standard rank voting systems?

As long as politics is not one-dimensional, there are completely reasonable cases where you get a rock-paper-scissors situation between 3 top candidates if voters select whomever is closest to them. That in turn violates the criteria that says the election result can't change if you add a non-winning candiate (rock beats scissors, but when paper enters the race now scissors is computed the winner).

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.

> Are the counterexamples offered by the theorem pathological, in the sense that they are unlikely to occur in practice but are theoretically possible? Or would they arise in practice frequently using standard rank voting systems?

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.

The "worry" is not that this-or-that fantastical scenario might play out. It is that, as it turns out, the very mechanisms we use to measure group preferences simply cannot satisfy a list of very basic requirements. For example, the reason we do not use random drawings to determine who gets elected president is that we want the choice to "reflect" our preferences on the whole: but the result shows that this kind of "reflection" is probably not possible, and is always distorted in some fashion by the very procedures we adopt to make these decisions.

In "standard" FPTP-like systems we frequently see real-world cases that encourage tactical voting. E.g. look at the French Presidential election where Le Pen went through to the final round because there were four leftist candidates that split the leftist vote.

Try the Stanford Encyclopedia of Philosophy's take on it: http://plato.stanford.edu/entries/arrows-theorem/

It's actually not that "simple", but it's overall less technical.

It's technical which is good but much better written than Wikipedia.

It's not Wikipedia, but http://tech.mit.edu/V123/N8/8voting.8n.html may be more intelligible (especially regarding the particular desireable conditions that Arrow's theorem says are mutually incompatible). There's also http://dev.whydomath.org/node/voting/Arrow's_Impossibility_T..., which includes some intuition-building exercises.

Here's the version of the story with respect to voting: Democracy requires voting. Voting involves an objective measurement of group preference with respect to choices. Arrow's theorem and related theorems (see Gibbard-Satterthwaite theorem) show that there is no way to objectively measure group preferences.

It is a theorem about the properties of all possible voting systems with preference rankings. The basic idea is there are a few desirable properties for any such voting system, but that it is mathematically impossible for any voting system to satisfy all of them.

> It is a theorem about the properties of all possible voting systems with preference rankings.

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.

There is a simple explanation in the introduction:

  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.
A "rank-order voting system" is one in which all voters order the possible choices, from most preferred to least preferred. The idea is that based on everyone's votes, and some set of rules on how to evaluate those votes, you can come up with a decision for the entire group that respects those preferences, in some way that is considered fair.

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.

A great popular read that covers this and similar topics is William Poundstone's Gaming the Vote.


I wrote about a linear programming proof of Arrow's Impossibility Theorem due to Rakesh Vohra and his collaborators in a series of posts, starting with http://deniallogic.blogspot.com/2015/04/transitivity.html and ending with a proof of Arrow's theorem in http://deniallogic.blogspot.com/2015/05/arrows-theorem.html. The point was to fill in enough details that, for me, were missing from the paper [1].

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.

Maybe I don't quite appreciate the significance. The Informal Proof section seems to boil down to: If the vote is tied and there is one vote left, then that last vote determines the outcome. The existence of a swing vote in this circumstance doesn't seem very surprising.

"Part One" of the informal proof is trivial, for the reason you've described. But "Part Two" is not: It shows that if the "pivotal voter" from Part One votes B>C, then B will beat C in the election, even if everyone else votes C>B.

I never published them, but I proved various extensions to the theorem back in the day. Giving the ordinal voters more options doesn't help in the slightest. And if you have some ordinal and some cardinal voters, the cardinal voters taken together wind up as a dictator.

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

How does Quadratic Voting fare in meeting these criteria?


I'm pretty sure that Quadratic Voting is a way to assign prices to votes, whereas this theorem is about the features of a system in which the results are determined by vote. So the results of quadratic voting will meet this criteria because after the votes are bought they can be thought of as emanating from discrete voters who align their preferences with those of the buyer.

That is to say that the issues solved by Quadratic Voting and those presented in Arrow's theorem are orthogonal.

Few theorems in economics, or political science in this case, are as disappointing as this one. Another one is Sonnenschein-Mantel-Debreu.


SMD: rational individuals do not sum up to a rational aggregate.

http://en.wikipedia.org/wiki/Voting_system has a nice comparison chart half way down.

Some people interpret Arrow's theorem to mean that democracy is a futile exercise. For example, the anarchist Robert Paul Wolff uses an argument similar to Arrow's theorem to show that all democracies must be tyrannical to at least some of its members.

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.

(1) Not quite. The "deliberative democracy" camp is not interested in the measurement of group preference, and are instead interested in consensus building, political "rationality" (in hopefully some eventually-stabilizing sense), and so on. That is not a response to Arrow and his associates, it is just a different topic.

(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??)

If we read early works (from the late 80s) in what is now called "deliberative democracy", we can see that it began as a response to certain models of democracy that emphasize preferences and procedures -- up to and including the participatory models of the 70s and early 80s. Although deliberative democracy is not a direct response to Arrow's impossibility theorem in particular, it was intended to sidestep its troubling implications as well as other problems with the older models.

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.

I think you are a bit confused. What would Arrow's theorem explain? There is no empirical phenomena that we are puzzled about that Arrow's theorem solves (unless you are wondering: Why is it so hard to come up with a voting system that doesn't have the potential for goof-ball results? - Answer, because it is impossible..)

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

If we're not interested in a system that satisfies preferences, then Arrow's impossibility theorem is irrelevant.

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.

Do you know an exposition for mathematicians? Preferably in front of a paywall. What is the mathematical content?

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact