[HN Gopher] Arrow and the Impossibility Theorem (2012) [pdf]
___________________________________________________________________
Arrow and the Impossibility Theorem (2012) [pdf]
Author : rfreytag
Score : 43 points
Date : 2021-10-25 14:54 UTC (8 hours ago)
(HTM) web link (econweb.ucsd.edu)
(TXT) w3m dump (econweb.ucsd.edu)
| pg_bot wrote:
| 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.
| ajennings wrote:
| 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
| mdp2021 wrote:
| 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")
| rfreytag wrote:
| 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.
| obelos wrote:
| Using cardinal (score/range) methods instead of ordinal ones
| avoids the constraints of Arrow. It only applies to ordinal
| methods.
| chisquared wrote:
| 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.
| obelos wrote:
| 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...
| rfreytag wrote:
| Perhaps obelos is referring to:
| https://en.wikipedia.org/wiki/Cardinal_voting
| obelos wrote:
| Correct. Methods that use "rating" instead of "ranking."
| YokoZar wrote:
| 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.
| tooltower wrote:
| 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.
| mdp2021 wrote:
| 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").
| YokoZar wrote:
| 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.
| drdeca wrote:
| 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.
| sologirlcamper wrote:
| 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."
| throw0101a wrote:
| 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
| YokoZar wrote:
| "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.
| ece wrote:
| 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.
| gbolcer wrote:
| My game theory professor got his phd under Arrow at Harvard. It
| was one of the funnest classes.
___________________________________________________________________
(page generated 2021-10-25 23:01 UTC)