On the Foundations of Expected Expected Utility

1 Introduction

Mos~ work on the foundations of decision theory­ specifically on the justification of expected utility-has fo­ cused on personal decision making, that is, settings where a ~ecision is being made by the "holder" of the utility func­ tion. Of course the decision maker may not be fully aware of (or have fully articulated) her utility function. The pro­ cess of articulation is complex, and much work in decision analysis deals with preference elicitation and decision fram­ ing to help the decision maker formulate her decision problem [ 11]. However, this work is primarily concerned with elicit­ ing enough . information about preference tradeoffs to allow an (approximately) optimal decision to be made. While an analyst can never be sure about the true nature of the deci­ sion mak~r's utili~ !Unction, thi.s uncertainty is not generally charactenzed exphc1tly, though 1ts impact is often minimized though sensitivity analysis and related techniques.

Recent emphasis has been placed on the development of automated decision tools, where a decision is being made on behalf of a user whose utility function is imprecisely known. As in goal programming or other forms of inter­ active optimization, a space of possible utility functions is usually maintained (often by imposing constraints on trade­ off weights). A decision can be made based on this set of feasible utility functions. For example, Pareto optimal deci­ sions can be identified [21; 18], or models based on mini­ max regret can be used to choose a specific decision [ 11; 2; 2~]: In eac~ o~ these models, the uncertainty regarding the utility functiOn 1s characterized by the feasible utility set.

Somewhat less common is work in which the system's un­ c~r:a~nty about a user's utility function is quantified proba­ blhstically. Some recent examples include [5; 6; 1]. In this work, a distribution over utility functions is assumed. The expecte~ utility of a decision is determined not just by taking expectatiOn over the outcomes of that decision, but also ex­ pectation over the space of possible utility functions. We use the term expected expected utility (EEU) to denote the value of~ decision co.mputed in this way. Elicitation strategies can ~e mformed usmg the current distribution over utility func­ tions. For example, value of information can be used to de­ termine whether the improvement in decision quality given by a. piece o! information outweighs the cost of obtaining that mformat10n. Thus, characterizing one's uncertainty over possible utility functions in a probabilistic fashion, and using EEU to determine decision quality, has much to recommend it from the point of view of elicitation.

Decision making using distributions over utility functions has been considered in other contexts. For example, Cyert and de Groot consider problems in sequential decision mak­ ing in which uncertainty in the underlying utility function is represented probabilistically [8; 9]. Fishburn [1 0] also ad­ dresses this problem (as we discuss below). Harsanyi's for­ mulation of games with incomplete information as Bayesian games [12; 13] relies critically on distributions over payoff functions, and virtually the entire literature on in this area adopts this perspective [7; 15]. 1

In all of this work, the EEU concept is used to determine the value of decisions in the context of an uncertain utility fu?ction. U~fortunately, while EEU has an intuitive appeal, th1s scheme 1s sensitive to positive affine transformations of the utility functions in question. Implicit in such a scheme is a commensurability assumption that allows the quantities present in the different utility functions to be meaningfully compared and combined. This is not always the case. The aim of this paper is to describe certain conditions under which this commensurability assumption can be justified by appeal to the foundational axioms for decision theory as proposed by von Neumann and Morgenstern [ 19] and Savage [ 17].

1 In some sense, much work in collaborative filtering [3; 16] and related models [4] can be viewed as incorporating distributions over utility functions. However, these are used for purposes of classi­ fication (i .e., determining a unique utility function for a particular user) and generally uncertainty in utility is not accounted for when making decisions.

The setting we consider is one in which an agent for a de­ cision maker or user is uncertain about the user's preferences, but wishes to recommend (or take) decisions on the user's be­ half. Fishburn [10] has considered the problems of the foun­ dations of expected expected utility from a somewhat differ­ ent perspective. He considers the problem in which a decision maker is uncertain about the set of consequences she might face and considers combining utility functions over different consequence sets. Unfortunately, his results cannot be ap­ plied (except in a trivial way) to the situation above. 2

We begin by defining the problem of decision making given uncertainty over utility functions and the EEU con­ cept. We then examine the sensitivity of EEU to the precise representation of the underlying utility functions, and pro­ pose an interpretation of utility uncertainty that allows one to prescribe "canonical" utility function representations under specific circumstances. We conclude with a brief discussion of the implications these considerations have for "practical" elicitation.

2 Expected Expected Utility

We begin by establishing notation and basic background with a quick overview of expected utility and then define the notion of expected expected utility formally.

2.1 Expected Utility

