博弈论 II · 零和、动态博弈与机制设计

上一页固定对手策略，检查单方面偏离。本页再改变三个条件：两人的利益完全相反时，怎样给出保底与上界？当前动作影响未来时，怎样把未来价值算进去？规则也可以选择时，怎样检验规则提供的激励？每一步都保留一份可以手算的证书。

1. 零和矩阵：用同一份收益给出下界与上界

令 \(A\in\mathbb R^{m\times n}\) 是有限实矩阵，行玩家最大化 \(x^\top Ay\)，列玩家最小化它，\(x\in\Delta_m,y\in\Delta_n\)。两人各自的保证为

对任意固定 \(x,y\)，行玩家的最坏收益不会高于 \(x^\top Ay\)，列玩家面对的最大收益不会低于它，从而 \(\underline v\le\overline v\)。

只允许纯动作时，这个不等式可以严格：猜硬币的每一行最小值都是 \(-1\)，每一列最大值都是 1。允许混合以后，双方各取一半，使对手的任意纯动作都给出期望 0，两个界就接上了。

von Neumann 极小极大定理：

一对最优概率 \(x^*,y^*\) 满足鞍点不等式

它就是零和博弈的 Nash 均衡。值是唯一的，最优策略不一定唯一；例如所有格都相同时，每个策略组合都最优。

把“对偶”写成真正可以核对的两个 LP

固定 \(x\) 后，列玩家的最坏回应可以取纯列，所以行玩家的问题是

它的对偶是列玩家的问题：

这里 \(v,w\) 是自由实变量，不能擅自要求非负：收益可以全为负。两问题均可行，最优值受矩阵最小格与最大格限制。LP 强对偶给出相等的最优值，正是极小极大等式。

任意一组可行 \(x,v,y,w\) 都给出

因此 \(w-v\) 是直接可核对的差距。若差为 0，就同时证明两边最优。互补松弛进一步说明：被 \(x\) 正概率使用的行，在 \(y\) 下收益都等于值；被 \(y\) 正概率使用的列，在 \(x\) 下收益也都等于值。未使用的动作仍要满足相应不等式。

一个非对称手算

对 \(A=\begin{pmatrix}3&0\\1&2\end{pmatrix}\)，行玩家以 \(p\) 选第一行。面对两列时分别得到 \(1+2p\) 和 \(2-2p\)，保底是两条线的较低者。令它们相交：

列玩家以 \(q\) 选第一列。两行对它的收益分别为 \(3q\) 与 \(2-q\)，压制值是两条线的较高者。交点 \(q=1/2\) 同样给 \(3/2\)。这同时给出概率、值与两个方向的证书。

2. 动态零和：把未来加进当前矩阵

现在令状态集合有限。每一轮双方观察状态 \(s\)，同时选择动作 \(i,j\)，行玩家得到 \(r_s(i,j)\)，下一状态服从 \(P(\cdot\mid s,i,j)\)。折扣目标采用未乘 \(1-\gamma\) 的总和：

收益有界使该总和绝对可积。给定未来价值候选 \(V\)，当前状态的有效矩阵是

每个状态单独解一次零和矩阵，得到 Shapley 算子

这里先把当前收益与未来收益相加，再求矩阵值。一般不能先对每个奖励矩阵求一个“局部最优动作”，然后把它永远重复，因为当前动作还改变转移。

压缩常数来自哪里

若两张矩阵每格至多相差 \(\eta\)，任何固定混合策略对的期望收益也至多相差 \(\eta\)。再分别取最大、最小，不会放大这个统一误差，因此

另一方面，转移概率非负且总和为 1，所以每一格

两步合起来就是

有限维空间完备，故压缩映射定理给出唯一固定点 \(V^*=TV^*\)。精确价值迭代 \(V_{k+1}=TV_k\) 从任意有限初始向量收敛到它。

不知道固定点，也能估计当前误差

对任意候选 \(V\)，用三角不等式：

移项得

因此接近 1 的折扣会放大残差证书；同一个 \(10^{-4}\) 残差，在 \(\gamma=0.5\) 与 \(0.999\) 下给出的界分别为 \(2\times10^{-4}\) 与 \(0.1\)。不能只看到残差“很小”就忽略折扣。

固定点为什么也是无限时域博弈的值

在每个 \(Q_s[V^*]\) 中选一组最优混合策略。行玩家按当前状态使用该策略，就能保证本轮奖励加折扣后的下一状态价值至少为当前 \(V^*(s)\)，无论对手如何根据历史行动。

把这个条件不等式逐轮取期望并相加，中间的未来价值项相消，留下有限段奖励与末端 \(\gamma^n V^*(s_n)\)。因为 \(V^*\) 有界，末端项趋于 0，行玩家就能保证至少 \(V^*(s_0)\)；列玩家同理给出至多这个值。这里得到的是按状态重新随机化的平稳策略，并不是游戏开始时抽一次纯策略以后永远照做。

