9.1 Preferences and Utility

9.1.2 Factored Utility

Utility for an agent is a function of outcomes or states. Representing utilities in terms of features or variables typically results in more compact representations that are easier to reason with and more natural to acquire.

Suppose each outcome can be described in terms of features X1,,Xn. An additive utility is one that can be decomposed into a sum of terms:

u(X1,,Xn)=f1(X1)++fn(Xn).

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. This decomposition is not unique, because adding a constant to one of the terms and subtracting it from another gives the same utility. A canonical form for additive utility has a unique decomposition. Canonical forms are easier to acquire as each number can be acquired without considering the other numbers. To put additive utility into canonical form, for each feature Xi, define a local utility function ui(Xi) that has a value of 0 for the value of Xi in the worst outcome and 1 for the value of Xi in the best outcome, and a non-negative real weight, wi. The weights should sum to 1. The utility as a function of the variables is:

u(X1,,Xn)=w1*u1(X1)++wn*un(Xn).

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 an agent and a worst value for the agent. Assessing the local functions and weights can be done as follows. Consider just X1; the other features then can be treated analogously. For feature X1, values x1 and x1 for X1, and fixed values x2,,xn for X2,,Xn:

u(x1,x2,,xn)-u(x1,x2,,xn)=w1*(u1(x1)-u1(x1)). (9.1)

The weight w1 can be derived when x1 is the best outcome and x1 is the worst outcome (because then u1(x1)-u1(x1)=1). The values of u1 for the other values in the domain of X1 can be computed using Equation 9.1, making x1 the worst outcome (as then u1(x1)=0).

Assuming additive independence entails making a strong independence assumption. In particular, in Equation 9.1, the difference in utilities must be the same for all values x2,,xn for X2,,Xn.

Additive independence is often not a good assumption. Consider binary features X and Y, with domains {x0,x1} and {y0,y1}.

  • Two values of X and Y are complements if having both is better than the sum of having the two separately. More formally, values x1 and y1 are complements if getting one when the agent has the other is more valuable than when the agent does not have the other:

    u(x1,y1)-u(x0,y1)>u(x1,y0)-u(x0,y0).
  • Two values are substitutes if having both is not worth as much as the sum of having each one. More formally, values x1 and y1 are substitutes if getting one when the agent has the other is less valuable than getting one when the agent does not have the other:

    u(x1,y0)-u(x0,y0)>u(x1,y1)-u(x0,y1).
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. Thus,

u(plane,hotel)-u(¬plane,hotel)>u(plane,¬hotel)-u(¬plane,¬hotel)

where the right side would be small or even negative.

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 terms, where each term can be a factor over multiple variables. Elicitation of the generalized additive independence model is much more involved than eliciting an additive model, because a variable can appear in many factors.