Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Arrow's impossibility theorem

en.wikipedia.org

Post reply on HN
Print view View original

51–60 of 93 posts

Re: Arrow's impossibility theorem

#51

Post by FLengyel »

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.

Re: Arrow's impossibility theorem

#52

Post by logicchop »

jonahx wrote: post #9
schmit wrote: 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…

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?

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.

Re: Arrow's impossibility theorem

#53

Post by logicchop »

kijin wrote: post #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…

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

Re: Arrow's impossibility theorem

#54

Post by reagency »

logicchop wrote: post #47
gjm11 wrote: post #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 preference…

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

Scoring lets you indicate ties, and strong preferences.

Re: Arrow's impossibility theorem

#55

Post by kijin »

logicchop wrote: post #53
kijin wrote: post #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…

(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 relat…

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.

Re: Arrow's impossibility theorem

#56

Post by CurtMonash »

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

Re: Arrow's impossibility theorem

#57

Post by reagency »

SilasX wrote: post #25
kelvintran wrote: post #14

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?

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.

Re: Arrow's impossibility theorem

#58

Post by reagency »

kragen wrote: post #29
mkehrt wrote: post #23

Earlier quoted context omitted.

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?

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

Re: Arrow's impossibility theorem

#59

Post by MichaelDickens »

gjm11 wrote: post #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 preference…

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?

Re: Arrow's impossibility theorem

#60

Post by grayclhn »

belovedeagle wrote: post #43
verteu wrote: 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 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…

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.

Post reply on HN