Choice Under Complete Uncertainty and Procedural Rationality Ricardo Arlegi? Department of Economics. Public University of Navarre, Campus Arrosadia s/n -31006 Pamplona-Iru˜nea (Spain). e-mail: rarlegi@unavarra.es fax: 34-948-169721. phone: 34-948-169344. Running Title: Procedural Rationality. ? The main part of this work was undertaken during an academic visit to the Department of Economics of the University of California at Riverside. I am indebted to Prasanta Pattanaik for his invitation, comments and suggestions. I also thank Jorge Alcalde-Unzu, Miguel Angel Ballester, Savvina Chowdhury, Bernard Gress, Marc Kilgour, Jorge Nieto, Esteban Oloriz, and Jongsheng Xu for their comments and help. The usual caveats apply. Financial support by the Spanish Government (SEC2000-0838, SEC2003-08105) is gratefully acknowledged. Abstract. This work analyzes the problem of individual choice under complete uncertainty or ignorance. In this context, each alternative action consists of a set of different possible outcomes with no associated probability distribution. The work examines and defines a class of choice procedures in which: a): the evaluation of sets (actions) is element-induced; and b): a particular assumption of procedural rationality, which is an adaptation of Sen’s  condition, is satisfied. In this framework, some results of characterization show that certain well-known rules for comparing sets of outcomes can be reinterpreted in procedural terms. Keywords: Choice Under Complete Uncertainty. Element-induced Rules. Procedural Rationality. JEL Code: D81. 2 1 Introduction Theories of individual choice under complete uncertainty, or ignorance, assume that the decision maker knows the possible consequences of each alternative action, but that he cannot their probability of occurrence. Several authors, such as Barber`a, Barret and Pattanaik [2], Barber`a and Pattanaik [3], Nitzan and Pattanaik [13], Pattanaik and Peleg [16], Bossert [5,6], and Bossert, Pattanaik and Xu [7] approach this problem by representing each particular choice by means of the set of possible outcomes it generates, and by the axiomatic characterization of rankings over such sets of uncertain outcomes. It is remarkable that almost all of the rankings considered in the related literature, such as the maximin, the maximax, or their lexicographic extensions, share a common characteristic, namely, that given an ordering R over the universe of outcomes, the actions (sets of outcomes) are always compared by induction from the comparison with respect to R of certain elements (outcomes) within the respective sets, such as the worst element in the case of the maximin, the best in the maximax, the second, third, or fourth worst, if the previous ones coincide two by two in the leximin, and so on. The above method of set comparison will be labeled throughout this work as ”element-induced”. This behavior can be naturally understood in procedural terms: We can interpret that the decision maker starts by concentrating on whichever is the representative or focal element of the set for him, and then compares the sets inductively, by contrasting their respective focal elements. If the first-focal elements coincide, then the information they provide cannot lead to a definite preference between the sets. In such a case, the decision maker can directly declare both sets to be indifferent, or, alternatively, look for another feature in the sets to help him to establish a preference, concentrating again on one focal element of each set. If, at this second step, a new tie arises, then the agent faces a similar dilemma: to continue with another step in this sequential process, or once again to declare the sets indifferent. Again, if the agent decides to continue, a similar new tie might arise, and so on. 3 The literature on bounded rationality, as well as experimental psychology, provide intuitive justification for this element-inductive and sequential behavior, and also for the possible existence of a limit in such a sequential process. (See, for example, March and Simon [20,21,22], Beach and Mitchel [4], Payne [14], Russo and Dosher [17] or Payne, Bettman and Johnson [15]).1 This paper aims to explain several well-known orderings over sets, such as the maximin, minimax, leximin, leximax and others, from a procedural perspective. Each of them can be explained as a particular case of an element-induced way to compare sets, but with certain additional peculiarities of a procedural nature. For example, the maximin rule could be interpreted as the result of the behavior of a risk-averse agent who never looks beyond one possible outcome; and the lexicographic extension of the maximin as the case of a risk-averse agent who is in some way recurrent or iterative. Analogous explanations can be figured out for the maximax and its lexicographic extension. Other rules that appear in the related literature, such as the ”max-min” and the ”min-max” (see Arlegi [1] and Bossert, Pattanaik and Xu [7]), which compare sets by looking only at their extreme results, are also interpretable as following certain patterns of behavior based on “focal” or “conspicuous” characteristics of the sets. Not all element-induced rules one might imagine can be supported by such reasonable patterns, however. Let us consider the case of an individual who, in order to evaluate the sets of uncertain outcomes, concentrates on the worst possible one when there is an even number of outcomes in the prospect, and on the best one when there is an odd number, and then extends the preference over these elements to rank their corresponding sets. Undoubtedly, this behavior seeks some procedural logic, but approaches the choice problem in a rather arbitrary way. In order to avoid pathological behaviors like these, a property that is close in spirit to the  condition of rational choice (Sen [18]) will be applied to the way the agent evaluates each set 1 It should be noted that element-induction is not the only possible way to compare and evaluate sets of outcomes. For example, if R is an ordering, then a utility function can be defined over X, and arithmetic rules could be applied. 4 of uncertain outcomes. As will be shown, this condition implies, for example, that if, for whatever reason, x is a focal or representative element in the set {x, y, z}, then x should continue to be so if the set were to shrink to {x, y}. In short, this work investigates the properties of the procedures used to evaluate sets of prospects underlying several well-known rankings of sets. The basic assumption is element-inductiveness. What is formally meant by an element-induced rule is defined in Section 2. Section 3 proposes some additional properties that affect the evaluation process of each set. The central one is the ”Procedural Rationality” condition, which is an adaptation of the classical principle of revealed preference. By this point, the assumptions represent certain procedural conditions on the way in which the decision problem is approached by the agent. In Section 4 some additional axioms that display simple conditions regarding attitudes towards uncertainty or risk are imposed on the relation over sets. These axioms allow us to characterize and explain some known criteria as particular cases of element-induced and procedurally rational rules. 2 Notation and basic definitions Let X be a finite set of outcomes (#X = n) and Z = 2X\;. Each element A of Z is interpreted as a set of possible outcomes associated to a certain action, such that the decision maker does not assign any probability nor any likelihood ranking to any of them. Let R be a linear ordering preference defined over X (reflexive, transitive, complete and antisymmetric). For all A 2 Z, a and a denote, respectively, the worst and bests element of A according to R, and if #A  2, a and a denote, respectively, the second worst and second best elements. Since R is a linear ordering, all of these elements are well-defined and unique for all A 2 Z. The formal concern of this work is the extension of the linear ordering R over X to a binary relation < defined over Z, the asymmetric and symmetric parts of which are denoted by  and  respectively. Given the interpretation of the elements of Z, < is interpreted as reflecting the agent’s preference over alternative actions, each consisting of its corresponding set of possible outcomes. 5 The following orderings over sets, standard in the field, will be considered: – The maximin relation <m is defined by: 8A,B 2 Z,A <m B iff aRb – The maximax relation <M is defined by: 8A,B 2 Z,A <M B iff aRb – The leximin relation <lm is defined by: 8A 2 Z,#A = r, let A = {a1, a2, . . . , ar} s.t. arRar−1R. . .Ra2Ra1. Then, 8A,B 2 Z, A <lm B iff (A = B) or (9l 2 N, l  max{#A,#B} s.t. ai = bi8i < l, and [(alPbl) or (al exists and bl does not exist)]). – The leximax relation <LM is defined by: 8A 2 Z,#A = r, let A = {a1, a2, . . . , ar} s.t. a1Ra2R. . .Rar. Then, 8A,B 2 Z,A <LM B iff (A = B) or (9l 2 N, l  max{#A,#B} s.t. ai = bi8i < l, and [(alPbl) or (al exists and bl does not exist)]) – The min-max relation <mM is defined by: 8A,B 2 Z,A <mM B iff (aPb) or (a = b and aRb) – The max-min relation <Mm is defined by: 8A,B 2 Z,A <mM B iff (aPb) or (a = b and aRb) The notion of evaluation sequence of a set will be central for the subsequent analysis. Let Z be the set of finite sequences involving elements of X. 8A 2 Z let F(A) 2 Z be any finite sequence involving elements of A, that is, F(A) = (f1(A), . . . , fk(A)) such that fi(A) 2 A 8A 2 Z. In our context, F(A) will be interpreted as an evaluation sequence of A. It identifies both the elements of the set that are considered as ”focal” by the agent, and the order in which they are successively considered. #F(A) will denote the number of elements in the sequence, and will represent the agent’s willingness to iterate in order to find successive focal elements. Any mapping F : Z −! Z of evaluation sequences of the same cardinality will be said to be an evaluation procedure. Such cardinality will be said to be the degree of the evaluation procedure.We will denote by (F, k) an evaluation procedure F with a degree of k. For the sake of fluency, we will denote it simply by F whenever its particular degree is irrelevant to the discourse. Definition 1. Let < be a binary relation defined on Z, and let R be a linear 6 ordering defined on X. < is said to be element-induced if there exists an evaluation procedure (F, k) such that 8A,B 2 Z, A < B , (F(A) = F(B)) or (9l  k such that 8i 2 N, i < l, fi(A) = fi(B) and fl(A)Pfl(B)) According to Definition 1, a relation over sets is element-induced if it is possible to find at least one evaluation procedure (F, k) that “explains” or “rationalizes” the relation in the particular terms expressed by the equivalence implication. It is easy to verify that every element-induced binary relation is an ordering (complete, reflexive and transitive). 3 Procedural Rationality Definition 1 provides the formal tools to propose an alternative theory of choice under complete uncertainty based on properties of the evaluation procedures and the elements involved in them. The following will be the central assumption: Procedural Rationality: Let (F, k) be an evaluation procedure. Then, 8A,B 2 Z, s.t. B  A, 8i  k, if (f1(A), . . . , fi−1(A)) = (f1(B), . . . , fi−1(B)); fi(A) = a; and a 2 B, then fi(B) = a. That is, given a set A and a subset B of A, if a set of successive “representative” elements of A coincide with those in B, and if the next representative element in A belongs to B, then it should also be the next representative element in B. In other words, it is plausible to assume that if the agent has been able to identify certain outcomes as representative in a given set A, he should then be able to identify them if they are present in a subset of A.2 In comparison with Chernoff’s classical postulate of rationality (Chernoff [8]) and Sen’s -property of choice functions (Sen [18]), Procedural Rationality concentrates on the coherence with which the decision maker evaluates each set, rather 2 This property recalls the notions of selective or calculated rationality in the bounded rationality theory (see March [12]) and other assumptions in the Prospect Theory (see Kahneman and Tversky [10,23]). 7 than on the way he compares different sets. Thus, it could be said that what is proposed is a model of rational evaluation of sets, rather than a model of rational choice among sets. At this point the following additional definitions can be naturally posed: Definition 2. We will say that “< is a procedurally rational rule” in relation with an evaluation procedure (F, k) if F induces < and satisfies Procedural Rationality. Definition 3. Let < be a procedural rational rule.We say that < is k times iterative if k is the minimal integer for which we can find an evaluation procedure (F, k) that satisfies Procedural Rationality, and such that F induces <.3 The previous definitions allow us to present the following preliminary results: Lemma 4. Let < be a procedurally rational rule defined on Z. If < is a linear ordering, then it is n-times iterative. Proof. The fact that < is procedurally rational implies, by definition, that < is element-induced. Let us suppose that < is not n-times iterative. Then, it ought to be k-times iterative, with k < n. Let (F, k) be the evaluation procedure in relation with which < is k-times iterative. Let F(X) = (f1(X), . . . , fk(X)). Consider X = {x 2 X s.t. x = fi(X) for some i  k}. Since k < n, X  X. Therefore, by Procedural Rationality, fi(X) = fi(X) 8i  k. Since (F, k) induces <, X  X. Therefore < is not a linear ordering, which is a contradiction. ut Lemma 5. <m,<M,<lm,<LM,<mM and <Mm are procedurally rational rules. Lemma 5 establishes that the rules defined in Section 2 are particular cases of procedurally rational rules, and will be used for the characterization results in the next section. The proof is easy but rather tedious. It consists of finding, for each of the rules in the lemma, an evaluation procedure that: (i) induces the rule, and (ii) satisfies Procedural Rationality. A series of such evaluation procedures are defined 3 Note that, by definition, the label ”k times iterative” will implicitly imply Procedural Rationality 8 below for their respective rules. The interested reader is left to check (i) and (ii) in each case. – <m: For all A 2 Z, let F(A) = (f1(A)) = a. – <M: For all A 2 Z, let F(A) = (f1(A)) = a. – <lm: Let n = #X. For all A 2 Z, #A = j, let F(A) = (a1, . . . , aj , n−j . . . , aj) s.t. ajRaj−1R. . . a1. – <LM: Let n = #X. For all A 2 Z, #A = j, let F(A) = (a1, . . . , aj , n−j . . . , aj) s.t. a1Ra2R. . . aj . – <mM: For all A 2 Z, let F(A) = (a, a). – <Mm: For all A 2 Z, let F(A) = (a, a). Proposed below are two additional properties of the evaluation procedures, but, unlike the Procedural Rationality condition, they will not be maintained as a general assumption throughout the model: Iteration Independence: 8A 2 Z, #A = m, fi(A) = f1(A\{f1(A), . . . , fi−1(A)}) 8i  m, and fi(A) = fm(A) if 8i 2 [m, n] Elimination: 8A 2 Z, 8i, j 2 N, i 6= j, if i, j  #A then fi(A) 6= fj(A) Iteration Independence establishes that, for any set A, for any level i of iteration, if that level is lower than the cardinality of the set, then the element considered by the agent in the i-th iteration for A is the same as the one he would have considered in a first iteration for a set consisting of A after removing those elements considered in previous iterations. Furthermore, Iteration Independence also requires that, once the level of iteration surpasses the cardinality m of the set, the focal element remains the same and equal to the m-th focal element until completing n iterations. For example, consider a set A = {a, b, c, d, e}, and let f1(A) = a, f2(A) = b. Then, Iteration Independence requires that f3(A) should be the same as f1({c, d, e}). Or, from a different perspective, the first focal element of {c, d, e} should be the same as the i-focal element of any set where, after removing the previous focal elements, the remaining elements are c, d, and e. A direct implication of Iteration Independence is that the agent always concen- 9 trates successively on different new elements of the set as far as the procedure can be repeated without exhausting the set. Elimination is weaker than Iteration Independence. It requires that, for iteration levels lower than the cardinality level of the set, the focal elements are different. However, unlike Iteration Independence, Elimination does not impose the existence of such focal elements: For example, if k < n, any k-iterative evaluation procedure may satisfy Elimination, but it cannot satisfy Iteration Independence. Lemma 6. Let < be induced by some evaluation procedure F. If F satisfies Iteration Independence and Procedural Rationality, then < is n-times iterative. Proof. First, we will see that if F satisfies Iteration Independence, then the corresponding element-induced relation < is a linear ordering: By element-induction < is an ordering. Then, if < is not a linear ordering, < fails antisymmetry, that is, 9A,B 2 Z s.t. A 6= B and A  B. Hence, by element-induction, F(A) = F(B). Given that B 6= A, whether 9b 2 B s.t. b /2 A or 9a 2 A s.t. a /2 B. In the former case, by Iteration Independence, 9i  n such that fi(B) = b. Then, given that F(A) = F(B), fi(A) = b and b /2 A, which contradicts the definition of F. In the latter case, we reach an analogous contradiction. Now, by Lemma 4, < is n-times iterative. ut 4 Attitudes towards risk and uncertainty: Some axioms on < and characterization results The class of procedurally rational rules contains a wide range of criteria. The agent’s different possible attitudes towards risk play an important role at this stage. Some of these attitudes will be expressed by means of the following axioms, which concern very simple comparisons. Simple Potential Benefit Appeal (SPBAP) 8x, y 2 X s.t. xPy, {x, y}  {y} Simple Risk Aversion (SRAV) 8x, y 2 X s.t. xPy, {x}  {x, y} Simple Risk Neutrality (SRN) 8x, y 2 X s.t. xPy, {x}  {x, y} 10 Simple Uncertainty Aversion (SUAV) 8x, y, z 2 X s.t. xPyPz, {y}  {x, z} Simple Uncertainty Appeal (SUAP) 8x, y, z 2 X s.t. xPyPz, {x, z}  {y} Simple Richness Appeal (SXAP): 8x, y, z 2 X s.t. xPyPz, {x, y, z}  {x, z} Simple Richness Aversion (SXAV): 8x, y, z 2 X s.t. xPyPz, {x, z}  {x, y, z} Simple Richness Neutrality (SXN): 8x, y, z 2 X s.t. xPyPz, {x, y, z}  {x, z} (SPBAP) and (SRAV) are fairly unquestionable in a context of choice under uncertainty. Both axioms together are equivalent to the G¨ardenfors Principle (see G¨ardenfors [9] or Kannai and Peleg [11]). (SRN) is not so plausible in the context, but, as long as it is satisfied by some rules in the field, it will be considered. (SUAV) and (SUAP) are taken from Bossert, Pattanaik and Xu [7]: (SUAV) establishes that the decision maker prefers a situation with two possible outcomes {x, z} rather than a totally certain outcome which is better than z but worse than x. (SUAP) reflects the dual attitude towards uncertainty, and both are empirically plausible in our context. (SXAV) ((SXN)((SXAP)) establishes that any threefold of outcomes is strictly worse (indifferent) (better) than another set consisting only of its best and worst elements. These axioms can be understood as reflecting attitudes of the decision maker towards a very simple diversification of risk within a given range. The main theorems in this section (Theorems 8 to 13) provide characterizations of the criteria defined in Section 2. These characterizations are meant to show that the rules are the result of two kinds of processes: one of a procedural nature that concerns the way the decision maker evaluates each alternative, and another that reflects his attitude towards risk. Theorems 8 to 13 will show that these rules can be plausibly characterized as particular cases of procedurally rational rules that respond both to particular properties of the evaluation procedure, and also to different plausible attitudes towards uncertainty. Thus, the approach departs from the kind of characterizations in the related literature, in which all axioms are imposed directly on <, including many that have nothing to do with attitudes towards risk or uncertainty, and can be interpreted as ”consistency” axioms (see, for example the ”Independence” conditions in Kannai and Peleg [11], Bossert, Pattanaik and Xu [7], 11 Barber`a, Barret and Pattanaik [2], Barber`a and Pattanaik [3], Pattanaik and Peleg [16], or the Consistency and Robustness axioms in Arlegi [1]). Before presenting the theorems, the following Lemma needs to be proven: Lemma 7. If < is k-times iterative in relation with a certain evaluation procedure (F, k) that satisfies Elimination, and such that k > 1, then < satisfies (SRAV) and (SPBAP). Proof : Since k > 1, for all x, y 2 X, f1({x, y}), f2({x, y}), f1({x}), f2({x}), f1({y}) and f2({y}) exist. By the definition of element induction, fi(A) 2 A 8i, 8A 2 Z, thus f1({x}) = f2({x}) = x and f1({y}) = f2({y}) = y. Since (F, k) satisfies Elimination, (f1({x, y}) = x and f2({x, y}) = y) or (f1({x, y}) = y and f2({x, y}) = x). Under either case, by comparing the first two focal elements of {x, y}, {x} and {y} we have, by element induction, {x}  {x, y}  {y}. ut Theorem8. Let < Z × Z. <=<m iff < satisfies (SRAV) and is once iterative. Theorem9. Let < Z × Z. <=<M iff < satisfies (SRN) and is procedurally rational. Theorem10. Let < Z × Z. <=<lm iff < satisfies (SUAV), (SXAV), and is procedurally rational in relation with an iteration independent evaluation procedure F.4 Theorem11. Let < Z × Z. <=<LM iff < satisfies (SUAP), (SXAP), and is procedurally rational in relation with an iteration independent evaluation procedure F. Theorem12. Let < Z×Z. <=<mM iff < satisfies (SUAV), (SXN), and is twice iterative in relation with an eliminative evaluation procedure F. Theorem13. Let < Z×Z. <=<Mm iff < satisfies (SUAP), (SXN), and is twice iterative in relation with an eliminative evaluation procedure F. 4 Sometimes, for the sake of fluency, when an evaluation procedure F satisfies Iteration Independence (Elimination) we will write “F is iteration independent” (eliminative). 12 We will only prove the ”if” parts of Theorems 8 to 13. Since the proofs of the ”only if” parts are easy, they are left for the interested reader. Proof of Theorem 8 (<m): Given that < is once iterative, 9f : Z −! X s.t. A < B , f(A)Rf(B), with f(A) 2 A and f(B) 2 B. We will prove that f(A) = a 8A, that is, <=<m: This is obvious when #A = 1. Let us assume that #A > 1, and let us suppose that f(A) = a 6= a. By (SRAV), {a}  {a, a}. Therefore f({a})Pf({a, a}), that is, f({a}) = a and f({a, a}) = a. By Procedural Rationality f1({a, a}) = a implies that f1(A) 6= a, which results in a contradiction. ut Proof of Theorem 9 (<M): We will first prove the following Claim: If < is procedurally rational and satisfies (SRN), then < is once iterative: Let us suppose this is not the case. Then 8A 2 Z such that #A = 1 (A = {a}), F(A) = (a, k . . ., a) with k > 1. Also, 8A 2 Z such that #A > 1 F(A) = (a, k . . ., a): Note that if this were not true, then 9j 2 N, 1  j  k, s.t. fi(A) = a 8i < j and fj(A) = a 6= a. In that case, by Procedural Rationality, fi({a, a}) = a 8i < j and fj({a, a}) = a, which implies by element induction that {a}  {a, a}, thereby entering into contradiction with (SRN). Therefore, 8A 2 Z, F(A) = (a, k . . ., a). However, there exists another evaluation procedure F0 given by F0(A) = (a) 8A 2 Z that induces exactly the same ordering as F. F0 is procedurally rational and once iterative. Thus, the minimal degree k for which we can find an evaluation procedure that is procedurally rational and that induces < is one. That is, < is once iterative. Since, by hypothesis, < is procedurally rational and satisfies (SRN), then the Claim applies and < is once iterative. From this point the proof is analogous to the proof of <m, except that (SRN) is applied instead of (SRAV) to prove f(A) = a 8A 2 Z. ut Proof of Theorem 10 (<lm): (Outline. Detailed proof in the Appendix) Basically, the proof involves obtaining the kind of evaluation sequences that, besides being procedurally rational and iteration independent, are consistent with (SUAV), (SXAV); and afterwards proving that such evaluation sequences determine, 13 by element-induction, the leximin criterion. The key step in the proof is the first, in which it is proved that the evaluation sequences have to satisfy that 8A s.t. #A  3, f1(A) = a. This is a relatively direct consequence of Procedural Rationality and the uncertainty aversion underlying (SUAV) and (SXAV). From this result, the proof involves the recursive application of Procedural Rationality and Iteration Independence to progressively construct the evaluation sequence of the sets of any cardinality. As a result of the inductive process, there are only two slightly different evaluation procedures that are fully consistent with the hypothesis. Afterwards, it is proved that both possible configurations of the evaluation sequences collapse, by element-induction, into the leximin criterion. Proof of Theorem 11 (<LM): (Outline. Detailed proof in the Appendix) The structure of the proof is very similar to that of Theorem 10. Nevertheless, the differences in the results are rooted on the fact that (SUAP) and (SXAP) display some degree of uncertainty appeal. Thus, the application of (SUAP) and (SXAP) instead of (SUAV) and (SXAV) leads to a result in the initial step of the proof that is dual to that obtained in the previous proof. In particular, it is proved that 8A s.t. #A  3 f1(A) = a. Taking this result, the proof follows parallel steps to obtain the only two possible configurations of the evaluation sequences that are consistent with the axioms, and are the duals of the two obtained in the proof of Theorem 10. Then, it is proven that both possible configurations of the evaluation sequences lead, by element-induction, to the leximax criterion. Proofs of Theorems 12 (<mM) and 13 (<Mm): (Outline. Detailed proofs in the Appendix) As in the proof of Theorem 10, the uncertainty aversion underlying (SUAP) together with (SXN) and Procedural Rationality, allow to prove that 8A s.t. #A  3 f1(A) = a. For the rest of the proof all the hypotheses are used, but, generally speaking, Elimination in this case prevents any element from being repeated in the sequence. On the other hand, (SXN) together with element-induction implies that there cannot be more than two elements in the evaluation sequence of any threefold. Finally, by Procedural Rationality it is possible to prove that f2(A) = a, and that 14 this holds for all sets with more than two elements. Thus the ranking that arises by element-induction from the configuration of the obtained evaluation sequences is <mM. The proof of Theorem 13 largely follows the logic of that of Theorem 12. The differences result from the substitution of axiom (SUAV) by axiom (SUAP). 5 Appendix Proof of Theorem 10: For notational convenience, the elements of sets will be presented in increasing order according to R, that is, A = {a1, a2, . . . , am}, means amPam−1P . . . Pa1. The proof when #X = 1 is trivial. If #X = 2 note that < is procedurally rational in relation with a certain evaluation procedure F that is iteration independent, hence Lemma 6 applies, therefore < is n-times iterative. Also, Iteration Independence implies Elimination, consequently Lemma 7 applies and < satisfies (SRAV) and (SPBAP). Then, by transitivity of <, <=<lm. We will prove the case #X = n with n  3: Since < is n-times iterative, all the conditions of Definition 1 are satisfied with a certain evaluation procedure (F, n). Step 1 . 8A 2 Z such that #A  3 f1(A) = a: Let a 2 A, a 6= a, a. By (SUAV) {a}  {a, a}. This implies, by element-induction that f1({a, a}) = a. Hence, by Procedural Rationality f1(A) 6= a. Let us suppose f1(A) = a 2 A, a 6= a, a. Then, by Procedural Rationality f1({a, a, a} = a. f1({a, a}) = a, hence {a, a, a}  {a, a}, which contradicts (SXAV). Therefore f1(A) = a. Step 2 . Let x, x be, respectively, the best and second best elements in X. Then, 8A 2 Z such that #A = 2 and A 6= {x, x}, F(A) = (a, a, n−1 . . . , a): Since #X  3 and A 6= {x, x}, 9x 2 X\A s.t. xPa. By Step 1 f1({a, x, a}) = a. By Procedural Rationality f1({a, a}) = a. By Iteration Independence f2({a, a}) = a and fi({a, a}) = a for all n > i > 2. Step 3 . Let B= {{x, x}, {x}, {x}}. Then, {x}  {x, x}  {x} and 8B /2 B, 8A 2 B, A  B: By (SRAV) and (SPBAP) {x}  {x, x}  {x}. Thus, it is enough to 15 prove that, 8B /2 B, {x}  B. If #B = 1, then, by element-induction, {x}  B. If #B  2, then, by Step 2, f1(B) = b and, by element-induction {x}  B. Step 4 . 8A 2 Z such that #A  3, and such that {x, x} * A, F(A) = (a1, a2, . . . , am, n−m . . . , am): The proof is easy the recursive application of Step 1, Iteration Independence and Step 2. Step 5 . 8A 2 Z, (A = {a1, . . . , am}) such that m  3, am = x and am−1 = x, F(A) = (a1, a2, . . . , am−2, am−1, am, n−m . . . , am) or otherwise 8A 2 Z, (A = {a1, . . . , am}) s.t. m  3, am = x and am−1 = x, F(A) = (a1, a2, . . . , am−2, am, am−1, n−m . . . , am−1): By recursively applying Iteration Independence and Step 1, it is easily proven that 8A 2 Z, (A = {a1, . . . , am}) such that m  3, fi(A) = ai 8i < m−1. Therefore A\{f1(A), . . . , fm−2(A)} = {am−1, am}. Given that am = x and am−1 = x, then let us see which is fm−1(A): By Iteration Independence fm−1(A) = f1({x, x}). If f1({x, x}) = x(= am−1), then, by Iteration Independence f2({x, x}) = x(= am). Therefore, by recursively applying Iteration Independence, 8A 2 Z s.t. m  3, am = x and am−1 = x, F(A) = (a1, a2, . . . , am−2, am−1, am, n−m . . . , am). If f1({x, x}) = x(= am), we obtain analogously that 8A 2 Z s.t. m  3, am = x, and am−1 = x, F(A) = (a1, a2, . . . , am−2, am, am−1, n−m . . . , am−1). Step 6 . 8A,B 2 Z A lm B implies A  B: A lm B implies A = B. By reflexivity of <, A  B. Step 7 . 8A,B 2 Z A lm B implies A  B: By Step 3, if A,B 2 B or (A 2 B and B /2 B) A lm B implies A  B. Also by Step 3, B 2 B and A /2 B enters into contradiction with A lm B. Therefore, it is enough to prove that, for all A,B /2 B, A lm B implies A  B: Taking into account Steps 1 to 5, and also that, by Iteration Independence, F(A) = {a, n . . ., a} for all singletons, we can assert that: either 8A 2 Z\B F(A) = (a1, a2, . . . , am−2, am−1, am, n−m . . . , am) (Case 1 ), or 8A 2 Z\B (F(A) = (a1, a2, . . . , am−2, am−1, am, n−m . . . , am) if {x, x} * A) and (F(A) = (a1, a2, . . . , am−2, am, am−1, n−m . . . , am−1) if {x, x}  A) (Case 2 ). The proof from this point is easy but becomes very tedious. It only remains to be proven that whether under Case 1 or Case 2, by element-induction, the criterion 16 that emerges is lm. The proof is left to the reader. ut Proof of Theorem 11: Unlike the previous proof, throughout this one the extensive presentation of the sets will be done in decreasing order according to R, that is, 8A 2 Z, #A = m, A = {a1, a2, . . . , am} means a1Pa2P . . . Pam. The case #X = 1 is degenerate. If #X = 2, since Lemma 6 and Lemma 7 apply for <, < satisfies (SRAV) and (SPBAP). Therefore, by transitivity of <, <=<LM. We will prove the case #X = n with n  3. Since < is n-times iterative, all the conditions of Definition 1 are satisfied for a certain evaluation procedure (F, k) such that k = n. Step 1 . 8A 2 Z such that #A  3, f1(A) = a: Let a 2 A, a 6= a, a. By (SUAP) {a, a}  {a}. By element-induction, this implies that f1({a, a}) = a. By Procedural Rationality f1(A) 6= a. Let us suppose f1(A) = a 2 A, a 6= a, a. Then, by Procedural Rationality f1({a, a, a} = a. f1({a, a}) = a, hence {a, a}  {a, a, a}, which contradicts (SXAP). From this point on the proof is analogous to that of Theorem 10, according to the following parallel steps: Step 2 . Let x, x be, respectively, the worst and second worst elements in X. Then, 8A 2 Z such that #A = 2 and A 6= {x, x}, F(A) = (a, a, n−1 . . . , a). Step 3 . Let W= {{x, x}, {x}, {x}}. Then, {x}  {x, x}  {x} and 8A /2 W, 8B 2 W, A  B. Step 4 . 8A 2 Z, (A = {a1, . . . , am}) such that m  3 and {x, x} * A F(A) = (a1, a2, . . . , am, n−m . . . , am). Step 5 . 8A 2 Z, (A = {a1, . . . , am}) such that m  3, am = x and am−1 = x, F(A) = (a1, a2, . . . , am−2, am−1, am, n−m . . . , am) or otherwise 8A 2 Z, (A = {a1, . . . , am}) s.t. m  3, am = x and am−1 = x, F(A) = (a1, a2, . . . , am−2, am, am−1, n−m . . . , am−1). Step 6 . 8A,B 2 Z A LM B implies A  B. Step 7 . 8A,B 2 Z A LM B implies A  B: Proof of Theorem 12: As in the previous theorems, the case #X = 1 is degenerate. If #X = 2, since < is twice iterative in relation with some eliminative evaluation procedure F, Lemma 7 applies and < satisfies (SRAV) and (SPBAP). Then, by transitivity of <, <=<mM. We will prove the case #X = n with n  3. 17 By hypothesis, < satisfies all the conditions of Definition 1 in relation with a certain evaluation procedure (F, 2) that satisfies Elimination. Step 1 . 8A 2 Z such that #A  3, f1(A) = a: The proof is, literally, the proof of Step 1 of Theorem 10 just by replacing “(SXAV)” with “(SXN)”. Step 2 . 8A 2 Z such that #A = 2 and such that A 6= {x, x}, F(A) = (a, a): Since A 6= {x, x}, 9x 2 X\A s.t. xPa. By Step 1 f1({a, x, a}) = a. Therefore, by Procedural Rationality, f1({a, a}) = a. By Elimination f2(A) = a. Step 3 . 8A 2 Z such that #A  3, f2(A) = a: By Step 1 and Elimination f2(A) 6= a. Let us suppose f2(A) = a 2 A, a 6= a. Let us take the set {a, a, a}. By Step 1 f1({a, a, a}) = a. By (SXN) {a, a, a}  {a, a}. By Step 2 F({a, a}) = (a, a). Therefore, by element-induction f2({a, a, a}) = a. Since, by Step 1, f1(A) = a, by Procedural Rationality f2(A) = a 6= a, which is a contradiction. Step 4 . Let B= {{x, x}, {x}, {x}}. Then, {x}  {x, x}  {x} and 8B /2 B, 8A 2 B, A  B: < is twice iterative in relation with F, and F is eliminative, hence, by Lemma 7, < satisfies (SRAV) and (SPBAP). Then the proof is similar to the proof of Step 3 in Theorem 10. Step 5 . 8A 2 Z (A mM B implies A  B) and (A mM B implies A  B): By Step 4, if A,B 2 B or (A 2 B and B /2 B) then (A mM B implies A  B) and (A mM B implies A  B). Note that A <mM B is incompatible with (A /2 B and B 2 B). Therefore, it is enough to prove that for all A,B /2 B (A mM B implies A  B) and (A mM B implies A  B). By twice iterativeness and Steps 1 to 4, 8A,B 2 Z F(A) = (a, a) and F(B) = (b, b). If A mM B, then a = b and a = b. Therefore, by element-induction, A  B. If A mM B, then aPb or (a = b and aPb). Hence, by element-induction, A  B. ut Proof of Theorem 13: The proof is closely analogous to the proof of Theorem 12. In particular, the crucial difference is that Step 1 states as follows: 8A 2 Z such that #A  3, f1(A) = a. The proof of this statement is, literally, the proof of Step 1 of Theorem 11 just by replacing “(SXAP)” with “(SXN)”. From this point on, the following steps have to be proved in a way parallel to that employed in the proof of Theorem 13: 18 Step 2 . 8A 2 Z such that #A = 2 and such that A 6= {x, x}, f1(A) = a and f2(A) = a. Step 3 . 8A 2 Z such that #A  3, f2(A) = a. Step 4 . Let W ={{x, x}, {x}, {x}}. Then, {x}  {x, x}  {x} and 8A /2 W, 8B 2 W, A  B. Step 5 . 8A 2 Z (A Mm B implies A  B) and (A Mm B implies A  B). ut The proofs of the independence of the conditions used in Theorems 8, 9, 10, 11, 12 and 13 are left for the interested reader and available upon request. References 1. R. Arlegi, A Note on Bossert, Pattanaik, and Xu’s ‘Choice under complete uncertainty: axiomatic characterization of some decision rules’, Econ. Theor. 22 (2003), 219-225. 6. S. Barber`a, C. R. Barret, and P. K. Pattanaik, On some axioms for ranking sets of alternatives, J. Econ. Theory 33 (1984), 301-308. 8. S. Barber`a and P. K. Pattanaik, Extending an order on a set to the power set: some remarks on Kannai and Peleg’s approach, J. Econ. Theory 32 (1984), 185-191. 9. L. R. Beach and T. R. Mitchell, A contingency model for the selection of decision strategies, Acad. Manage. Re. 3 (1978), 439-449. 11. W. Bossert, Preference extension rules for ranking sets of alternatives with a fixed cardinality, Theor. Decis. 39 (1995), 301-317. 12. W. Bossert, Uncertainty aversion in non-probabilistic decision models, Math. Soc. Sci. 34 (1997), 191-203. 13. W. Bossert, P. K. Pattanaik, and Y. Xu, Choice under complete uncertainty: axiomatic characterization of some decision rules, Econ. Theor. 16(2) (2000), 295-312. 15. H. Chernoff, Rational selection of decision functions, Econometrica 22 (1954), 422-443. 21. P. G¨ardenfors, Manipulability of social choice functions, J. Econ. Theory 13 (1976), 217-218. 25. D. Kahneman and A. Tversky, Prospect Theory: An analysis of decisions under risk, Econometrica 47 (1979), 263-291. 26. Y. Kannai and B. Peleg, A note on the extension of an order on a set to the power set, J. Econ. Theory 32 (1984), 172-175. 28. J. G. March, Bounded rationality, ambiguity, and the engineering of choice, Bell Journal of Economics 9 (1978), 587-608. 19 31. S. Nitzan and P. K. Pattanaik, Median-based extensions of an ordering over a set to the power set: an axiomatic characterization, J. Econ. Theory 34 (1984), 252-261. 32. J. W. Payne, Contingent decision behaviour, Psychol. Bulletin 92 (1982), 382-402. 33. J. W. Payne, J. R. Bettman, and J. E. Johnson, Adaptative strategy selection in decision making, J. Exp. Psychol. Learn. 14(3) (1988), 534-552. 34. P. K. Pattanaik and B. Peleg, An axiomatic characterization of the lexicographic maximin extension of an ordering over a set to the power set, Soc. Choice Welfare 1 (1984) 113-122. 36. J. E. Russo and B. A. Dosher, Strategies for multiattribute binary choice, J. Exp. Psychol. Learn., 9 (1983), 676-696. 37. A. K. Sen, Choice functions and revealed preferences, Rev. Econ. Stud. 38 (1971), 307-317. 38. A. K. Sen, Internal consistency of choice, Econometrica 61 (1993), 495-521. 41. H. A. Simon, A behavioral model of rational choice, Q. J. Econ. 69 (1955), 99-118. 42. H. A. Simon, Rational choice and the structure of the environment, Psychol. Review 63 (1956), 129-138. 43. H. A. Simon, From substantive to procedural rationality, in “Methods and Appraisal in Economics” (S.J. Latis, Eds), pp. 129-148, Cambridge University Press, New York, 1976. 44. A. Tversky and D. Kahneman, The framing of decisions and the Psychology of choice, Science 211 (1981), 453-458. This article was processed using the LATEX macro package with LLNCS style 20