Arrows Theorem

[From VotingPatterns]

Kenneth Arrow, NobelPrize winner in economics, defined some basic characteristics that a democratic system should seek to provide, and then showed why they were mutually exclusive. These characteristics were:

Universality The voting method should provide a complete ranking of all alternatives from any set of individual preference ballots.
Monotonicity If one set of preference ballots would lead to an an overall ranking of alternative X above alternative Y and if some preference ballots are changed in such a way that the only alternative that has a higher ranking on any preference ballots is X, then the method should still rank X above Y.
Independence of irrelevant alternatives If one set of preference ballots would lead to an an overall ranking of alternative X above alternative Y and if some preference ballots are changed without changing the relative rank of X and Y, then the method should still rank X above Y.
Citizen Sovereignty Every possible ranking of alternatives can be achieved from some set of individual preference ballots.
Non-dictatorship There should not be one specific voter whose preference ballot is always adopted.

An example: You have a group of 100 voters. There are two candidates, A and B. The votes split like this:

  A: 55 votes.
  B: 45 votes.

If we introduce candidate C into the mix, we should now have two possibilities: A should win, or C should win. B should not be a contender. However, C is to A as Ralph Nader was to Al Gore, and the new voting pattern looks like this:

  A: 44 votes.
  B: 45 votes.
  C: 11 votes.

A simple "first-past-the-post" system, where the winner is the person with the most votes, has violated the criterion of independence.

