博弈论：二元函数的鞍点定理

摘要: 二元函数的鞍点

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 minimax算法初探以及若干例子 中，我们介绍了博弈算法中最重要的 minimax 算法，其背后是二人有限零和博弈的理论体系。其中涉及到了分析、代数、优化等数学内容。本文我们就来看其中比较重要的一块内容：双变量函数的鞍点及其相关的定理。

在此前，我们可能已经多次接触过鞍点的概念。比如在大学或考研高等数学中，关于通过导数研究函数的极值这块，函数的极值有驻点条件，驻点就是导数(或Jacobi矩阵)为零的点，如果一个驻点它不是极值点，则称其为鞍点。在高等数学中我们知道鞍点的一个判定方法是通过 Hessian 矩阵的特征值来判定。

在优化中，当我们谈某个问题的最优性条件时，也会涉及到鞍点的概念。这块在机器学习中应用的非常多，比如入行时间比较早的机器学习算法工程师肯定听说过 SVM 的 KKT 条件，以及对偶问题和拉格朗日函数吧。这块其实就是高等数学中的鞍点概念的延伸和应用。

在复变函数中，可以将复变函数的模视为一个曲面，那么我们也可以谈鞍点的概念，并且在渐近分析中非常有用，相关的定理可以用于推导一些算法的时间复杂度。因为如果算法运行时间与数据规模的关系为 $T(n)$ 的话，其生成函数视为复变函数的话经常是解析函数，那么该解析函数的鞍点就隐含了关于 $T(n)$ 渐近估阶的重要信息。在算法分析中，这种通过解析函数的鞍点来给出渐近估阶的方法有很多非常精彩的例子，以后再跟大家分享。

本文我们针对二人有限零和博弈，因此我们谈的是二元函数的鞍点。首先我们基于二元函数给出博弈论中的重要概念，比如策略（全局最大策略、全局最小策略、最小最大策略、最大最小策略等）、保底盈利函数、保底亏本函数等。其中二元函数的最小最大策略、最大最小策略就跟鞍点有关了，具体的关系是通过鞍点定理来描述的，本文给出该定理的证明。

本文主要的参考资料是电子工业出版社 2023 年 7 月出版的《博弈论基础》，作者刘进，如果喜欢看推导过程的话，可以考虑看看这本书。

---

一元函数的最值和最值点

假设 $\Omega$ 为一个集合，函数 $f: \Omega \rightarrow \mathbb{R}$ 是一个函数，关于这个函数可以讨论其最值、最值点的集合，其符号的定义如下：

最大值：$f_{max}^{* } = \max\limits_{x\in \Omega} f(x)$

最大值点集合：$\arg\max\limits_{x\in\Omega} f(x) = \{x^{* } | x^{* } \in\Omega, f(x^{* }) = f_{max}^{* }\}$

最小值：$f_{min}^{* } = \min\limits_{x\in \Omega} f(x)$

最小值点集合：$\arg\min\limits_{x\in\Omega} f(x) = \{x^{* } | x^{* } \in\Omega, f(x^{* }) = f_{min}^{* }\}$

---

二元函数的值和策略

假设 $X, Y$ 为两个集合，函数 $f: X \times Y \rightarrow \mathbb{R}$，对于这个关于两个变量 $x, y$ 的函数 $f$，我们依然可以讨论其最值以及最值点。只是这里有两个变量 $x, y$，因此在实际操作上我们可以先对一个取最值再对另一个取最值。

比如先固定 $x$，得到一个关于 $y$ 的函数并取最大值，然后再将 $x$ 视为变量，再取最大值，最终会得到一个值，记为 $f_{min}^{*}$，对应地有一个点 $(x^{*}, y^{*})$，$f_{min}^{*} = f(x^{*}, y^{*})$。这可以理解为先对 $y$ 取最大值再对 $x$ 取最大值。在博弈论中，$x, y$ 分别表示两个参与人的策略或行动，因此 $(x^{*}, y^{*})$ 可以理解为一种让 $f$ 取到整体最大值的策略，称其为整体最大策略。

