零和博弈极大极小定理证明

约 596 个字 预计阅读时间 2 分钟

为什么引入零和博弈？

在一般博弈的时候，一个玩家除了关心“自己期望最大收益”，同时也会关心“自己保底能获得多少收益”，也就是说，他关心自己最差情况下，通过决策能收获的最大收益。

引入零和博弈的价值，就是将“收益最大化”和“最差情况下最好”等价。

直观角度来讲，因为自己在最大化自己的时候，给对方带来了最大的损害，对方针对这种损害策略的方案，就是“在最差情况下最大化自己”。

形式化的就是我们接下来要证明的 Minmax 定理。

定义

在二人零和博弈中，记参与者为甲乙，博弈矩阵为 \(A\in \mathbb{R}^{m\times n}\)，甲（row player）的混合策略记作 \(x\in \mathbb{R}^n\)，乙（column player）的混合策略记作 \(y\in \mathbb{R}^m\)，那么这个博弈的效用是 \(x^\top Ay\).

甲想要最小效用，乙想要最大效用，所以如果甲先进行行动（或者是甲的安全选择），最终的效用是： $$ \min_{x \in \Delta_n} \max_{y \in \Delta_m} x^\top A y $$ 如果是乙先行动（或者是乙的安全选择），最终的效用是： $$ \max_{y \in \Delta_m} \min_{x \in \Delta_n} x^\top A y $$ Minmax 定理指出：这两个东西是相等的，这意味着两个人的安全选择是“可以相遇的”，即可以在同一次盘面中出现，容易发现，如果如此，双方没有从利益和安全都没有偏移动机，就是博弈的纳什均衡。

方法一：函数求导方向的证明

记 \(y^* = \arg \min_y \max_x x^T A y\)，显然有： $$ \underline{v} = \max_x \min_y x^T A y \leq \max_x x^T A y^* = \min_y \max_x x^T A y = \overline{v} $$ 接下来的目标是证不等式的右半边。

记 \(y^* = \arg \min_y \max_x x^T A y\) 依赖于两个结论：

• 如果 \(f(x,y)\) 是连续函数，那么 \(y = \max_x f(x,y)\) 也是连续函数。
• 紧集上的连续函数必能取最大 / 最小值。

包络定理

若 \(f(x, y)\) 可微，令 \(g(y) = \max_x f(x, y)\)，\(x(y)\) 表示固定 \(y\) 时最大化 \(f(x, y)\) 的 \(x\)，则 $$ \frac{dg(y)}{dy} = \frac{\partial f(x(y), y)}{\partial y}. $$