---
title: "Decision Analysis: Multi-Attribute Utility and Decision Networks"
module: Uncertainty
moduleNumber: 4
lessonNumber: 9
order: 409
summary: >
  Decision analysis takes the single-agent utility framework and makes it
  practical: utility over several attributes, dominance and additive value
  functions, influence diagrams that fold Bayesian networks together with
  decision and utility nodes, and the value of information that tells an agent
  which questions are worth asking. Structure in an agent's preferences — dominance,
  preferential and utility independence — collapses an exponential utility table into
  a few one-dimensional functions, the same move that made Bayesian networks compact.
topics: [Uncertainty]
sources:
  - book: AIMA
    ref: "Ch. 16 — Making Simple Decisions; §16.4 Multiattribute Utility Functions"
  - book: AIMA
    ref: "§16.5 Decision Networks; §16.6 The Value of Information"
---

The [utility-theory lesson](/artificial-intelligence/uncertainty/making-decisions)
built one agent that maximizes expected utility, alone, against a non-strategic
environment. It left the practical machinery of _decision analysis_
unbuilt: how to specify utility when an outcome has many attributes, how to lay a
decision problem out as a network you can evaluate, and how to price the information
an agent might buy before deciding. This lesson supplies that machinery and sets up
the strategic, multi-agent decisions of the next lesson.

## Utility over many attributes

If an outcome is described by several attributes, a table holding a preference for
every combination of their values grows exponentially. The remedy is _structure_ in
the agent's preferences — regularities that collapse the big table into a few small
ones, exactly as conditional independence collapsed a joint distribution earlier in
the module. This section works from the crudest tool (dominance, which needs no
numbers) up to the compact additive form.

Real decisions rarely turn on one number. Siting an airport weighs construction
disruption, land cost, distance from population, noise, and safety all at once. A
public-policy choice weighs money against lives. **Multiattribute utility theory**
handles outcomes described by a vector of attributes $\mathbf{X} = \langle X_1,
\dots, X_n\rangle$, each $x_i$ a number or an ordered discrete value.[^aima-mau]
We assume utility increases monotonically in each attribute (more absence-of-noise
is better; if an attribute like temperature has an interior peak, split it into
two monotone attributes measuring distance from the ideal on each side).

### Dominance

Sometimes you can decide without combining attributes into a single utility.
Suppose airport site $S_1$ costs less, makes less noise, _and_ is safer than
$S_2$. Then $S_1$ **strictly dominates** $S_2$: it is at least as good on every
attribute, so $S_2$ can be dropped from consideration no matter how the attributes
trade off. Strict dominance rarely picks a unique winner, but it prunes the field
cheaply.

$$
% caption: Strict dominance in two attributes ($X_1$, $X_2$, higher is better).
% Everything in the shaded quadrant strictly dominates A; B lies there and beats A,
% while C and D are incomparable to A (each wins on one attribute, loses the other).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, black] (0,0) -- (5.4,0) node[right, black] {X1};
  \draw[->, black] (0,0) -- (0,4.1) node[above, black] {X2};
  % point A
  \fill[black] (1.8,1.6) circle (2.2pt); \node[anchor=north east] at (1.8,1.6) {A};
  % dominating region (upper-right of A)
  \fill[acc!14] (1.8,1.6) rectangle (5.1,3.9);
  \draw[acc, dashed] (1.8,1.6) -- (5.1,1.6);
  \draw[acc, dashed] (1.8,1.6) -- (1.8,3.9);
  \node[acc, anchor=west, align=left] at (3.0,3.5) {this region\\dominates A};
  % B dominates A
  \fill[acc] (3.4,2.9) circle (2.2pt); \node[acc, anchor=south west] at (3.4,2.9) {B};
  % C and D incomparable
  \fill[black] (0.9,3.0) circle (2.2pt); \node[anchor=south east] at (0.9,3.0) {C};
  \fill[black] (3.9,0.7) circle (2.2pt); \node[anchor=north west] at (3.9,0.7) {D};
\end{tikzpicture}
$$

