11 ms·

Arrow's impossibility theorem

97 points by Gray0Ed 11y ago

c-slice 11y ago
Can I get a simple wikipedia explanation? That was the most challenging wikipedia article I've ever read.
- vezzy-fnord 11y ago
  Try the Stanford Encyclopedia of Philosophy's take on it: http://plato.stanford.edu/entries/arrows-theorem/ http://plato.stanford.edu/entries/arrows-theorem/ It's actually not that "simple", but it's overall less technical.
  - theVirginian 11y ago
    It's technical which is good but much better written than Wikipedia.
- bradleyjg 11y ago
  It is a theorem about the properties of all possible voting systems with preference rankings. The basic idea is there are a few desirable properties for any such voting system, but that it is mathematically impossible for any voting system to satisfy all of them.
  - dragonwriter 11y ago
    > It is a theorem about the properties of all possible voting systems with preference rankings. More accurately, it is a theorem about the properties of all possible voting systems where the input is voters preference rankings and the output is also a preference ranking.
- JadeNB 11y ago
  It's not Wikipedia, but http://tech.mit.edu/V123/N8/8voting.8n.html http://tech.mit.edu/V123/N8/8voting.8n.html may be more intelligible (especially regarding the particular desireable conditions that Arrow's theorem says are mutually incompatible). There's also http://dev.whydomath.org/node/voting/Arrow's_Impossibility_Theorem.html http://dev.whydomath.org/node/voting/Arrow's_Impossibility_T..., which includes some intuition-building exercises.
- schmit 11y ago
  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 comparing just A and B, then one should also prefer A over B when an additional option C is offered Sounds like some reasonable properties for a voting system, right? Well, the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above.
  - jonahx 11y ago
    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?
    - dragonwriter 11y ago
      > 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? Which particular problems occur, and the frequency with which they occur, depend on the particular voting system. Plurality and majority/runoff (which are ranked preference voting systems with a vary narrow constraint on the preferences that are expressed on the input ballots, which is pretty much the same constraint as on the preferences reflected in the output of any single-winner voting system) hits problems fairly frequently in practice, but most of the common voting systems that most people think of as ranked-preference systems (IRV, etc.) still hit them in practice as well, though not generally as frequently and in ways which create as clear incentives to tactical voting.
    - stephencanon 11y ago
      http://en.wikipedia.org/wiki/Burlington_mayoral_election,_2009 http://en.wikipedia.org/wiki/Burlington_mayoral_election,_20...
- kelvintran 11y ago
  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, such that A is preferred over C (eg, A > B > C). Option A is known as the Condorcet winner. But there may be cases where the vote yields no Condorcet winner (eg, A > B > C > A). This is illustrated by the following table: Preferences Voter 1 Choc Vanil Strwb Voter 2 Vanil Strwb Choc Voter 3 Strwb Choc Vanil Two voters prefer C over V and two prefer V over S, but two also prefer S over C. To ensure transitivity, we can introduce voting rules, but it is impossible to introduce rules that do not violate the fair and democratic norms (referred to as the pre-specified criteria in the Wikipedia article: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives).
  - SilasX 11y ago
    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?
    - gweinberg 11y ago
      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".
      - SilasX 11y ago
        "Screwy" in this context means the sort of intransitive situations referred to in the parent of my last comment.
    - 11y ago