[sources: http://condorcet.org/rp/arrow.shtml, http://www.anjccf.net/NJCoHE_Testimony/2003/April_2003.htm]

Not all of the desirable characteristics are equal. For example, universality is only important when there's a prize for second place. By the same token, monotonicity isn't important as long as the first place result isn't affected.

ArrowsTheorem is flawed. PreferentialVoting can achieve the desired characteristics (with the weakened definition). In a preferential system, the people who chose C would have given their second preference to A. In the second round of counting, the votes for C would have been allocated to A, and the result would have been A: 55 votes, B: 45 votes.

No preferential system of voting achieves universality or monotonicity (after the first place). However, the data is there; every voter has expressed his or her complete set of preferences over the candidates. If a universal ranking system was desired, each preference could be given a weighting and universality would be achieved. Monotonicity probably wouldn't be (in that removing some candidates from the mix may cause some minor reshuffling of places), but it would be pretty close.

-- RobertWatkins

If by "preferential voting" you mean single-transferable-vote, I wonder whether your opinion that it's good enough survives the following example.

ABCDE 21% ABCD 21% ABC 21% BC 21% BACDE 21% BACD 21% BAC 21% BC 21% CABDE 20% CABD 20% CAB 20% CB 20% DBACE 20% DBAC 20% BAC 20% BC 20% ECDAB 18% CDAB 18% CAB 18% CB 18% ... B wins. E eliminated D eliminated A eliminated

ABCDE 21% ABCD 21% ABD 21% AD 21% BACDE 21% BACD 21% BAD 21% AD 21% CABDE 20% CABD 20% ABD 20% AD 20% DBACE 20% DBAC 20% DBA 20% DA 20% EDCAB 18% DCAB 18% DAB 18% DA 18% ... A wins. E eliminated C eliminated B eliminated

The only difference in the preferences is that some people decided they prefer D to C instead of vice versa. Note that they didn't change their first preferences, that all other comparisons remained the same for those people, and that neither D nor C eventually won or even came second. That seems like a pretty severe breach of independence to me.

-- GarethMcCaughan

It still survives, Gareth. The criterion of independence states that if the relative rank of X and Y remain unchanged, then X should still be on top of Y. It doesn't say that relative ranks have to be linear. In the case of preferential voting, the relative relationships can be very heavily weighted, and moving them around has effects, because not all of the alternatives are irrelevant (nor is there a requirement for them to be so).

One of us is confused. The first set of ballots results in B being preferred to A. The second results in A being preferred to B. The relative rankings of A and B are the same (on every ballot) in the two sets. This is exactly what the criterion of independence rules out. No? I have no idea what you mean by "it doesn't say that relative ranks have to be linear".

-- GarethMcCaughan

The single-transferable-vote resolution rule, as you demonstrate, fails these criteria. Its flaw is that it eliminates whichever candidate gathers the least number of top votes at each step. In a simpler example,

 A B C D  1/3
 C B D A  1/3
 D B A C  1/3

In this sequence, B is the first eliminated under single-transferable-vote because he garnered the fewest top votes (none). Also, notice that there is no way for any system to deterministically satisfy universality from these votes, without introducing systemic bias.

In a democratic system, using voting as a means of choice, we do not need a complete ranking of all alternatives -- just sufficient ranking to select which alternatives to accept and which to decline. We don't need an absolute ranking of all candidates in a winner-take-all (N options, choose 1) to determine who won. Nor do you need to rank all candidates to select which two will represent your riding.

Possible fix, implementing instant-runoff-voting. Take pairwise comparisons of all options. Accept those options preferred in the most number of pairings, else remove from consideration those options preferred in the fewest number of pairings; repeat until you accept just enough, or are about to reject too many. Some other means of resolution is required to handle these last ("ties"). I believe most entities which use voting as a decision mechanism have ways to deal with these already in place. At least a few states in the US name specific random or semi-random means for this (eg one hand of seven-card stud poker).

I have Perl code implementing this. It can be easily extended to handle election rankings with ties, arbitrary don't-cares, and anyone-but-him indications. It can even be tasked with the randomized tie-breaking, since a tie only happens when there is no group preference for one over another, so it should not matter which is chosen.

-- JosephBeckenbach

I am not sure that Arrow's theorem precludes us from finding a good voting system. For example, the first-past-the-post system leads to what seems an unacceptable paradox, that the addition of a candidate can split the vote and produce a bad result when one candidate is clearly ahead. GarethMcCaughan's example does not seem to be a big problem because the voters in the example seem to be almost unable to decide among the various alternatives. I don't really care what decision a voting system makes in this case, because the fact of the matter is that the voters don't have a strong preference in any direction (another example of this: recent US election recount anguish. If the vote is so close, I don't really care if the recounts of a few thousand votes were done correctly or not. The candidates did about the same, we may as well flip a coin)

Is there a voting system which can be proved to not violate any of the Arrow properties except when the preferences are sufficiently "indecisive"?

-- BayleShanks

Sounds like DeCondorcet

If a voting system is too complex it will be hard for the electors (that's the people casting the ballots) to understand what is going on, and that can lead to a lack of confidence in the outcome. -- AnonymousCoward

Is non-dictatorship really as simple as it sounds? Does the universality criterion mean that the system should be unable to produce ties?

Could someone show me why AcceptanceVoting doesn't meet all the above criteria? I'm not really expecting an answer to this, as it would involve quite a lot of work one somebody else's part!

-- TomAnderson

Universality requires a complete ranking of all the alternatives, so yes, it does require that the system not produce ties. Thus, AcceptanceVoting does not meet the universality criterion. Of course, one can use another voting method to resolve ties - but this method, too, will be subject to ArrowsTheorem.

It might seem, at a glance, that AcceptanceVoting also violates non-dictatorship. After all, a voter who accepts every candidate will certainly have their vote adopted. However, this is a misunderstanding of the non-dictatorship criterion. In fact, non-dictatorship specifies that there should be no specific voter whose ballot is always adopted. To fail non-dictatorship, there must be a voter whose vote will always decide the election, regardless of who they vote for.

You know, this just pisses me off. Someone who "summarizes" by butchering and smearing one side.

There are two different interpretations of dictatorship. First is that the person's vote will be adopted (not "decisive") regardless of the other votes. Second is that the person's vote will be adopted regardless of their preferences (and so regardless of the content of the vote).

This second interpretation of dictatorship, while it may seem more "natural", is completely out of whack with everything else in the description of Arrow's Theorem. First, because this form of dictatorship is trivial and uninteresting (in the context of a democratic system). And second, because every other condition of Arrow's Theorem talks about the set of votes and not the wishes of any "voters"; who are irrelevant except as vote-generators.

Arrow's theorem is a technical result about a technical process and has nothing to do with any issues of "power". It's a more than even bet that any definitions will also be technical.

In fact, let's examine in detail exactly how trivial and uninteresting the second definition of dictatorship is. How is it possible for a person to always decide the outcome of an election? This can only be the case if there's a single dictator and nobody else has any votes whatsoever. So we're talking about a rare and utterly obvious case. That makes the second definition of dictatorship blatantly stupid.

I was not basing my interpretation on what sounds 'natural'. This is math. It would be idiotic to use anything other than the stated technical definition. My interpretation was based on the definition of dictatorship given at the top of the page: "There should not be one specific voter whose preference ballot is always adopted."

I read this as saying: there should not exist some voter, V, such that the candidate given the highest ranking by V will always win the election. Then you obviously read wrong. The correct interpretation is "There should not be a vote-generator, V, such that whatever votes are generated by V, those votes will be accepted." And this interpretation is obviously closer to the original since it doesn't make the unwarranted assumption that the vote-generator V is free. In fact, the notion of a free voter is rather absurd since there are always options which any voter will consider intolerable; real voters can never be free voters. In order to get your interpretation, you have to redefine what a voter means from a real-world voter to a free voter. Then you have to redefine "adopted" votes to "decisive" votes. You can't justify your interpretation on the original when you've modified its meaning so extensively.

Yes, this is a rare and obvious case. For completeness, though, every case must be stated. A dictatorship could meet the other four criteria, therefore non-dictatorship must be explicitly stated as a fifth criterion. Citizen sovereignty is obvious but necessary in much the same way.

Citizen sovereignty isn't trivial or useless like the second interpretation of dictatorship is. And in fact, the context of the problem as "democratic systems" automatically negates the possibility of the second interpretation of dictatorship. So your variant of the non-dictatorship condition is not only pathological, trivial, and useless, but it's also completely redundant.

You do yourself no service trying to justify a blatant error. That just forces me to explain in detail the magnitude of the error in question. And having to provide that kind of tedious detail only makes me sullen and resentful.

Why do you phrase your correction as an attack? How does that improve the page over, say, calmly pointing out why the second interpretation is too trivial to be the intended one? -- GeorgePaci (not a previous contributor to this page)

I'd like to leap in here and suggest that the trivial interpretation of non-dictatorship is the right one. For example, read the introduction of this paper:

http://cowles.econ.yale.edu/P/cd/d11a/d1123RRR.pdf

It says "The constitution is a dictatorship by individual n if for every pair a and b, society strictly prefers a to b whenever n strictly prefers a to b".

The following are some pages which talk more simply about ArrowsTheorem:

http://jmvidal.ece.sc.edu/talks/voting/index.html et seq http://www.staff.city.ac.uk/andy.denis/research/thesis/03.htm http://www.geocities.com/daitorg/theme/axiom_social.html http://www.cs.byu.edu/info/mikeg/CS501R/lectures/Arrow.html

LinksAreContent, although this is usually said of internal wiki links. I would prefer to digest and summarize them here, I think, but I do not have as much time to do this as I would like.

ArrowsTheorem seems to deal with voting systems in which the ballots are ranked preferences; since AcceptanceVoting doesn't use that sort of ballot, it may not be covered by the theorem. It's also obvious that it falls down completely on universality - it is quite easy to get a tie; introducing a tie-breaking mechanism would probably lead to violation of one of the other requirements.

-- TomAnderson

The best way to look at ArrowsTheorem is that it proves that at least one of the conditions is completely unreasonable. The best candidate is the irrelevancy of "irrelevant" alternatives. This is simply not a reasonable condition for a voting system since it doesn't apply even in decisions made by a single person.

Consider for example the choice between buying a small, medium and large computer monitor. Let's assume that the large computer monitor is ridiculously expensive and so will not get chosen. However, it's well-known that a person who would buy the small monitor when presented with only the first two options, may well buy the medium sized monitor if they see it presented next to the large one. The monitor which the shopper thought to be too expensive now seems cheap in comparison with the ridiculously expensive one. This is a well-documented phenomenon, exploited by shopkeepers and salespeople all over the world and observed in animals as well.

No alternative is ever "irrelevant" and ArrowsTheorem is pretty meaningless.

The discussion at the top of this page seems to suggest that there has to be a single winner as the outcome of a voting process. This is the case in the U.S. presidential elections, but perhaps this is an AmericanCulturalAssumption. In Swedish parliamentary elections (and possibly those of some other European countries as well), candidates or parties A, B, and C would get 44, 45, and 11 percents of the seats in parliament, respectively. (I'm not going into the complex rules for sorting away the smallest parties or how to even out representatives from different districts.) The parliament is a projection of the voters, which could be lined up on a left-to-right political scale or seen as a political N-dimensional landscape with bordering regions, each border representing a possible alliance. The speaker of the parliament then asks the chairman of the party most likely to form and lead a majority parliamentary alliance (in the left-to-right Nader-Gore-Bush landscape, this would be Gore) to be prime minister and form a government. (Sweden is a "constitutional monarchy" and the king plays the symbolic role of head of state, but the prime minister "runs the country" for all practical purposes, very much like a president.) Both the government and any member of parliament can suggest new legislation, but it has to win a majority in parliament. If the government is based on a solid majority, this works out smoothly, but minority governments are not uncommon. This means different party alliances can be formed for each specific issue. In Sweden, the social democratic party has been able to dominate the scene by adjusting their policy to almost always grab the 40% of parliament seats needed to play the leading role. If this was America, the Democratic party would have adjusted their politics to the right to steal some republican votes, because they could always count on the Green party to support them. Getting the 40% share of parliament seats necessary to dominate the scene is similar to getting a 40% share of a commercial market (cf AT&T, IBM, Microsoft, Nokia, Ericsson). Should antitrust legislation apply to political parties? The majority political parties are probably unlikely to suggest that.

Wow - you managed to explain all that without saying once that this system is called ProportionalRepresentation! The fact that Arrow is talking about choosing one option from many is not AmericanCulturalAssumption, but a product of the work Arrow was doing - he wasn't really working on voting, he was working on social choice functions in economics (of which some kinds of voting are a special case). ProportionalRepresentation certainly seems to be a fairer system (although it can't deliver the many-to-one association between voters and representatives that constituency system can, unless you go for some weird hybrid like PrSquared), but it's not always applicable - you couldn't choose presidents proportionally (well, not unless the genetic research budget gets increased quite a bit).

Israel has a system where a parliament elected by ProportionalRepresentation chooses a prime minister, just like Sweden, and a few small parties are willing to join a coalition with whatever major party accedes to their demands. Since those parties hold the swing votes, their influence on the process is far out of proportion to their numbers. This is ArrowsTheorem in action. -- SethGordon

And in any democracy, at least 49% of the population has absolutely no influence on the process.

See also the GibbardSatterthwaiteTheorem.

CategoryVoting