Assume a decision scenario consisting of a finite set of pos­ sible decisions D, a finite set of possible outcomes (or states) S, and a distribution function Prd E ~(S), for each d E D. The term Prd(s) denotes the probability of outcomes being realized if the system takes decision d. Prd(s) can be viewed as a vector Pd whose ith component is Prd(si) (given a suit­ able enumeration of outcomes in S).

A utility function u : S --+ lR associates utility u( s) with each outcome s. We will generally view u as a lSI­ dimensional vector u whose ith component Ui is u(si). 3 The expected utility of decision d w.r.t. u is:

The optimal decision d* w.r.t. u is that with maximum ex­ pected utility (MEU).

2 While our results are general, it is unclear how profitable it is to model a decision maker's uncertainty about her own utility function. It can be argued that such uncertainty should be viewed as "tradi­ tional" uncertainty about future outcomes, context, etc. Rather than take a stand on this issue, we simply emphasize that an agent can be genuinely uncertain about a user's utility function, and that our model and results apply (in a practical way) to such a setting.

3 If u is represented using some more concise model, u is simply the vector of parameters required for that model.

It is well known that utility functions are invariant under positive affine transformations. That is, the relative expected utility of any pair of decisions (in any decision scenario) will be unaltered by such a transformation of a utility function. This implies that the optimal decision in any decision sce­ nario is unaffected by such a transformation.

