Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Rationality & Expected Utility

Von Neumann–Morgenstern axioms and what “rational” really means.

Why should an agent maximize expected utility, rather than guard against the worst case or follow a rule of thumb? Von Neumann and Morgenstern gave a startling answer: if its preferences satisfy four innocent-looking axioms, it already behaves as an expected-utility maximizer. This lesson proves the theorem, then probes where people, and practical agents, depart from it.

What you’ll learn

  • State the von Neumann–Morgenstern axioms and prove the expected utility theorem, including uniqueness up to positive affine transformations.
  • Use a money pump to argue for transitivity, and show which axiom the Allais paradox violates.
  • Characterize risk attitudes by the curvature of utility, and derive the Arrow–Pratt approximation to the risk premium.
  • Explain why stationary preferences over reward sequences lead to exponential discounting, and predict how discounting changes an optimal policy.
  • Distinguish perfect rationality from bounded optimality, and prove that the expected value of information is never negative.

Lotteries and the axioms

Independence says that a component both options share, received with the same probability, should not affect the ranking: if a coin decides between rr and your choice, only your choice matters. Russell and Norvig list six "constraints" instead (orderability, transitivity, continuity, substitutability, monotonicity, decomposability), a presentation in the same spirit.

Why transitivity? An agent with cyclic strict preferences A≻B≻C≻AA\succ B\succ C\succ A can be money-pumped. Holding CC, it pays a cent to swap for BB, another to swap for AA, and another to swap for CC: it is back where it started, three cents poorer, and ready to go round again.

Check your understanding

Allais (1953). Choose within each pair (amounts in millions of dollars):

  • L1L_1: 1 for sure, or L1′L_1': 5 with 10%, 1 with 89%, 0 with 1%.
  • L2L_2: 1 with 11%, 0 with 89%, or L2′L_2': 5 with 10%, 0 with 90%.

Most people choose L1L_1 and L2′L_2'. Which axiom does that pattern violate?

  1. Completeness
  2. Transitivity
  3. Continuity
  4. Independence
Show the answer

D. Independence

Let MM be the lottery "5 with probability 1011\tfrac{10}{11}, else 0". Then L1=0.11 δ1+0.89 δ1L_1=0.11\,\delta_1+0.89\,\delta_1, L1′=0.11 M+0.89 δ1L_1'=0.11\,M+0.89\,\delta_1, L2=0.11 δ1+0.89 δ0L_2=0.11\,\delta_1+0.89\,\delta_0 and L2′=0.11 M+0.89 δ0L_2'=0.11\,M+0.89\,\delta_0. Each pair differs only in δ1\delta_1 versus MM; the shared 89% component is δ1\delta_1 in the first pair and δ0\delta_0 in the second. Independence forces L1≻L1′  ⟺  L2≻L2′L_1\succ L_1'\iff L_2\succ L_2'. In expected-utility terms, L1≻L1′L_1\succ L_1' says 0.11 u(1)>0.10 u(5)+0.01 u(0)0.11\,u(1)>0.10\,u(5)+0.01\,u(0), and L2′≻L2L_2'\succ L_2 says the reverse.

The expected utility theorem