- lambda 11y ago
  There is a simple explanation in the introduction: In short, the theorem states that no rank-order voting system can be designed that always satisfies these three "fairness" criteria: 1. If every voter prefers alternative X over alternative Y, then the group prefers X over Y. 2. If every voter's preference between X and Y remains unchanged, then the group's preference between X and Y will also remain unchanged (even if voters' preferences between other pairs like X and Z, Y and Z, or Z and W change). 3. There is no "dictator": no single voter possesses the power to always determine the group's preference. A "rank-order voting system" is one in which all voters order the possible choices, from most preferred to least preferred. The idea is that based on everyone's votes, and some set of rules on how to evaluate those votes, you can come up with a decision for the entire group that respects those preferences, in some way that is considered fair. All of these requirements listed above seem like fairly simple requirements for a voting system to have; if there's unanimous agreement about the ordering of two of the choices, then the voting system should order them that way. If a voter changes preferences about one choice C (maybe changing between them being ranked above or below D, or above or below one of A or B), without changing their ordering between choices A and B, that shouldn't affect the outcome of the A/B ordering that the voting system gives you. And finally, there is not dictator; no single voter is able to always determine the group ordering unilaterally. The first requirement seems pretty obvious; if everyone is unanimous that we should pick one option over another, then the group should pick that option. The second is a little trickier; but it basically states that there shouldn't be able to be "spoiler"; someone whose ordering in people's preferences affects the ordering of to other choices. Think about, say, the 2000 election, with Bush and Gore and a couple of third party candidates; now, that used just single choices per voter rather than a ranking, but imagine it used a ranking. So let's say Bush and Gore are fairly close, but 51% of voters prefer Gore over Bush. Their preferences for other candidates should not affect the fact that Gore wins over Bush. If I rank candidates Nader > Gore > Bush, that should not change the Gore/Bush result compared to if I ranked the candidates Gore > Bush > Nader. And the last is pretty trivially desirable; generally a democracy wants to democratically make a choice, in which everyone's vote has the same weight in affecting the final outcome. The fact that these conditions are impossible to achieve together is fairly profound, and means that almost any voting system will have serious flaws under certain circumstances.
- logicchop 11y ago
  Here's the version of the story with respect to voting: Democracy requires voting. Voting involves an objective measurement of group preference with respect to choices. Arrow's theorem and related theorems (see Gibbard-Satterthwaite theorem) show that there is no way to objectively measure group preferences.
pixelcort 11y ago
How does Quadratic Voting fare in meeting these criteria? http://ericposner.com/quadratic-voting/ http://ericposner.com/quadratic-voting/
- deleted 11y ago
  [deleted]
- rbkillea 11y ago
  I'm pretty sure that Quadratic Voting is a way to assign prices to votes, whereas this theorem is about the features of a system in which the results are determined by vote. So the results of quadratic voting will meet this criteria because after the votes are bought they can be thought of as emanating from discrete voters who align their preferences with those of the buyer. That is to say that the issues solved by Quadratic Voting and those presented in Arrow's theorem are orthogonal.
verteu 11y ago
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 pie."
- mcphage 11y ago
  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.
  - deleted 11y ago
    [deleted]
  - grayclhn 11y ago
    Arrow's impossibility theorem, and the IIA criterion, is about preferences not about uncertain actions. In particular, IIA doesn't mean that you'll vote differently than your preferences in some sort of election, it means that your preferences themselves don't change when you introduce other irrelevant options. In your example, it wouldn't be about how Sidney would vote in an election given the different menu of candidates, it's about who Sidney would prefer win the election. (with the caveat that it has been a long time since I've thought about these results.)
  - logicchop 11y ago
    In the context of voting, all IIA represents is the requirement that we only take into account the information on the ballots..
VanillaCafe 11y ago
Maybe I don't quite appreciate the significance. The Informal Proof section seems to boil down to: If the vote is tied and there is one vote left, then that last vote determines the outcome. The existence of a swing vote in this circumstance doesn't seem very surprising.
- verteu 11y ago
  "Part One" of the informal proof is trivial, for the reason you've described. But "Part Two" is not: It shows that if the "pivotal voter" from Part One votes B>C, then B will beat C in the election, even if everyone else votes C>B.
aaron-lebo 11y ago
A great popular read that covers this and similar topics is William Poundstone's Gaming the Vote. http://www.amazon.com/Gaming-Vote-Elections-Arent-About/dp/0809048922 http://www.amazon.com/Gaming-Vote-Elections-Arent-About/dp/0...
kijin 11y ago
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.
- 11y ago
gjm11 11y ago
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.)
- logicchop 11y ago
  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 simple ranking (including rankings of indifference). This approach has always struck me as an unmotivated anti-empirical gimmick to get around this-or-that condition in the theorem(s).
  - reagency 11y ago
    Scoring lets you indicate ties, and strong preferences.
marcoperaza 11y ago
The criteria considered by the theorem concern how democratic a voting system is. I'd argue that 'democraticness' is secondary to two other criteria: accountability and government-effectiveness. Accountability means that bad rulers can get voted out of office when enough people are displeased. Government-effectiveness means that the resulting government can practice good governance. When considering these criteria, I think plurality/first-past-the-post voting systems are superior. Unpopular leaders are voted out and elections usually result in single-party majorities that can govern effectively.
- deleted 11y ago
  [deleted]
FLengyel 11y ago
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 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 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.
CurtMonash 11y ago
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).
JDDunn9 11y ago
http://en.wikipedia.org/wiki/Voting_system http://en.wikipedia.org/wiki/Voting_system has a nice comparison chart half way down.
Tloewald 11y ago
It seems to me that concern over the dictatorship criterion is ill founded. Its failure merely implies that for any given set of alternatives there will always be one voter whose preferences, whatever they may be, determine the outcome. Now if everyone's preferences were known and constant then in theory you could find that person and they would be able to decide the outcome. In practice preferences don't stay constant and no-one knows them all, so as long as you have secret ballots the dictatorship criterion doesn't matter. So you can have the other two criteria which are far more important.
gerty 11y ago
Few theorems in economics, or political science in this case, are as disappointing as this one. Another one is Sonnenschein-Mantel-Debreu. https://en.wikipedia.org/wiki/Sonnenschein%E2%80%93Mantel%E2%80%93Debreu_theorem https://en.wikipedia.org/wiki/Sonnenschein%E2%80%93Mantel%E2... SMD: rational individuals do not sum up to a rational aggregate.
- deleted 11y ago
  [deleted]
