Arrow's Theorem | Hacker News Reader

Arrow's Theorem

plato.stanford.edu

67 pointsinfinity36 comments

Arrow's theorem has to be one of the most overhyped and overplayed theorems in existence. Here, for instance, are three major things what it doesn't say: 1) That all voting systems are equivalent in any sort of meaningful sense 2) That the current voting system you are using is not awful 3) That a perfect class of voting system doesn't exist if you are willing to accept that rock-paper-scissors situations can happen among people's preferences.

I'm not being hyperbolic here. Number 1 and 2 are how people quickly use vague citations to Arrow's Theorem to shut down talk about voting reform even when the status quo consists of provably terrible systems like plurality voting.

Number 3 is the true result that if you relax the rather overly-strongly defined IIA criteria with a much more-reasonable criteria -- that the winner must remain among the top rock-paper-scissors loop of the voters -- then Arrow's theorem simply doesn't apply. This is well known: that "top loop" is the Smith Set and every Condorcet method of voting satisfies it.

There's also another interesting result: if voters have merely "single-peaked preferences", such as opinions about where to set a volume knob, then Arrow's theorem also doesn't apply since there will be no rock-paper-scissors set of equally fair options.

Number 3 is a valid criticism, but criticizing the theorem on the basis of people using it to support the status quo is like criticizing water because some people drown.

His theorem says nothing about the way things should be, but rather about how things are. I mentioned Poundstone's Gaming the Vote in another post, but that book in particular discusses the implications of the theorem and analyzes better alternatives to current systems.

The problem is people assume it means more than it does. It's like someone using Godel's incompleteness theorem to argue that math is pointless.

Well he said it was overhyped, which isn't so much a criticism of the theorem, but a criticism of the hypers.

The problem is that the flaw in thinking is everywhere. Even wikipedia unfairly lumps in Condorcet voting with its various "tiebreaker methods" - it's the tiebreaker methods that run afoul of Arrow's criteria, while the Condorcet method itself does not. And so the Condorcet method gets unfairly lumped together with voting techniques like plurality and IRV.

I disagree with a lot of that. Most people's criticism of a particular voting system takes the form of "your system sucks because it doesn't fulfill desirable criteria A." It's very appropriate to point out that no voting system can fulfill all desirable criteria. Obviously, it doesn't mean that certain voting systems aren't "better" than others, at least if we've agreed on what our goals are (and thus what constitutes "better").

For example, you confidently dismiss plurality voting, but you can't really do that unless you establish what the goals of your voting system are. These goals need to be clearly defined, you can't just say your goal is "making sure everyone has a voice" or "making sure the best candidate wins." That's really all Arrow's theorem says: there are several criteria that most of us agree are desirable, but you cannot have all of them.

Once you actually explain them to people, it's hard to argue that Arrow's theorem still lists desirable criteria. Some are surely reasonable sounding (eg non-dictatorship), but the "independence of irrelevant alternatives" is very deceptively-named: it requires that when voters preferences form a rock-paper-scissors relationship among a set of candidates, the system should never reflect that by having rock win once scissors enters the race.

