Notes

Expectation is a standard notion in the context of probability and is discussed in all standard texts on probability. Proposition 5.1.1 is proved in all of the standard texts. Proposition 5.1.2 is also well known. Walley [1991] gives a proof; he also gives the characterization of Exercise 5.5.

Huber [1981] discusses upper and lower expectation and proves Proposition 5.2.1, Theorem 5.2.2, and a number of other related results. The characterization of lower expectation given in Exercise 5.9 is due to Walley [1991]. Choquet [1953] used (5.9) to define expectation for capacities. (Recall from the notes to Chapter 2 that a belief function is an infinitely monotone capacity.)

Walley's notion of lower and upper previsions, mentioned in the notes to Chapter 2, are essentially lower and upper expectations of sets of probability measures. (Technically, lower and upper expectations are what Walley calls coherent lower and upper previsions, respectively.) Thus, lower and upper previsions are really expectations (and associate numbers with random variables, not events). There is a close connection between sets of probability measures and lower and upper expectations. Proposition 5.2.1 and Theorem 5.2.2 show that lower and upper expectations can be obtained from sets of probability measures and vice versa. In fact, the connection is even stronger than that. Theorem 5.2.2 actually provides a one-to-one mapping from closed convex sets of probability measures to lower and upper expectations. That is, if is a closed convex set, then is the largest set ′ of probability measures such that E = E_′. Thus, lower and upper expectations (and coherent lower and upper previsions) can be identified with closed convex sets of probability measures. It then follows from Example 5.2.10 and Exercise 5.10 that lower and upper previsions are strictly more expressive than lower and upper probability, but less expressive than Pl.

As discussed in the notes to Chapter 2, sets of probabilities are often taken to be convex (and, in fact, closed as well). Moreover, there are cases where there is no loss of generality in assuming that a set is closed and convex (or, equivalently, in replacing a set by the least closed convex set that contains it). On the other hand, as observed in the notes to Chapter 2, there are cases where it does not seem appropriate to represent uncertainty using a convex set. Exercise 4.12 shows that a set of probabilities and its convex hull act differently with respect to determination of independencies.

Walley [1991] discusses both the philosophical and technical issues involved in using lower and upper previsions as a way of representing uncertainty in great detail. His book is perhaps the most thorough account of an alternative approach to reasoning about uncertainty that can be viewed as generalizing both probability measures and belief functions.

Dempster [1967] discusses expectation for belief functions. The fact that expected belief satisfies comonotonic additivity was shown by Dellacherie [1970]; Proposition 5.2.5 and Theorem 5.2.8 are due to Schmeidler [1986].

Inner and outer expectations do not appear to have been studied in the literature. Lemma 5.2.13 was observed by Dieter Denneberg [personal communication, 2002].

Dubois and Prade [1987] discuss expectation for possibility measures, using the same approach as considered here for belief functions, namely, E_Poss. Other approaches to defining expectation for possibility measures have been discussed. Some involve using functions ⊕ and ⊗ (defined on ℝ), somewhat in the spirit of the notion of expected plausibility defined here; see, for example, [Benvenuti and Mesiar 2000]. Results essentially like Theorem 5.2.16 are also proved by Benvenuti and Mesiar [2000]. Luce [1990; 2000] also considers general additive-like operations applied to utilities.

Decision theory is also a well-established research area; some book-length treatments include [Jeffrey 1983; Kreps 1988; Luce and Raiffa 1957; Resnik 1987; Savage 1954]. Savage's [1954] result is the standard defense for identifying utility maximization with rationality. (As discussed in the notes to Chapter 2, it is also viewed as a defense of probability.) Of course, there has been a great deal of criticism of Savage's assumptions; see, for example, [Shafer 1986] for a discussion and critique, as well as related references. Moreover, there are many empirical observations that indicate that humans do not act in accord with Savage's postulates; perhaps the best-known examples of violations are those of Allais [1953] and Ellsberg [1961]. Camerer and Weber [1992] and Kagel and Roth [1995] discuss the experimental evidence.

In the economics literature, Knight [1921] already drew a distinction between decision making under risk (roughly speaking, where there is an "objective" probability measure that quantifies the uncertainty) and decision making under uncertainty (where there is not). Prior to Savage's work, many decision rules that did not involve probability were discussed; maximin and minimax regret are perhaps the best-known. The maximin rule was promoted by Wald [1950]; minimax regret was introduced (independently) by Niehans [1948] and Savage [1951]. The decision rule corresponding to lower expectation has a long history. It was discussed by Wald [1950], examined carefully by G rdenfors and Sahlin [1982] (who also discussed how the set of probability measures might be chosen), and axiomatized by Gilboa and Schmeidler [1989]. Borodin and El Yaniv [1998, Chapter 15] give a number of examples of other rules, with extensive pointers to the literature.

