Is Arrow’s Theorem interesting?

Suppose a group of people has to make a choice from a set S of options.  Each member of the group ranks the options in S from best to worst.  A “voting system” is a mechanism for aggregating these rankings into a single ranking, meant to represent the preferences of the group as a whole.

There are certain natural features you’d like a voting system to have.  For instance, you might want it to be “monotone” — if a voter who likes option A better than B switches those two in her ranking, that shouldn’t improve A’s overall position or worsen B’s.

Kenneth Arrow wrote down a modest list of axioms, including monotonicity, that seem like pretty non-negotiable features you’d want a voting system to have.  Then he proved that no voting system satisfies all the axioms when S consists of more than two options.

Why wouldn’t that be interesting?

Well, here are some axioms that are not on Arrow’s list:

  • Anonymity (the overall outcome is invariant under permutation of voters)
  • Neutrality (the overall outcome is invariant under permutation of options)

Surely you don’t really want to consider a voting system that doesn’t meet these requirements.  But if you add these two requirements, the resulting special case of Arrow’s theorem was proved more than 150 years earlier, by Condorcet!  Namely:  it is not hard to check that when |S| = 2, the only anonymous, neutral, Arrovian voting system is majority rule.  Add to that Arrow’s axiom of  “independence of irrelevant alternatives” and you get

(*) if a majority of the population ranks A above B, then A must finish above B in the final ranking.

But what Condorcet observed is the following discomfiting phenomenon:  suppose there are three options, and suppose that the rankings in the population are equally divided between A>B>C, C>A>B, and B>C>A.  Then a majority ranks A over B, a majority ranks B over C, and a majority ranks C over A.  This contradicts (*).

Given this, my question is:  why is Arrow’s theorem considered such a big deal in the theory of social choice?  Suppose it were false, and there were a non-anonymous or non-neutral voting mechanism that satisfied Arrow’s other axioms; would there be any serious argument that such a voting system should be adopted?

Thanks to Greg Kuperberg for some helpful explanation about this stuff on Google+.  Relevant reading:  Ben Webster says Arrow’s Theorem is a scam, but not for the reasons discussed in this post.

Tagged , , , ,

