Arrow and the Impossibility Theorem (2012) [pdf] | Hacker News Reader

Arrow and the Impossibility Theorem (2012) [pdf]

econweb.ucsd.edu

50 pointsrfreytag24 comments

There's also the much stronger Hylland's theorem, which shows that any cardinal system of voting, one where votes also show how much they prefer one candidate to another, must either encourage strategic voting, or be a randomized dictatorship.

https://www.researchgate.net/publication/24064783_Strategy-p...

"This paper analyses strategy-proof mechanisms or decision schemes which map profiles of cardinal utility functions to lotteries over a finite set of outcomes. We provide a new proof of Hylland’s theorem which shows that the only strategy-proof cardinal decision scheme satisfying a weak unanimity property is the random dictatorship. Our proof technique assumes a framework where individuals can discern utility differences only if the difference is at least some fixed number which we call the grid size. We also prove a limit random dictatorship result which shows that any sequence of strategy-proof and unanimous decision schemes defined on a sequence of decreasing grid sizes approaching zero must converge to a random dictatorship."

"Strategy-proof" is a really strange thing to strive for. Making dishonest strategic voting "really really hard" is more than good enough.

By way of example, exploiting a strategic voting vulnerability in certain ranked ballot elections can require both near-perfect information about how everyone else is voting and then solving an NP-hard math problem.

Saying that such an exploit is theoretically possible and then to start talking about dictatorships as being immune is like saying there's a risk someone will win the lottery unless we ban earning money.

Polling tries to figure out how everyone is going to vote, and if you look at the trends, it still mostly works. NP-hard problems can be estimated. I'm not saying that systems like RCV aren't better when compared to others, but that parties can still attempt to game the system.

Ultimately, the real tradeoffs with voting systems are societal I feel. Districts aren't mentioned enough in conversations like this. You can have districts and elect multiple people, through smaller and closer elections. If you must elect one person, you can still have an odd number of districts and pick a winner. To game neutrally drawn districts, people would have to move.

Also ran across:

> It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

> 1. The process is dictatorial, i.e. there exists a distinguished agent who can impose the outcome;

> 2. The process limits the possible outcomes to two options only;

> 3. The process is open to strategic voting: once an agent has identified their preferences, it is possible that they have no action at their disposal that best defends these preferences irrespective of the other agents' actions.

> […] Gibbard's theorem can be proven using Arrow's impossibility theorem.

> Gibbard's theorem is itself generalized by Gibbard's 1978 theorem[2] and Hylland's theorem, which extend these results to non-deterministic processes, i.e. where the outcome may not only depend on the agents' actions but may also involve an element of chance.

* https://en.wikipedia.org/wiki/Gibbard%27s_theorem

I really don't understand why so many people seem to be impressed with Arrow's theorem. It seems to me that it only demonstrates that it's impossible to do something you clearly don't want to do in the first place.

Imagine you have a voting public whose preferences are (roughly) 1/3 prefer A > B > C, 1/3 prefer B > C > A, and 1/3 C > A > B. Fisrt off, it's quite obvious that there is no real "right" thing to do, whichever candidate wins, roughly 2/3 of the electorate would prefer one of the others. Fine as far as it goes. But let's say there are slightly more A > B > C, and A is declared the winner. Arrow seems to think it is a bug that only people's knowledge of B allows A to defeat C, but obviously it's a feature.

Disambiguation. If 34% (or even 49%) claiming A>B>C made A the winner, 66% (large majority, or even 51%, simple majority) explicitly claimed that C>A ...

That «roughly 2/3 of the electorate would prefer one of the others» means that whatever candidate is chosen (say, A), the large majority states that a single different candidate (in this case, C) is better than the winner.

There is clearly a paradox.

A couple months ago, I tried to make a visualization video on Arrow's Theorem:

https://youtu.be/Uvax1Hj8t_E

I probably need to get my act together and do a final version of that video.

If you're into this, then feedback on that video would be helpful. (Or pull requests on the corresponding website...)

Edit: As mdp2021 said, you're welcome to go to the (poorly-documented) accompanying website https://hexagon.bettervoting.org/ and git repo https://github.com/abjennings/socialchoice-hexagons

Checking it; meanwhile, you may have also notified this public of the accompanying website you prepared... ;)

https://hexagon.bettervoting.org

I would suggest you add chapters (e.g. 14:59 → "Borda")

As stated the impossibility theorem is true, however we can design a democratic system that does satisfy all of the conditions set forth. (unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives) The key is to elect multiple people and give them power proportional to their electoral results, and to allow people to split their single vote fractionally between multiple candidates. I think this is where democracy will head in about 200 years.

> The key is to elect multiple people

Coalitions are already used in many political systems worldwide. But they do not solve the theoretical problem caused by the special cases in ordinal preference, where "for every candidate another has larger preference".

> allow people to split their single vote fractionally

Let us note that there are many other strategies... Weighed voting, layers of electors... And let us note that in general they usually have theoretical and practical weaknesses.

I like the formulation with Gibbard’s 1978 theorem about “straightforward” games.

It gives necessary (but not sufficient) conditions for the best play in a mechanism to only depend on each player’s own preferences over the potential outcomes, where knowing how others will likely make moves is of no benefit.

It took me a while to find the statement of the theorem. For other readers like me, starting at page 5 might help.

It's about how it is impossible for democracies to simultaneously satisfy certain desirable traits.