类似地，根据对 $x$ 取最大还是最小，以及对 $y$ 取最大还是最小的几种情况，可以定义整体最小策略、最大最小策略、最小最大策略。下面对四种策略及其对应的相关概念分别给出定义。

整体最大

称 $f_{max}^{*}$ 为整体最大值，定义如下：

$$f_{max}^{* } = \max\limits_{x\in X, y\in Y} f(x, y)$$

相应地，称 $(x^{*}, y^{*})$ 为整体最大策略，定义如下：

$$(x^{* }, y^{* }) = \arg\max\limits_{x\in X, y\in Y} f(x,y)$$

整体最小

称 $f_{min}^{*}$ 为整体最小值，定义如下：

$$f_{min}^{* } = \min\limits_{x\in X, y\in Y} f(x, y)$$

相应地，称 $(x^{*}, y^{*})$ 为整体最小策略，定义如下：

$$(x^{* }, y^{* }) = \arg\min\limits_{x\in X, y\in Y} f(x,y)$$

最大最小

先固定 $x$，对 $y$ 取最小值，得到的函数称为保底盈利函数，如下：

$$f_{ymin}(x) = \min\limits_{y\in Y} f(x, y)$$

在参与人1 的角度看，$f_{ymin}(x)$ 可以理解为固定其策略 $x$，参与人2 选取了使得值最小的策略之后，参与人1依然可以取得盈利 $f_{ymin}(x)$，也就是当参与人1选择策略 $x$ 时，不论参与人2 选什么策略，参与人1 的盈利不会比 $f_{ymin}(x)$ 更少，因此称为保底盈利函数，这是站在参与人1 的角度说的。

在保底盈利函数 $f_{ymin}(x)$ 上再对 $x$ 取大值，称为最大最小值，记为 $f_{ymin}^{*}$，如下：

$$f_{ymin}^{* } = \max\limits_{x\in X}f_{ymin}(x) = \max\limits_{x\in X}\min\limits_{y\in Y} f(x, y)$$

对应的参与人1 的策略 $x^{*} = \arg\max\limits_{x\in X}f_{ymin}(x)$ 称为最大最小策略。

最小最大

先固定 $y$，对 $x$ 取最大值，得到的函数称为保底亏本函数，如下：

$$f_{xmax}(y) = \max\limits_{x\in X} f(x, y)$$

由于两个参与人之间是零和博弈，因此一个人的盈利就是另一个人的亏损。$f$ 是参与人1 的盈利，那么在参与人2 的角度看，$f$ 就是其亏损值。$f_{xmax}(y)$ 可以理解为参与人2固定其策略 $y$，参与人1 选取了使得值最大的策略之后，参与人2的亏损最多为 $f_{xmax}(y)$，也就是当参与人2选择策略 $y$ 时，不论参与人1 选什么策略，参与人2 的亏本不会比 $f_{xmax}(y)$ 更多，因此称为保底亏损函数，这是站在参与人2 的角度说的。

在保底亏本函数 $f_{xmax}(y)$ 上再对 $y$ 取小值，称为最小最大值，记为 $f_{xmax}^{*}$，如下：

$$f_{xmax}^{* } = \min\limits_{y\in Y}f_{xmax}(y) = \min\limits_{y\in Y}\max\limits_{x\in X} f(x, y)$$

对应的参与人2 的策略 $y^{*} = \arg\min\limits_{y\in Y}f_{xmax}(y)$ 称为最小最大策略。

整体最小/最大策略的性质

前面介绍了整体最小策略和整体最大策略，那么对于二元函数，一个很自然的问题是先固定 x 对 y 求最大值，然后再对 x 求最大值，所得的值等于整体最大值吗。

答案是求二元函数的整体最大值等于分别求每个变量的最大值，对顺序没有要求，这也是整体最小/最大策略的性质。这组性质指示了我们如何计算整体最大/整体最小策略及其对应的值。