Arrow calls scissors an "irrelevant alternative" to the race between paper and rock (since scissors doesn't win but makes paper lose). This is just unreasonable -- if there exists a rock-paper-scissors loop among the top preferences of voters, then the voting system should at least acknowledge that reality and make sure it picks someone within that loop (the particular winner is somewhat arbitrary).

And, indeed, if you instead use a more reasonable criteria that requires just that -- that the winner must come from the smith set -- then all of the "reasonable" criteria are satisfiable. Hence the overhyping of Arrow's theorem.

You are right, though, that basing analysis of voting systems on rigid criteria can lead you into trouble. Over-reliance on Arrow's theorem is just an example of that.

The entire point of Arrow's theorem, as I see it, is that criteria which apply to an individual's preferences do not apply to an aggregate of many individual's preferences. Since aggregating the preferences of many individuals is ostensibly the point of any election, it's extremely relevant to point out this rather unfortunate and counterintuitive fact.

IIA is an extremely reasonable quality of an individual's preferences. Although you could probably construct pathological cases where it might sort of make sense for an individual to swap his preference of X and Y when Z is introduced, I contend that it would be exceedingly rare. Showing that IIA is impossible to guarantee (at the same time as other criteria) in an aggregate of preferences is a pretty big deal.

Arrow's theorem does not say or logically imply that, if there is a cyclical Smith set, the voting system shouldn't acknowledge that and pick someone within that loop.

> Arrow's theorem says there are no such procedures whatsoever—none, anyway, that satisfy certain apparently quite reasonable assumptions concerning the autonomy of the people and the rationality of their preferences

The article alludes to one very important corollary, though IMHO it doesn't explain it very well: Arrow's theroem is like the CAP theorem - it seems to be a much stronger restriction than it is. In other words, if you're willing to make just a few very straightforward assumptions (ie, compromises), you can create a system that appears to "satisfy... rationality of their preferences".

Nobel laureate Amartya Sen[0] has demonstrated that if you assume that there are certain rankings of preferences that are rare enough to be ignored altogether, then instant-runoff voting[1] will in fact satisfy all the constraints of the Impossibility Theorem[2].

Let's use the 2000 US Presidential election as an example. There were three main candidates in Florida (Bush, Gore, Nader), for a total of 6 rankings. While Nader played a spoiler role, Nader and Gore shared more of a platform than Nader and Bush did. So it is very reasonable to assume that there are few people who would have voted for Nader over Bush, but Bush over Gore. This reasoning allows us to eliminate a number of those 6 rankings - and more importantly, enough rankings that the criteria of the Impossibility Theorem are likely to hold.

[0] https://en.wikipedia.org/wiki/Amartya_Sen

[1] https://en.wikipedia.org/wiki/Instant-runoff_voting

[2] The article does mention Sen, and alludes to this finding, but I don't think it explains it very clearly.

> Arrow's theroem is like the CAP theorem

accepting dictatorship in the former or non-availability in the later gives you consistency. Reminds about USSR - high consistency (at it least it was initially) with very limited availability of salami (all the way until the last day of USSR).

This is probably just being pedantic, but the Nader->Bush->Gore ranking was commonly preferred by Nader supporters, not because they preferred Bush's policies to Gore's, but because they thought it would teach society the error of their ways in the long run or something. Also because they hated Nader being labeled a spoiler candidate, so it was probably something of a spiteful response.

"Arrow's theorem says there are no such procedures whatsoever—none, anyway, that satisfy certain apparently quite reasonable assumptions concerning the autonomy of the people and the rationality of their preferences."

The trick there is the "apparently quite reasonable" part. Far too many people take it as a given that those assumptions are sacred, which leads to a form of worship about this theorem. The IIAC in particular is problematic, and if that is relaxed, it's not quite so certain anymore that a "perfect" vote-counting method is impossible.

I'm curious which of the assumptions you think are unreasonable.

If you have a Smith Set, you don't want to just arbitrarily remove one of its candidate to resolve the "tie".

Similarly, if an election has a Condorcet Winner, and adding a candidate creates a Smith Set (thus potentially violating IIA if a certain candidate is chosen in a "tiebreaker"), this is not necessarily a bad thing.

If that happens it means that people always legitimately had those views, and were not able to properly express their views by choosing among the more limited number of candidates.

Regarding your second sentence, who says that would be a bad thing? I'm a little confused about the situation you're describing. Most analysis of voting systems I've seen isn't concerned with the fact that valid candidates may be left off the ballot. That's obviously an important consideration in real elections, and if there are primary elections the choice of voting system there obviously matters, but in the final election it doesn't seem particularly relevant.

This theorem only applies to ordinal voting systems. Cardinal voting algorithms like score and approval voting escape this predicament.

http://rangevoting.org/ArrowThm.html

And they have far bigger problems of their own, compared to condorcet methods. Score is the worst....any rational voter will just vote with a 0% or 100% for all candidates. Those who vote "sincerely" are at a huge disadvantage.

Approval gives a big advantage to those who can best predict how others will vote. Yuk.

Not nessisarily, suppose you like X your OK with Y and you hate Z. Do you vote 100% on Y or 0% on Y.

It would depend on whether X or Y is more likely to win the election (according to polls). You can hurt X by voting 100% on Y.

Your specific vote is only important when the election is to close to call. If X is up by 80% in the polls you can probably stay home and nothing happens.

Yeah as baddox says, you'd still be smart to vote 0% or 100%, as long as you can make a better than random pick at who is the leader and runner up. That's because voting in "black and white" is the same as Approval, and as I said, Approval gives an advantage to those who can guess better who are the leaders. Making it especially annoying in elections (such as local ones) where you have no idea who the front runners are.

Cardinal voting algorithms are only superior if people vote sincerely. Unfortunately, cardinal voting methods offer significant incentives to vote insincerely. Condorcet voting does not.

I always thought an interesting vote gathering technique would be something that actually interviews/polls the voter. Ask them for their ordinal ranking. The voter would know that if a Condorcet Winner exists, then that candidate would be the winner, but also ask for various cardinal ranking numbers, along with their approval line. That way there would still be the incentive to vote sincerely, while the cardinal information could be used to break the Smith Set loops. (The only downside here is that some people claim that the presence of cardinal tiebreakers creates an incentive for people to vote insincerely to create a Smith Set...)

Alternatively, if a Smith Set occurs, schedule a second round of voting for only those candidates (like a Louisiana Runoff, but Condorcet style), so that voters could better educate themselves on the remaining candidates.

I will note that a Smith Set Condorcet loop can occur even among 100% rational, wholly informed voters. It's not an aberration due to irrationality, it's just a fact of politics not being one-dimensional (quite literally -- if voters rank candidates based on whomever is closest to them in n-dimensional space, then for any n > 1 you can have a cycle).

You can draw your own example of this if you like. Draw an equilateral triangle and its altitudes, creating 6 regions inside. Put some dots in the 6 regions in the middle (voters), but leave every other region blank. Now, declare the vertices to be candidates (a 3-way race). If you compare any two of them, and have voters vote for whomever they're closest to (based on which side of the altitude they fall on), you'll end up with a rock-paper-scissors situation.

It's interesting and it brings up the question of how a vote should actually be interpreted if there is that kind of legitimate Smith Set. The only options I can think of are either factoring in intensity of preference (see above), or some kind of power-sharing agreement.

Also interesting to me is that I believe the IIAC can actually uncover that kind of completely-legitimate cycle. Meaning, while introducing an additional candidate can never lead you from one Condorcet Winner to another, it can lead you from a Condorcet Winner to a Smith Set. If people change their preferences in that manner, then it means that they have found better choices for them. In other words, if IIAC happens, it could be an indication that the original set of candidates wasn't really appropriate for the voters in the first place.

Thinking about both at the same time is uncomfortable, because if Smith Sets aren't an indication of voter-population confusion that can be resolved with more education and communication, then it basically means that the more choice you offer, the less likely there will be one candidate deserving of victory. If that's true, then making the arbitrary choice (among most likely candidates) might actually be the best outcome. Not exactly democratic though.

I think nondeterminism is fairly reasonable in a cyclical Smith set. In fact, I think nondeterminism in voting systems has a worse reputation than it deserves.

> Cardinal voting algorithms are only superior if people vote sincerely.

What do you mean by "sincerely"? Can you demonstrate a situation where it is in a voter's interest to give a less preferred candidate a greater score than a more preferred candidate?

Is there a good data structure to represent Ordinal Data? I frequently see pairwise count matrices used [1], but they don't seem to completely capture all of the information. For example, the number of times a choice was first, second, third, or last such as would be necessary for the Borda method [2].

[1] http://en.wikipedia.org/wiki/Condorcet_method#Pairwise_count... [2] http://en.wikipedia.org/wiki/Borda_count#Voting_and_counting

Well, Condorcet and Borda do fundamentally different things with people's preferences.

There's no real way to simplify it beyond "here's a set containing the rank order of every voter" if you don't know in advance what election method will be used. In fact, you might argue that the rank order is insufficient, and you also need to know whether the voter would approve of each option in an approval vote, or 0-10 rankings for range voting, or whatever.

Condorcet cares most of all about people's preferences between pairs of options, so that's why you'd summarize it as a matrix made out of those pairwise preferences. Borda cares most of all how many times something is "first place", "second place", and so on, and cares nothing about the pairwise rankings; Borda advocates claim that pairwise rankings will just confuse the issue.

(Opinion: I happen to believe that Borda is garbage for anything where politics is involved. It might be okay for the kind of contests where it's in use, like the baseball MVP or Eurovision, except those are probably secretly political too.)

William Poundstone's Gaming the Vote is a great read that covers this and related topics.

Interestingly, the theorem is false if the number of voters is infinite http://blog.jyotirmoy.net/2013/10/arrows-impossibility-theor...

A fascinating result. I am interested in understanding how this can apply to decisions about consuming news.

Given some objective, like "stay informed" or "make the best possible choice when I vote", and given certain problems like "news is corrupted by advertising" or "news is dumbed down", is it at all plausible to achieve any of those goals in 1 hour of news consumption each day?

A naive application of this theorem suggests not... "none, anyway, that satisfy certain apparently quite reasonable assumptions concerning the autonomy of the people and the rationality of their preferences."

In other words, might it be the case that there is little intrinsic value in consuming the news piecemeal, in the way that most of us do?

I'm not sure you can expand the theorem to deal with that issue. Arrow's theorem essentially says even if you as an individual or society as a whole had perfect news sources, there is no voting method (edit: no ordinal voting method), or method of choice (other than dictatorship, which is bad for obvious reasons), which can accurately register preferences. All voting systems fail at some point, though some are better than others.

To be cynical, in the context of voting, consume news however you want to because to some extent it doesn't matter.

NOPE.

It just means that those "apparently quite reasonable assumptions" weren't reasonable after all and must be relaxed a bit according to a precise definition.

You just took a mathematical theorem and went into a completely unrelated tangent. It's as if someone says there's no point in keeping development schedule because temporal order is relative to the observer.

Please don't do that.

"Say there are some alternatives to choose among. They could be policies, public projects, candidates in an election, distributions of income and labour requirements among the members of a society, or just about anything else. There are some people whose preferences will inform this choice, and the question is: which procedures are there for deriving, from what is known or can be found out about their preferences, a collective or “social” ordering of the alternatives from better to worse?"

Keep reading. This one is more than just math.

Always interesting, but given the median voter theorem is I'm not sure it's a problem in practice.

[1]http://en.wikipedia.org/wiki/Median_voter_theorem

That only applies for one dimensional politics, and, if plurality voting is used, a two party system.

Reply on news.ycombinator.com