DerivationProof sketch
  1. δxˉ ≿ p ≿ δx‾for all p,Lα=α δxˉ+(1−α) δx‾\delta_{\bar x}\ \succsim\ p\ \succsim\ \delta_{\underline x}\quad\text{for all }p,\qquad L_\alpha=\alpha\,\delta_{\bar x}+(1-\alpha)\,\delta_{\underline x}

    Necessity is easy: expected utility is linear in pp, which gives independence, and continuous in mixing weights, which gives continuity. For sufficiency, pick a best outcome xˉ\bar x and a worst x‾\underline x (finitely many outcomes, complete and transitive preferences). Repeated use of independence shows that every lottery lies between them. Assume δxˉ≻δx‾\delta_{\bar x}\succ\delta_{\underline x} (otherwise everything is indifferent) and write LαL_\alpha for "xˉ\bar x with probability α\alpha, else x‾\underline x".

  2. Lα=γ δxˉ+(1−γ) Lβ,γ=α−β1−β∈(0,1]L_\alpha=\gamma\,\delta_{\bar x}+(1-\gamma)\,L_\beta,\qquad\gamma=\frac{\alpha-\beta}{1-\beta}\in(0,1]

    More chance of the best is better. Independence gives δxˉ≻Lβ\delta_{\bar x}\succ L_\beta for β<1\beta<1 (mix δxˉ≻δx‾\delta_{\bar x}\succ\delta_{\underline x} with δxˉ\delta_{\bar x}). For α>β\alpha>\beta, write LαL_\alpha as a mixture of δxˉ\delta_{\bar x} and LβL_\beta, and apply independence once more to get Lα≻LβL_\alpha\succ L_\beta:

  3. p∼LU(p),U(p)∈[0,1]p\sim L_{U(p)},\qquad U(p)\in[0,1]

    Calibrate. By continuity each pp is indifferent to some LαL_\alpha, and by the previous step that α\alpha is unique. Call it U(p)U(p). Then p≿q  ⟺  U(p)≥U(q)p\succsim q\iff U(p)\ge U(q).

  4. λp+(1−λ)q ∼ λLU(p)+(1−λ)LU(q)=LλU(p)+(1−λ)U(q)\lambda p+(1-\lambda)q\ \sim\ \lambda L_{U(p)}+(1-\lambda)L_{U(q)}=L_{\lambda U(p)+(1-\lambda)U(q)}

    Linearity. Independence lets you replace pp and qq by their calibrated equivalents inside a mixture, and a mixture of two LL's is again an LL:

  5. U(p)=∑xp(x) u(x)U(p)=\sum_xp(x)\,u(x)

    So UU is affine in mixtures. Writing p=∑xp(x) δxp=\sum_xp(x)\,\delta_x and setting u(x)=U(δx)u(x)=U(\delta_x) gives the representation.

  6. v(x)=u(x) v(xˉ)+(1−u(x)) v(x‾)=a u(x)+b,a=v(xˉ)−v(x‾)>0v(x)=u(x)\,v(\bar x)+\big(1-u(x)\big)\,v(\underline x)=a\,u(x)+b,\qquad a=v(\bar x)-v(\underline x)>0

    Uniqueness. If vv is another expected-utility representation, apply it to δx∼Lu(x)\delta_x\sim L_{u(x)}, where uu is normalized by u(xˉ)=1u(\bar x)=1 and u(x‾)=0u(\underline x)=0:

The theorem constrains consistency, not content. It says nothing about which outcomes an agent should value, only that coherent preferences over gambles act as if a utility were being averaged. Utilities live on an interval scale: "utility 10 versus 5" does not mean twice as good, but ratios of utility differences are meaningful, because they survive every map au+bau+b.