性质1 (整体最大值的计算)

$X, Y$ 是两个集合，函数 $f: X\times Y \rightarrow \mathbb{R}$，那么整体最大值为：

$$f_{max}^{* } = \max\limits_{x\in X, y\in Y} f(x, y) = \max\limits_{x\in X}\max\limits_{y\in Y} f(x, y) = \max\limits_{y\in Y}\max\limits_{x\in X} f(x, y) = \max\limits_{y\in Y}f_{xmax}(y)$$

整体最大策略 $(x^{* }, y^{* })$ 可以表示为：

$$y^{* } \in \arg\max\limits_{y\in Y}f_{xmax}(y) \\$$ $$x^{* } \in \arg\max\limits_{x\in X}f(x, y^{* }) \\$$

性质2 (整体最小值的计算)

$X, Y$ 是两个集合，函数 $f: X\times Y \rightarrow \mathbb{R}$，那么整体最小值为：

$$f_{min}^{* } = \min\limits_{x\in X, y\in Y} f(x, y) = \min\limits_{y\in Y}\min\limits_{x\in X} f(x, y) = \min\limits_{x\in X}\min\limits_{y\in Y} f(x, y) = \min\limits_{x\in X}f_{ymin}(x)$$

整体最小策略 $(x^{* }, y^{* })$ 表示为：

$$x^{* } \in \arg\min\limits_{x\in X}f_{ymin}(x) \\$$ $$y^{* } \in \arg\min\limits_{y\in Y}f(x^{* }, y) \\$$

例子与计算过程

前面介绍了二元函数上的很多概念，下面是一个具体例子的计算。

考虑二元函数 $f(x, y) = 4xy - 2x - y + 3$，其中 $x \in [0, 1], y \in [0, 1]$，下面是各个概念的计算结果。

step1：保底盈利函数

• 保底盈利函数：$f_{ymin}(x) = \min\limits_{y\in Y}f(x, y) = \min\limits_{y\in [0, 1]}(4x-1)y + (3 - 2x)$，这里涉及到一个最优化的计算，结果如下：