That is the deterministic case, where attribute values are known exactly. Under
uncertainty each option induces a _distribution_ over each attribute, and a direct
analog holds: $S_1$ strictly dominates $S_2$ if every possible outcome of $S_1$
beats every possible outcome of $S_2$. This almost never happens. The useful
generalization is **stochastic dominance**. Suppose cost at $S_1$ is uniform on
$[\text{\textdollar}2.8\text{B}, \text{\textdollar}4.8\text{B}]$ and cost at $S_2$ is uniform on $[\text{\textdollar}3\text{B},
\text{\textdollar}5.2\text{B}]$. Plotting cost as a negative value, the two distributions overlap,
yet $S_1$'s is shifted toward lower cost throughout, and any agent whose utility
_decreases_ with cost prefers $S_1$ — without ever pricing money.

$$
% caption: Stochastic dominance seen through cumulative distributions of negative
% cost. $S_1$ (right curve) lies entirely to the right of $S_2$: for every cost
% threshold, $S_1$ has at least as much probability of being cheaper, so $S_1$
% stochastically dominates $S_2$ on cost.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.4,0) node[right, black] {negative cost};
  \draw[->, black] (0,0) -- (0,3.6) node[above, black] {cumulative P};
  \node[anchor=east, black] at (0,3.1) {1.0};
  \draw[black, dashed] (0,3.1) -- (6.1,3.1);
  % S2 (left / worse): rises earlier
  \draw[red, very thick] (0.4,0) -- (2.6,3.1) -- (6.1,3.1);
  \node[red, anchor=south east] at (2.55,2.7) {S2};
  % S1 (right / better): rises later, stays right of S2
  \draw[acc, very thick] (1.6,0) -- (3.8,3.1) -- (6.1,3.1);
  \node[acc, anchor=north west] at (3.7,2.4) {S1};
\end{tikzpicture}
$$

Formally, if actions $A_1, A_2$ induce densities $p_1, p_2$ on attribute $X$, then
$A_1$ stochastically dominates $A_2$ when its cumulative distribution never
exceeds the other's,

