Chapter 5: Decision Making Under Uncertainty

Chapter 5 Decision Making under Uncertainty In previous lectures, we considered decision problems in which the decision maker does not know the consequences of his choices but he is given the probability of each consequence under each choice. In most economic applications, such a probability is not given. For example, in a given game, a player cares not only about what he plays but also about what other players play. Hence, the description of consequences include the strategy profiles. In that case, in order to fit in that framework, we would need to give other players’ mixed strategy profiles in the description of the game, making Game Theoretical analysis moot. Likewise in a market, the price is formed according to the collective actions of all market participants, and hence the price distribution is not given. In all these problems, the decision makers hold subjective beliefs about the unknown aspects of the problem and use these beliefs in making their decisions. For example, a player chooses his strategy according to his beliefs about what other players may play, and he may reach these beliefs through a combination of reasoning and the knowledge of past behavior. This is called decision making under uncertainty. As established by Savage and the others, under some reasonable assumptions, such subjective beliefs can be represented by a probability distribution, in the sense that the decision maker finds an event more likely than another if and only if the probability distribution assigns higher probability to the former event than latter. In that case, using the probability distribution, one can convert a decision problem under uncertainty to a decision problem under risk, and apply the analysis of the previous lecture. In this lecture, I will describe this program in detail. In particular, I will describe 35 36 CHAPTER 5. DECISION MAKING UNDER UNCERTAINTY • the conditions such consistent beliefs impose on the preferences, • the elicitation of the beliefs from the preferences, and • the representation of the beliefs by a probability distribution. 5.1 Acts, States, Consequences, and Expected Utility Representation Consider a finite set C of consequences. Let S be the set of all states of the world. Take a set F of acts f : S → C as the set of alternatives (i.e., set X = F ). Each state s ∈ S describes all the relevant aspects of the world, hence the states are mutually exclusive. Moreover, the consequence f (s) of act f depends on the true state of the world. Hence, the decision maker may be uncertain about the consequences of his acts. Recall that the decision maker cares only about the consequences, but he needs to choose an act. Example 5.1 (Game as a Decision Problem) Consider a complete information game with set N = {1, . . . , n} of players in which each player i ∈ N has a strategy space Si . The decision problem of a player i can be described as follows. Since he cares about the strategy profiles, the set of consequences is C = S1 × · · · × Sn . Since he does not know what the other players play, the set of states is S = S−i ≡ j=i = Sj . Since he chooses among his strategies, the set of acts is F = Si , where each strategy si is represented as a function s−i → (si , s−i ). (Here, (si , s−i ) is the strategy profile in which i plays si and the others play s−i .) Traditionally, a complete-information game is defined by also including the VNM utility function ui : S1 × · · · × Sn → R for each player. Fixing such a utility function is equivalent to fixing the preferences on all lotteries on S1 × · · · × Sn . Note that above example is only a way to model a player’s uncertainty in a game, although it seems to be most direct way to model a player’s uncertainty about the others’ strategies. Depending on the richness of the player’s theories in his decision making, one may consider richer state spaces. For example, the player may think that the other players react to whether it is sunny or rainy in their decisions. In that case, one would include the state of the weather in the space space, e.g., by taking S = 5.2. ANSCOMBE-AUMANN MODEL 37 S−i × {sunny, rainy}. Sometimes, it may also be useful to consider a state space that does not directly refer to the others’ strategies. We would like to represent the decision maker’s preference relation U : F → R such that on F by some U (f ) ≡ E [u ◦ f ] (in the sense of (OR)) where u : C → R is a “utility function” on C and E is an expectation operator on S. That is, we want f g ⇐⇒ U (f ) ≡ E [u ◦ f ] ≥ E [u ◦ g] ≡ U (g) . (EUR) In the formulation of Von Neumann and Morgenstern, the probability distribution (and hence the expectation operator E) is objectively given. In fact, acts are formulated as lotteries, i.e., probability distributions on C. In such a world, as we have seen in the last lecture, is representable in the sense of (EUR) if and only if it is a continuous preference relation and satisfies the Independence Axiom. For the cases of our concern in this lecture, there is no objectively given probability distribution on S. We therefore need to determine the decision maker’s (subjective) probability assessment on S. This is done in two important formulations. First, Savage carefully elicits the beliefs and represents them by a probability distribution in a world with no objective probability is given. Second, Anscombe and Aumann simply uses indifference between some lotteries and acts to elicit preferences. I will first describe Anscombe and Aumann’s tractable model, and then present Savage’s deeper and more useful analysis. 5.2 Anscombe-Aumann Model Anscombe and Aumann consider a tractable model in which the decision maker’s subjective probability assessments are determined using his attitudes towards the lotteries (with objectively given probabilities) as well as towards the acts with uncertain consequences. To do this, they consider the decision maker’s preferences on the set P S of all “acts” whose outcomes are lotteries on C, where P is the set of all lotteries (probability distributions on C). In the language defined above, they assume that the consequences and the decision maker’s preferences on the set of consequences have the special structure of Von-Neumann and Morgenstern model. 38 CHAPTER 5. DECISION MAKING UNDER UNCERTAINTY Note that an act f assigns a probability f (x|s) on any consequence x ∈ C at any state s ∈ S. The expected utility representation in this set up is given by f g ⇐⇒  u (x) f (x|s) p (s) . s∈S x∈C In this set up, it is straightforward to determine the decision maker’s probability assessments. Consider a subset A of S and any two consequences x, y ∈ C with x  y. Consider the act fA that yields the sure lottery of x on A,1 and the sure lottery of y on S\A. That is, fA (x|s) = 1 for any s ∈ A and fA (y|s) = 1 for any s ∈ A. (See Figure 5.1.) Under some continuity assumptions (which are also necessary for representability), there exists some π A ∈ [0, 1] such that the decision maker is indifferent between fA and the act gA with gA (x|s) = π A and gA (y|s) = 1 − π A at each s ∈ S. That is, regardless of the state, gA yields the lottery pA that gives x with probability π A and y with probability 1 − π A . Then, π A is the (subjective) probability the decision maker assigns to the event A – under the assumption that π A does not depend on which alternatives x and y are used. In this way, one obtains a probability distribution on S. Using the theory of Von Neumann and Morgenstern, one then obtains a representation theorem in this extended space where we have both subjective uncertainty and objectively given risk. While this is a tractable model, it has two major limitation. First, the analysis generates little insights into how one should think about the subjective beliefs and their representation through a probability distribution. Second, in many decision problems there may not be relevant intrinsic events that have objectively given probabilities and rich enough to determine the beliefs on the events the decision maker is uncertain about. 5.3 Savage Model Savage develops a theory with purely subjective uncertainty. Without using any objectively given probabilities, under certain assumptions of “tightness”, he derives a unique probability distribution on S that represent the decision maker’s beliefs embedded in his preferences, and then using the theory of Von Neumann and Morgenstern he obtain a representation theorem – in which both utility function and the beliefs are derived from the preferences. 1 That is, fA (s) = x whenever s ∈ A where the lottery x assigns probability 1 to the consequence x. 5.3. SAVAGE MODEL 39 fA  x  1 x x y  1 y y A S\A  gA  πA    PA A S\A    x 1 − πA y PA  Figure 5.1: Figure for Anscombe and Aumann 40 CHAPTER 5. DECISION MAKING UNDER UNCERTAINTY Take a set S of states s of the world, a finite set C of consequences (x, y, z), and take the set F = C S of acts f : S → C as the set of alternatives. Fix a relation would like to find necessary and sufficient conditions on so that on F . We can be represented by some U in the sense of (EUR); i.e., U (f ) = E[u ◦ f ]. In this representation, both the utility function u : C → R and the probability distribution p on S (which determines E) are derived from P1 . Theorems 1.2 and 1.3 give us the first necessary condition: is a preference relation. The second condition is the central piece of Savage’s theory: 5.3.1 The Sure-thing Principle The Sure-thing Principle If a decision maker prefers some act f to some act g when he knows that some event A ⊂ S occurs, and if he prefers f to g when he knows that A does not occur, then he must prefer f to g when he does not know whether A occurs or not. This is the informal statement of the sure-thing principle. Once we determine the decision maker’s probability assessments, the sure-thing principle will give us the Independence Axiom, Axiom 2.3, of Von Neumann and Morgenstern. The following formulation of Savage, P2, not only implies this informal statement, but also allows us to state it formally, by allowing us to define conditional preferences. (The conditional preferences are also used to define the beliefs.) P 2 Let f, f  , g, g  ∈ F and B ⊂ S be such that f (s) = f  (s) and g (s) = g  (s) at each s ∈ B and f (s) = g (s) and f  (s) = g  (s) at each s ∈ B. If f g, then f  g. 5.3. SAVAGE MODEL 5.3.2 41 Conditional preferences Using P2, we can define the conditional preferences as follows. Given any f, g, h ∈ F h h and g|B by and B ⊂ S, define acts f|B if s ∈ B f (s) f|hB (s) = h (s) otherwise and g (s) h g|B (s) = if s ∈ B h (s) otherwise . h h and g|B agree with f and g, respectively, on B, but when B does not occur, That is, f|B they yield the same default act h. Definition 5.1 (Conditional Preferences) f P2 guarantees that f g given B iff f|hB g|hB . g given B is well-defined, i.e., it does not depend on the   h h and g|B accordingly. Check default act h. To see this, take any h ∈ F , and define f|B that   f|hB (s) ≡ f (s) ≡ f|hB (s) and g|hB (s) ≡ g (s) ≡ g|hB (s) at each s ∈ B and   f|hB (s) ≡ h (s) ≡ g|hB (s) and f|hB (s) ≡ h (s) ≡ g|hB (s) at each s ∈  B. Therefore, by P2, f|hB  g|hB iff f|hB  g|hB . Note that P2 precisely states that f g given B is well-defined. To see this, take f  h h and g  = g|B . Moreover, the and g  arbitrarily. Set h = f and h = g  . Clearly, f = f|B  conditions in P2 define f  and g as f  = f|hB and g = g|hB . Thus, the conclusion of P2, “if f g, then f  g  ”, is the same as “if f|hB  g|hB , then f|hB  g|hB . Exercise 5.1 Show that the informal statement of the sure-thing principle is formally true: given any f1 , f2 ∈ F , and any B ⊆ S, [(f1 f2 given B) and (f1 f2 given S\B)] ⇒ [f1 f2 ] . f1 f1 f2 f2 f2 f1 [Hint: define f := f1 = f1|B = f1|S\B , g  := f2 = f2|B = f2|S\B , f  := f1|B = f2|S\B , and f2 f1 g := f2|B = f1|S\B . Notice that you do not need to invoke P2 (explicitly).] 42 CHAPTER 5. DECISION MAKING UNDER UNCERTAINTY Null Events Imagine that the decision maker remains indifference towards any changes made to an action within an event B. Namely, for any acts f and g, the decision maker remains indifferent between f and g, so long as f and g are identical on S\B, no matter how widely differ on B. In that case, it is plausible to deduce that the decision maker does not think that event B obtains. Such events are called null. Definition 5.2 An event B is said to be null if and only if f ∼ g given B for all f, g ∈ F . Recall that our aim is to develop a theory that relates the preferences on the acts with uncertain consequences to the preferences on the consequences. (The preference relation we say x on F is extended to C by embedding C into F as constant acts. That is, x iff f f  where f and f  are constant acts that take values x and x , respectively.) The next postulate does this for conditional preferences: P 3 Given any f, f  ∈ F , x, x ∈ C, and B ⊂ S, if f ≡ x, f  ≡ x , and B is not null, then f f  given B ⇐⇒ x x . For B = S, P3 is rather trivial, a matter of definition of a consequence as a constant act. When B =  S, P3 is needed as an independent postulate. Because the conditional preferences are defined by setting the outcomes of the acts to the same default act when the event does not occur, and two distinct constant acts cannot take the same value. 5.3.3 Representing beliefs with qualitative probabilities We want to determine the decision maker’s beliefs reflected in . Towards this end, given any two events A and B, we want to determine which event the decision maker thinks is more likely. To do this, take any two consequences x, x ∈ C with x  x . The decision maker is asked to choose between the two gambles (acts) fA and fB with fA (s) = fB (s) = x if s ∈ A , if s ∈ B . x otherwise x x  otherwise (5.1) 5.3. SAVAGE MODEL 43 If the decision maker prefers fA to fB , we can infer that he finds event A more likely than event B, for he prefers to get the “prize” when A occurs, rather than when B occurs. Definition 5.3 Take any x, x ∈ C with x  x . Given any A, B ⊆ S, A is said to be at least as likely as B (denoted by A ˙ B) if and only if fA fB , where fA and fB defined by (5.1). We want to make sure that this yields well-defined beliefs. That is, it should not be the case that, when we use some x and x , we infer that decision maker finds A strictly more likely than B, but when we use some other y and y  , we infer that he finds B strictly more likely than A. Then next assumption guaranties that ˙ is indeed well-defined. P 4 Given any x, x , y, y  ∈ C with x  x and y  y  , define fA , fB , gA , gB by fA (s) = fB (s) = x if s ∈ A , gA (s) = if s ∈ B , gB (s) = x otherwise x x  otherwise y if s ∈ A y  otherwise y y  if s ∈ B otherwise . Then, fA fB ⇐⇒ gA gB . Finally, make sure that we can find x and x with x  x : P 5 There exist some x, x ∈ C such that x  x . We have now a well-defined relation ˙ that determines which of two events is more likely. It turns out that, ˙ is a qualitative probability, defined as follows: Definition 5.4 A relation ˙ between the events is said to be a qualitative probability iff 1. ˙ is complete and transitive; 2. for any B, C, D ⊂ S with B ∩ D = C ∩ D = ∅, B ˙ C ⇐⇒ B ∪ D ˙ C ∪ D; 44 CHAPTER 5. DECISION MAKING UNDER UNCERTAINTY ˙ 3. B ˙ ∅ for each B ⊂ S, and S ∅. Exercise 5.2 Show that, under the postulates P1-P5, the relation ˙ defined in Definition 5.3 is a qualitative probability. 5.3.4 Quantifying the qualitative probability assessments Savage uses finitely-additive probability measures on the discrete sigma-algebra: Definition 5.5 A probability measure is any function p : 2S → [0, 1] with 1. if B ∩ C = ∅, then p (B ∪ C) = p (B) + p (C), and 2. p (S) = 1. We would like to represent our qualitative probability ˙ with a (quantitative) probability measure p in the sense that B ˙ C ⇐⇒ p (B) ≥ p (C) ∀B, C ⊆ S. (QPR) Exercise 5.3 Show that, if a relation ˙ can be represented by a probability measure, then ˙ must be a qualitative probability. When S is finite, since ˙ is complete and transitive, by Theorem 1.2, it can be represented by some function p, but there might be no such function satisfying the condition 1 in the definition of probability measure. Moreover, S is typically infinite. (Incidentally, the theory that follows requires S to be infinite.) We are interested in the preferences that can be considered coming from a decision maker who evaluates the acts with respect to their expected utility, using a utility function on C and a probability measure on S that he has in his mind. Our task at this point is to find what probability p (B) he assigns to some arbitrary event B. Imagine that we ask this person whether p (B) ≥ 1/2. Depending on his sincere answer, we determine whether p (B) ∈ [1/2) or p (B) ∈ [0, 1/2, 1]. Given the interval, we ask whether p (B) is in the upper half or the lower half of this interval, and depending on his answer, we obtain a smaller interval that contains p (B). We do this ad infinitum. Since the length of the interval at the nth iteration is 1/2n , we learn p (B) at the end. 5.3. SAVAGE MODEL 45 For example, let’s say that p (B) = 0.77. We first ask if p (B) ≥ 1/2. He says Yes. We ask now if p (B) ≥ 3/4. He says Yes. We then ask if p (B) ≥ 7/8. He says No. Now, we ask if p (B) ≥ 13/16 = (3/4 + 7/8) /2. He says No again. We now ask if p (B) ≥ 25/32 = (3/4 + 7/8) /2. He says No. Now we ask if p (B) ≥ 49/64. He says Yes now. At this point we know that 49/64=0.765 ˜ ≤ p (B) < 25/32=0.781. ˜ As we ask further we get a better answer. This is what we will do, albeit in a very abstract setup. Assume that S is infinitely divisible under ˙ . That is, S has ˙ D12 , • a partition {D11 , D12 } with D11 ∪ D12 = S and D11 ∼ ˙ D22 ∼ ˙ D23 ∼ ˙ D24 , • a partition {D21 , D22 , D23 , D24 } with D21 ∪D22 = D11 , D23 ∪D24 = D12 , and D21 ∼ . • ..  n • a partition Dn1 , · · · , Dn2 with Dn1 ∪ Dn2 = Dn1 −1 , . . . , Dn2k−1 ∪ Dn2k = Dnk−1 , . . ., n ˙ · · · ∼D ˙ n2 , and Dn1 ∼ . • .. ad infinitum. S D11 D21 .. . D12 D22 .. . D23 .. . D24 .. . Exercise 5.4 Check that, if ˙ is represented by some p, then we must have p (Dnr ) = 1/2n . Given any event B, for each n, define k (n, B) = max r|B ˙ r  Dni , i=1 where we use the convention that ∪ri=1 Dni = ∅ whenever r < 1. Define p (B) := lim n→∞ k (n, B) . 2n (5.2) 46 CHAPTER 5. DECISION MAKING UNDER UNCERTAINTY Check that k (n, B) /2n ∈ [0, 1] is non-decreasing in n. Therefore, limn→∞ k (n, B) /2n is well-defined. Since ˙ is transitive, if B ˙ C, then k (n, B) ≥ k (n, C) for each n, yielding p (B) ≥ p (C). This proves the =⇒ part of (QPR) under the assumption that S is infinitely divisible. The other part (⇐) is implied by the following assumption: ˙C∪ ˙ C, then there exists a finite partition {D 1 , . . . , Dn } of S such that B P 6’ If B Dr for each r. Under P1-P5, P6’ also implies that S is infinitely divisible. (See the definition of “tight” and Theorems 3 and 4 in Savage.) Therefore, P1-P6’ imply (QPR), where p is defined by (5.2). Exercise 5.5 Check that, if ˙ is represented by some p , then k (n, B) k (n, B) + 1 ≤ p (B) < n 2n 2 at each B. Hence, if both p and p represent ˙ , then p = p . Postulate 6 will be somewhat stronger than P6’. (It is also used to obtain the continuity axiom of Von Neumann and Morgenstern.) P 6 Given any x ∈ C, and any g, h ∈ F with g  h, there exists a partition {D1 , . . . , Dn } of S such that g  hxi and gix  h for each i ≤ n where hxi (s) = x if s ∈ Di h (s) otherwise and gix (s) = x if s ∈ Di g (s) otherwise . Take g = fB and h = fC (defined in (5.1)) to obtain P6’. Theorem 5.1 Under P1-P6, there exists a unique probability measure p such that B ˙ C ⇐⇒ p (B) ≥ p (C) ∀B, C ⊆ S. (QPR) 5.3. SAVAGE MODEL 5.3.5 47 Expected Utility Representation In Chapter 5, Savage shows that, when C is finite, Postulates P1-P6 imply Axioms 2.12.3 of Von Neumann and Morgenstern –as well as their modeling assumptions such as only the probability distributions on the set of prizes matter. In this way, he obtains the following Theorem:2 Theorem 5.2 Assume that C is finite. Under P1-P6, there exist a utility function u : C → R and a probability measure p : 2S → [0, 1] such that f g ⇐⇒  c∈C p ({s|f (s) = c}) u (c) ≥  p ({s|g (s) = c}) u (c) c∈C for each f, g ∈ F . 2 For the inifinte C, we need the infinite version of the sure-thing principle: P 7 If we have f g (s) given B for each s ∈ B, then f for each s ∈ B, then f g given B. Likewise, if f (s) g given B. Under P1-P7, we get the expected utility representation for general case. g given B