More precisely, von Neumann and Morgenstern equate [ 19] (classes of) utility functions with preferences over lotter­ ies. Let (p1 , s1; P2, s2; .. . Pn, sn), where I:i Pi = 1, denote a simple lottery over outcomes, with each outcome s; obtained with probability Pi· As a shorthand, we sometimes omit out­ comes whose probability is zero. Note that an outcome s ; is itself a (trivial) simple lottery, and that each decision d in­ duces a simple lottery l(d) over outcomes. A compound lot­ tery is a lottery whose elements may be further lotteries. Let >- a preference function over lotteries, with h >- l2 meaning that h is strictly preferred to l2. The relations C: , --<, ::S , and "" are defined in the usual way. Assuming certain (relatively uncontroversial) axioms restricting the form of the preference function >-, von Neumann and Morgenstern show that there exists a utility function u>- that exactly represents >- in the following sense: EU(d,u>-) > EU(d', u>-) iffl(d) >- l(d'). Furthermore, the utility function u>- is unique up to positive affine transformation. Because of this, we can partition the space of utility functions into equivalence classes, each cor­ responding to a unique preference ordering >-. We denote this class by [>- J.

Several of the axioms used to equate utility functions with preferences over lotteries are listed here. These are based on the work of von Neumann and Morgenstern [ 19] and Savage [ 17], though the particular form used here is drawn from [ 14]. We use ST to denote some most preferred outcome inS (i.e. , ST C: s, Vs E S), and s.1. to denote some least preferred outcome (these are guaranteed to exist due to other axioms).

Reduction of Compound Lotteries Let l be the lottery (p1, h; . .. ; Pn, ln) where each li is a lottery of the form {qi, li; ... ; q:,.(i), z:,.(i)). Let [k, k ~ K denote the K (unique) lotteries within the set {lj : i ~ n , j ~ m(i)}. Let r be the (reduced) lottery over the (unique) component lotteries fk with probability Pk = I: {piqJ : lj = fk} associated with each fk . Then r"" l.

2.2 Uncertainty over Utility Functions

An agent will often not know the user's utility function u with certainty. We model this uncertainty using a density P over the set of utility functions U ~ JRI 8 1 (or a distribution over a finite support set contained in U). If a system makes a decision d under such conditions of uncertainty, the expected utility of d must reflect this. We consider the following defi­ nition for the expected utility of d given density P over U:

We refer to this as the expected expected utility (EEU) of de­ cision d, since it is the expectation of EU(d, u) w.r.t. P(U) .

This definition is precisely that used in [5; 6; 1] in the con­ text of utility elicitation, and also that used in much other work involving uncertainty over utility [12; 8; 9] . In such a state of uncertainty-or belief state-the optimal decision is that d* with maximum EEU EU(d*, P). We denote by EU(P) the value of being in belief state P, assuming one is forced to make a decision:

We call this generic decision rule the MEEU decision rule, by analogy with the classical MEU decision rule.

EEU seems to be a fairly natural concept given proba­ bilistically quantified uncertainty over utilities. The fact that it occurs in many different contexts certainly attests to this fact. Unfortunately, the proposed definition can induce cer­ tain anomalies, as we examine below.

3 Justifying MEEU

3.1 Loss of lnvariance

The results of von Neumann and Morgenstern suggest that the decisions one makes with respect to belief state P over U should be invariant to legitimate transformations of the el­ ements of U. Certainly, this would be a desirable feature of the MEEU decision rule. One might even claim that the de­ cision ruh~ can only be considered useful if it satisfies this condition. In general, unfortunately, this is not the case.

As a simple illustration, suppose we have a domain with two outcomes s1 and s2 , and a distribution P that assigns probability 0.5 to u1 = (1, 3) and probability 0.5 to uz = (2, 1). Suppose we use the MEEU decision rule in this con­ text, by computing

and choosing the decision d* with maximum expected utility EU(d*, P). Then a decision that accords higher probability to s2 will be preferred to one that gives lower probability to s2. However, if we transform u2 into u~ = (20, 10), the relative utilities of these decisions will be reversed. Thus, the MEEU decision rule is not insensitive to transformations of individual utility functions with positive support. Note that we are not suggesting that agent's will arbitrarily transform some utility functions and not others. 4 Rather, the question is: which representation of a specific utility function (e.g., uz in the example) should be adopted in the first place?

One possible way to deal with this problem is to recognize that a utility function is simply a convenient (and nonunique) way of expressing preferences over lotteries. Rather than working with utility functions, we could work explicitly with a density over preference functions (in fact, we will do this implicitly below). Unfortunately, the set of lotteries over which a preference ordering is defined is uncountable; there­ fore, some compact representation (of the individual prefer­ ence functions) is needed. But this is precisely the role of a utility function-to serve as a concise representation of a preference function over lotteries.

4 If the same transformation is applied to all functions with posi­ tive support, the MEEU decision is unchanged.

This gives rise to the question of how to choose a repre­ sentative utility function from each equivalence class [>-] that allows formal justification of the MEEU decision rule, and under what circumstances such representatives exist.

3.2 A Lottery Interpretation of MEU

We give a formal justification for the MEEU rule under a spe­ cific condition: we assume the existence of a known best and worst outcome. That is, each utility function with positive support has the same best outcome ST and worst outcome s J... We also insist that the user is not indifferent to these alterna­ tives, that is, that ST must be strictly preferred to s J... 5 We call such utility functions extremum equivalent. In many settings, such as those involving active preference elicitation, restrict­ ing attention to a set of extremum equivalent utility functions is not problematic. One simply needs to ask the user to iden­ tify her most and least preferred outcomes (these need not be unique, but only one such representative need be identified).

Once we know outcomes ST and s J.., we insist that our be­ lief state P assign nonzero measure only to normalized utility functions u in which u(sT) = CT and u(sJ..) = CJ.. for some constants CT > CJ.. . For convenience, we will assume CT = 1 and CJ.. = 0, but nothing crucial depends on these choices. Under these conditions, every preference ordering >- for lot­ teries has a unique utility function representation satisfYing the normalization constraints.

We note that each preference ordering corresponds to a unique set of indifference conditions between outcomes and standard lotteries. A standard lottery is one of the form (p, sT; 1 - p, SJ..). By the Continuity Axiom, we have, for each outcomes; and each preference ordering>-,

for some unique Pt. We denote by l(>-, si) this standard lot­ tery. This implies that u>- ( s;) = p; in the normalized utility function u>- corresponding to >-. 6

Now given a belief state P, how does one compare the value of different decisions d? This can be reduced to a ques­ tion of how one compares the value of guaranteed outcomes Si, since decisions are just lotteries over outcomes. Given a particular preference ordering)-, we have Si rv l(>-, Si)· However, the choice facing the agent for the decision maker involves uncertainty over the true preference ordering. Thus, we can view the outcome Si as a compound lottery, where first a preference ordering is chosen according to distribution P, and then the standard gamble involving Si is played. This will induce a new preference ordering>-p over outcomes (and de­ cisions). We illustrate this for the case of a discrete distribu­ tion over two preference orderings>- and>-', with probabil­ ities q and 1 - q respectively. In this case, the outcome Si is equated with the compound lottery

----- 5If ST "' s .L, then the decision problem is trivial since each decision is equally preferred. Indeed, in some axiomatizations, non­ triviality is imposed on legitimate preferences [II] .

6 If the normalizing constants differ from 0/ I, then utility is some linear function of p;. This has no impact on our argument.

By reduction of compound lotteries, this means that

Similarly, for any other outcome Sj, we have

By the Monotonicity Axiom, we have s; >- p Sj iff

Since p;- = u>- ( s; ) (and similarly for the other terms), we have s; ?- p Sj iff EU(s;, P ) > EU(sj, P) (where we em­ phasize that here we are treating outcomes as deterministic decisions that guarantee the corresponding outcomes). 7 From this one can easily show that for any two decisions d, d' (that induce distributions over outcomes), l(d) ?-p l(d') iff EU(d, P ) > EU(d', P ).

This argument applies to arbitrary discrete distributions, and can be generalized to continuous densities as follows:

Here the first step refers to a compound lottery over an con­ tinuous set of component (simple) lotteries, while we assume in second step that a such a compound lottery can be reduced to a simple lottery in an analogous way to the reduction of a finite compounded lottery.

Thus under the assumption that one can identify a best and worst outcome, the MEEU decision rule can be justified for use with normalized (extremum equivalent) utility functions by appeal to the foundational axioms of decision theory, and an interpretation of uncertainty over utility as a lottery over the lotteries defined by the component utility functions.

We now formalize the legitimacy ofEEU and MEE.

Definition 1 Let{>-;} be a set of extremum equivalent pref­ erence relations with respect to finite outcome setS, with best and worst outcomes ST and S j_ , respectively. Let P be a den­ sity over{>-;}. For any>-;, let p~' denote the tradeoff prob­ ability for states in its standard gamble w.r.t. >-;;that is,

7 Note that if we chose other normalizing constants for our best and worst outcomes, then we would have that u >- ( s;) is some linear function of p~ ; but this linear function is identical for each term in the equation, so the conclusion holds.

The aggregate standard gamble for s E S induced by {>-;} and P is defined:

Let l be any lottery w.r.t. S. The aggregate reduction of l is the standard gamble

obtained by replacing every outcome s in l by its aggregate standard gamble and reducing it to a standard gamble in the usual fashion. The aggregate preference relation >- (w.r.t. S) induced by{>-;} and Pis given by

Theorem 1 Let { t: i} and P be defined as above. Let { u;} be a set of utility functions (one for each t ;, consistent with t: ;) such that u;(sT) = CT and u;(s1_) = Cj_, for all u; and two fixed constants CT > Cj_ ~ 0. Then the utility function u(s ) = J>- u;(s)P(t;) isconsistentwiththeaggregatepreference reTdtion t induced by {t:;} and P.

Extremum equivalence is thus sufficient to ensure commen­ surability, as it puts all utility functions on a common scale. It is important to realize that the scale dictated by the best and worst outcomes cannot vary, since these are truly best and worst outcomes; we return to this point below. It appears to be much more difficult to apply this type of argument to den­ sities over utility functions that are not extremum equivalent.

Fishburn [10] considers the problem of EEU when a deci­ sion maker is uncertain about the nature of the consequence sets she will face. He proposes foundational axioms that jus­ tify the use EEU to compare decisions. However, the setting is rather different: specifically, Fishburn requires that any consequences that two utility functions have in common be ranked identically. In our context, where each utility function lies over the same consequence set, the Fishburn axioms im­ pose overly stringent requirements. It is interesting to note that Fishburn requires something akin to extremum equiva­ lence, namely, that there exist two consequences common to the domains of each utility function such that one of the con­ sequences is preferred to the other in each function.

4 Dealing with Small Worlds

It is important to realize that the best and worst outcomes with which one calibrates must either be truly best and worst outcomes from the decision maker's standpoint, or they them­ selves must be calibrated. Using Savage's [17] terminology, we must be careful to distinguish "small worlds" reasoning from "grand worlds." Consider the case where the set of out­ comes is restricted to the subset of outcomes that are possible given the set of actions in a specific decision scenario. But assume there exist outcomes outside the domain of the re­ stricted scenario for which the user has concrete preferences. Let's refer to the set of restricted outcomes as local, while the space of all outcomes is global .

We might imagine determining the best and worst local outcomes, s~ and s~, respectively, and engaging in the elic­ itation process using standard gambles with respect to these extreme local outcomes. Unfortunately, this is not sufficient to justify the MEEU decision rule. The difficulty is that the user's degrees of preference for s~ and s~ may themselves be characterized by uncertainty. Specifically, s~ can be equated with a standard gamble (p~, ST ; 1- p~, s.1.) (where sT, s.1. denote the globally best and worst outcomes). Sim­ ilarly, s~ ,....., (p~, ST ; 1 - p~, s .1.). But the relevant gamble probabilities-p~ and p~ -may vary with the utility function and will not be known if attention is restricted to the small worlds domain. As a consequence, our distribution over lo­ cal utility functions is insufficient to justify MEEU.

To illustrate, suppose that we believe the user's utility func­ tion is either u1 (with probability q1) or u2 (with probability q2 = 1- q1) . Furthermore, suppose that we consider only the projection of these onto the set of local outcomes, calibrat­ ing two outcomes Si and Sj with respect to "local" standard gambles. Suppose that we have the following tradeoffs with respect to the local extrema in u1:

and similarly in u2:

Using EEU, we have

Now, were we to place this small world in the grand world context, we might say that the local best and worst outcomes, s~ and s~, have specific lottery probabilities with respect to the global utility functions. Let's assume that we have

In other words, in (the normalized, global counterpart of) util­ ity function u1, we have u1(s~) = p~ and u1(s~) =pi; while in u2 we have u2 ( s~) = p~ and u2 ( s~) = Pl. Apply­ ing EEU and reduction of compound lotteries, we see that

Si ,.......,

and

Hence, s; >- Sj iff

Unfortunately, this condition is not equivalent to the MEEU rule in the original small worlds domain. Specifically, this condition cannot generally be assessed without having some assessment of the global tradeoff probabilities p~, etc. In other words, to accurately compare two small world out­ comes given uncertainty about the local utility functions, we have to explicitly assess our uncertainty about the range of values the local extrema can take with respect to the global utility function. Thus while one can generally use small world reasoning in the classic decision-theoretic setting, its use is problematic in the EEU framework.

Fortunately, the MEEU principle can be recovered if we make one simple assumption: that the global tradeoffs asso­ ciated with the best and worst local outcomes do not vary with the utility function (at least, with those utility functions having positive support). For example, to continue with the illustration above, suppose that the tradeoff probabilities as­ sociated with the two utilities u1 and u2 are identical; that is, p~ = p~ and p}_ = Pl. (Whether the probabilities are known is irrelevant, all that matters is that they are known to be identical.) If this is so we have Si >- Sj iff

