Cornell Institute of Business & Technology ECON 1023 Arrow's impossibility theorem

Document Content and Description Below

Arrow's impossibility theorem In social choice theory, Arrow’s impossibility theorem, the General Possibility Theorem, or Arrow’s paradox, states that, when voters have three or more distinct al... ternatives (options), no rank order voting system can convert the ranked preferences of individuals into a communitywide (complete and transitive) ranking while also meeting a pre-specified set of criteria. These prespecified criteria are called unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives. The theorem is often cited in discussions of election theory as it is further interpreted by the Gibbard–Satterthwaite theorem. The theorem is named after economist Kenneth Arrow, who demonstrated the theorem in his doctoral thesis and popularized it in his 1951 book Social Choice and Individual Values. The original paper was titled "A Difficulty in the Concept of Social Welfare".[1] In short, the theorem states that no rank-order voting system can be designed that satisfies these three "fairness" criteria:  If every voter prefers alternative X over alternative Y, then the group prefers X over Y.  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).  There is no "dictator": no single voter possesses the power to always determine the group's preference. Voting systems that use cardinal utility (which conveys more information than rank orders; see the subsection discussing the cardinal utility approach to overcoming the negative conclusion) are not covered by the theorem.[2] The theorem can also be sidestepped by weakening the notion of independence. Arrow rejected cardinal utility as a meaningful tool for expressing social welfare,[3] and so focused his theorem on preference rankings. The axiomatic approach Arrow adopted can treat all conceivable rules (that are based on preferences) within one unified framework. In that sense, the approach is qualitatively different from the earlier one in voting theory, in which rules were investigated one by one. One can therefore say that the contemporary paradigm of social choice theory started from this theorem.[5] Statement of the theorem[edit] The need to aggregate preferences occurs in many disciplines: in welfare economics, where one attempts to find an economic outcome which would be acceptable and stable; indecision theory, where a person has to make a rational choice based on several criteria; and most naturally in voting systems, which are mechanisms for extracting a decision from a multitude of voters' preferences. The framework for Arrow's theorem assumes that we need to extract a preference order on a given set of options (outcomes). Each individual in the society (or equivalently, each decision criterion) gives a particular order of preferences on the set of outcomes. We are searching for a ranked voting system, called a social welfare function (preference aggregation rule), which transforms the set of preferences (profile of preferences) into a single global societal preference order. The theorem considers the following properties, assumed to be reasonable requirements of a fair voting method: Non-dictatorship The social welfare function should account for the wishes of multiple voters. It cannot simply mimic the preferences of a single voter.Unrestricted domain (or universality) For any set of individual voter preferences, the social welfare function should yield a unique and complete ranking of societal choices. Thus:  It must do so in a manner that results in a complete ranking of preferences for society.  It must deterministically provide the same ranking each time voters' preferences are presented the same way. Independence of irrelevant alternatives (IIA) The social preference between x and y should depend only on the individual preferences between x and y (Pairwise Independence). More generally, changes in individuals' rankings of irrelevant alternatives (ones outside a certain subset) should have no impact on the societal ranking of the subset. For example, the introduction of a third candidate to a twocandidate election should not affect the outcome of the election unless the third candidate wins. (See Remarks below.) Positive association of social and individual values (or monotonicity) If any individual modifies his or her preference order by promoting a certain option, then the societal preference order should respond only by promoting that same option or not changing, never by placing it lower than before. An individual should not be able to hurt an option by ranking it higher. Non-imposition (or citizen sovereignty) Every possible societal preference order should be achievable by some set of individual preference orders. This means that the social welfare function is surjective: It has an unrestricted target space. Arrow's theorem says that if the decision-making body has at least two members and at least three options to decide among, then it is impossible to design a social welfare function that satisfies all these conditions at once. A later (1963) version of Arrow's theorem can be obtained by replacing the monotonicity and non-imposition criteria with: Pareto efficiency (or unanimity) If every individual prefers a certain option to another, then so must the resulting societal preference order. This, again, is a demand that the social welfare function will be minimally sensitive to the preference profile. The later version of this theorem is stronger—has weaker conditions—since monotonicity, non-imposition, and independence of irrelevant alternatives together imply Pareto efficiency, whereas Pareto efficiency and independence of irrelevant alternatives together do not imply monotonicity. (Incidentally, Pareto efficiency on its own implies non-imposition.) Remarks on IIA  The IIA condition can be justified for three reasons (Mas-Colell, Whinston, and Green, 1995, page 794): (i) normative (irrelevant alternatives should not matter), (ii) practical (use of minimal information), and (iii) strategic (providing the right incentives for the truthful revelation of individual preferences). Though the strategic property is conceptually different from IIA, it is closely related.  Arrow's death-of-a-candidate example (1963, page 26) suggests that the agenda (the set of feasible alternatives) shrinks from, say, X = {a, b,c} to S = {a, b} because of the death of candidate c. This example is misleading since it can give the reader an impression that IIA is a condition involving two agenda and one profile. The fact is that IIA involves just one agendum ({x, y} in case of Pairwise Independence) but two profiles. If the condition is applied to this confusing example, it requires this: Suppose an aggregation rule satisfying IIA chooses b from the agenda {a, b} when the profile is given by (cab, cba), that is, individual 1 prefers c to a to b, 2 prefers c to b to a. Then, it must still choose b from {a, b} if the profile were, say, (abc, bac) or (acb, bca) or (acb, cba) or (abc, cba). Formal statement of the theorem[edit] Let be a set of outcomes, a number of voters or decision criteria. We shall denote the set of all full linear orderings of by . A (strict) social welfare function (preference aggregation rule) is a function which aggregates voters' preferences into a single preference order on .[6] The -tuple of voters' preferences is called a preference profile. In its strongest and simplest form, Arrow's impossibility theorem states that whenever the set of possible alternatives has more than 2 elements, then the following three conditions become incompatible: unanimity, or Pareto efficiency If alternative a is ranked above b for all orderings , then a is ranked higher than b by . (Note that unanimity implies non-imposition). non-dictatorship There is no individual i whose preferences always prevail. That is, there is no such that . independence of irrelevant alternatives For two preference profiles and such that for all individuals i, alternatives a and b have the same order in as in , alternatives a and bhave the same order in as in . Informal proof[edit] Based on two proofs[7][8] appearing in Economic Theory. For simplicity we have presented all rankings as if ties are impossible. A complete proof taking possible ties into account is not essentially different from the one below, except that one ought to say "not above" instead of "below" or "not below"instead of "above" in some cases. Full details are given in the original articles. We will prove that any social choice system respecting unrestricted domain, unanimity, and independence of irrelevant alternatives (IIA) is a dictatorship. The key idea is to identify a pivotal voter whose ballot swings the societal outcome. We then prove that this voter is a partial dictator (in a specific technical sense, described below). Finally we conclude by showing that all of the partial dictators are the same person, hence this voter is a dictator Part One: There is a "pivotal" voter for B over A[edit] Part One: Successively move B from the bottom to the top of voters' ballots. The voter whose change results in B being ranked over A is the pivotal voter forB over A. Say there are three choices for society, call them A, B, and C. Suppose first that everyone prefers option B the least. That is, everyone prefers every other option to B. By unanimity, society must prefer every option to B. Specifically, society prefers Aand C to B. Call this situation Profile 0. On the other hand, if everyone preferred B to everything else, then society would have to prefer B to everything else by unanimity. Now arrange all the voters in some arbitrary but fixed order, and for each i let Profile i be the same as Profile 0, but move B to the top of the ballots for voters 1 through i. So Profile 1 has B at the top of the ballot for voter 1, but not for any of the others. Profile 2 has B at the top for voters 1 and 2, but no others, and so on [Show More]

Last updated: 2 years ago

Preview 1 out of 18 pages