$$
\forall x \;\; \int_{-\infty}^{x} p_1(x')\,dx' \;\le\; \int_{-\infty}^{x} p_2(x')\,dx',
$$

and the consequence is a theorem: _if $A_1$ stochastically dominates $A_2$, then for
every monotonically nondecreasing utility function $U(x)$, the expected utility of
$A_1$ is at least that of $A_2$._ So a dominated action can be discarded without
knowing $U$ at all. The condition can often be settled qualitatively — if
transport cost rises with distance to the supplier and $S_1$ is closer, $S_1$
dominates on cost — and there are algorithms that propagate such qualitative facts
through **qualitative probabilistic networks** to reach rational decisions with no
numeric values whatsoever.

### Preference structure and the additive form

When dominance leaves several contenders you must combine attributes. To tabulate
$U(x_1, \dots, x_n)$ directly over $n$ attributes with $d$ values each takes $d^n$
numbers — the worst case, an agent whose preferences have _no regularity at all_.
Multiattribute utility theory rests on the supposition that real agents have far
more structure than that, and the tool for exploiting it is the **representation
theorem**: identify a regularity in the agent's preferences and derive a compact
utility from it. Formally we hope to show that an agent with a certain preference
structure has a utility function

$$
U(x_1, \dots, x_n) = F\big[f_1(x_1), \dots, f_n(x_n)\big],
$$

where $F$ is some simple combining function — ideally addition. The parallel to a
Bayesian network is exact: there, a structural regularity (conditional
independence) let us decompose a joint probability into small local terms; here, a
structural regularity in preferences will decompose a utility into small local
terms.

#### Preferential independence

Begin with the deterministic case, where the agent has a **value function**
$V(x_1, \dots, x_n)$ over outcomes known for sure. The basic regularity is
**preferential independence**.

> **Definition (Preferential independence).** Attributes $X_1$ and $X_2$ are
> **preferentially independent** of a third attribute $X_3$ if the preference
> between outcomes $\langle x_1, x_2, x_3 \rangle$ and $\langle x_1', x_2', x_3
> \rangle$ does not depend on the particular value $x_3$. That is, how you trade
> off $X_1$ against $X_2$ is unaffected by the fixed level of $X_3$.

Take the airport attributes _Noise_, _Cost_, _Deaths_. Suppose you prefer a site
with $20{,}000$ people in the flight path at a $\text{\textdollar}4$ billion construction cost over
one with $70{,}000$ people at $\text{\textdollar}3.7$ billion _when safety is $0.06$ deaths per
million passenger-miles in both cases_. If you hold the same preference when safety
is instead $0.12$, and again when it is $0.03$ — and likewise for every other pair
of _Noise_/_Cost_ values — then $\{Noise, Cost\}$ is preferentially independent of
_Deaths_. The trade-off between noise and cost is fixed; only the safety level
riding alongside changes, and it does not move the trade-off.

$$
% caption: Preferential independence of Noise-Cost from Deaths. At two safety
% levels (top and bottom rows) the same two airport sites are compared; the
% preference (arrow from worse to better) points the same way in both rows, so the
% Noise-Cost trade-off does not depend on the Deaths level. If the arrow flipped
% between rows, independence would fail.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  opt/.style={draw, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % row 1: deaths = 0.06
  \node[font=\scriptsize, text=black, anchor=east] at (-0.3,2.0) {Deaths = 0.06:};
  \node[opt] (s1a) at (1.9,2.0) {20k people\\cost 4.0B};
  \node[opt, draw=acc, text=acc] (s1b) at (6.1,2.0) {70k people\\cost 3.7B};
  \draw[->, acc, thick] (s1a) -- (s1b) node[midway, above, font=\scriptsize, text=acc] {prefer};
  % row 2: deaths = 0.12
  \node[font=\scriptsize, text=black, anchor=east] at (-0.3,0.2) {Deaths = 0.12:};
  \node[opt] (s2a) at (1.9,0.2) {20k people\\cost 4.0B};
  \node[opt, draw=acc, text=acc] (s2b) at (6.1,0.2) {70k people\\cost 3.7B};
  \draw[->, acc, thick] (s2a) -- (s2b) node[midway, above, font=\scriptsize, text=acc] {prefer};
  \node[font=\scriptsize, text=black, anchor=north] at (4.0,-0.6)
    {same preference at every Deaths level: Noise-Cost independent of Deaths};
\end{tikzpicture}
$$

Symmetrically, $\{Cost, Deaths\}$ is preferentially independent of _Noise_, and
$\{Noise, Deaths\}$ of _Cost_. When _every_ subset of attributes is preferentially
independent of the rest, the set exhibits **mutual preferential independence**
(MPI). MPI says that each attribute may matter to the overall value, yet none of
them changes _how you trade off the others_ against each other.

#### The additive-value theorem

MPI is a strong assumption, but it yields a simple form, due to a theorem of the
economist Gérard Debreu.

> **Theorem (Additive value function).** If attributes $X_1, \dots, X_n$ are
> mutually preferentially independent, then the agent's preference behavior can be
> described as maximizing an **additive value function**
> $$V(x_1, \dots, x_n) = \sum_{i} V_i(x_i),$$
> where each $V_i$ is a value function over the single attribute $X_i$ alone.

For the airport this might be

$$
V(\mathit{noise}, \mathit{cost}, \mathit{deaths})
= -\mathit{noise} \times 10^{4} \;-\; \mathit{cost} \;-\; \mathit{deaths} \times 10^{12}.
$$

Assessing an additive value function means eliciting $n$
one-dimensional functions $V_i$ instead of one $n$-dimensional table — typically an
_exponential_ reduction in the number of preference questions the analyst must
ask. And the additive form is robust: even when MPI does not hold exactly at
extreme attribute values, it often approximates the true preferences well, provided
the violations occur in ranges of the attributes that seldom arise in practice.

$$
% caption: The exponential saving from additivity. A full utility table over $n$
% attributes with $d = 5$ values each needs $d^n$ numbers (upper curve); an
% additive value function needs only $n$ one-dimensional functions, about $n \cdot
% d$ numbers (lower curve). The two diverge fast: at $n = 5$ the table wants 3125
% numbers and the additive form about 25.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.4,0) node[right, black, font=\scriptsize] {attributes n};
  \draw[->, black] (0,0) -- (0,4.2) node[above, black, font=\scriptsize] {numbers (log)};
  % full table d^n (steep)
  \draw[red, very thick] (0.4,0.25) .. controls (2.6,0.6) and (3.6,1.6) .. (5.2,3.8);
  \node[red, anchor=south east, font=\scriptsize] at (5.2,3.8) {full table (d to the n)};
  % additive n*d (shallow, near-linear on log)
  \draw[acc, very thick] (0.4,0.35) .. controls (2.6,0.95) and (4.2,1.2) .. (5.8,1.35);
  \node[acc, anchor=north west, font=\scriptsize] at (4.6,1.05) {additive (n times d)};
  % marker n = 5
  \draw[black, dashed] (4.4,0) -- (4.4,3.25);
  \node[anchor=north, font=\scriptsize, text=black] at (4.4,-0.05) {n = 5};
  \fill[red] (4.4,3.25) circle (1.6pt);
  \node[red, anchor=south east, font=\scriptsize] at (4.25,3.3) {3125};
  \fill[acc] (4.4,1.28) circle (1.6pt);
  \node[acc, anchor=south east, font=\scriptsize] at (4.3,1.35) {25};
\end{tikzpicture}
$$

MPI can genuinely fail, and the failure is instructive. At a medieval market you are
buying hunting dogs, chickens, and wicker cages. The dogs are valuable — but with
too few cages, the dogs eat the chickens, so the trade-off between dogs and chickens
depends strongly on the number of cages. That three-way **interaction** breaks
preferential independence and, with it, additivity: you cannot score dogs, chickens,
and cages separately and sum, because the value of dogs is entangled with how many
cages you hold.

$$
% caption: A violation of mutual preferential independence. The dogs-versus-chickens
% trade-off (arrow) reverses depending on the number of cages: with enough cages
% more chickens are good, but with too few cages the dogs eat them, so more
% chickens are bad. Because a third attribute changes the trade-off, the attributes
% are not additively separable.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  opt/.style={draw, minimum width=26mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[font=\scriptsize, text=black, anchor=east] at (-0.3,2.0) {many cages:};
  \node[opt] (a1) at (1.7,2.0) {few chickens};
  \node[opt, draw=acc, text=acc] (b1) at (5.7,2.0) {many chickens};
  \draw[->, acc, thick] (a1) -- (b1) node[midway, above, font=\scriptsize, text=acc] {prefer};
  \node[font=\scriptsize, text=black, anchor=east] at (-0.3,0.2) {too few cages:};
  \node[opt, draw=red, text=red] (a2) at (1.7,0.2) {few chickens};
  \node[opt] (b2) at (5.7,0.2) {many chickens};
  \draw[->, red, thick] (b2) -- (a2) node[midway, above, font=\scriptsize, text=red] {prefer};
  \node[font=\scriptsize, text=black, anchor=north] at (3.7,-0.6)
    {trade-of\/f reverses with cage count: MPI violated};
\end{tikzpicture}
$$

#### Utility independence under uncertainty

Everything above concerned _value_ functions over sure outcomes. When outcomes are
uncertain the agent chooses among **lotteries**, and we need the analogous
structure on preferences over lotteries. **Utility independence** extends
preferential independence to cover them.

> **Definition (Utility independence).** A set of attributes $\mathbf{X}$ is
> **utility independent** of a set $\mathbf{Y}$ if preferences between _lotteries_
> on the attributes in $\mathbf{X}$ are independent of the fixed values of the
> attributes in $\mathbf{Y}$. A set is **mutually utility independent** (MUI) when
> each of its subsets is utility independent of the remainder.

MUI is the uncertain-world counterpart of MPI, and it yields its own
representation theorem. Where MPI gave a purely additive value function, MUI gives
a **multiplicative utility function**. For three attributes, writing $U_i$ for
$U_i(x_i)$,

$$
U = k_1 U_1 + k_2 U_2 + k_3 U_3
+ k_1 k_2 U_1 U_2 + k_2 k_3 U_2 U_3 + k_3 k_1 U_3 U_1
+ k_1 k_2 k_3 U_1 U_2 U_3.
$$

The expression looks busy, but it contains only three single-attribute utilities
$U_1, U_2, U_3$ and three constants $k_1, k_2, k_3$. In general an $n$-attribute MUI
problem needs $n$ single-attribute utilities and $n$ constants, each of the utility
functions developed independently of the others, and the combination is guaranteed
to reproduce the correct overall preferences. What the additive form lacks is the
cross-terms $U_i U_j$ — they capture how the attributes interact under risk —
and with additional independence assumptions those terms vanish and the utility
collapses to the purely additive $U = \sum_i k_i U_i$.

$$
% caption: The ladder of preference structure. Stronger regularity (down the
% ladder) buys a simpler utility form and fewer numbers to assess: no structure
% needs a full $d^n$ table; MUI over lotteries gives the multiplicative form (n
% utilities, n constants); MPI over sure outcomes gives the additive value
% function (n one-dimensional functions).
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  band/.style={draw, minimum width=54mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[band] (none) at (0,3.0) {no structure\\full table: d to the n numbers};
  \node[band] (mui) at (0,1.4) {mutual utility independence (MUI)\\multiplicative: n utilities, n constants};
  \node[band, draw=acc, text=acc] (mpi) at (0,-0.2) {mutual preferential independence (MPI)\\additive: sum of n one-dim functions};
  \draw[->, thick] (none) -- (mui) node[midway, right=2mm, font=\scriptsize, text=black] {more structure};
  \draw[->, acc, thick] (mui) -- (mpi) node[midway, right=2mm, font=\scriptsize, text=black] {+ extra assumptions};
\end{tikzpicture}
$$

## Decision networks

A **decision network** — the more descriptive name for an **influence diagram** —
lays a decision problem out as a graph, extending a Bayesian network with two new
node types.[^aima-dn] It captures the agent's current state, its possible actions,
the state its action produces, and the utility of that state, all in one picture
you can evaluate mechanically.

$$
% caption: A decision network for the airport-siting problem. Oval chance nodes
% (Air Traffic, Litigation, Construction, Deaths, Noise, Cost) are random
% variables; the rectangle Airport Site is the decision node; the diamond U is the
% utility node. Airport Site influences Deaths, Noise, and Cost, which together
% with their other causes feed the utility.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  chance/.style={draw, ellipse, minimum width=20mm, minimum height=8mm, align=center, font=\scriptsize},
  decision/.style={draw, rectangle, minimum width=20mm, minimum height=8mm, font=\scriptsize},
  util/.style={draw, diamond, aspect=1.3, inner sep=1pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[decision, draw=acc, text=acc] (site) at (3.0,4.0) {Airport Site};
  \node[chance] (traffic) at (0,2.4) {\texttt{Air Traffic}};
  \node[chance] (litig)   at (0,1.2) {Litigation};
  \node[chance] (constr)  at (0,0)   {Construction};
  \node[chance] (deaths)  at (4.0,2.4) {Deaths};
  \node[chance] (noise)   at (4.0,1.2) {Noise};
  \node[chance] (cost)    at (4.0,0)   {Cost};
  \node[util, draw=acc, text=acc] (u) at (7.0,1.2) {U};
  \draw[->] (traffic) -- (deaths);
  \draw[->] (site) -- (deaths);
  \draw[->] (site) -- (noise);
  \draw[->] (site) to[out=-90,in=150] (cost);
  \draw[->] (litig) -- (cost);
  \draw[->] (constr) -- (cost);
  \draw[->, acc] (deaths) -- (u);
  \draw[->, acc] (noise) -- (u);
  \draw[->, acc] (cost) -- (u);
\end{tikzpicture}
$$

Three node types appear:

- **Chance nodes** (ovals) are random variables, exactly as in a Bayesian network,
  each carrying a conditional distribution indexed by its parents. Parents may be
  chance _or_ decision nodes. _Air Traffic_, _Litigation_, _Construction_ describe
  the current state; _Deaths_, _Noise_, _Cost_ describe the outcome and depend on
  the chosen site.
- **Decision nodes** (rectangles) are the points where the agent chooses. Here
  _Airport Site_ takes a different value for each candidate site, and that choice
  influences cost, safety, and noise. We treat the single-decision case; sequential
  decisions are the province of MDPs.
- **Utility nodes** (diamonds, also called _value nodes_) hold the utility as a
  function of the parents that directly affect it — a table, or a parameterized
  additive/linear function of the attribute values.

A common shorthand omits the outcome-state chance nodes and wires the utility node
straight to the decision and current-state nodes. The utility node then encodes the
**expected** utility of each action given the state — an **action-utility function**,
the same object called a **Q-function** in reinforcement learning. Because outcome
nodes like _Noise_ and _Cost_ refer to future states and can never be observed as
evidence, this compiled form is always usable when the full one is; it has fewer
nodes but hides the outcome structure, so a change in aircraft noise now has to be
edited into the action-utility table rather than a single conditional distribution.

$$
% caption: The action-utility (compiled) form of the airport network. The outcome
% chance nodes are factored out; the utility node U attaches directly to the
% decision node Airport Site and the current-state chance nodes, and stores the
% expected utility of each action.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  chance/.style={draw, ellipse, minimum width=20mm, minimum height=8mm, font=\scriptsize},
  decision/.style={draw, rectangle, minimum width=20mm, minimum height=8mm, font=\scriptsize},
  util/.style={draw, diamond, aspect=1.3, inner sep=1pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[decision, draw=acc, text=acc] (site) at (2.6,3.2) {Airport Site};
  \node[chance] (traffic) at (0,2.0) {\texttt{Air Traffic}};
  \node[chance] (litig)   at (0,0.9) {Litigation};
  \node[chance] (constr)  at (0,-0.2) {Construction};
  \node[util, draw=acc, text=acc] (u) at (5.6,0.9) {U};
  \draw[->, acc] (site) -- (u);
  \draw[->] (traffic) -- (u);
  \draw[->] (litig) -- (u);
  \draw[->] (constr) -- (u);
\end{tikzpicture}
$$

### Evaluating a decision network

Once the decision node is fixed to a value it behaves like an observed chance node,
and inference in the resulting Bayesian network gives the expected utility of that
action. Trying each action and keeping the best gives the algorithm.

```algorithm
caption: $\textsc{Evaluate-Decision-Network}(DN, \mathbf{e})$ — pick the best action
set the evidence variables in $DN$ to the current state $\mathbf{e}$
$a^\ast \gets$ none;  $u^\ast \gets -\infty$
for each possible value $a$ of the decision node do
  set the decision node to $a$
  run probabilistic inference for the utility node's parents given $a, \mathbf{e}$
  $EU(a) \gets \sum_{s'} P(s' \mid a, \mathbf{e})\, U(s')$ // expected utility of $a$
  if $EU(a) > u^\ast$ then
    $u^\ast \gets EU(a)$;  $a^\ast \gets a$
return $a^\ast$
```

This is a direct extension of Bayesian-network inference, and it slots into a
utility-based agent unchanged. What makes the sequential problem harder — several
decisions in a row, each observing the outcome of the last — is the province of
MDPs; a single decision node needs only one inference sweep per action.

## The value of information

The evaluation above assumed the agent already holds all available evidence. In
practice one of the most important parts of deciding is knowing _what questions to
ask_. A doctor cannot run every test at once; tests cost money and time and
sometimes carry risk, so their worth depends on whether the result would change the
treatment plan and by how much. **Information value theory** lets an agent decide
which observations to acquire, treating the observation of a chance variable as a
simplified action that changes only the agent's _belief state_, not the world.

### A worked example

An oil company can buy one of $n$ indistinguishable ocean-drilling blocks. Exactly
one block holds oil worth $C$ dollars; the rest are worthless. Each block sells for
$C/n$, so a risk-neutral company is indifferent between buying and not buying — its
expected profit is zero either way.

Now a seismologist offers a survey of block $3$ that reveals _definitively_ whether
it holds oil. What is that survey worth? Reason through what the company would do
with the answer:

- With probability $1/n$ the survey says block 3 has oil. The company buys it for
  $C/n$ and profits $C - C/n = (n-1)C/n$.
- With probability $(n-1)/n$ the survey says block 3 is dry. The company now buys
  one of the _other_ blocks, whose chance of oil has risen from $1/n$ to
  $1/(n-1)$, for an expected profit of $C/(n-1) - C/n = C/(n(n-1))$.

Averaging over the two survey outcomes,

$$
\frac{1}{n} \cdot \frac{(n-1)C}{n} \;+\; \frac{n-1}{n} \cdot \frac{C}{n(n-1)} \;=\; \frac{C}{n}.
$$

The information is worth exactly $C/n$ — the price of a block, and the entire
expected profit the company can now make. Its value comes from letting the company
tailor its action to the _actual_ situation instead of doing what is best _on
average_ across situations.

### The VPI formula

Let the agent's current evidence be $\mathbf{e}$. The expected utility of the best
action now is

$$
EU(\alpha \mid \mathbf{e}) \;=\; \max_a \sum_{s'} P\big(\textsc{Result}(a) = s' \mid a, \mathbf{e}\big)\, U(s'),
$$

and after learning $E_j = e_{j}$ the best action might change, giving
$EU(\alpha_{e_j} \mid \mathbf{e}, e_{j})$. But $E_j$ is a random variable whose
value is currently unknown, so we average over its possible values $e_{jk}$ using
current beliefs. The **value of perfect information** is

$$
\mathit{VPI}_{\mathbf{e}}(E_j) \;=\; \Big(\sum_k P(E_j = e_{jk} \mid \mathbf{e})\; EU(\alpha_{e_{jk}} \mid \mathbf{e}, E_j = e_{jk})\Big) \;-\; EU(\alpha \mid \mathbf{e}).
$$

In words: the expected utility of acting _after_ the observation, minus the
expected utility of acting now. Three regimes illustrate it. Choosing between a
safe highway ($a_1$) and a winding dirt road ($a_2$) over a mountain range, the
value of a satellite report on road conditions depends on how the resulting
utilities $U_1', U_2'$ are distributed.

$$
% caption: Three cases for the value of information (distributions of the two
% actions' post-observation utilities). (a) $a_1$ almost always wins, so the report
% will not change the plan and is worthless. (b) The choice is unclear and the
% outcomes differ widely, so the report is valuable. (c) The choice is unclear but
% the outcomes differ little, so the report is worth little.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- (a) separated ---
  \begin{scope}
    \draw[->, black] (0,0) -- (3.6,0) node[right, black] {U};
    \draw[->, black] (0,0) -- (0,2.4);
    \draw[red, thick] plot[smooth, domain=0.3:1.7, samples=30] (\x, {1.3*exp(-8*(\x-1.0)^2)});
    \draw[acc, thick] plot[smooth, domain=1.6:3.2, samples=30] (\x, {1.3*exp(-8*(\x-2.4)^2)});
    \node[red, anchor=north] at (1.0,-0.05) {U2};
    \node[acc, anchor=north] at (2.4,-0.05) {U1};
    \node[anchor=north] at (1.8,-0.55) {(a)};
  \end{scope}
  % --- (b) overlapping, broad ---
  \begin{scope}[xshift=4.6cm]
    \draw[->, black] (0,0) -- (3.6,0) node[right, black] {U};
    \draw[->, black] (0,0) -- (0,2.4);
    \draw[red, thick] plot[smooth, domain=0.2:3.0, samples=40] (\x, {1.0*exp(-3*(\x-1.4)^2)});
    \draw[acc, thick] plot[smooth, domain=0.4:3.3, samples=40] (\x, {1.1*exp(-3*(\x-1.8)^2)});
    \node[red, anchor=north] at (1.4,-0.05) {U2};
    \node[acc, anchor=north] at (2.0,-0.05) {U1};
    \node[anchor=north] at (1.8,-0.55) {(b)};
  \end{scope}
  % --- (c) overlapping, narrow ---
  \begin{scope}[xshift=9.2cm]
    \draw[->, black] (0,0) -- (3.6,0) node[right, black] {U};
    \draw[->, black] (0,0) -- (0,2.4);
    \draw[red, thick] plot[smooth, domain=1.35:1.95, samples=30] (\x, {2.1*exp(-90*(\x-1.65)^2)});
    \draw[acc, thick] plot[smooth, domain=1.55:2.15, samples=30] (\x, {1.7*exp(-90*(\x-1.85)^2)});
    \node[red, anchor=north] at (1.55,-0.05) {U2};
    \node[acc, anchor=north] at (2.05,-0.05) {U1};
    \node[anchor=north] at (1.8,-0.55) {(c)};
  \end{scope}
\end{tikzpicture}
$$

In short: _information has value to the extent that it is likely to cause a change
of plan, and to the extent that the new plan is significantly better than the old
one._ In case (a) no report changes the decision; in (b) it might, and the stakes
are high; in (c) it might, but the stakes are tiny.

### Properties, and an agent that gathers information

VPI has two general properties.

> **Theorem (Nonnegativity of information value).** For any evidence variable and
> any current evidence, $\mathit{VPI}_{\mathbf{e}}(E_j) \ge 0$. In the worst case
> the agent can ignore what it learns, so learning cannot lower expected utility.

It is a statement about _expected_ value, not actual value — a misleading test can
lead to a worse plan (a false positive prompting needless surgery), but that does
not mean the test should be skipped. The second property is that VPI is **not
additive** — learning $E_j$ can raise or lower the value of later learning $E_k$ —
but it _is_ **order independent**:

$$
\mathit{VPI}_{\mathbf{e}}(E_j, E_k) = \mathit{VPI}_{\mathbf{e}}(E_j) + \mathit{VPI}_{\mathbf{e}, e_j}(E_k) = \mathit{VPI}_{\mathbf{e}}(E_k) + \mathit{VPI}_{\mathbf{e}, e_k}(E_j).
$$

Order independence is what distinguishes sensing actions from ordinary actions and
simplifies planning a sequence of observations. An information-gathering agent uses
VPI as its guide: request the observation with the best value-per-unit-cost, until
no observation is worth its cost.

```algorithm
caption: $\textsc{Information-Gathering-Agent}(percept)$ — sense before acting
persistent: $D$, a decision network
integrate $percept$ into $D$
$j \gets$ the value that maximizes $\mathit{VPI}(E_j) / \mathit{Cost}(E_j)$
if $\mathit{VPI}(E_j) > \mathit{Cost}(E_j)$ then
  return $\textsc{Request}(E_j)$ // gather more evidence first
else
  return the best action from $D$
```

Because it evaluates VPI as though only one variable will ever be observed, this
design is **myopic** — the same shortsighted heuristic as greedy search. It can
undervalue a sequence of observations that only jointly pay off, but in practice it
works well; myopic information-gathering has been shown to outperform expert
physicians at selecting diagnostic tests.

That completes single-agent decision analysis. Every tool so far assumed a
non-strategic environment. When outcomes depend on _other_ rational agents, whose
choices react to the agent's own, a different theory is needed.

This continues in [Game Theory and Mechanism Design](/artificial-intelligence/uncertainty/game-theory-and-mechanism-design),
which studies decisions among agents (Nash and maximin equilibria) and then inverts the
question to engineer rules under which selfish play yields a good collective outcome.

[^aima-mau]: **Russell & Norvig**, _Artificial Intelligence: A Modern Approach_ (3rd ed.), §16.4 — Multiattribute Utility Functions: dominance (strict and stochastic), preference and utility independence, and the additive and multiplicative value/utility functions that follow from them.
[^aima-dn]: **Russell & Norvig**, §16.5 — Decision Networks: chance, decision, and utility nodes; the action-utility (compiled) form; and the evaluation procedure that treats a set decision node as evidence.