Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

### 9.1.1 Factored Utility

Utility, as defined, is a function of outcomes or states. Often too many states exist to represent this function directly in terms of states, and it is easier to specify it in terms of features.

Suppose each outcome can be described in terms of features
*X _{1},...,X_{n}*. An

**additive utility**is one that can be decomposed into set of factors:

u(X_{1},...,X_{n})= f_{1}(X_{1})+...+f_{n}(X_{n}).

Such a decomposition is making the assumption of **additive independence**.

When this can be done, it greatly simplifies **preference
elicitation** - the problem of acquiring preferences from the
user. Note that this decomposition is not unique, because adding a constant
to one of the factors and subtracting it from another factor gives
the same utility. To put this decomposition into canonical form, we can have a local utility function
*u _{i}(X_{i})* that has a value of 0 for the value of

*X*in the worst outcome, and 1 for the value of

_{i}*X*in the best outcome, and a series of weights,

_{i}*w*, that are non-negative numbers that sum to 1 such that

_{i}u(X_{1},...,X_{n})= w_{1}×u_{1}(X_{1})+...+w_{n}×u_{n}(X_{n}).

To elicit such a utility function requires eliciting each local
utility function and assessing the weights. Each feature, if it is
relevant, must have a
best value for this feature and a
worst value for this feature.
Assessing the local functions and weights can be done as follows. We consider just *X _{1}*;
the other features then can be treated analogously. For feature

*X*, values

_{1}*x*and

_{1}*x*for

_{1}'*X*, and values

_{1}*x*for

_{2},...,x_{n}*X*:

_{2},...,X_{n}u(x_1,x_2...,x_n)-u(x_1',x_2...,x_n)=w_1×(u_1(x_1)-u_1(x_1')).

The weight *w _{1}* can be derived when

*x*is the best outcome and

_{1}*x*is the worst outcome (because then

_{1}'*u*). The values of

_{1}(x_{1})-u_{1}(x_{1}')=1*u*for the other values in the domain of

_{1}*X*can be computed using Equation (9.1.1), making

_{1}*x*the worst outcome (as then

_{1}'*u*).

_{1}(x_{1}')=0Assuming additive independence entails making a strong independence
assumption. In particular, in Equation (9.1.1), the difference in utilities must be the same for all
values *x _{2},...,x_{n}* for

*X*.

_{2},...,X_{n}Additive independence is often not a good assumption. Two values of
two binary features are
**complements** if having both is better than the sum of the
two. Suppose the features are *X* and *Y*, with domains *{x _{0},x_{1}}*
and

*{y*. Values

_{0},y_{1}}*x*and

_{1}*y*are complements if getting one when the agent has the other is more valuable than when the agent does not have the other:

_{1}u(x_{1},y_{0})-u(x_{0},y_{0}) < u(x_{1},y_{1}) - u(x_{0},y_{1}).

Note that this implies *y _{1}* and

*x*are also complements.

_{1}Two values for binary features are
**substitutes** if having both is not worth as much as the sum
of having each one. If values *x _{1}* and

*y*are substitutes, it means that getting one when the agent has the other is less valuable than getting one when the agent does not have the other:

_{1}u(x_{1},y_{0})-u(x_{0},y_{0}) > u(x_{1},y_{1}) - u(x_{0},y_{1}).

This implies *y _{1}* and

*x*are also substitutes.

_{1}**Example 9.3:**For a purchasing agent in the travel domain, having a plane booking for a particular day and a hotel booking for the same day are complements: one without the other does not give a good outcome.

Two different outings on the same day would be substitutes, assuming the person taking the holiday would enjoy one outing, but not two, on the same day. However, if the two outings are in close proximity to each other and require a long traveling time, they may be complements (the traveling time may be worth it if the person gets two outings).

Additive utility assumes there are no substitutes or complements. When
there is interaction, we require a more sophisticated model, such as a
**generalized additive independence** model, which represents
utility as a sum of factors. This is similar to the optimization
models of Section 4.10; however, we want to use these
models to compute expected utility. Elicitation of the generalized
additive independence model is much more involved than eliciting an
additive model, because a feature can appear in many factors.