Savage's work on expected utility was so influential that it shifted the focus to probability and expected utility maximization for many years. More recently, there have been attempts to get decision rules that are more descriptively accurate, either by using a different representation of uncertainty or using a decision rule other than maximizing expected utility. These include decision rules based on belief functions (also called nonadditive probabilities and Choquet capacities) [Schmeidler 1989], rules based on nonstandard reals [Lehmann 1996; Lehmann 2001], prospect theory [Kahneman and Tversky 1979], and rank-dependent expected utility [Quiggin 1993].

There has been a great deal of effort put into finding techniques for utility elicitation and probability elicitation. Utility elicitation can, for example, play an important role in giving doctors the information they need to help patients make appropriate decisions regarding medical care. (Should I have the operation or not?) Farquhar [1984] gives a good theoretical survey of utility elicitation techniques; the first few chapters of [Yates 1990] give a gentle introduction to probability elicitation.

All the material in Section 5.4.3 is taken from [Chu and Halpern 2003a; Chu and Halpern 2003b], where GEU and the notion of one decision rule representing another are introduced. A more refined notion of uniformity is also defined. The decision-problem transformation τ that takes nonplausibilistic decision problems to plausibilistic decision problems is uniform if the plausibility measure in τ(DP) depends only on the set of worlds in DP. That is, if DP_i = ((A_i, W_i, C_i), D_i, u_i), i = 1, 2, and W₁ = W₂, then the plausibility measure in τ(DP₁) is the same as that in τ(DP₂). The plausibility measure must depend on the set of worlds (since it is a function from subsets of worlds to plausibility values); uniformity requires that it depends only on the set of worlds (and not on other features of the decision problem, such as the set of acts). The decision problem transformation used to show that regret minimization can be represented by GEU is not uniform. There is a characterization in the spirit of Theorem 5.4.4 of when GEU can uniformly represent a decision rule (see [Chu and Halpern 2003b]). It follows from the characterization that GEU cannot uniformly represent regret minimization. Roughly speaking, this is because the preference order induced by regret minimization can be affected by irrelevant acts. Suppose that DP₁ and DP₂ are decision problems that differ only in that DP₂ involves an act a that is not among the acts in DP₁. The presence of a can affect the preference order induced by regret minimization among the remaining acts. This does not happen with the other decision rules I have considered here, such as maximin and expected utility maximization.

This general framework has yet another advantage. Theorem 5.4.2 shows that any partial preorder on acts can be reprsented by GEU. Savage considers orders on acts that satisfy certain postulates. Each of Savage's constraints can be shown to correspond to a constraint on expectation domains, utility functions, and plausibility measures. This gives an understanding of what properties the underlying expectation domain must have to guarantee that each of Savage's postulates hold. See [Chu and Halpern 2003a] for details.

Besides the additive notion of regret that I have considered here, there is a multiplicative notion, where regret_u(a, w) is defined to be u(w, a_w)/u(w, a). With this definition, if regret_u(a) = k, then a is within a multiplicative factor k of the best act the agent could perform, even if she knew exactly what the state was. This notion of regret (unlike additive regret) is affected by linear transformations of the utility (in the sense of Exercise 5.35). Moreover, it makes sense only if all utilities are positive. Nevertheless, it has been the focus of significant recent attention in the computer science community, under the rubric of online algorithms; [Borodin and El-Yaniv 1998] is a book-length treatment of the subject.

Influence diagrams [Howard and Matheson 1981; Shachter 1986] combine the graphical representation of probability used in Bayesian networks with a representation of utilities, and thus they are a very useful tool in decision analysis. There have also been attempts to define analogues of independence and conditional independence for utilities, in the hope of getting representations for utility in the spirit of Bayesian networks; see [Bacchus and Grove 1995; Keeney and Raiffa 1976; La Mura and Shoham 1999]. To date, relatively little progress has been made toward this goal.

The two-envelope puzzle discussed in Exercise 5.7 is well known. The earliest appearance in the literature that I am aware of is in Kraitchik's [1953] book of mathematical puzzles, although it is probably older. Nalebuff [1989] presents an interesting introduction to the problem as well as references to its historical antecedents. In the mid-1990s a spate of papers discussing various aspects of the puzzle appeared in the philosophy journals Analysis and Theory and Decision; see [Artzenius and McCarthy 1997; McGrew, Shier, and Silverstein 1997; Rawlings 1994; Scott and Scott 1997; Sobel 1994] for a sampling of these papers as well as pointers to some of the others.

Walley [1991] discusses carefully the notion of conditional expectation. Denneberg [2002] gives a recent discussion of updating and conditioning expectation.