第 3 章：决策问题（Decision Problems）

章节作者：Mykel J. Kochenderfer 章节定位：理论篇第三章，把第 2 章的概率模型扩展为"在不确定性下做最优决策"的形式化框架——以"效用（utility）"为偏好的实值度量，以"决策网络（decision network）"为贝叶斯网络在决策语境下的推广，以"博弈（game）"为多智能体场景下的均衡分析工具；本章覆盖的是单步决策问题，序贯决策留待第 4 章。

3.1 Utility Theory

作者开篇点明本章与第 2 章的承接关系：第 2 章关注"不确定性的概率表示与推理"，本章则在概率模型之上引入"效用函数"作为偏好的实值度量，讨论如何在此基础上做出"理性"决策。整章是单步决策问题的形式化版本，作者明确把"序贯决策"留到下一章。本章的论述路径分为三段：第 3.1 节以效用理论（utility theory）奠定理性决策的公理化基础；第 3.2 节把效用理论嵌入第 2 章的贝叶斯网络得到决策网络（decision network）；第 3.3 节则把视角扩展到多智能体场景，用博弈论处理"其他主体行为无法用概率模型直接刻画"的情形。这一"单智能体静态 → 单智能体网络化 → 多智能体"的递进与全书"先理论后应用"的整体结构一致。

承接第 2 章"比较两个命题的可信度"，本章需要"比较两个结果的合意度"。作者引入三个偏好算子来形式化地表达这种比较：用 $A \succ B$ 表示"严格偏好 A 胜于 B"，用 $A \sim B$ 表示"对 A 与 B 同样合意"，用 $A \succeq B$ 表示"偏好 A 胜于 B 或对两者无差异"。与信念一样，偏好同样可以是主观的——不同的人对同一结果可以有不同的偏好排序，而无需诉诸某个客观的"合意度"度量。在结果之上，我们还可以对"不确定的结果"——亦即"抽奖（lottery）"——做偏好比较：若 $S_{1:n}$ 是一组结果，$p_{1:n}$ 是与之对应的概率，则把这一抽奖记为

$[S_1 : p_1 ; \dots ; S_n : p_n]. \tag{3.1}$

本节聚焦的核心问题：在对偏好的某种约束之下，效用函数是否必然存在？若存在，它又具有什么数学性质？这一论证与第 2 章中"对信念度的约束导出概率公理"是同构的——后者处理的是"不确定的认知"，前者处理的是"不确定的偏好"，两者共同构成本书"概率 + 效用 = 理性决策"这一形式化路径的两根支柱。

3.1.1 Constraints on Rational Preferences

正如第 2 章对信念度施加了一组公理性约束，本节对偏好也施加一组约束；这组约束常被称为"冯·诺依曼—摩根斯坦公理（von Neumann–Morgenstern axioms）"，以 1940 年代提出该公理变体的 John von Neumann 与 Oskar Morgenstern 命名。整组公理共四条：完备性（completeness）要求对任意两个结果 A 与 B，恰好有 $A \succ B$、$B \succ A$ 或 $A \sim B$ 三者之一成立；传递性（transitivity）要求若 $A \succeq B$ 且 $B \succeq C$，则 $A \succeq C$；连续性（continuity）要求若 $A \succeq C \succeq B$，则存在某个概率 $p$ 使得 $[A : p; B : 1 - p] \sim C$——也就是可以在 A 与 B 之间用某个概率 $p$ 构造一个"等值抽奖"来匹配 C；独立性（independence）要求若 $A \succ B$，则对任意 C 与任意概率 $p$，有 $[A : p; C : 1 - p] \succeq [B : p; C : 1 - p]$——也就是说，在两个抽奖上"叠加"同一个 C 不会改变它们之间的偏好排序。

这四条公理是"理性偏好"的必要约束。作者明确指出：它们不描述真实人类的偏好——事实上有强证据表明人类常常并不满足这些公理（3.1.7 节将进一步讨论这一非理性）。本书的目标是"从计算视角理解理性决策"，以便构建可用的决策系统；把这些公理外推到"理解人类决策"则是次要兴趣。这一表态贯穿全书：本书关心的是"工程上可实现的理性"，而非"心理上可观察的人类决策"。

3.1.2 Utility Functions

正如对命题可信度的比较约束导出了实值概率测度的存在性，对理性偏好的公理性约束同样导出实值效用测度的存在性。具体而言，由上节给出的四条公理可以证明：必然存在实值函数 $U$，满足 $U(A) > U(B)$ 当且仅当 $A \succ B$，$U(A) = U(B)$ 当且仅当 $A \sim B$。该效用函数在"仿射变换"意义下唯一——也就是说，对任意常数 $m > 0$ 与 $b$，$U'(S) = mU(S) + b$ 导出的偏好与 $U$ 完全相同。效用与温度类似：开尔文、摄氏度、华氏度都是温度的合法标度，它们之间仅差一个仿射变换。

由公理还可推出"抽奖的效用"是各结果效用的概率加权平均：

\[ U\big([S_1 : p_1 ; \dots ; S_n : p_n]\big) = \sum_{i=1}^{n} p_i U(S_i). \tag{3.2} \]