Reinforcement learning has the same freedom to rescale rewards. Potential-based reward shaping (Ng, Harada and Russell, 1999) is a sequential cousin: adding γΦ(s′)−Φ(s)\gamma\Phi(s')-\Phi(s) to every reward leaves optimal policies unchanged.

Think first You normalize u(xˉ)=1u(\bar x)=1 and u(x‾)=0u(\underline x)=0, and find you are indifferent between outcome yy and a 70% chance of xˉ\bar x (else x‾\underline x). On a new scale where xˉ\bar x is worth 1010 and x‾\underline x is worth −10-10, what is yy worth?

u(y)=0.7u(y)=0.7, and the new scale is v=20u−10v=20u-10, so v(y)=20(0.7)−10=4v(y)=20(0.7)-10=4; equivalently 0.7(10)+0.3(−10)=40.7(10)+0.3(-10)=4. Every positive affine rescaling preserves every choice between lotteries.

Risk attitudes and the utility of money

When outcomes are amounts of money, uu is an increasing function on R\R. The certainty equivalent of a gamble WW is the sure amount valued equally, CE=u−1(E[u(W)])\mathrm{CE}=u^{-1}\big(\E[u(W)]\big), and the risk premium is π=E[W]−CE\pi=\E[W]-\mathrm{CE}. By Jensen's inequality, uu is concave exactly when E[u(W)]≤u(E[W])\E[u(W)]\le u(\E[W]) for every gamble: concave utility means risk aversion (π≥0\pi\ge0), linear utility risk neutrality, convex utility risk seeking.

DerivationThe Arrow–Pratt approximation
  1. u(w+μ)−π u′(w+μ) ≈ u(w+μ)+12 u′′(w+μ) σ2u(w+\mu)-\pi\,u'(w+\mu)\ \approx\ u(w+\mu)+\tfrac12\,u''(w+\mu)\,\sigma^2

    Let W=w+ZW=w+Z with E[Z]=μ\E[Z]=\mu and a small variance Var⁡(Z)=σ2\Var(Z)=\sigma^2. Expand both sides of u(w+μ−π)=E[u(w+Z)]u(w+\mu-\pi)=\E[u(w+Z)] around w+μw+\mu:

  2. π ≈ 12 rA(w) σ2,rA(w)=−u′′(w)u′(w)\pi\ \approx\ \tfrac12\,r_A(w)\,\sigma^2,\qquad r_A(w)=-\frac{u''(w)}{u'(w)}

    Solve for the premium. It is proportional to the variance, with the coefficient of absolute risk aversion rA=−u′′/u′r_A=-u''/u' (Pratt, 1964; Arrow):

  3. u(w)=−e−aw ⇒ rA=a,u(w)=ln⁡w ⇒ rA=1wu(w)=-e^{-aw}\ \Rightarrow\ r_A=a,\qquad u(w)=\ln w\ \Rightarrow\ r_A=\frac1w

    Exponential utility has constant absolute risk aversion; logarithmic utility has rA=1/wr_A=1/w, so the same gamble matters less to a richer agent.

Think first With u(w)=wu(w)=\sqrt w, what is the certainty equivalent of a fair coin flip paying 0 or 100 dollars?

E[u]=120+12100=5\E[u]=\tfrac12\sqrt0+\tfrac12\sqrt{100}=5, so CE=52=25\mathrm{CE}=5^2=25 dollars, and the risk premium is 50−25=2550-25=25 dollars. The Arrow–Pratt approximation is poor here, because the gamble is not small relative to wealth.

Utilities over time

An agent acting over time chooses among sequences of rewards. Suppose its preferences over sequences are stationary: if two sequences begin with the same reward, they are ranked the same way as the sequences with that first reward removed. Koopmans (1960) and later work showed that stationarity, together with separability across periods and mild regularity conditions, forces the additive discounted form

U(r0,r1,r2,… )=∑t≥0γt rt,0<γ≤1,U(r_0,r_1,r_2,\dots)=\sum_{t\ge0}\gamma^t\,r_t,\qquad0<\gamma\le1,

the return of reinforcement learning, with discount factor γ\gamma (γ=1\gamma=1 only when every sequence is finite).

Think first Many human choices are described well by hyperbolic discounting, D(t)=1/(1+t)D(t)=1/(1+t). Why can't a time-consistent agent use it?

Compare 100 dollars on day tt with 110 dollars on day t+1t+1. At t=0t=0: 100100 versus 110/2=55110/2=55, so you take the 100 now. At t=30t=30: 100/31≈3.23100/31\approx3.23 versus 110/32≈3.44110/32\approx3.44, so you plan to wait. But when day 30 arrives, you face the first comparison again and switch. Only exponential discounting makes the ratio D(t+1)/D(t)=γD(t+1)/D(t)=\gamma independent of tt, so plans are never reversed (Strotz, 1950s).

Predict before you look

In the bridge world below, the start cell has a +1 exit one step to the west and a +10 exit five steps to the east, across a bridge over a chasm. Steps cost nothing and, with the noise at 0, moves always succeed. Below which discount factor γ\gamma does the rational agent at the start stop crossing?

Show the answer

0.56

Going west is worth γ⋅1\gamma\cdot1; crossing is worth γ5⋅10\gamma^5\cdot10, because the big reward arrives five steps later. Crossing wins iff 10γ5>γ10\gamma^5>\gamma, that is γ4>0.1\gamma^4>0.1, or γ>10−1/4≈0.562\gamma>10^{-1/4}\approx0.562.

Rationality with limited computation

The definition of a rational agent ignores the cost of thinking. Perfect rationality, always outputting the expected-utility-maximizing action at once, is usually out of reach: planning over a finite horizon in a partially observable MDP is PSPACE-complete (Papadimitriou and Tsitsiklis, 1987), and for some infinite-horizon criteria even deciding whether a policy can reach a given value is undecidable (Madani, Hanks and Condon, 2003). Herbert Simon's bounded rationality (1955) replaced optimizing with satisficing. Russell's later distinctions are sharper:

  • Calculative rationality: the program would eventually compute the optimal decision for the situation it started in, by which time the world may have moved on.
  • Metalevel rationality: treat computations as actions, and deliberate only while the expected improvement in the decision exceeds the cost of the time spent (Russell and Wefald, 1991).
  • Bounded optimality (Russell and Subramanian, 1995): among all programs ℓ\ell that run on the agent's machine MM, choose one with the best expected performance in its class of environments E\mathbf E.
ℓ∗=arg max⁡ℓ∈LM V(⟨ℓ,M⟩, E)\ell^*=\argmax_{\ell\in\mathcal L_M}\ V\big(\langle\ell,M\rangle,\ \mathbf E\big)
Unlike a perfectly rational agent, a bounded-optimal program always exists for a given machine, and deliberation time is part of what it optimizes.
DerivationProof
  1. E[U(a,S)]=EE[E[U(a,S)∣E]] ≤ EE[max⁡a′E[U(a′,S)∣E]]\E\big[U(a,S)\big]=\E_E\Big[\E\big[U(a,S)\mid E\big]\Big]\ \le\ \E_E\Big[\max_{a'}\E\big[U(a',S)\mid E\big]\Big]

    For any fixed action aa, the law of total expectation and the definition of a maximum give

  2. max⁡aE[U(a,S)] ≤ EE[max⁡a′E[U(a′,S)∣E]]\max_a\E\big[U(a,S)\big]\ \le\ \E_E\Big[\max_{a'}\E\big[U(a',S)\mid E\big]\Big]

    Take the maximum over aa on the left. Equality holds iff a single action attains the inner maximum for almost every observation, i.e. the information never changes the decision. The value of information is the convexity of the maximum.