折扣为 1 时改变了什么

\(\gamma=1\) 时，压缩常数不再小于 1，残差除以 \(1-\gamma\) 的公式不能使用。单状态恒定奖励 1 就给出 \(TV=1+V\)，不存在有限固定点，未折扣无限总和也发散。

有限时域仍可从终端价值向前倒推。长期平均收益则是另一个目标，例如 \(\liminf_n n^{-1}\mathbb E\sum_{t<n}r_t\)，不能把无限折扣总和公式直接改成 \(\gamma=1\) 就得到它。有限状态动作的零和平均收益理论有更深入的值存在性结果；这不意味着原始价值迭代必然收敛到一个有限向量。扩展到无限状态或动作时还要重新检查相应条件。

3. 抽样：抽的是哪一个随机变量

给定最后一行的 \(V_k\) 与 \(Q_s[V_k]\)，实验按该矩阵的一组最优混合概率独立抽行动，记录随机收益

于是理论期望为矩阵值，方差为

\(N\) 次理想独立抽样的样本均值标准误是 \(\sqrt{\operatorname{Var}(Y)/N}\)。它不同于固定点残差：前者来自有限抽样，后者检验当前价值候选是否满足方程。增加 \(N\) 不会替代增加价值迭代轮数，也不会修好一个错误的转移模型。

实验使用有限精度伪随机数和固定种子复现抽样；四格次数与每一步样本均值均可核对。样本均值偶然非常接近矩阵值，不证明未来所有种子或样本规模都会同样接近。

4. 先后行动：策略是一份完整的条件计划

扩展型博弈可以包含轮流行动、同时行动、随机节点与不完全信息。有限树、完全信息且每次行动都观察到此前历史时，可以用逆向归纳：在最后的决策节点，按该节点行动者自己的收益选择；把结果传回上层，一直回到根。

这给出子博弈完美均衡（SPNE）：限制到每个子博弈后仍是 Nash 均衡。策略必须说明在所有相关决策节点怎样行动，包括均衡路径上不会到达的节点。遇到并列最优时应保留选择分支，不能据此宣称均衡唯一。

两步例子。A 可以立即拿 \((2,0)\)，也可以传给 B。B 接到后可以拿 \((1,3)\)，或继续得到 \((3,2)\)。B 比较自己的第二分量，选拿，因为 \(3>2\)；A 预见这一点，比较自己的第一分量，选择立即拿，因为 \(2>1\)。

得到的完整策略是“A 立即拿；如果到 B，B 也拿”，结果 \((2,0)\)。另一个叶子 \((3,2)\) 对两人都更好，却不能由这套完全信息一次性树中的逆向归纳支持。要解释其他行为，需要修改或扩展效用、信息、承诺或行为假设。

先行动不自动意味着优势。Stackelberg 模型中，领导者选择后能否可信地承诺、跟随者怎样打破并列最佳回应、谁观察到什么，都影响结果；有些博弈有先手优势，有些有后手优势。

5. 重复博弈：合作有条件地成为均衡

沿用上一页囚徒困境的 \(T=5,C=3,P=1,S=0\)，满足 \(T>C>P>S\)。无限重复、双方完整观察每轮行动、共同折扣 \(0\le\delta<1\)。

明确规定一份公共触发策略：只要此前每一轮双方都合作，就继续合作；一旦历史中任意一方出现过背叛，从下一轮起双方永远背叛。惩罚状态是吸收状态，不能因为刚好是自己先背叛，就假定自己仍在合作状态。

在合作历史后，遵守策略的收益为 \(C/(1-\delta)\)；本轮背叛后进入惩罚，最好能得 \(T+\delta P/(1-\delta)\)。所以合作阶段的激励条件为

还必须检查路径之外的惩罚历史：对手永远背叛，自己本轮背叛得 \(P\)，合作只得 \(S<P\)，而未来仍在惩罚状态。因此惩罚也是可信的。有限动作、有界收益与严格小于 1 的折扣使单次偏离原理适用；检查这两类历史就证明了整份策略的子博弈完美性。

这组数值给 \(\delta\ge1/2\)。等号时合作与一次背叛无差异，仍可构成均衡；这既不保证合作是唯一均衡，也不保证真实参与者会选择它。双方永远背叛仍是一个 SPNE。监控错误还可能让公共触发永久惩罚一次误判，不能直接把它作为现实制度的无条件处方。

若重复次数有限、终点事先共同知道，且阶段博弈的 Nash 均衡唯一，则标准完整信息模型中的 SPNE 从最后一轮往前逐轮回到阶段均衡。未来重要并不能越过已知终点，自动替最后一轮创造合作激励。

Folk 定理研究更广泛的可支持收益，但其版本取决于监控、耐心程度、可行收益和个体理性等条件。一个触发策略的阈值，不能代替整个定理，也不能推出“长期生意必然诚信”。