Since the inner terms in each expression sum to one, and p~ > p}_ (since s~ >- s~), we must haves; >- Sj iff

This, of course, is the expression for MEEU.

Indeed, we don't have to assume that the global tradeoff probabilities are fixed. It is sufficient to assume that the un­ known range of(global) utility spanned by s~ and s~ is prob­ abilistically independent of the unknown local utility function u. This too is sufficient to allow MEEU to be used justifiably. We omit the argument, which is straightforward.

5 Consequences for Preference Elicitation

The considerations above have implications for practical pref­ erence elicitation. From a foundational perspective, calibra­ tion of utilities relative to known best and worst outcomes is required if decisions are to be based on EEU. In the case of incremental elicitation, where EEU is used to determine value of information, we must first obtain a prior over a set of ex­ tremum equivalent utility functions before engaging in such deliberations. Fortunately, it often seems to make sense to determine best and worst outcomes beforehand, and engage in "serious" elicitation after this initial calibration.

Another important question: how does one determine pri­ ors over utility functions? Utility function databases [ 4] could be used. This poses some problems regarding interpersonal utility comparison for which there are no especially com­ pelling solutions. When using EEU, things are a bit worse: we need to construct priors conditioned on the observed or elicited best and worst outcomes. Given a prior over arbitrary utility functions, as long as decisions using EEU are not made until the determination of best and worst outcomes is com­ pleted, this poses no difficulties. An alternative, in certain scenarios, is to suppose that certain outcomes are universally most and least preferred (e.g., in medical contexts, death can be used as the latter). This may be hard to justify formally, but from a practical point of view will be quite useful and (one hopes) have little impact on actual decision quality.