The hypotheses matter. Information that is costly or arrives late can lower expected utility, and in games even free information can hurt: a player known to be informed may be exploited, or lose the ability to commit credibly. Those are exactly the settings in which agents interact with other agents.

Key takeaways

  • Von Neumann–Morgenstern: preferences over lotteries that are complete, transitive, continuous and independent are exactly those that maximize expected utility, with uu unique up to au+bau+b, a>0a>0.
  • Intransitive agents can be money-pumped; the Allais pattern violates independence. Expected utility is a normative standard, not a description of people.
  • Concave utility means risk aversion, with risk premium π≈12rAσ2\pi\approx\tfrac12r_A\sigma^2; the St. Petersburg game shows why utilities over unbounded gambles must be bounded.
  • Stationary, separable preferences over reward sequences force exponential discounting; γ\gamma encodes time preference and can flip optimal policies (on the bridge, at γ=10−1/4\gamma=10^{-1/4}).
  • Perfect rationality is intractable; bounded optimality optimizes over feasible programs; free information never lowers a single decision maker's expected utility.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

uu is a von Neumann–Morgenstern utility for an agent's preferences. Which function is guaranteed to represent the same preferences over lotteries?

  1. u3u^3
  2. eue^{u}
  3. 3u+73u+7
  4. −u-u
Show the answer

C. 3u+73u+7

Only positive affine transformations preserve every expected-utility comparison. Monotone but nonlinear maps such as u3u^3 or eue^u preserve the ranking of sure outcomes but can reverse comparisons between gambles.

Question 2

An agent with concave utility of money is offered a gamble, or the gamble's expected value for sure. What does it choose?

  1. The gamble
  2. The sure amount (or it is indifferent)
  3. It is always indifferent
  4. It depends only on the gamble's variance
Show the answer

B. The sure amount (or it is indifferent)

Jensen's inequality: E[u(W)]≤u(E[W])\E[u(W)]\le u(\E[W]) for concave uu, so the sure expected value is weakly preferred and the risk premium is non-negative. Variance alone determines the premium only approximately, for small gambles.

Question 3

Which discount function guarantees that an agent never reverses a plan merely because time has passed?

  1. D(t)=γtD(t)=\gamma^t
  2. D(t)=1/(1+kt)D(t)=1/(1+kt)
  3. D(t)=1D(t)=1 for t≤Ht\le H steps from now, else 00
  4. D(t)=1/tD(t)=1/t
Show the answer

A. D(t)=γtD(t)=\gamma^t

Only with exponential discounting is the relative weight of t+1t+1 versus tt, D(t+1)/D(t)=γD(t+1)/D(t)=\gamma, the same at every tt. That stationarity is what makes plans time-consistent.

Question 4

What distinguishes bounded optimality from perfect rationality?

  1. It accepts any action that is good enough, without optimizing
  2. It allows the agent to violate the von Neumann–Morgenstern axioms
  3. It applies only to deterministic environments
  4. It optimizes over the programs that can run on the agent's actual machine, so the cost of deliberation counts
Show the answer

D. It optimizes over the programs that can run on the agent's actual machine, so the cost of deliberation counts

Perfect rationality demands the optimal action regardless of computation. Bounded optimality asks for the best program given the machine and the class of environments, which always exists.

Further reading

  • J. von Neumann & O. Morgenstern, Theory of Games and Economic Behavior, 2nd ed. (Princeton University Press, 1947).
  • M. Allais, "Le comportement de l'homme rationnel devant le risque: critique des postulats et axiomes de l'école américaine," Econometrica 21, 503–546 (1953).
  • T. C. Koopmans, "Stationary ordinal utility and impatience," Econometrica 28, 287–309 (1960).
  • S. J. Russell & D. Subramanian, "Provably bounded-optimal agents," Journal of Artificial Intelligence Research 2, 575–609 (1995).
  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapters 16–17.