fithisux 11y ago
Do you know an exposition for mathematicians? Preferably in front of a paywall. What is the mathematical content?

97 points by Gray0Ed 11y ago

c-slice 11y ago

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

vezzy-fnord 11y ago
Try the Stanford Encyclopedia of Philosophy's take on it: http://plato.stanford.edu/entries/arrows-theorem/ http://plato.stanford.edu/entries/arrows-theorem/ It's actually not that "simple", but it's overall less technical.
- theVirginian 11y ago
  It's technical which is good but much better written than Wikipedia.
bradleyjg 11y ago
It is a theorem about the properties of all possible voting systems with preference rankings. The basic idea is there are a few desirable properties for any such voting system, but that it is mathematically impossible for any voting system to satisfy all of them.
- dragonwriter 11y ago
  > It is a theorem about the properties of all possible voting systems with preference rankings. More accurately, it is a theorem about the properties of all possible voting systems where the input is voters preference rankings and the output is also a preference ranking.
JadeNB 11y ago
It's not Wikipedia, but http://tech.mit.edu/V123/N8/8voting.8n.html http://tech.mit.edu/V123/N8/8voting.8n.html may be more intelligible (especially regarding the particular desireable conditions that Arrow's theorem says are mutually incompatible). There's also http://dev.whydomath.org/node/voting/Arrow's_Impossibility_Theorem.html http://dev.whydomath.org/node/voting/Arrow's_Impossibility_T..., which includes some intuition-building exercises.
schmit 11y ago
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 comparing just A and B, then one should also prefer A over B when an additional option C is offered Sounds like some reasonable properties for a voting system, right? Well, the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above.
- jonahx 11y ago
  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?
  - dragonwriter 11y ago
    > 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? Which particular problems occur, and the frequency with which they occur, depend on the particular voting system. Plurality and majority/runoff (which are ranked preference voting systems with a vary narrow constraint on the preferences that are expressed on the input ballots, which is pretty much the same constraint as on the preferences reflected in the output of any single-winner voting system) hits problems fairly frequently in practice, but most of the common voting systems that most people think of as ranked-preference systems (IRV, etc.) still hit them in practice as well, though not generally as frequently and in ways which create as clear incentives to tactical voting.
  - stephencanon 11y ago
    http://en.wikipedia.org/wiki/Burlington_mayoral_election,_2009 http://en.wikipedia.org/wiki/Burlington_mayoral_election,_20...