15 thoughts on “Is Arrow’s Theorem interesting?

  1. Maybe the greatest interest in Arrow’s theorem comes from its popularization of the axiom of independence of the irrelevant alternatives. And also for its effect of elevating voting models as a non-trivial topic in mathematics. It’s easy to believe that a good voting system could somehow calculate its way out of a Condorcet paradox, precisely by using alternatives to break a stalemate among choices as long as their is no exact symmetry. But Arrow obviously believed that independence of irrelevant alternatives was important. This belief is justified by the later Gibbard-Satterthwaite theorem, which implies that any relevant voting system that always gives an answer but doesn’t satisfy Arrow’s axioms, can be gamed. As I was saying on Google+, the optimistic view is that you can choose a good voting system for which gamed outcomes are artificial; but I suspect that any Arrow-type voting system can be gamed accidentally by earnest voters.

  2. Eric Hsu says:

    Thanks to all for these interesting comments above and linked.

    My blurry 2 cents: back when I last thought about Arrow’s Thm (years ago), I recall noticing that the “non-dictatorship” axiom wasn’t reasonable.

    Yes, in theory you don’t want someone’s preferences “overriding” anyone else’s. But, there were some voting systems disqualified because there was a “dictator” — even if no one knew who the dictator was! That seems to go against the spirit of why we would want that axiom.

  3. Hi Jordan! Perhaps another interesting thing that Arrow did for us was make explicit the assumption of universality (ie unrestricted domain). Don’t forget that we have a voting system which satisfies neutrality, anonymity, monotonicity and IIA: that’s approval voting, which restricts the possible inputs. As you know, to me this is a very interesting yet overlooked assumption.

  4. Willie Wong says:

    Just to note that Laura Balzano’s comment is precisely the same lament that Ben Webster gave, in the link that Jordan provided in the post.

  5. […] Condorcet anticipated Arrow, Approval voting as a counter-example to Arrow. […]

  6. djmarsay says:

    Arrow’s theorem only applies to deterministic methods. Thus putting all the ballots into a hat and drawing one out at random seems to satisfy most requirements, but may leave a bit too much to chance for most folk. I blog around this at http://djmarsay.wordpress.com/2011/10/06/is-there-a-reasonable-way-to-count-votes/ . Regards.

  7. Tom Leinster says:

    There are reasonable real-world situations where anonymity is violated, e.g. when the chair of a committee has a casting vote. There are also reasonable situations where neutrality is violated, e.g. when a constitutional reform requires (say) a two-thirds majority to be passed.

  8. Tom Leinster says:

    Here’s the question that I think truly matters for political applications.

    Most political elections are of the following form: there is a list of candidates, and k of them will be elected. (Often k = 1.) The k elected candidates are not put in order: they are simply elected, and the others are not. Is there any way of establishing a voting system so that the top k candidates can be determined fairly?

    By “any” I include the possibility that the voters will assign numerical scores to the candidates, or put a Lie algebra structure on the set of candidates, or really anything at all. I haven’t thought about how this could be made precise, but the point is to look way beyond Arrow’s scenario of total orders.

    “Fairly” is of course up for negotation. Maybe I really mean “without avoidable unfairness”, since, for instance, if there’s a tie between the first k+1 candidates then there’s no fair way to pick the top k.

    Has anything like this been done?

  9. Henry Cohn says:

    I know this isn’t really what you were asking, but there’s an amusing example of using nontrivial Arrow-style voting systems within mathematics. Arrow’s hypotheses imply that the election outcomes are determined by an ultrafilter on the set of voters (see, for example, http://www.math.wisc.edu/~robbin/ARROW.pdf), and on a finite set the only ultrafilters are the principal ultrafilters, i.e., the ones that correspond to dictatorships. However, for infinite sets of voters there are non-principal ultrafilters.

    This is important in model theory, for example in the theory of ultraproducts. Given a bunch of models of some axioms, their ultraproduct more or less smooshes them together and uses an ultrafilter to let them vote on which properties the ultraproduct should have. If you use a principal ultrafilter, the ultraproduct is completely boring, since it just recovers the factor corresponding to the dictator. However, for a non-principal ultrafilter it does really interesting things. For example, this leads to a slick proof of the compactness theorem (that if every finite subset of an infinite set of first-order axioms has a model, then the whole set does).

    So I doubt anyone would use a voting system like this for human votes, but we do it all the time for mathematical objects.

  10. But a restriction on inputs is a red herring as an explanation of why the theorem does not apply to approval voting. The reason that approval voting works is that it asks voters for one NEW piece of information: where they are willing to compromise. Arrow’s theorem does apply to any modification of approval voting in which voters cannot control the level of compromise, e.g., approve of exactly half of the choices. It applies for the simple reason that the voter’s ballot would be a deterministic function of his or her list of preferences. A function of a function of an input, is still a function of an input.

  11. Dave Marsay says:

    Good question. Most methods seek to identify the k top-scoring candidates, but is that ‘fair’? Could one have a sensible criterion that tends to most voters having supported one of those elected, and yet the overall spread being in some sense proportional?

  12. Dave Marsay says:

    Greg, Being picky, you seem to be assuming that there is no tactical voting. Shouldn’t we start by assuming that ballots are derived from actual preferences together with expectations about how others will vote. Thus under your variant of approval voting I would be tempted to waste some of my votes on no-hopers.

  13. That’s a nice interpretation– a new piece of information about where voters are willing to compromise. But I’m not sure we couldn’t gin something up where voters still choose the level of compromise and yet Arrow’s theorem applies. For example it seems to me if we extend approval voting to three levels– approve, neutral and disapprove– then we’re in trouble again, because on 3 candidates we could see full rankings. So here, voters would control a level of compromise, and yet still Arrow’s theorem would apply.

    I wasn’t saying that all voting systems which break universality will break Arrow. For example if you remove only one rank order from the possible inputs, Arrow’s theorem will still apply. But perhaps only allowing ballots which have a group tied for first and the rest tied for second is what allows approval voting to satisfy Arrow’s other criteria.

  14. Dave – Yes, any Arrovian imitation of approval voting would invite tactical or dishonest voting. That’s inevitable by the Gibbard-Satterthwaite theorem, which sharpens Arrow’s theorem precisely by saying that tactical voting will sometimes be in your interest in any Arrovian scheme. (Other than a dictatorship; that’s the one solution allowed by Arrow’s theorem.) That shows you the real reason that approval voting isn’t beset by these diseases: It explicitly recognizes tactical voting in an honest form. It not only asks you something about your preferences, it also asks you where you draw the line.

    But it still IS tactical voting. In approval voting, you could still kick yourself for compromising too much or too little.

  15. valuevar says:

    Wasn’t there some “optimistic” work by Amartya Sen a few decades ago (in the sense that a pretty fair-looking system *can* be obtained if you weaken your requirements a little)? In particular, he pointed out that most elections just needed a (fair) winner, not a ranking supposed to be a full representation of the preferences of an abstract collective.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: