Arrow theorem

from Wikipedia, the free encyclopedia

The Arrow theorem formulated by the economist Kenneth Arrow and named after him (also called Arrow Paradox or General Impossibility Theorem (after Arrow) ) is a proposition of social choice theory . It says that there is no complete and transitive social hierarchy that is composed of any individual hierarchy subject to certain conditions that are obvious for ethical or methodological reasons. The only requirement is that the preference order of each individual contains at least three elements (objects). The four conditions, of which at least one is always violated in this case, are usually known as universality, weak Pareto principle, independence from irrelevant alternatives and non-dictatorship .

The theorem was first formulated by Arrow in his dissertation, which was published as a book in 1951 under the title “Social Choice and Individual Values”. The work arose from the discussions of Pareto efficiency -oriented welfare economics (welfare economics), whose concepts and methods used Arrow. In its original version, however, the theorem contained an error that Julian Blau first pointed out in 1957, which later led Arrow to submit a revised version. The corrected version of the theorem is presented below.

presentation

Fundamental to the Arrow theorem is the assumption that individuals can choose from a number of alternatives; this could be, for example, different parties in a political election. With regard to these alternatives, the individuals have preference relations to which the (minimum) requirement must be placed that they are i) complete and ii) transitive . Property i) means that each individual must actually be able to rank two alternatives A and B. He is always able to decide between any two alternatives A and B, whether A is better, worse or equivalent to B for him is. Property ii) means that a household that finds A at least as good as B and B at least as good as C also finds A at least as good as C. i) and ii) provided, the choice of the individual must then actually be based on the order of preferences, so that an individual who has to decide between a certain number of alternatives actually prefers the one who is “better” than the others according to the preference relation Is evaluated.

The subject of the theorem is then the relationship between the will of individuals and the social decision. Arrow writes: “We ask whether it is formally possible to design a procedure in order to arrive at a structured social decision on the basis of a set of given individual preferences , whereby it is required of the procedure in question that there are certain obvious conditions (natural conditions) . ”Such a process of transforming individual preference orders into social hierarchies is called the social welfare function according to Arrow. This assigns each vector of (complete and transitive) preference orders of individuals - in a society of two people, this can, for example, from the elements "Person 1 prefers A over B and B over C" and "Person 2 prefers B over C and C over A." “Exist - a (again complete and transitive) social hierarchy.

The Arrow theorem states that there cannot exist such a social welfare function that simultaneously fulfills all of the following properties:

  • U (universality / universality): The welfare function is suitable for all imaginable individual (complete and transitive) orders of preference.
  • I (independence ): For the social ranking of two alternatives A and B, only the preferences of the individuals with regard to these two alternatives are relevant. (In other words: If one wants to know how society evaluates two alternatives A and B, it is not necessary to consider the complete order of preferences of the individuals, but rather it is sufficient to ask everyone how he evaluates A and B.)
  • M (monotonicity ): If the welfare function gives the alternative A socially preference over B, then this ranking must not change because some individuals modify their order of preference so that they now rate A even better than before, while at the same time nobody A rated worse than previously.
  • N (non-imposition, also citizen sovereignty): Every social hierarchy can be reached through at least a set of individual hierarchies.
  • D (non-dictatorship / non-dictatorship): There is no dictator whose individual order of preference also represents the social hierarchy.

If there are at least two individuals and at least three decision variants, there is no mechanism that could derive from the individual decisions a collective decision that satisfies all five axioms. In other words, every mechanism that derives a collective decision from individual decisions and fulfills four of the axioms violates the remaining axiom. For a corresponding collective decision-making mechanism, one of the conditions must be changed or dropped.

The conditions M and N can be replaced by a single condition P without restricting the validity of the theorem:

  • P (weak Pareto principle): If every person in their order of preference strictly prefers alternative A, this also applies at a social level.

Formal representation

Be the set of all possible social allocations, then the Cartesian product is the set of all ordered tuples , . be a binary relation , and it is agreed that it can be written alternatively . The prerequisite for this is that the relation

  1. is complete , that is, or (or both),
  2. and that they transitive is so for all applies that .

In the resulting order, the spelling is now casually interpreted as “is better than or as good as” (preference-indifference relation). At the same time induce the relations (“is strictly better than”; preference relation), where exactly if , but not , as well as (“is equally good as”; indifference relation), where exactly if and at the same time .

Be , an individual order of preference of a person from a society of members ( and defined analogously). Let it be the set of all possible social rank orders and the set of all possible individual preference orders. Then there is a social welfare function.

Arrow's theorem (1951, 1963): Be finite and . Then there is no function that fulfills the properties i) U, I, M, N and D or ii) U, I, P and D at the same time .

Formal addendum to the properties postulated above:

  • I: Be alternatives. If it applies to everyone that the relative ranking of and after a modification of in does not change in any individual order of preference , then the ranking changes with regard to and also not during the transition from to the new social welfare order .
  • M: For all tuples and for a given alternative : if for all and for all that on the one hand and on the other as well as , then applies .
  • N: There are no two alternatives , so for any Präferenztupel .
  • P: Be , alternatives .
  • D: There is no individual , so for all , holds that , regardless of the preference orderings of other individuals besides .

proof

In the following, an illustrative proof of the theorem will be outlined, which follows that of Geanakoplos (1996, 2005) and its presentation in Jehle / Reny (2011). The basic idea of ​​the strategy is identical to that in the original proof by Arrow (1951): It is shown that, under the assumptions of the theorem, the assumption of U , I and P directly leads to the welfare function against the non-dictatorship Assumption D violates. Consequently, there cannot be a welfare function that satisfies all four conditions.

One starts with an alternative that is strictly least preferred by all persons, i.e. H. . From P it follows that so too . This is illustrated in the following table based on the society of members described (note that the preference orders shown can also be weak):

(Table 1:)
1. Preference
  
  
nth preference

Then one after the other lets person to change the ranking from in such a way that for the individual is now strictly preferred over all other alternatives (that is, placed in the first position of the preference order). Then there is a voter whose preference change first leads to an improvement in the social ranking of ; The position in which this voter is depends on the specific electoral process, but at the latest, because of P , it must apply that the social ranking changes with . Below is an illustration of this as well:

(Table 2 :)
1. Preference
  
  
nth preference

It is now shown that the social ranking of persons not only improves, but also necessarily ranks at the top of the welfare order.

( Proof of contradiction :) Suppose that applies to person :, but at the same time for certain , - there is still (at least) one alternative that is at least slightly better than . Then you can modify each individual preference order so that now . This leaves the position of unchanged, because it is either first or last in every individual order of preference. However, this provides a contradiction, because on the one hand [1]:
(because of P ),
but on the other hand [2] the ranking of regarding and regarding has not changed for any person, which is why according to I the social ranking of regarding and regarding must have remained unchanged. From this it follows that furthermore and what also implies because of the transitivity property - in contradiction to [1].

Denote two other options under the preferential arrangements and , , , , and again accordingly . It now applies to person that , that is, now that in the order of preference of prior to the first place pushes. The order of preference of the other people can be changed with regard to and at will, as long as the position of is left unchanged. For the sake of simplicity, differentiate the following profiles, some of which have already been sketched above:

  • Profile 1 (preliminary to Table 2): All persons up to (but without) person prefer all other alternatives; for everyone else (inclusive ) is the worst alternative.
  • Profile 2 (see Table 2): All persons up to and including person prefer all other alternatives; for everyone else is the worst alternative.
  • Profile 3 (see Table 3): All persons up to (but without) person prefer all other alternatives; Person prefers strictly before and strictly before ; for the people after is still the worst alternative. Each person can choose their ranking from and at will, as long as only the extreme preferences for (at the bottom or at the top) are left unchanged.

The third profile is also graphically visualized below:

(Table 3 :)
1. Preference
  
  
  
  
nth preference

Please note that profile 2 and 3 do not differ from and in terms of the relative ranking : up to and including, everyone prefers , all others prefer . Since the welfare order is already changing with person , it follows for both profile 2 and (because of I ) for profile 3 that . At the same time, profiles 1 and 3 do not differ from and in terms of the relative ranking : Until (but without) everyone prefers , all others (including ) prefer . Since the welfare order only changes with the person , it follows for both profile 1 and (because of I ) for profile 3 that .

This applies in summary (according to the transitivity characteristic). Now it has been shown that regardless of the rankings of all other persons the ranking from person decides how at the social level and are valued (one could and indeed exchange) that so therefore - contrary to  D .

Examples

With the help of two voting procedures, examples for the application of the Arrow theorem will be given in the following with different definitions of the welfare function.

  • Relative majority vote : the alternative that receives the most votes of all the alternatives put to the vote is elected, with each person casting one vote for their preference.
Suppose five people (1, 2, 3, 4 and 5) are voting on four alternatives (A, B, C, D). The situation can be noted, for example, as described below, whereby for the sake of simplicity it is assumed here that everyone between the four alternatives has strict preferences:
1 2 3 4th 5
1. Preference B. B. A. D. C.
2. Preference D. A. C. C. A.
3. Preference A. D. D. A. D.
4. Preference C. C. B. B. B.
These are the orders of preference of the five people considered; The alternative that the individual will choose is highlighted in red. From this it can be seen that B will be chosen as a whole because it can unite one vote more than the other three alternatives, each with one vote. The electoral process, however, violates the indifference property I , as becomes immediately apparent when one takes the alternatives A and D from the tableau; then namely - in violation of the condition - the relative ranking between B and C also changes.
1 2 3 4th 5
1. Preference B. B. C. C. C.
2. Preference C. C. B. B. B.
Condition U , on the other hand, is fulfilled, since every voting procedure based on a scoring protocol provides a complete and transitive welfare order. D is obviously also fulfilled. However, the procedure also violates the weak Pareto principle P, as the following scenario (for simplification with only three decision alternatives) shows:
1 2 3 4th 5
1. Preference A. A. A. A. A.
2. Preference B. B. B. B. B.
3. Preference C. C. C. C. C.
Alternative B is strictly preferred to C by all five people, but in the end receives the same number of votes (0) as C.
  • Condorcet method : Each person presents their complete order of preference. Of two alternatives evaluated, the one that is preferred to the other by a larger number of individuals is considered to be socially preferred. We assume the following preference structure:
1 2 3
1. Preference A. B. C.
2. Preference B. C. A.
3. Preference C. A. B.
A comparison of A and B shows that A is socially superior to B (preferred by people 1 and 3). At the same time, B is better than C (preferred by people 1 and 2). C is again better than A (preferred by persons 2 and 3).
Again, it is obviously not a dictatorship, so D is fulfilled. From the method, which is based on a pairwise comparison, it is also clear that I is satisfied. The same applies to  P . If everyone would strictly prefer an alternative A to B, then the pairwise comparison also ensures that A, ceteris paribus, is certainly preferred to B. However, the described method violates the universality  assumption U. In the example chosen above, A is already better than B, B better than C, from which, according to the transitivity requirement, it should follow that A is also better than C. But this is precisely not the case ( Condorcet paradox ). The relation is thus intransitive, which contradicts the universality assumption.

Extensions and assessment

Arrow's “General Impossibility Theorem” poses a fundamental problem for all social science theories that attempt to describe rules for social decisions based on individual preferences. In practice, the theorem calls into question the possibility of a clear definition of a “common good” with the help of abstract rules, for example in the form of voting rules or the like. The problem, however, also affects collectivist theories and ideologies, insofar as it points out that - assumed - collective interests can always conflict with other interests even of the majority of the members of the collective.

The Arrow theorem is based on an ordinal utility concept , as is commonly used in modern economics. According to some critics, this leads to significant practical problems; the ordinal concept does not distinguish whether two alternatives are only marginally different or whether there are significant differences between them. Amartya Sen (1970) modified Arrow's theorem to make it accessible to cardinal preferences, and with the resulting framework justified the paradox of liberalism with changed conditions.

Wilson (1972) generalizes the theorem by proposing to abandon the weak Pareto criterion in favor of a weak non-imposition condition, the fulfillment of which, with the simultaneous validity of the conditions other than D, implies that it is either a dictator or an inverse dictator (inverse dictator) there.

literature

Web links

Wiktionary: Arrow theorem  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. ^ Julian H. Blau: The Existence of Social Welfare Functions. In: Econometrica. 25, No. 2, 1957, pp. 302-313 ( JSTOR 1910256 ).
  2. See Arrow 2008.
  3. See usually Sen 1986, p. 1075 ff.
  4. In contrast to the strong Pareto principle P *, according to which . Of course, P * also implies P.
  5. Geoffrey A. Jehle, Philip J. Reny: Advanced Microeconomic Theory. 3rd ed. Financial Times / Prentice Hall, Harlow 2011, ISBN 978-0-273-73191-7 , pp. 288-291.
  6. A formalized version of the same proof can be found in Tobias Nipkow: Social Choice Theory in HOL. Arrow and Gibbard-Satterthwaite. In: Journal of Automated Reasoning. 43, No. 3, 2009, pp. 289-304, doi: 10.1007 / s10817-009-9147-4 .
  7. ^ Robert Wilson: Social choice theory without the Pareto Principle. In: Journal of Economic Theory. 5, No. 3, 1972, pp. 478-486, doi: 10.1016 / 0022-0531 (72) 90051-8 .