More precisely: suppose that all voters provide an ordered list of preferences, each complete and transitive (option A preferred to B, both preferred to C - no other options available): there does not exist a function that returns a "collective" preference so that ("non-dictatorship") there is no individual list that will always predominate irregardless of the other lists, and ("unanimity") if all voters declare the same highest preference the collective preference will reflect that, and ("non-irrelevance") the collective preference between two alternatives will only depend on the preferences voters claim about those two alternatives.

The page member rfreytag indicates, https://mises.org/wire/arrows-impossibility-theorem-exposes-... , has a very good explanation.

Edit: I realize there could be another (suggestive) way to express it: at least in the (theoretically possible) cases where preferences show a cyclic pattern (when similar numbers of voters claim A>B>C, C>A>B, B>C>A), there is no """optimal""" way to determine a collective preference.

Edit: there is again another nice way to express it - member ajennings shows it at the end of his video (see nearby) with a simulation: if when all voters express preference for an option the outcome reflects that ("unanimity"), and we take a decision in the controversial scenarios, and we demand that the collective preference between two alternatives will be a function of the preferences individual voters claim about those two alternatives ("relevance"), then one ordered list of preferences will make the others uninfluent ("dictatorship").

The "theoretically possible" case of voters having cyclic preferences is actually quite reasonable! A rock-paper-scissors situation among the top 3 candidates doesn't require irrational voters or anything of the sort: all you need is for there to be at least 2 issues.

This is the rational response to Arrow's theorem - not to cynically conclude all voting systems are "bad", or that "dictatorship" makes some sort of sense, but rather just to say that if there's a rock-paper-scissors situation among the top candidates, one of them should win.

For those who don't know Amartya Sen is also a Nobel Laureate in the field of Economics.

He is one of the finest intellectuals and thinkers of our time.

I recently read one of his books- The Argumentative Indian. It is among the best non-fiction that I have ever read.

My game theory professor got his phd under Arrow at Harvard. It was one of the funnest classes.

Arrow's Impossibility Theorem is one of the great results in decision theory. This is an area where Kahneman and Tversky made major contributions.

Voting is important in cases where multiple criteria need to be optimally fused into a single decision.

The above link came from page talking about Arrow's Impossibility Theorem: https://mises.org/wire/arrows-impossibility-theorem-exposes-...

... I'm not that happy with the scary tone of the article but the summary of the theorem is a useful start for what follows...

Interestingly, the IIA result (Arrow's postulate 3, on that page), was shown experimentally by Khaneman and discussed in _The Undoing Project_ to be a irrational behavior experimentally exhibited by humans making a decision. In this experiment prisoner's were asked to choose between food items and then a third, irrelevant food choice, was offered. Non-transitive choices would appear in a significant fraction of the prisoners.

Reading the Mises.org article reminds me why humans might change their decision given irrelevant information (Arrow postulate 3). Breaking Arrow postulate 3 might be necessitated by using a voting algorithm that prefers being anti-dictatorial (Arrow postulate 1) and assuring that any globally preferred choice is selected over any globally less-preferred choice (Arrow postulate 2). Y

It has been shown that a voting scheme can preserve Arrow postulates 1 and 2 only if one allows irrelevant choices to change voting behavior (e.g. strategic voting in our current first-past-the-post, plurality, voting system).

Please consider Borda Count which is said to be close to optimal but still can be 'gamed' by strategic collusive voting. See: https://en.wikipedia.org/wiki/Borda_count

Also please consider Ranked Choice. In ranked choice there are rare cases where globally preferred choice lose to a globally less-preferred choice (Arrow postulate 2). See: https://en.wikipedia.org/wiki/Ranked_voting

Interestingly, Ranked Choice tends to retain incumbents in popular elections because name-recognition tends to produce many valuable runner-up votes. This is why some think a certain Senator from Maine survives challenges by well-funded opponents.

Using cardinal (score/range) methods instead of ordinal ones avoids the constraints of Arrow. It only applies to ordinal methods.

Perhaps obelos is referring to: https://en.wikipedia.org/wiki/Cardinal_voting

Correct. Methods that use “rating” instead of “ranking.”

I’m not sure what you mean by “avoiding constraints”, but Arrow’s theorem very much applies to cardinal methods too. Typically these methods (e.g. the Borda count) do not satisfy IIA.

Cardinal methods induce an order, and once a method creates an order, anything said about ordinal methods applies.

I'm no mathematician, but Arrow himself said he was speaking of ordinal methods: “And in my theorem I’m assuming that the information is a ranking. Each voter can say of any two candidates, I prefer this one to this one.”[1] That's not to say that cardinal methods don't have failure modes, but the particular set of interdependent failures and how pathologically one or more failure of them can appear is not described generally by Arrow's theorem.

How can a ballot capturing cardinal values be reduced to ordinal ones? I don't understand what you're saying here. In an election using a cardinal method, the slate of candidates can be ordered ultimately when summing results, but that's not the same information as the collective mass of ballot data.

1. https://electionscience.org/commentary-analysis/voting-theor...

I think you’re misinterpreting Arrow there. Even a voting method that requires cardinal information entails that voters be able to say which one they prefer between two candidates.

As for how a ballot capturing cardinal methods be reduced to ordinal ones: it depends on the ballot. Can you give an example of a cardinal ballot that does not induce an order or otherwise implies something about a voter’s preferences (assuming they were voting sincerely)?

You don't need to bring irrational individual behavior into it: you can get rock-paper-scissors group cycles even when every voter has a well-ordered list of preferences.

As a basic example, imagine voters prefer whoever is closer to them on some 2-dimensional politics. 3 candidates form a triangle. Draw the altitudes to form six regions, and put a voter in alternating ones. That's a rock-paper-scissors cycle, with very simple rational voters.

Reply on news.ycombinator.com