这条公式是后续一切"期望效用最大化"推导的基础——它把"对抽奖的偏好"还原为"对确定性结果的偏好 + 概率"。

为具体化，作者用碰撞告警（collision avoidance）作为贯穿本节的运行实例。定义"系统是否告警（A）"与"是否发生碰撞（C）"两个二元变量，则一共有四种可能结果 $(a^0, c^0)$、$(a^1, c^0)$、$(a^0, c^1)$、$(a^1, c^1)$；只要我们的偏好是理性的，效用函数就可以用这四个参数完全刻画。例如，对形如 $[a^0, c^0 : 0.5;\, a^1, c^0 : 0.3;\, a^0, c^1 : 0.1;\, a^1, c^1 : 0.1]$ 的抽奖，其效用等于 $0.5U(a^0, c^0) + 0.3U(a^1, c^0) + 0.1U(a^0, c^1) + 0.1U(a^1, c^1)$。如果效用函数是有界的，则可以把它归一化到 $[0, 1]$：把最佳结果赋效用 1，最差结果赋效用 0，其余结果按比例缩放与平移即可。

3.1.3 Maximum Expected Utility Principle

本节把"效用函数 + 概率模型"组合为"在不确定性下做决策"的核心规则。假设我们有一个概率模型 $P(s' \mid a, o)$，表示"在观察到 $o$ 并采取行动 $a$ 后，世界状态变为 $s'$ 的概率"；并设 $U(s')$ 是对结果的偏好编码。则在观察到 $o$ 后、采取行动 $a$ 的"期望效用"定义为

\[ EU(a \mid o) = \sum_{s'} P(s' \mid a, o) U(s'). \tag{3.5} \]

最大期望效用原理（principle of maximum expected utility）指出：理性主体应当选择使期望效用最大的行动

$a^* = \arg\max_a EU(a \mid o). \tag{3.6}$

这一原则是本书的核心运算规则。作者明确表示，本书关心的是"构建理性主体"，而式 (3.6) 在这一过程中扮演中心角色——后续的决策网络评估、序贯决策中的策略搜索、多智能体决策中的均衡求解，都可以视为这条原则在不同场景下的具体化。从结构上看，(3.5) 把"概率模型 + 效用函数 → 行动的期望效用"这一映射做成了可计算的代数形式，而 (3.6) 则在这一映射之上引入了一个优化问题——这一"在不确定性下求最优"的两步法是第 3 章之后所有决策问题（包括第 4 章的 MDP、第 6 章的 POMDP）共同的形式化骨架。

3.1.4 Utility Elicitation

在构建决策系统或决策支持系统时，常常需要从一个人或一群人那里反推出效用函数，这一过程被称为"效用引导（utility elicitation）"或"偏好引导（preference elicitation）"。一种常见做法是先把效用"归一化"：把最差的结果 $S_\bot$ 赋效用 0、最好的结果 $S_\top$ 赋效用 1。只要各结果的效用是有界的，归一化只涉及缩放与平移而不改变偏好。要确定某个中间结果 $S$ 的效用 $U(S)$，只需找到概率 $p$ 使得 $S \sim [S_\top : p;\, S_\bot : 1 - p]$，则 $U(S) = p$——这是把"对结果的偏好"翻译为"对抽奖的偏好等价"，再由 (3.2) 反解出效用值。

回到碰撞告警实例：最佳结果是"不告警且无碰撞"，故设 $U(a^0, c^0) = 1$；最差结果是"告警且发生碰撞"，故设 $U(a^1, c^1) = 0$。定义抽奖 $L(p) = [a^0, c^0 : p;\, a^1, c^1 : 1 - p]$，要确定 $U(a^1, c^0)$，需找到 $p$ 使得 $(a^1, c^0) \sim L(p)$；类似地，要确定 $U(a^0, c^1)$，需找到 $p$ 使得 $(a^0, c^1) \sim L(p)$。这个过程把"对中间结果的偏好"与"对极端结果构成的标准抽奖的偏好"做了一一对应，从而把效用函数的反推还原为一个"在 $[0, 1]$ 区间上做二分搜索"的简单问题。

3.1.5 Utility of Money

一种直觉性的做法是直接用货币价值来构造效用函数：例如在为森林火灾决策系统设计效用时，可以用"财产损失的货币成本"加上"部署灭火资源的货币成本"作为效用。然而作者援引经济学共识指出：货币的效用通常不是线性的。若效用与货币呈线性关系，则"使期望货币价值最大化"与"使期望效用最大化"等价——而任何最大化期望货币价值的主体都不会购买保险，因为保险的期望货币价值通常是负的；这与现实中绝大多数人会购买保险的事实相冲突，因此货币的效用不可能是线性的。

货币的效用可以用 3.1.4 节的引导过程确定。不同的人有不同的货币效用函数，但总体趋势与图 3.1 的曲线一致：对小额货币，曲线近似线性——$100 大约是 $50 的两倍好；对较大额货币，关系常被处理为对数关系——曲线逐渐变平。这一"边际效用递减"是合理的：$1000 对亿万富翁的意义远小于对普通人的意义。

讨论货币效用时常用三个术语：假设 A 表示"得到 $50"，B 表示"以 50% 概率赢得 $100"。风险中性（risk neutral）对应线性效用，对 $50 与 50% 概率赢得 $100 无差异（$A \sim B$）。风险偏好（risk seeking）对应上凸效用，倾向于选择抽奖，即 $A \prec B$。风险厌恶（risk averse）对应下凸效用，倾向于选择确定的 $50$，即 $A \succ B$。在构建决策系统时，把货币价值作为构造效用函数的参考点是合理的，但必须时刻记住货币与效用之间的潜在非线性关系——这一非线性在保险设计、投资组合、公共政策等"涉及大量货币的决策"中尤其重要。

3.1.6 Multiple Variable Utility Functions

上节的碰撞告警效用函数只依赖两个二元变量（A 与 C），要枚举所有可能需要 $2^2 = 4$ 个参数。当变量数为 $n$ 时，参数个数为 $2^n$——这在实际应用中很快就变得不可承受。如果能利用变量之间的某种独立性，效用函数就可以被紧凑地表示；这与第 2 章用贝叶斯网络紧凑表示联合概率分布是同构的思路。

一种最简单的紧凑表示是加性分解（additive decomposition）。在某些偏好结构假设下，$n$ 个变量 $X_{1:n}$ 上的效用函数可以写成

\[ U(x_{1:n}) = \sum_{i=1}^{n} U(x_i). \tag{3.7} \]

假设所有变量都是二元的，则表示这一加性效用函数只需要 $2n$ 个参数：$U(x_1^0),\, U(x_1^1),\, \dots,\, U(x_n^0),\, U(x_n^1)$。

为说明加性分解的价值，作者把碰撞告警的例子扩展为四个二元变量：是否告警（A）、是否碰撞（C）、是否告警系统要求飞行员"加强（strengthening, S）"爬升或下降、是否告警系统要求飞行员"反转（reversal, R）"方向。若不利用任何偏好结构，需要 $2^4 = 16$ 个参数；采用加性分解则只需要 8 个参数。一种自然的构造方式是：把"无告警、无碰撞、无加强、无反转"作为基线（零成本），即 $U(a^0) = U(c^0) = U(s^0) = U(r^0) = 0$；最坏情况是碰撞，设 $U(c^1) = -1$；告警的代价最低，反转的代价高于加强（因为反转对飞行员的干扰更大）。固定 $U(c^1) = -1$ 后，整个效用函数只有三个自由参数。

加性分解并非总能成立。考虑另一类碰撞告警效用函数，定义在三个二元变量上：入侵者是否在水平方向接近（H）、是否在垂直方向接近（V）、系统是否告警（A）。碰撞威胁仅在"水平与垂直方向都接近"时才构成，因此效用函数不能在 H、V、A 之上做加性分解；但可以写成 $U(h, v, a) = U(h, v) + U(a)$——即把"威胁判断"与"是否告警"作为两个独立的加性成分。

加性分解可以用图 3.2 这样的图显式表达。图中效用节点（utility node）用菱形表示，不确定性节点（chance node）用圆圈表示；效用节点的父节点集合就是该效用节点依赖的变量集合。若父节点是离散的，效用函数可以表示为表格；若父节点是连续的，则任一实值函数都可以用于表示该效用节点。当图中存在多个效用节点时，把它们的值相加即得到整体效用值。这一"图 + 表格"的形式化表示是后文"决策网络"（3.2 节）的直接前身。

3.1.7 Irrationality

作者明确指出：决策理论是规范性的（normative）理论，告诉人们"应该怎么做"，而非描述性的（descriptive）理论，预测人们实际会怎么做。人类的判断与偏好常常不满足 3.1.1 节给出的理性公理；即便是人类专家也可能持有一组前后不一致的偏好，这对设计"以期望效用最大化为目标"的决策支持系统会构成实质性的困难。

为具体化这一非理性，作者援引 Tversky 与 Kahneman 的实验。受试者是大学生，场景是"应对一场流行病"。他们要在两个方案中表达偏好：

A：100% 概率损失 75 条生命；
B：80% 概率损失 100 条生命。

多数人选择 B。由 (3.2)，这意味着 $U(\text{lose 75}) < 0.8 U(\text{lose 100})$。他们又被要求在另一对方案中做选择：

C：10% 概率损失 75 条生命；
D：8% 概率损失 100 条生命。

多数人选择 C。这给出 $0.1 U(\text{lose 75}) > 0.08 U(\text{lose 100})$，两边同乘 10 得 $U(\text{lose 75}) > 0.8 U(\text{lose 100})$。这两个不等式互相矛盾——而推导过程并未对 $U(\text{lose 75})$ 与 $U(\text{lose 100})$ 的具体取值做假设，也未假设"损失 100 条生命比损失 75 条生命更差"。由于 (3.2) 直接来自 3.1.1 节的冯·诺依曼—摩根斯坦公理，因此矛盾必然意味着至少有一条公理被违反——尽管许多做出 B 与 C 选择的人会认可这些公理本身。

Tversky 与 Kahneman 的实验还揭示了确定性效应（certainty effect）：人们倾向于夸大"确定损失"相对于"可能损失"的负面程度。这一效应在收益侧同样存在——一个较小的"确定收益"常常被偏好于一个较大的"可能收益"，而这必然违反理性公理。

Tversky 与 Kahneman 还用流行病场景展示了框架效应（framing effect）。假设一场流行病预计将夺去 600 人的生命。受试者要在以下两个方案中做选择：

E：200 人将被救下；
F：1/3 概率 600 人被救下、2/3 概率无人被救下。

多数人选择 E。然后他们被要求在以下两个方案中做选择：

G：400 人将死亡；
H：1/3 概率无人死亡、2/3 概率 600 人将死亡。

多数人选择 H。然而 E 与 G 在数学上等价，F 与 H 在数学上等价——这种不一致完全源自"问题的措辞方式"。

除上述之外，还有大量其他认知偏差会导致实际偏好偏离效用理论的规范。在从人类专家那里引导效用函数以构建决策支持系统时必须格外小心。即便决策支持系统的推荐是"理性"的，它在某些情形下也可能不完全反映人类的真实偏好。

3.2 Decision Networks

本节把第 2 章的贝叶斯网络推广为"决策网络（decision network）"，从而在贝叶斯网络的框架中自然地引入"行动"与"效用"两类新元素。决策网络由三类节点组成：机会节点（chance node）对应一个随机变量（用圆圈表示）；决策节点（decision node）对应一个待做出的决策（用方块表示）；效用节点（utility node）对应效用函数的一个可加成分（用菱形表示）。三类有向边也分别承担不同语义：条件边（conditional edge）指向机会节点，表示该节点的不确定性以所有父节点为条件；信息边（informational edge）指向决策节点，表示该节点所对应的决策是在已知其父节点取值的前提下做出的（这种边在图中常用虚线表示，为了简洁有时会被省略）；函数边（functional edge）指向效用节点，表示该效用节点的取值由其父节点的取值决定。决策网络有时也被称为影响图（influence diagram）；与贝叶斯网络一样，决策网络也不能包含有向环。把一个决策问题表示为决策网络，可以让我们在计算最优决策时利用问题的结构——这与第 2 章用贝叶斯网络结构加速概率推理的思路一脉相承。

作者用图 3.3 给出示例决策网络：有一组诊断测试的结果，可能指示某种特定疾病的存在；需要根据诊断结果决定是否施加治疗；效用是"是否施加治疗"与"疾病是否真实存在"的函数。这一网络将作为本节的运行示例反复出现。本节聚焦"单步决策问题"——所有决策同时做出；下一章则把视角推广到"序贯决策"——决策可以按时间顺序依次做出。

3.2.1 Evaluating Decision Networks

承接 3.1.3 节，给定观察 $o$，行动 $a$ 的期望效用为

\[ EU(a \mid o) = \sum_{s'} P(s' \mid a, o) U(s'). \tag{3.11} \]

式中的 $s'$ 表示对决策网络中各节点取值的"实例化"。可以用 (3.11) 来计算图 3.3 中"治疗疾病"这一决策的期望效用——先假设只观察到第一个诊断测试的结果且为阳性。若要在图中显式表达"对第一个测试结果的观察"，需画一条从 $O_1$ 到 $T$ 的信息边，于是

\[ EU(t^1 \mid o_1^1) = \sum_{o_3, o_2, d} P(d, o_2, o_3 \mid t^1, o_1^1) U(t^1, d, o_1^1, o_2, o_3). \tag{3.12} \]

利用贝叶斯网络的链式法则与条件概率的定义，可以计算 $P(d, o_2, o_3 \mid t^1, o_1^1)$。由于效用节点只依赖于"疾病是否存在"与"是否治疗"，可以把 $U(t^1, d, o_1^1, o_2, o_3)$ 化简为 $U(t^1, d)$，于是

\[ EU(t^1 \mid o_1^1) = \sum_{d} P(d \mid t^1, o_1^1) U(t^1, d). \tag{3.13} \]

为评估 $P(d \mid t^1, o_1^1)$，可以使用第 2 章介绍的任何精确或近似推理方法。要决定是否施加治疗，只需分别计算 $EU(t^1 \mid o_1^1)$ 与 $EU(t^0 \mid o_1^1)$，并选择期望效用更大的那个。

评估一般单步决策网络的标准流程是：先实例化所有决策节点与所有已观察到的机会节点；再调用任一推理算法计算效用节点父节点集合上的后验分布；与 (3.11) 中"对所有变量的实例化做求和"不同，只需对效用节点父节点的实例化做求和。最优决策就是使决策网络在决策节点被实例化为该决策时，期望效用最高。

实践中已有多种方法可提高决策网络的评估效率。一种方法是"剪枝"：若一个行动节点或机会节点没有子节点（无论按条件边、信息边还是函数边定义），则可以从决策网络中删除。例如在图 3.3 中，$O_2$ 与 $O_3$ 没有子节点，可以删除；但 $O_1$ 不能删除，因为在本节中我们把它视作已观察量——这意味着存在从 $O_1$ 到 $T$ 的信息边（虽然图中未显式画出）。

3.2.2 Value of Information

在图 3.3 中，假设只观察到 $o_1^1$（第一个诊断测试结果为阳性），则仅凭这一结果可能选择不治疗。然而，再做更多诊断测试以降低"未治疗真实存在的疾病"的风险可能是值得的。决定"应当做哪些诊断测试"的一种方法就是计算"信息的价值（value of information）"。

记 $EU^*(o)$ 为在观察 $o$ 之后"采取最优行动"的期望效用。则在已知 $o$ 的条件下，关于变量 $O'$ 的信息的价值定义为

\[ VOI(O' \mid o) = \sum_{o'} P(o' \mid o) \big[ EU^*(o, o') - EU^*(o) \big]. \tag{3.14} \]

换言之，关于一个变量的信息价值等于"在观察到该变量后期望效用的增量"。期望效用只在"观察到该变量能改变最优决策"时才会增加；若观察到新变量 $O'$ 不会改变任何行动选择，则对所有 $o'$ 都有 $EU^*(o, o') = EU^*(o)$，(3.14) 计算结果为 0。例如在疾病场景中，若无论诊断测试结果如何最优决策都是治疗，那么观察该测试结果的信息价值为 0。

需要强调的是，信息价值仅反映"做一次观察所带来的期望效用增量"，并未考虑观察本身的成本。有些诊断测试成本很低，例如量体温；有些则更贵且更具侵入性，例如腰椎穿刺。腰椎穿刺的信息价值可能远高于量体温，但在决策中必须把测试成本考虑在内。

信息价值指标在"选择要观察什么"时极为常用。有时它被用于确定"按什么顺序进行观察"——每做一次观察，就对剩余未观察变量计算信息价值；选信息价值最大的未观察变量进行观察；若不同观察有不同的成本，则从信息价值中减去成本后再选择。这一过程持续到"再做任何一个观察都不再带来净收益"为止，然后做出最优行动。值得指出的是，这种贪心式的观察选择仅是一种启发式，并不一定得到真正的最优观察序列。要得到真正最优的观察序列，需要使用后续章节将介绍的"序贯决策"技术。

3.2.3 Creating Decision Networks

决策网络是构建决策支持系统的强大框架。本节在前面要素讨论的基础上，简述构建决策网络的标准流程。

第一步是确定可能行动的空间。对于机载碰撞告警系统，行动可以是"爬升、下降或不操作"。在某些问题中，把行动空间分解为多个决策变量是值得的——例如既可推荐水平机动又可推荐垂直机动的碰撞告警系统，一个决策变量控制"爬升或下降"，另一个决策变量控制"左转或右转"。

第二步是确定与问题相关的观察变量与未观察变量。若碰撞告警系统上装有光电传感器，则可以观察"与另一架飞机的相对方位角"——这一角度测量对应一个被观察的机会节点。入侵者的真实位置与问题相关但无法直接观察，因此由图中的一个未观察变量表示。

第三步是确定各机会节点与决策节点之间的关系。这一关系可以通过专家判断、根据数据学习（2.4 节）、或两者的结合来确定。设计者通常倾向于让有向边的方向反映变量之间的因果性。

第四步是选择条件概率分布的表示模型。对离散节点，表格表示是最直观的选择；对连续节点，可以选择参数化模型（如线性高斯模型）。模型的参数可以由专家指定，也可以由数据用 2.3 节介绍的方法估计。

第五步是引入效用节点，并加上从相关机会节点与决策节点指向效用节点的函数边。效用节点的参数可以通过 3.1.4 节的人类专家偏好引导来确定；也可以通过调参使"决策网络的最优决策"与人类专家的决策一致。

第六步是验证与精化。给定一个决策场景，可以用决策网络确定最优行动，并把它与人类专家会推荐的结果做比较；通常需要检查大量场景才能建立对决策网络的信心。

当决策网络与人类专家出现分歧时，可以检查决策网络以理解"为什么最优行动是这一个"。某些情形下，更仔细地审视模型会导致修正条件概率、修改变量间关系、调整效用节点的参数、或在模型中引入新变量；某些情形下，更深入的研究会让人类专家修正自己的行动选择。在找到一个合适的决策网络之前往往需要多轮迭代。

3.3 Games

本章至此关注的是"在已知环境模型下做理性决策"。本章前面介绍的方法当然可以应用于"环境中存在其他智能体"的情形——只要概率模型能捕捉其他智能体行为的影响。然而在很多场景下，我们既没有其他智能体行为的概率模型，却掌握它们的效用函数。在此类场景下做决策正是博弈论（game theory）的研究对象，本节做一个简要介绍。

为具体化讨论，作者援引博弈论最著名的例子——囚徒困境（prisoner's dilemma）：两个囚犯被分别审讯；每个囚犯都有"指证对方"或"保持沉默"两种选择。若一方指证而另一方沉默，则指证者无罪释放、沉默者被判十年；若双方都指证，则各判五年；若双方都沉默，则各判一年。

图 3.4 给出了两个囚犯的效用矩阵。矩阵中的第一个分量是 Agent 1 的效用，第二个分量是 Agent 2 的效用。假设这一效用矩阵在两个智能体之间是共同知识；两个智能体必须在不知道对方选择的情况下同时做出行动。

3.3.1 Dominant Strategy Equilibrium

在囚徒困境这类博弈中，智能体可以选择的策略（strategy）有两种：纯策略（pure strategy），即确定地选择某一行动；混合策略（mixed strategy），即按一定概率选择各个行动。纯策略是混合策略在某个行动上取概率 1 时的特例。囚徒困境中"以 0.7 概率指证"的混合策略可以借用前面抽奖的记法写成

$[\text{Testify} : 0.7;\ \text{Refuse} : 0.3].$

混合策略的效用可以写成各纯策略效用的概率加权和

\[ U\big([a_1 : p_1;\ \dots;\ a_n : p_n]\big) = \sum_{i=1}^{n} p_i U(a_i). \tag{3.15} \]

记智能体 $i$ 的策略为 $s_i$；策略组合（strategy profile）$s_{1:n}$ 是对所有 $n$ 个智能体策略的指定；除智能体 $i$ 之外的策略组合记为 $s_{-i}$；在策略组合 $s_{1:n}$ 下智能体 $i$ 的效用记为 $U_i(s_{1:n})$，或等价地 $U_i(s_i, s_{-i})$。

智能体 $i$ 对策略组合 $s_{-i}$ 的最佳响应（best response）是策略 $s_i^*$，满足 $U_i(s_i^*, s_{-i}) \ge U_i(s_i, s_{-i})$ 对所有策略 $s_i$ 成立。一般而言，对给定的 $s_{-i}$ 可能有多个不同的最佳响应。若存在一个 $s_i$ 对所有可能的 $s_{-i}$ 都是最佳响应，则称 $s_i$ 是占优策略（dominant strategy）。例如在囚徒困境中，无论 Agent 2 选择"指证"还是"沉默"，Agent 1 选择"指证"都更好；因此"指证"是 Agent 1 的占优策略。由于博弈是对称的，"指证"也是 Agent 2 的占优策略。当所有智能体都拥有占优策略时，这些占优策略的组合称为占优策略均衡（dominant strategy equilibrium）。

囚徒困境之所以引起广泛兴趣，是因为它揭示了"个体最佳响应"可能导致"对所有智能体都次优的结局"。占优策略均衡下两个囚犯都指证、各判五年；然而若双方都保持沉默，则各判一年——对双方都更优。

3.3.2 Nash Equilibrium

设想两架飞机处于碰撞航向，每架飞机的飞行员必须在"爬升"或"下降"之间选择以避免碰撞。若两机选择相同机动，则发生坠机，对两架飞机的效用均为 $-4$。由于爬升比下降消耗更多燃油，选择爬升的飞行员还要承担一个额外的 $-1$ 惩罚。图 3.5 给出了这一碰撞避免博弈的效用矩阵。

在碰撞避免博弈中不存在占优策略均衡——一个特定飞行员的最优反应依赖于另一个飞行员的选择。这里需要引入另一均衡概念——纳什均衡（Nash equilibrium）：若对所有智能体 $i$，$s_i$ 都是对 $s_{-i}$ 的最佳响应，则称策略组合 $s_{1:n}$ 是纳什均衡。换言之，纳什均衡下没有任何智能体能通过单方面改变策略而获益——前提是其他智能体都遵守该均衡策略。

碰撞避免博弈中存在两个纯策略纳什均衡：(Climb, Descend) 与 (Descend, Climb)。可以证明每个博弈都至少有一个纳什均衡，该均衡可能（也可能不）包含纯策略。然而对一般博弈而言，目前没有已知的"多项式时间"算法来寻找纳什均衡——尽管寻找纳什均衡的复杂度并非 NP-complete（它属于称为 PPAD 的复杂性类）。

3.3.3 Behavioral Game Theory

当需要构建与人类交互的决策系统时，纳什均衡信息并不总是有用。人类常常并不采取纳什均衡策略。首先，若博弈中存在多个均衡，则很难决定"采用哪个均衡"；即便博弈中只有唯一均衡，由于认知能力的限制，人类也常常难以计算纳什均衡；即便人类能计算纳什均衡，他也会怀疑对手是否能完成同样的计算。

行为博弈论（behavioral game theory）致力于为人类智能体建模。已存在许多不同的行为模型，其中logit level-k 模型（亦称 quantal level-k 模型）近年来较为流行，实践中效果也不错。logit level-k 模型刻画了"人类"的两条假设：一是"错误代价越小、越容易犯错"；二是"策略性前瞻的步数有限"（即"我猜你会猜我会……"的链条长度有限）。该模型由两个参数定义：精度参数 $\lambda \ge 0$ 控制对效用差异的敏感度（$\lambda = 0$ 表示完全无差异）；深度参数 $k > 0$ 控制理性深度。

在 logit level-k 模型中，level-0 智能体均匀地选择行动；level-1 智能体假设对手采用 level-0 策略，并按 logit 分布选择自己的行动

$P(a_i) \propto e^{\lambda U_i(a_i, s_{-i})}, \tag{3.16}$

其中 $s_{-i}$ 表示对其他智能体所采用策略的假设。level-k 智能体假设其他智能体采用 level k − 1 策略，并按 (3.16) 选择自己的行动。参数 $k$ 与 $\lambda$ 可以用上一章介绍的技术从数据中学习。

为说明 logit level-k 模型，作者引入旅行者困境（traveler's dilemma）：航空公司丢失了两位旅客的同款行李；航空公司请两位旅客写下各自行李的价值，取值范围 $[2, 100]$ 美元。若两人写下的值相同，则两人各得该值；写下较低值者得"较低值 + 2"；写下较高值者得"较低值 − 2"。效用函数可形式化为

\[ U_i(a_i, a_{-i}) = \begin{cases} a_i & \text{若 } a_i = a_{-i} \\ a_i + 2 & \text{若 } a_i < a_{-i} \\ a_{-i} - 2 & \text{其他情形} \end{cases} \tag{3.17} \]

多数人倾向于写下 97–100 美元。然而看似反直觉的是：这一博弈存在唯一的纳什均衡——仅 $2 美元。图 3.6 给出了 logit level-k 模型在不同 $\lambda$ 与 $k$ 下的策略分布：level-0 智能体均匀地选择行动；level-1 智能体的分布偏向谱的高端，精度参数控制其"集中程度"；随着 $k$ 增大，$\lambda = 0.3$ 与 $\lambda = 0.5$ 之间的差异越来越不明显。人类行为常常可以用 logit level 2 较好地建模——可以看到，logit level 2 比纳什均衡更接近人类实际行为。

3.4 Summary

理性决策把概率论与效用论结合在一起。
效用函数的存在性由对理性偏好的公理化约束导出。
理性决策就是使期望效用最大的决策。
我们可以基于从人类那里反推出的效用函数构建理性决策系统。
人类并不总是理性的。
决策网络是决策问题的紧凑表示。
当决策涉及多个智能体时，行为博弈论是有用的工具。

3.5 Further Reading

期望效用理论由 Bernoulli 于 1793 年开启 [2]。3.1.1 节给出的理性决策公理基于 Neumann 与 Morgenstern 在其经典著作《Theory of Games and Economic Behavior》中给出的版本 [3]。Neumann 与 Morgenstern 证明了这些公理导致效用函数的存在性，并奠定了最大期望效用原理的基础 [3]。Schoemaker 综述了效用理论的发展 [4]；Fishburn 对该领域进行了综述 [5]。Russell 与 Norvig 在其著作中讨论了最大期望效用原理对人工智能领域的重要性 [6]。

Farquhar 综述了多种效用引导方法 [7]；Markowitz 讨论了货币的效用 [8]。Keeney 与 Raiffa 合著的《Decisions with Multiple Objectives: Preferences and Value Tradeoffs》对多属性效用理论做了综述 [9]；该书讨论了"允许某种效用分解"所需的偏好结构假设，包括 3.1.6 节介绍的加性分解。

3.1.7 节的非理性偏好例子取自 Tversky 与 Kahneman [1]。Kahneman 与 Tversky 对期望效用理论提出了批评，并引入了一个看起来更符合人类行为的替代模型——前景理论（prospect theory）[10]。近年来出版的若干书籍讨论了人类的非理性，包括《Predictably Irrational: The Hidden Forces That Shape Our Decisions》[11] 与《How We Decide》[12]。

教材《Bayesian Networks and Decision Graphs》（Jensen 与 Nielsen）讨论了决策网络。Shachter 的早期论文给出了评估决策网络的算法 [14], [15]。Howard 提出了"信息价值"这一量化概念 [16]；该概念已被应用于决策网络 [17], [18]。

博弈论是一个广阔的领域，已有多本标准入门书 [19]–[21]。Koller 与 Milch 把决策网络扩展到博弈论语境 [22]。Daskalakis、Goldberg 与 Papadimitriou 讨论了计算纳什均衡的复杂度 [23]。Camerer 对行为博弈论做了综述 [24]。Wright 与 Leyton-Brown 讨论了行为博弈论模型，并展示了如何从人类行为的实验数据中提取参数 [25], [26]。

本章个人批注

作为全书理论篇的第三章，本章的职能是把"在不确定性下做最优决策"从第 1 章的口语化直觉转化为可计算的形式化语言。如果说第 2 章是"用概率承载不确定性"，本章则是"在概率之上引入效用承载偏好"——这两个维度共同构成第 2 章末尾已经暗示的"决策理论"基础。本章的形式化路径是高度公理化的：从偏好的几条公理（3.1.1）出发，先证明效用函数的存在性（3.1.2），再推出"抽奖的效用是各结果效用的加权平均"（式 (3.2)），最终以最大期望效用原理（3.1.3）作为决策的规则。这一从公理到运算规则的递进结构与第 2 章"从信念度公理到概率公理到贝叶斯网络"的递进是同构的，也是本书理论篇的统一方法论。

3.1.5 节关于"货币效用通常不是线性的"这一观察让我印象很深。作者用"买保险的人不会最大化期望货币值"这一反例直观地说明了"货币 ≠ 效用"，并把风险态度（中性、偏好、厌恶）与效用函数的凸凹联系起来。这一讨论在我自己处理"涉及金额的实际决策"时具有直接的应用价值——尤其是在做"灾害损失"或"运营成本"相关的工程决策时，简单的"期望货币值最大化"会系统性地高估低概率大损失事件的影响，因此需要在效用层面引入风险厌恶的修正。3.1.6 节关于"加性分解"的讨论则让我想到一个工程上的现实问题：当变量数增加时，$2^n$ 的参数增长是不可承受的，但"哪些变量可以加性分解、哪些不能"完全取决于问题的领域知识。这一"用领域知识换取参数压缩"的思路与第 2 章"用图结构编码条件独立"是同构的——两者都把"结构假设"作为稀疏性来源。

3.1.7 节关于"人类是非理性的"这一节是本章中我个人读起来最有趣的一节。Tversky 与 Kahneman 的几个例子（确定性效应、框架效应）揭示了"偏好不是稳定的对象，而是依赖于问题的措辞方式"。这一观察对工程实践的启示是：在构建"以人类偏好为输入"的决策支持系统时，必须做大量的偏好稳定性检验——简单的"问一下专家某个结果的效用"是不够的，因为同一个结果在不同的措辞下可能被赋以不同的效用。我在读这一节时想到一个跨章节的联系：3.1.7 节末尾提到"在从人类专家那里引导效用函数时必须格外小心"——这一警示与 2.3 节"从数据中学习概率分布"形成对照：前者关心的是"人类给出的标签是否可信"，后者关心的是"数据是否足够大、是否独立同分布"。两者结合在一起构成"机器学习 + 决策理论"实践中的两类主要风险来源。

3.2 节把贝叶斯网络推广为决策网络是本章最具结构洞见的部分。3.2.2 节关于"信息价值"的概念让我想到 2.4 节关于"结构搜索"中"如何选择下一个要学习的变量"的联系——两者都是"在不确定的多个候选中按'边际信息增益'做贪心选择"的范式。3.2.3 节关于"创建决策网络"的六步流程则给了我一个非常实用的工程模板：行动空间 → 观察变量 → 节点关系 → 条件概率 → 效用节点 → 验证精化。这套流程在第 8、9、10 章的应用案例中都会被反复使用。

3.3 节关于博弈论的讨论则让我意识到"理性决策"在多智能体场景下的根本变化：在单智能体场景下，"最优"是"使期望效用最大的行动"；在多智能体场景下，"最优"变成了"对所有智能体的策略组合的最佳响应"——这一转变不仅是技术上的（从 $\arg\max$ 到不动点方程），更是概念上的（从"求解"变成"均衡"）。3.3.3 节关于 logit level-k 模型的讨论在我看来是本章最具实践意义的小节：它给出了一个"用有限理性近似真实人类"的实用工具——这与第 8 章（视频监控中的目标搜索）那种"人类在环"的实际场景直接相关。

整体而言，本章是一份"单步决策的形式化导论"——它把效用论公理、效用函数、期望效用原理、决策网络、信息价值、多智能体均衡这六个话题压缩在约 30 页内，每一节都给出了该话题的最小可用版本并指明 Further Reading。本章的风格与第 2 章高度一致：以"公理化起点 + 关键算法 + 工程实例"作为每一节的统一结构。这种"以一本书的篇幅做地图"的工作方式在第 4 章（序贯问题）应当还会继续。

与上下章的衔接（一段话）

本章是全书 12 章中的第 3 章，也是理论篇的第三章——紧接在第 2 章"概率模型"之后，把第 2 章的概率模型扩展为"在不确定性下做最优决策"的形式化框架。从位置上看：第 1 章给出了"为什么要做不确定性下的决策"以及"五种设计方法"；第 2 章把"概率视角"这一支展开为信念度公理化、贝叶斯网络、推理与学习；本章则在第 2 章的概率模型之上加入"效用（utility）"与"决策节点"的概念，把贝叶斯网络推广为决策网络（decision network）——这是从"表示不确定性"到"在不确定性下做最优决策"的关键一跳。第 4 章 Sequential Problems 会进一步引入"行动的结果是概率性的"以及"决策按时间顺序依次做出"这两个时间维度，把本章的静态决策网络推广为动态决策网络（即第 4 章将系统讨论的 Markov decision process）；第 5、6 章则分别在"模型未知"与"状态观测不完备"两个方向上扩展本章的框架；第 7 章则把"多智能体"这一维度从本章 3.3 节的简单博弈推广为更系统的多智能体决策框架。从作者的整体布局看，本章在理论篇中的位置类似于"先把单步决策的形式化骨架搭好，再让后续章节用这些积木搭出更大的结构"。