Live data from Hacker News

Arrow's impossibility theorem

en.wikipedia.org

31–40 of 93 posts

Re: Arrow's impossibility theorem

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

Re: Arrow's impossibility theorem

#32
post #6
post #2

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

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 compar…

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

Re: Arrow's impossibility theorem

#33
post #24

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 p…

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.

Re: Arrow's impossibility theorem

#34
post #24

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 p…

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

Re: Arrow's impossibility theorem

#35
post #33
post #24

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 p…

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…

[deleted]

Re: Arrow's impossibility theorem

#36
post #24

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 p…

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

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

Re: Arrow's impossibility theorem

#37
post #6

Earlier quoted context omitted.

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 compar…

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 satis…

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

Re: Arrow's impossibility theorem

#38
post #24

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 p…

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

Re: Arrow's impossibility theorem

#39
post #25

Earlier quoted context omitted.

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, s…

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

Re: Arrow's impossibility theorem

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

Post reply on HN