C.3 Agent Foundations: Coherence and Embedded Agency
Coherence and consequentialism
Reading: Coherent decisions imply consistent utilities
Reading: Complete class theorem — consequentialist foundations
Exercise 3: The Complete Class Theorem
🔵🔵🔵🔵⚫️ Importance
🔴🔴🔴⚫️⚫️ Difficulty
The setup: decision-making under uncertainty. Imagine you must choose an action, but you do not know which environment you are in. There are finitely many actions \(\mathcal{A} = \{a_1, \ldots, a_k\}\) and finitely many possible environments \(\Omega = \{\omega_1, \ldots, \omega_n\}\). If you take action \(a\) and the true environment turns out to be \(\omega\), you receive a reward \(u(a, \omega) \in \mathbb{R}\).
Example. You are deciding whether to carry an umbrella (\(a_1\)) or not (\(a_2\)). The environment is either rainy (\(\omega_1\)) or sunny (\(\omega_2\)). The rewards might be:
\[ \begin{array}{c|cc} & \omega_1 \text{ (rain)} & \omega_2 \text{ (sun)} \\ \hline a_1 \text{ (umbrella)} & 8 & 5 \\ a_2 \text{ (no umbrella)} & 2 & 10 \end{array} \]
Decision rules. A decision rule \(\delta = (\lambda_1, \ldots, \lambda_k)\) is a possibly randomized strategy: you play action \(a_j\) with probability \(\lambda_j\), where \(\lambda_j \geq 0\) and \(\sum_{j=1}^k \lambda_j = 1\). A pure decision rule puts all its weight on a single action. A mixed rule randomizes.
The reward of \(\delta\) in environment \(\omega\) is the average reward under this randomization:
\[ u(\delta, \omega) := \sum_{j=1}^k \lambda_j \, u(a_j, \omega). \]
Risk vectors and the risk set. To compare decision rules across all environments at once, package the rewards into a single vector. The risk vector of \(\delta\) is
\[ r(\delta) = \bigl(u(\delta, \omega_1), \ldots, u(\delta, \omega_n)\bigr) \in \mathbb{R}^n. \]
The risk set is the set of all achievable risk vectors:
\[ \mathcal{R} = \Bigl\{\sum_{j=1}^k \lambda_j \, r(a_j) : \lambda_j \geq 0,\; \sum_{j=1}^k \lambda_j = 1\Bigr\}. \]
Geometrically, \(\mathcal{R}\) is the convex hull of the pure-action risk vectors \(\{r(a_1), \ldots, r(a_k)\}\). In the umbrella example, \(r(a_1) = (8, 5)\) and \(r(a_2) = (2, 10)\).
Admissibility. A decision rule \(\delta\) is admissible if there is no other rule \(\delta'\) that does at least as well as \(\delta\) in every environment and strictly better in at least one. The Pareto frontier \(\mathcal{F} \subseteq \mathcal{R}\) is the set of admissible risk vectors, and a pure action \(a_j\) is Pareto-optimal if \(r(a_j) \in \mathcal{F}\).
Bayesian expected utility. Given a prior \(\pi = (\pi_1, \ldots, \pi_n)\) with \(\pi_i \geq 0\) and \(\sum_i \pi_i = 1\), the expected utility of \(\delta\) under \(\pi\) is
\[ \mathrm{EU}(\delta, \pi) := \sum_{i=1}^n \pi_i \, u(\delta, \omega_i) = \pi \cdot r(\delta). \]
A decision rule \(\delta\) is Bayes-optimal under \(\pi\) if \(\mathrm{EU}(\delta, \pi) \geq \mathrm{EU}(\delta', \pi)\) for all \(\delta' \in \Delta(\mathcal{A})\).
The theorem. These two weak-looking rationality criteria turn out to match exactly.
Theorem (Complete Class). Every admissible decision rule is Bayes-optimal under some prior \(\pi\) with \(\pi_i > 0\) for all \(i\). Conversely, every Bayes-optimal rule under such a prior is admissible.
Part 3(a). Show the following two facts:
- Any admissible decision rule \(\delta = \sum_j \lambda_j a_j\) places zero weight on dominated pure actions: \(\lambda_j = 0\) whenever \(a_j\) is not Pareto-optimal.
- Every Bayes-optimal rule under a prior \(\pi\) with \(\pi_i > 0\) for all \(i\) is admissible.
Hint: Part 3(a)
For (i), replace any positive weight on a dominated pure action by the action that dominates it.
For (ii), if \(\delta'\) dominated \(\delta\), what would happen to \(\mathrm{EU}(\delta', \pi)\) compared to \(\mathrm{EU}(\delta, \pi)\)? What does full support of \(\pi\) buy you?
Part 3(b). A face \(F\) of the Pareto frontier is a maximal convex subset of \(\mathcal{F}\) of the form
\[ F = \Bigl\{\sum_{l=1}^p \mu_l \, r(a_{i_l}) : \mu_l \geq 0,\; \sum_{l=1}^p \mu_l = 1\Bigr\} \]
for some subset of Pareto-optimal pure actions \(\{a_{i_1}, \ldots, a_{i_p}\}\). Define the difference vectors \(v_l := r(a_{i_l}) - r(a_{i_1})\) for \(l = 2, \ldots, p\), and let \(H = \mathrm{span}\{v_2, \ldots, v_p\}\). Show that \(H\) consists precisely of the directions along which one can move within \(F\): if \(r(\delta) \in F\), then \(r(\delta) + h\) can lie in \(F\) only if \(h \in H\).
Hint for Part 3(b)
- First show that each \(v_l \in H\) is a feasible direction: for any \(\delta = \sum_l \mu_l r(a_{i_l}) \in F\), you can move in the direction \(v_l\) by adjusting the weights \(\mu_1\) and \(\mu_l\) while keeping all weights non-negative.
- For the converse, write any point \(r(\delta') \in F\) as \(r(\delta') = \sum_l \mu'_l r(a_{i_l})\). Then \(r(\delta') - r(\delta) = \sum_l (\mu'_l - \mu_l) r(a_{i_l})\). Since \(\sum_l \mu_l = \sum_l \mu'_l = 1\), the difference vector is a linear combination of the \(v_l\).
Part 3(c). Let \(\pi\) be the unit normal to the hyperplane \(H\) constructed in Part 3(b), normalized so that \(\pi_i > 0\) for all \(i\) and \(\sum_i \pi_i = 1\). You may assume that the entire risk set \(\mathcal{R}\) lies on one side of this hyperplane. Show that \(\mathrm{EU}(\delta, \pi)\) is constant for all \(\delta\) with \(r(\delta) \in F\), and that every rule on the face is simultaneously Bayes-optimal under \(\pi\). Conclude the Complete Class Theorem.
Hint for Part 3(c)
- For any \(\delta\) with \(r(\delta) \in F\), \(\mathrm{EU}(\delta, \pi) = \pi \cdot r(\delta)\). If \(\delta'\) also lies on \(F\), then \(r(\delta') - r(\delta) \in H\) by Part 3(b). Since \(\pi\) is normal to \(H\), \(\pi \cdot (r(\delta') - r(\delta)) = 0\), so \(\mathrm{EU}\) is constant on \(F\).
- For any \(\delta''\) with \(r(\delta'') \in \mathcal{R}\), the assumption that \(\mathcal{R}\) lies on one side of the hyperplane through \(F\) with normal \(\pi\) gives \(\pi \cdot r(\delta'') \leq \pi \cdot r(\delta)\), so every rule on \(F\) is Bayes-optimal.
- Since every admissible rule lies on some face and every face yields a prior, every admissible rule is Bayes-optimal under some full-support \(\pi\).