foundations of computational agents
The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).
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 ${X}_{1},\mathrm{\dots},{X}_{n}$. An additive utility is one that can be decomposed into a sum of terms:
$$u({X}_{1},\mathrm{\dots},{X}_{n})={f}_{1}({X}_{1})+\mathrm{\cdots}+{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. 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 ${X}_{i}$, define a local utility function ${u}_{i}({X}_{i})$ that has a value of 0 for the value of ${X}_{i}$ in the worst outcome and 1 for the value of ${X}_{i}$ in the best outcome, and a non-negative real weight, ${w}_{i}$. The weights should sum to 1. The utility as a function of the variables is:
$$u({X}_{1},\mathrm{\dots},{X}_{n})={w}_{1}*{u}_{1}({X}_{1})+\mathrm{\cdots}+{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 an agent and a worst value for the agent. Assessing the local functions and weights can be done as follows. Consider just ${X}_{1}$; the other features then can be treated analogously. For feature ${X}_{1}$, values ${x}_{1}$ and ${x}_{1}^{\prime}$ for ${X}_{1}$, and fixed values ${x}_{2},\mathrm{\dots},{x}_{n}$ for ${X}_{2},\mathrm{\dots},{X}_{n}$:
$$u({x}_{1},{x}_{2},\mathrm{\dots},{x}_{n})-u({x}_{1}^{\prime},{x}_{2},\mathrm{\dots},{x}_{n})={w}_{1}*({u}_{1}({x}_{1})-{u}_{1}({x}_{1}^{\prime})).$$ | (9.1) |
The weight ${w}_{1}$ can be derived when ${x}_{1}$ is the best outcome and ${x}_{1}^{\prime}$ is the worst outcome (because then ${u}_{1}({x}_{1})-{u}_{1}({x}_{1}^{\prime})=1$). The values of ${u}_{1}$ for the other values in the domain of ${X}_{1}$ can be computed using Equation 9.1, making ${x}_{1}^{\prime}$ the worst outcome (as then ${u}_{1}({x}_{1}^{\prime})=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 ${x}_{2},\mathrm{\dots},{x}_{n}$ for ${X}_{2},\mathrm{\dots},{X}_{n}$.
Additive independence is often not a good assumption. Consider binary features $X$ and $Y$, with domains $\{{x}_{0},{x}_{1}\}$ and $\{{y}_{0},{y}_{1}\}$.
Two values of $X$ and $Y$ are complements if having both is better than the sum of having the two separately. More formally, values ${x}_{1}$ and ${y}_{1}$ are complements if getting one when the agent has the other is more valuable than when the agent does not have the other:
$$u({x}_{1},{y}_{1})-u({x}_{0},{y}_{1})>u({x}_{1},{y}_{0})-u({x}_{0},{y}_{0}).$$ |
Two values are substitutes if having both is not worth as much as the sum of having each one. More formally, values ${x}_{1}$ and ${y}_{1}$ 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({x}_{1},{y}_{0})-u({x}_{0},{y}_{0})>u({x}_{1},{y}_{1})-u({x}_{0},{y}_{1}).$$ |
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}{}{(}{p}{}{l}{}{a}{}{n}{}{e}{,}{h}{}{o}{}{t}{}{e}{}{l}{)}{-}{u}{}{(}{\mathrm{\neg}}{}{p}{}{l}{}{a}{}{n}{}{e}{,}{h}{}{o}{}{t}{}{e}{}{l}{)}{>}{u}{}{(}{p}{}{l}{}{a}{}{n}{}{e}{,}{\mathrm{\neg}}{}{h}{}{o}{}{t}{}{e}{}{l}{)}{-}{u}{}{(}{\mathrm{\neg}}{}{p}{}{l}{}{a}{}{n}{}{e}{,}{\mathrm{\neg}}{}{h}{}{o}{}{t}{}{e}{}{l}{)}$$ |
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.