6. 拍卖：支付规则如何改变激励

机制设计先给定结果、报告与支付规则，再检查参与者怎样回应。一个重要目标是优势策略激励相容：无论别人怎样报告，如实报告都至少一样好。它不要求真实性一定是唯一最优报告。

二价拍卖的三种情况

单物品、非负私人估值、准线性效用、无预算或外部性约束；最高出价者获物品并付第二高价，平局按预先给定规则处理。固定别人的出价，令其最高价为 \(m\)，自己的估值为 \(v\)。

出价 \(v\) 正好实现这些选择，所以如实出价是弱优势策略。证明逐个固定别人的报价，不需要估值相互独立；独立同分布往往是另一类收入或均衡计算的假设。

一价拍卖不能照搬二价证明

一价拍卖中，赢者付自己的报价，报价同时影响赢的机会与赢后的利润。一个可完整算出的例子是：\(n\ge2\) 个风险中性竞标者，估值独立均匀分布于 \([0,1]\)，无保留价且报价非负，对称递增均衡为

若别人采用 \(b(t)=\alpha t\)，自己报价 \(\beta\in[0,\alpha]\)，赢的概率是 \((\beta/\alpha)^{n-1}\)，期望效用为

对 \(\beta\) 求导，内部最大点为 \(\beta=(n-1)v/n\)。令 \(\alpha=(n-1)/n\)，这个最佳回应恰好与假设一致；端点 \(v=0,1\) 也符合边界。报价超过 \(\alpha\) 虽然必胜，却比报价 \(\alpha\) 支付更多，不能进一步改善收益。这个压价公式依赖分布与模型，不是所有一价拍卖的统一比例。

VCG 与 GSP 分清楚

在标准私人价值、准线性、可转移支付的环境中，VCG 选择报告总价值最大的可行结果，并让每个人支付自己对其他人造成的外部性。固定别人报告后，自己的效用可写为“所选结果的真实自身价值加他人报告价值，减去一个不依赖自己报告的常数”。如实报告使机制最大化前一项，因此是弱优势策略。这个推理要求分配优化确实按规则完成。

广告位的 GSP 按下一名报价定价，一般不具有同样的真实性。举个两广告位、三竞标者、每点击估值分别为 \(10,9,1\)，点击率分别为 \(1,1/2\) 的简单模型：如实报价时，第一人拿第一位，效用 \(1(10-9)=1\)；如果把报价改为 2，他改拿第二位，付每点击 1，效用变成 \((1/2)(10-1)=9/2\)。存在有利偏离，已经足够否定“如实出价是优势策略”。

这没有否定 GSP 可能存在其他均衡；它只是说明相似的“第二价格”名称不等于同一激励结构。

7. 向学习动态与演化理论再走一步

有均衡，不代表交替优化会自动找到它。对双线性目标 \(\min_x\max_y xy\)，同时梯度更新为

直接展开可得

只要步长 \(\eta>0\) 且初值不在原点，离均衡 \((0,0)\) 的距离就增长。连续时间版本绕圈，离散同时更新甚至向外扩张。分析对抗训练时，必须同时给出目标函数、策略空间和更新算法；“有 minimax 形式”不是收敛证明。

演化博弈则让高收益策略改变种群比例。对称单种群矩阵博弈的复制方程为

每个单一策略顶点都是方程的静止点，因为其他策略的比例为零；但如果缺席策略收益更高，这个顶点未必是 Nash 均衡，也未必能抵抗入侵。ESS 要求一个策略在任意不同入侵策略 \(y\) 出现时，都存在一个依赖于 \(y\) 的正阈值，使入侵比例低于该阈值时得到严格更高收益：

在这里的对称有限矩阵模型中，令 \(\varepsilon\) 趋于零可见 ESS 必须是对称 Nash 均衡，反过来不成立。例如 \(A=\left(\begin{smallmatrix}1&0\\2&0\end{smallmatrix}\right)\) 的顶点 \(x=(1,0)\) 虽是复制方程静止点，第二个策略面对它却得 2，比现有策略的 1 更高，因此该顶点不是 Nash 均衡。把静止点、Nash、ESS 和具体动态的稳定性分别检验，才是从“求均衡”走向“研究均衡怎样出现”的起点。

8. 三道展开题

延伸阅读。Shapley 的原始论文第 1–2 节把矩阵值的稳定性与随机博弈的压缩映射联系起来。重复博弈可结合 MIT 的讲义比较不同触发策略的路径外规定；尤其不要把“只针对对方过去行动的触发”与本页“任意背叛后公共进入吸收惩罚”的完整策略混为一谈。

接下来的热方程反问题项目把建模、正向计算、噪声与可辨识性放到一个完整任务中。博弈论这两页留下的通用习惯同样适用：先说清模型、目标和信息，再给出证书与误差，最后才解释观察到的行为。