$$f_{ymin}(x) = \left\{ \begin{array}{**ll**} 3 - 2x & \quad x \in (\frac{1}{4}, 1] \\ \frac{5}{2} & \quad x = \frac{1}{4} \\ 2 + 2x & \quad x \in [0, \frac{1}{4}) \\ \end{array} \right.$$

step2：保底亏本函数

• 保底亏本函数：$f_{xmax}(y) = \max\limits_{x\in X}f(x, y) = \max\limits_{x\in [0, 1]}(4y-2)x + (3-y)$，这里依然是一个最优化的计算，结果如下：

$$f_{xmax}(y) = \left\{ \begin{array}{**ll**} 1 + 3y & \quad x \in (\frac{1}{2}, 1] \\ \frac{5}{2} & \quad x = \frac{1}{2} \\ 3 - y & \quad x \in [0, \frac{1}{2}) \\ \end{array} \right.$$

在有了上面的保底盈利函数和保底亏本函数后，我们就可以计算四种策略及其对应的值了。

step3：整体最小策略

由前面的性质2，$f_{min}^{* } = \min\limits_{x\in X}f_{ymin}(x) = \min\limits_{x\in [0,1]}f_{ymin}(x)$，这依然是一个最优化计算，结果为 $f_{min}^{* } = 1$。这是整体最小策略的值。

进一步根据性质2：

• $x^{*} \in \min\limits_{x\in [0,1]}f_{ymin}(x) = \{1\}$。
• $y^{* } \in \arg\min\limits_{y\in Y}f(x^{* }, y) = \arg\min\limits_{y\in [0,1]}f(1, y) = \arg\min\limits_{y\in [0,1]}(3y - 1) = \{0\}$

因此整体最小策略为 $\arg\min\limits_{x\in X, y\in Y} f(x,y) = \{(1, 0)\}$。

step4：整体最大策略

由前面的性质1，$f_{max}^{* } = \max\limits_{y\in Y}f_{xmax}(y) = \max\limits_{y\in Y}f_{xmax}(y)$，这依然是一个最优化计算，结果为 $f_{max}^{* } = 4$。这是整体最大策略的值。

进一步根据性质1：

• $y^{*} \in \max\limits_{y\in [0,1]}f_{xmax}(y) = \{1\}$。
• $x^{*} \in \arg\max\limits_{x\in X}f(x, y^{*}) = \arg\max\limits_{x\in [0,1]}f(x, 1) = \arg\max\limits_{x\in [0,1]}(2x+2) = \{1\}$

因此整体最大策略为 $\arg\max\limits_{x\in X, y\in Y} f(x,y) = \{(1, 1)\}$。

step5：最大最小策略

根据定义，$f_{ymin}^{* } = \max\limits_{x\in X}f_{ymin}(x) = \max\limits_{x\in [0, 1]}f_{ymin}(x)$，这依然是一个最优化计算，结果为 $f_{ymin}^{* } = \frac{5}{2}$。这是最大最小策略的值。

对应的参与人1 的最大最小策略为 $x^{*} = \arg\max\limits_{x\in [0,1]}f_{ymin}(x) = \{\frac{1}{4}\}$。

step6：最大最小策略

根据定义，$f_{xmax}^{* } = \min\limits_{y\in Y}f_{xmax}(y) = \max\limits_{y\in [0, 1]}f_{xmax}(y)$，这依然是一个最优化计算，结果为 $f_{xmax}^{* } = \frac{5}{2}$。这是最小最大策略的值。

对应的参与人2 的最小最大策略为 $y^{*} = \arg\min\limits_{y\in [0,1]}f_{xmax}(y) = \{\frac{1}{2}\}$。

总结

计算过程涉及到大量的最优化计算，当函数和取值范围复杂的时候计算量非常大。经过一系列计算后，各个策略及其对应的值总结如下：

• 整体最大策略是 $(1, 1)$，对应的整体最大值为 4。
• 整体最小策略是 $(1, 0)$，对应的整体最小值为 1。
• 最大最小策略为 $x = \frac{1}{4}$，对应的最大最小值是 $\frac{5}{2}$。
• 最小最大策略为 $y = \frac{1}{2}$，对应的最小最大值也是 $\frac{5}{2}$。

---

最大最小/最小最大策略与鞍点

在前面的例子中，我们发现最大最小值与最小最大值是相等的，这在博弈论中很有意义。那么一个自然的问题就是最小最大值跟最大最小值是相等的吗，如果不一定相等，那么要满足什么条件它们就相等了。

要回答这个问题就需要借助鞍点的概念了。鞍点主观来讲类似于马鞍上的一个特殊点，沿着马身方向是最小值点，沿着垂直于马身（人骑上去时从左腿到右腿的方向）是大值点。下面给出二元函数上鞍点的定义。

鞍点的定义

$X, Y$ 为两个集合，函数 $f: X\times Y \rightarrow \mathbb{R}$，若：

$$f(X, y^{* }) \leq f(x^{* }, y^{* }) \leq f(x^{* }, Y)$$

则称 $(x^{*}, y^{*}) \in X\times Y$ 为鞍点。

所有鞍点的集合记为 $\mathrm{Saddle}(f)$。

引理 (最大最小值 $\leq$ 最小最大值)

$X, Y$ 为两个集合，函数 $f: X\times Y \rightarrow \mathbb{R}$，则若：

$$\max\limits_{x\in X}\min\limits_{y\in Y}f(x, y) \leq \min\limits_{y\in Y}\max\limits_{x\in X}f(x, y)$$

进一步可得：

$$f_{ymin}(x) \leq f_{ymin}^{* } \leq f_{xmax}^{* } \leq f_{xmax}(y)$$

---

证明

从 $f(x, y) \leq \max\limits_{x\in X}f(x, y)$ 出发，两边对 $y$ 取最小值，得：

$$\min\limits_{y\in Y}f(x, y) \leq \min\limits_{y\in Y}\max\limits_{x\in X}f(x, y)$$

然后两边同时对 $x$ 取最大，得：

$$\max\limits_{x\in X}\min\limits_{y\in Y}f(x, y) \leq \max\limits_{x\in X}\min\limits_{y\in Y}\max\limits_{x\in X}f(x, y)$$

上式右边，由于 $\min\limits_{y\in Y}\max\limits_{x\in X}f(x, y)$ 已经是一个常数，所以再对 $x$ 取一个最小还是它本身，因此：

$$\max\limits_{x\in X}\min\limits_{y\in Y}f(x, y) \leq \min\limits_{y\in Y}\max\limits_{x\in X}f(x, y)$$

这正是待证明的第一个不等式。

上式左边的 $\min\limits_{y\in Y}f(x, y)$ 正是保底盈利函数 $f_{ymin}(x)$，上式右边的 $\max\limits_{x\in X}f(x, y)$ 正是保底亏本函数 $f_{xmax}(y)$，将其代入得：

$$\max\limits_{x\in X}f_{ymin}(x) \leq \min\limits_{y\in Y}f_{xmax}(y)$$

上式左边和右边分别是最大最小值 $f_{ymin}^{* }$ 和最小最大值 $f_{xmax}^{* }$ 的定义，于是最终得到最终结论：

$$f_{ymin}(x) \leq f_{ymin}^{* } \leq f_{xmax}^{* } \leq f_{xmax}(y)$$

$\Box$

该引理说明，最大最小值是小于等于最小最大值的，这是二元函数普适的结论，与博弈论无关。但是要推导博弈论中的有用结论，需要用到这个引理。

下面介绍本文的核心内容，也就是二元函数的鞍点定理。前面的引理指出最大最小值肯定不大于最小最大值，即 $f_{ymin}^{* } \leq f_{xmax}^{* }$，鞍点定理指出了不等式等号什么时候成立，及其与鞍点的关系。基于该定理，我们之前写过很多的 minimax 算法就有了理论基础。

鞍点定理1

$X, Y$ 为两个集合，函数 $f: X\times Y \rightarrow \mathbb{R}$，若：

$$f_{ymin}^{* } = f_{xmax}^{* }$$

则对 $\forall x^{*} \in \arg\max\limits_{x\in X}f_{ymin}(x), y^{*} \in \arg\min\limits_{y\in Y}f_{xmax}(y)$，有：

$$(x^{* }, y^{* }) \in \mathrm{Saddle}(f)$$

并且 $f_{ymin}^{* } = f_{xmax}^{* } = f(x^{* }, y^{* })$。

---

证明 (不等式)

取 $x^{*} \in \arg\max\limits_{x\in X}f_{ymin}(x)$，$y^{*} \in \arg\min\limits_{y\in Y}f_{xmax}(y)$，其中 保底盈利函数 $f_{ymin}(x) = \min\limits_{y\in Y}f(x, y)$，保底亏本函数 $f_{xmax}(y) = \max\limits_{x\in X}f(x, y)$。

利用不等式的放缩，可以做以下推导：

$$f(x, y^{* }) \leq \max\limits_{x\in X}f(x, y^{* }) = f_{xmax}(y^{* }) = f_{xmax}^{* } \\$$ $$f_{ymin}^{* } = f_{ymin}(x^{* }) = \min\limits_{y\in Y}f(x^{* }, y) \leq f(x^{* }, y^{* }) \\$$

另一方面，考虑另一个放缩，写出以下不等式：

$$f(x^{* }, y^{* }) \leq \max\limits_{x\in X}f(x, y^{* }) = f_{xmax}(y^{* }) = f_{xmax}^{* } \\$$ $$f_{ymin}^{* } = f_{ymin}(x^{* }) = \min\limits_{y\in Y}f(x^{* }, y) \leq f(x^{* }, y) \\$$

由于 $f_{ymin}^{* } = f_{xmax}^{* }$，上述不等式可以首尾连接到一起，化简后得到：

$$f(x,y^{* }) \leq f(x^{* }, y^{* }) \leq f(x^{* }, y)$$

这是鞍点的定义，因此 $(x^{*}, y^{*}) \in \mathrm{Saddle}(f)$。

同样地在上述首尾相连后的不等式中，考虑下面这一段：

$$f_{xmax}^{* } = f_{ymin}^{* } = f_{ymin}(x^{* }) = \min\limits_{y\in Y}f(x^{* }, y) \leq f(x^{* }, y^{* }) \\$$ $$f(x^{* }, y^{* }) \leq \max\limits_{x\in X}f(x, y^{* }) = f_{xmax}(y^{* }) = f_{xmax}^{* } = f_{ymin}^{* } \\$$

即可得到：

$$f_{xmax}^{* } = f_{ymin}^{* } = f(x^{* }, y^{* })$$

$\Box$

鞍点定理2

$X, Y$ 为两个集合，函数 $f: X\times Y \rightarrow \mathbb{R}$，若：

$$(x^{* }, y^{* }) \in \mathrm{Saddle}(f)$$

则 $x^{*} \in \arg\max\limits_{x\in X}f_{ymin}(x), y^{*} \in \arg\min\limits_{y\in Y}f_{xmax}(y)$，并且：

$$f_{ymin}^{* } = f_{xmax}^{* } = f(x^{* }, y^{* })$$

---

证明

记 $f$ 的保底盈利函数 $f_{ymin}(x) = \min\limits_{y\in Y}f(x, y)$，对应的最大最小值为 $f_{ymin}^{* } = \max\limits_{x\in X}f_{ymin}(x)$；

记 $f$ 的保底亏本函数 $f_{xmax}(y) = \max\limits_{x\in X}f(x, y)$，对应的最小最大值为 $f_{xmax}^{* } = \min\limits_{y\in Y}f_{xmax}(y)$。

对于 $(x^{*}, y^{*}) \in \mathrm{Saddle}(f)$，根据鞍点的定义，有：

$$f(x,y^{* }) \leq f(x^{* }, y^{* }) \leq f(x^{* }, y)$$

再利用放缩可以写出以下不等式：

$$f_{xmax}^{* } \leq f_{xmax}(y^{* }) = \max\limits_{x\in X}f(x, y^{* }) \leq f(x^{* }, y^{* })$$ $$f(x^{* }, y^{* }) \leq \min\limits_{y\in Y}f(x^{* }, y) = f_{ymin}(x^{* }) \leq f_{ymin}^{* }$$

由前面的引理，$f_{ymin}^{* } \leq f_{xmax}^{* }$，那么上面的不等式中所有的 $\leq$ 都需要改为等号，即：

$$f_{xmax}^{* } = f_{xmax}(y^{* }) = \max\limits_{x\in X}f(x, y^{* }) = f(x^{* }, y^{* })$$ $$f(x^{* }, y^{* }) = \min\limits_{y\in Y}f(x^{* }, y) = f_{ymin}(x^{* }) = f_{ymin}^{* }$$

由此可得：

$$f_{ymin}^{* } = f_{xmax}^{* } = f(x^{* }, y^{* })$$ $$x^{* } \in \arg\max\limits_{x\in X}f_{ymin}(x)$$ $$y^{* } \in \arg\min\limits_{y\in Y}f_{xmax}(y)$$

$\Box$

该定理说明，如果二元函数有鞍点，那么鞍点对应的函数值是唯一的，该值即为最大最小值以及最小最大值。

---

总结

在博弈论中，我们会定义二人有限零和博弈的均衡解和博弈解，根据相关的定义我们会发现，鞍点就是均衡解，最大最小值和最小最大值就是博弈解。

因此鞍点定理可以用来描述二人有限零和博弈的均衡解和博弈解，结论是如果二人有限零和博弈存在均衡解，那么博弈解等于均衡解。我们此前写过很多的 minimax 算法，求的就是博弈解。

---