The issue of small worlds also poses certain problems. From the point of view of practical elicitation, the prospect of calibrating some small set of relevant outcomes using a user's "global" utility function is unappealing. Fortunately, as argued above, for a given individual, strength of prefer­ ence can be assumed fixed for the best and worst outcomes, which allows things to carry through. Strength of preference may prove to be important however when trading off the in­ crease in EEU with the effort associated with the elicitation process. Furthermore, this can have an important impact on the construction of priors from databases of utility functions.

6 Concluding Remarks

Decision making when the underlying utility function is un­ known is an important problem in game theory, interactive optimization, and preference elicitation. Quantifying this un­ certainty using distributions over utility functions has anum­ ber of appealing qualities, and quite naturally leads to the no­ tion of expected expected utility, a concept that has been used in several different lines of research.

The aim of this paper is to point out that expectations taken with respect to utility function distributions require some care. More precisely, the operation of expected expected util­ ity only makes sense (from a foundational standpoint) when the distribution is over extremal equivalent utility functions. While this has certain implications for practical utility elic­ itation, we have argued that this requirement is not overly stringent from a practical perspective.

Acknowledgements

Thanks to Radford Neal whose comments on preference elic­ itation led to this investigation and to Moshe Tennenholtz for suggesting interesting connections. This work was supported by the Institute for Robotics and Intelligent Systems (IRIS), and the Natural Sciences and Engineering Research Council of Canada (NSERC).