kelvintran 11y ago
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, such that A is preferred over C (eg, A > B > C). Option A is known as the Condorcet winner. But there may be cases where the vote yields no Condorcet winner (eg, A > B > C > A). This is illustrated by the following table: Preferences Voter 1 Choc Vanil Strwb Voter 2 Vanil Strwb Choc Voter 3 Strwb Choc Vanil Two voters prefer C over V and two prefer V over S, but two also prefer S over C. To ensure transitivity, we can introduce voting rules, but it is impossible to introduce rules that do not violate the fair and democratic norms (referred to as the pre-specified criteria in the Wikipedia article: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives).
- SilasX 11y ago
  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?
  - gweinberg 11y ago
    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".
    - SilasX 11y ago
      "Screwy" in this context means the sort of intransitive situations referred to in the parent of my last comment.
  - 11y ago
lambda 11y ago
There is a simple explanation in the introduction: In short, the theorem states that no rank-order voting system can be designed that always satisfies these three "fairness" criteria: 1. If every voter prefers alternative X over alternative Y, then the group prefers X over Y. 2. If every voter's preference between X and Y remains unchanged, then the group's preference between X and Y will also remain unchanged (even if voters' preferences between other pairs like X and Z, Y and Z, or Z and W change). 3. There is no "dictator": no single voter possesses the power to always determine the group's preference. A "rank-order voting system" is one in which all voters order the possible choices, from most preferred to least preferred. The idea is that based on everyone's votes, and some set of rules on how to evaluate those votes, you can come up with a decision for the entire group that respects those preferences, in some way that is considered fair. All of these requirements listed above seem like fairly simple requirements for a voting system to have; if there's unanimous agreement about the ordering of two of the choices, then the voting system should order them that way. If a voter changes preferences about one choice C (maybe changing between them being ranked above or below D, or above or below one of A or B), without changing their ordering between choices A and B, that shouldn't affect the outcome of the A/B ordering that the voting system gives you. And finally, there is not dictator; no single voter is able to always determine the group ordering unilaterally. The first requirement seems pretty obvious; if everyone is unanimous that we should pick one option over another, then the group should pick that option. The second is a little trickier; but it basically states that there shouldn't be able to be "spoiler"; someone whose ordering in people's preferences affects the ordering of to other choices. Think about, say, the 2000 election, with Bush and Gore and a couple of third party candidates; now, that used just single choices per voter rather than a ranking, but imagine it used a ranking. So let's say Bush and Gore are fairly close, but 51% of voters prefer Gore over Bush. Their preferences for other candidates should not affect the fact that Gore wins over Bush. If I rank candidates Nader > Gore > Bush, that should not change the Gore/Bush result compared to if I ranked the candidates Gore > Bush > Nader. And the last is pretty trivially desirable; generally a democracy wants to democratically make a choice, in which everyone's vote has the same weight in affecting the final outcome. The fact that these conditions are impossible to achieve together is fairly profound, and means that almost any voting system will have serious flaws under certain circumstances.
logicchop 11y ago
Here's the version of the story with respect to voting: Democracy requires voting. Voting involves an objective measurement of group preference with respect to choices. Arrow's theorem and related theorems (see Gibbard-Satterthwaite theorem) show that there is no way to objectively measure group preferences.

pixelcort 11y ago

How does Quadratic Voting fare in meeting these criteria? http://ericposner.com/quadratic-voting/ http://ericposner.com/quadratic-voting/

deleted 11y ago
[deleted]
rbkillea 11y ago
I'm pretty sure that Quadratic Voting is a way to assign prices to votes, whereas this theorem is about the features of a system in which the results are determined by vote. So the results of quadratic voting will meet this criteria because after the votes are bought they can be thought of as emanating from discrete voters who align their preferences with those of the buyer. That is to say that the issues solved by Quadratic Voting and those presented in Arrow's theorem are orthogonal.

verteu 11y ago

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

mcphage 11y ago
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.
- deleted 11y ago
  [deleted]
- grayclhn 11y ago
  Arrow's impossibility theorem, and the IIA criterion, is about preferences not about uncertain actions. In particular, IIA doesn't mean that you'll vote differently than your preferences in some sort of election, it means that your preferences themselves don't change when you introduce other irrelevant options. In your example, it wouldn't be about how Sidney would vote in an election given the different menu of candidates, it's about who Sidney would prefer win the election. (with the caveat that it has been a long time since I've thought about these results.)
- logicchop 11y ago
  In the context of voting, all IIA represents is the requirement that we only take into account the information on the ballots..

VanillaCafe 11y ago

Maybe I don't quite appreciate the significance. The Informal Proof section seems to boil down to: If the vote is tied and there is one vote left, then that last vote determines the outcome. The existence of a swing vote in this circumstance doesn't seem very surprising.

verteu 11y ago
"Part One" of the informal proof is trivial, for the reason you've described. But "Part Two" is not: It shows that if the "pivotal voter" from Part One votes B>C, then B will beat C in the election, even if everyone else votes C>B.

aaron-lebo 11y ago

A great popular read that covers this and similar topics is William Poundstone's Gaming the Vote. http://www.amazon.com/Gaming-Vote-Elections-Arent-About/dp/0809048922 http://www.amazon.com/Gaming-Vote-Elections-Arent-About/dp/0...

kijin 11y ago

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.

11y ago

gjm11 11y ago

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

logicchop 11y ago
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 simple ranking (including rankings of indifference). This approach has always struck me as an unmotivated anti-empirical gimmick to get around this-or-that condition in the theorem(s).
- reagency 11y ago
  Scoring lets you indicate ties, and strong preferences.

marcoperaza 11y ago

The criteria considered by the theorem concern how democratic a voting system is. I'd argue that 'democraticness' is secondary to two other criteria: accountability and government-effectiveness. Accountability means that bad rulers can get voted out of office when enough people are displeased. Government-effectiveness means that the resulting government can practice good governance. When considering these criteria, I think plurality/first-past-the-post voting systems are superior. Unpopular leaders are voted out and elections usually result in single-party majorities that can govern effectively.

deleted 11y ago
[deleted]

FLengyel 11y ago

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

CurtMonash 11y ago

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

JDDunn9 11y ago

http://en.wikipedia.org/wiki/Voting_system http://en.wikipedia.org/wiki/Voting_system has a nice comparison chart half way down.

Tloewald 11y ago

It seems to me that concern over the dictatorship criterion is ill founded. Its failure merely implies that for any given set of alternatives there will always be one voter whose preferences, whatever they may be, determine the outcome. Now if everyone's preferences were known and constant then in theory you could find that person and they would be able to decide the outcome. In practice preferences don't stay constant and no-one knows them all, so as long as you have secret ballots the dictatorship criterion doesn't matter. So you can have the other two criteria which are far more important.

gerty 11y ago

Few theorems in economics, or political science in this case, are as disappointing as this one. Another one is Sonnenschein-Mantel-Debreu. https://en.wikipedia.org/wiki/Sonnenschein%E2%80%93Mantel%E2%80%93Debreu_theorem https://en.wikipedia.org/wiki/Sonnenschein%E2%80%93Mantel%E2... SMD: rational individuals do not sum up to a rational aggregate.

deleted 11y ago
[deleted]

fithisux 11y ago

Do you know an exposition for mathematicians? Preferably in front of a paywall. What is the mathematical content?