求解纳什均衡点

基本知识回顾

两个人的双矩阵博弈可以这样描述：

两个玩家 M 和 N 各有 m,n 个纯策略，当 M 使用纯策略 i 而 N 使用纯策略 j 时，M 的收益是 $a_{ij}$ , N 的收益是 $b_{ij}$ . 用 A 和 B 表示由 $a_{ij}$ 和 $b_{ij}$ 构成的矩阵.

M 的混合策略 $x = (x_1,x_2,\cdots,x_m)^T$ 是指玩家 M 以概率 $x_i$ 使用第 i 个策略，其中 $x_1 + x_2 + \cdots + x_m = 1$ , 同理 N 的混合策略是 $y = (y_1,y_2,\cdots,y_n)^T$ .

用矩阵的形式，一个混合策略 $(x,y)$ 如下定义：

$e^T x = e^T y = 1,\text{ and } x \ge 0, y\ge 0 \tag{2}$

(策略是单纯形? 这个回头学习一下回来补上)

对应的收益是

$x^T A y \text{ and } x^T B y \tag{3}$

一个游戏的均衡点 $(x_0,y_0)$ 需要满足对于任意满足 (2) 的策略 $(x,y)$ , 有

$x_0^T A y0 \ge x^T A y_0, \text{ and } x_0^T B y_0 \ge x_0^T B y \tag{4}$

纳什证明了平凡的结论：对于 n 个人的有限博弈一定存在均衡点。

均衡的等价表述

(4) 是说一个策略如果是纳什均衡，则对每个人来说在别人不改变策略的情况下，自己的收益不比采取任何一个策略带来的收益低。另一种等价的表述是：一个策略如果是纳什均衡，则对每个人来说在别人不改变策略的情况下，自己的收益不比采取任何一个自己的纯策略带来的收益低。这一点用期望效用的公式很容易证明。对应的矩阵形式是

$B^T x_0 \le (x_0^T B y_0)e \text{ and } Ay_0 \le (x_0^T A y_0)e \tag{5}$

也就是说， (2)(4) 和 (2)(5) 是等价的。

记 $u = x_0^T B y_0, v = x_0^T A y_0$ , 也就是二人的均衡收益. 当 $u,v>0$ 时可以把不等式的右边标准化成 $e$ , 所以上式可以写成

$B^T (\frac 1 u x_0) \le e \text{ and } A (\frac 1 v y_0) \le e$

均衡收益是矩阵元素按照实现概率的线性加和, 所以这里如果矩阵 $A,B$ 都是正数构成的矩阵, 就一定可以满足 $u,v > 0$ . 而对一个收益矩阵的每个元素都增加 a, 对于任意一种策略 (x,y), 两个人收益的改变都为 $x(aE)y = a$ , 所以并不会改变均衡. 其中 $E = ee^T$ 是全部元素都是 1 的矩阵, 满足 (2) 的 $(x,y)$ 满足 $Ey = e, x^TEy = x^Te = 1$ .

现在令 $k$ 是一个固定的且足够大的数使得 $kE - B^T > 0, kE - A >0$ , 将上式左右同时乘 $(K - 1)$ , 并把伸缩后的向量仍然记为 $(x,y)$ , 整理后可得形式
考虑以下方程的解 $(x,y)$ (不需要满足条件(2))

$\begin{equation*} \left\{ \begin{array}{ll} (kE-B^T)x \ge e, x\ge 0, \\ (kE - A)y \ge e, y\ge 0, \end{array} \right. \text{ and } \left\{ \begin{array}{ll} y^T[(kE - B^T)x - e] = 0, \\ x^T[(kE - A)y - e] = 0. \end{array} \right. \end{equation*} \tag{6}$

两个等式约束是为了满足互补松弛条件, 也就是对于 $x$ 和 $(kE - A)y - e$ 的第 $k$ 项( $k$ 任意), 至少有一个等于 $0$ , 否则说明在非最优反应的行动上分配了正的概率, 存在可获利的偏离.

正如上文论述, 这样的解可以与均衡点 $(x_0,y_0)$ 一一对应, 只要把这个方程的解标准化到 $\Sigma x_i = 1, \Sigma y_i = 1$ 即可.

将 $k$ 也看作参数, 约束 (6) 的解其实可以看作对 $\Sigma x_i, \Sigma y_i$ 无约束的 (5) 的解, 而固定下了 $k$ 二者就构成了一一对应.

充分性

展开 (6) 的左边两个不等式约束, 得到

$\begin{equation*} \left\{ \begin{array}{ll} B^T x \le k E x - e, \\ Ay \le k E y - e. \end{array} \right. \end{equation*}$

$y$ 和 $(kE - B^T)x - e$ 都是大于等于 0 的向量, 它们的内积为零说明在任意一个维度上至多只能有一个向量为正, 且两个向量都存在一些维度为零.

$k E x - e$ 是所有元素都为 $k\Sigma x_i - 1$ 的列向量, $(kE - B^T)x - e \ge 0$ 且有些元素严格取等说明 $k\Sigma x_i - 1 = \max B^Tx$ , $y$ 只能在 $B^T x$ 中等于 $\max B^Tx$ 的维度上大于零, 这其实对应于均衡时每个人策略的支撑集应当包含于对其他人策略的最优反应( $\text{supp}(\sigma_i) \subset BR_i(\sigma_{-i})$ ). 这里已经给出了均衡时各个策略之间分布的比例关系, 将 $(x,y)$ 标准化到 $\Sigma x_i = 1, \Sigma y_i = 1$ 即可得到一个均衡点.

$x_0 = (\frac 1 {x^T e})x, y_0 = (\frac 1 {y^Te})y.$

必要性

展开 (6) 的右边两个等式约束, 得到

$\begin{equation*} \left\{ \begin{array}{ll} k y^TE x - y^Te = y^TB^Tx, \\ k x^T E y - x^Te = x^TAy. \end{array} \right. \end{equation*}$

注意到 $y^TE x = x^T E y = (\Sigma x_i)(\Sigma y_j)$ , 想从 $(x_0,y_0)$ 映射到 $(x,y)$ , 其实也是要确定缩放的比例 $r_1,r_2$ , 记均衡收益为 $(p_1,p_2)$ , 求解方程组

$\begin{equation*} \left\{ \begin{array}{ll} k r_1 r_2 - r_2 = r_1 r_2 p_2, \\ k r_1 r_2 - r_1 = r_1 r_2 p_1. \end{array} \right. \end{equation*}$

方程在两人均衡收益不同 ( $p_1 \neq p_2$ ) 时有唯一解 $r_1 = \frac 1 {k - p_2}, r_2 = \frac{1}{k - p_1}$ .

$p_1= p_2 = p$ 时方程退化, 唯一解为 $r_1 = r_2 = \frac{1}{k - p}$ .

因此方程的解有统一形式 $r_1 = \frac 1 {k - p_2}, r_2 = \frac{1}{k - p_1}$ .

对应的 $(x,y) = (r_1 x_0, r_2 y_0)$ .

非退化问题

上一节已经证明了 (2)(5) 与 (2)(6) 的等价性, 接下来只要考虑以下问题的解: A 和 B 都是矩阵元素都为正数的 m 行 n 列矩阵, 求解 $(x,y)$ 满足

$\begin{equation*} \left\{ \begin{array}{ll} B^Tx \ge e, x\ge 0, \\ Ay \ge e, y\ge 0, \end{array} \right. \text{ and } \left\{ \begin{array}{ll} y^T(B^Tx - e) = 0, \\ x^T(Ay - e) = 0. \end{array} \right. \end{equation*} \tag{7}$

这里的 $A,B$ 对应于上一节中的 $kE - A$ 和 $kE - B$ .

令

$X = \{x:x \ge 0, B^Tx - e \ge 0\}$

记

$B = (b_1,b_2,\cdots,b_n), I = (e_1,e_2,\cdots,e_m)$

$X$ 是满足 $m+n$ 个不等式约束的 $x$ 的集合

$\begin{align*} &e_i^T x \ge 0, & i = 1,2,\cdots,m,\\ &b_j^T x - 1 \ge 0, & j = 1,2,\cdots,n. \end{align*} \tag{10}$

这些约束对应 (7) 中的 $B^Tx \ge e, x\ge 0$ . 写成矩阵形式就是 $(B,I)^T x \ge (1,1,\cdots,1,0,0,\cdots,0)$ .

X 边界上的点是 X 中满足以下至少一个线性关系的x

$\begin{align*} &e_i^T x = 0, & i = 1,2,\cdots,m,\\ &b_j^T x - 1 = 0, & j = 1,2,\cdots,n. \end{align*} \tag{11}$

对于任意的 x, 对应了一个由 $(B,I)$ 的若干列向量构成的矩阵 $M(x)$ : $b_j$ (或者 $e_i$ ) 是 M 中的列向量当且仅当 $b_j^T x - 1 = 0$ (或者 $e_i^Tx = 0$ ). M(x) 中列向量的顺序并不重要.

或者说 $M(x)$ 是由 (11) 中使得等号成立的向量作为列向量构成的矩阵.

若 m 行 r 列的矩阵 $\bar B$ 是 $(B,I)$ 的一些列向量组成的矩阵, 当 $\bar B$ 的秩为 $m$ 时, 至多存在一个 $x$ 使得 $\bar B = M(x)$ (因为 m 维的 x 此时要满足 m 个线性无关的约束, 有常数项时只能是唯一解或者无解). 如果更进一步, $x\in X$ , 这就是 X 的一个极端点( $extreme\ point$ ). 即使不是计算上的需要，也是非常方便的，在下面的内容中要确保对于一个极端点x，M(x)正好有m列 (因为超出行数 m 之后一定存在线性相关的列可以不做考虑). 在这一节的剩余部分我们考虑 X 满足非退化假设:

$\bar B = (B,I)$ 是 m 行 r 列的矩阵.如果存在 x 使得 $\bar B = M(x)$ , 则 $rank(B) = r$ .

扰动定义一个给定的凸多面体（如X）的数据，从而使扰动的数据定义一个非退化多面体的方法，是众所周知的。

对于给定的凸多面体 X，可以通过多种方式扰动定义该多面体的数据，使得扰动后的数据定义一个非退化的多面体

这种扰动并不会影响存在性的证明,而是简化了均衡点的计算.这里指出一些这种假设的相关影响.

令 $x_0$ 是 X 中的一个点, $M(x_0)$ 是 $m \times r$ 的矩阵. 由非退化假设, $rank(M(x_0)) = r$ , 所以 $M(x_0)$ 的列向量线性无关. 把 $M(x_0)$ 写作 $(d_1, d_2, \cdots, d_r)$ , 可以扩充成m个线性无关的向量 $C = (d_1, d_2, \cdots, d_m)$ , 记 C 的逆矩阵的转置为 $C^{-T} = (d^1, d^2, \cdots, d^m)$ , 则有性质

$d_i^Td^j = \delta_i^j$

$\delta_i^j$ 是克罗内克尔符号(Kronecker symbol), 当 $i = j$ 时, $\delta_i^j=1$ , 当 $i \neq j$ 时, $\delta_i^j=0$ .

考虑从 $x_0$ 变化得到的点

$x = x_0 + \Sigma_{i = 1}^m t_i d^i, \tag{12}$

其中 $t_i$ 是标量.

则有以下引理:

存在 k 使得 $\Sigma_{i=1}^m t_i^2 \le k$ 且 $t_i \ge 0 (1 \le i \le r)$ 时, (12) 给出的点都在 X 中.

证明思路：考虑直接把 x 代入约束条件记得到证明. 等号成立的式子只可能变成更大, 大于等于的要求依然成立. 不等号的式子在小区间内晃动时依然保号.

这个引理基于非退化性假设 (因为扩张成基时默认了原先的列向量是线性无关的), 在非退化性质下可得:

(i) 如果 $x_0$ 是 X 的一个极端点, 由 (12) 给出的 x 对应的 $M(x)$ 是非奇异的. $t_i$ 非负且很小的情形下 $x = x_0 + t_i d^i$ 得到的 x 都在 X 中. $t_i>0$ 的 x, $M(x) = M_i$ 是从 $M(x_0)$ 中删除第 i 列得到的矩阵. 这些点构成的集合叫做 X 的端点为 $x_0$ 的一条开边(open edge).
(ii) 如果 $x_0$ 是 X 中满足 $rank(M(x_0)) = m - 1$ 的点, 由 (12) 可得, 对一些 $x = x_0 + t_m d^m \quad (|t_m \le k|)$ 满足 $M(x) = M(x_0)$ . 这些点构成 X 的一条开边(open edge). 这是由于对于任意的 x, x 附近的点仅能满足 x 的(其中一些)线性约束条件(约束 (11)), 恰好有 m 条开边使得各自其中一个端点是某个极端点(或者每个极端点都恰好连接 m 条开边).
(iii) X 恰好有 m 条无限边(unbounded edges), 每条边只有一个端点. 这些边上的点有性质 $x = ke_i$ , 其中 k 是足够大的正数. 这是由于 B 只有正的元素 (这个开边对应的极端点满足 $e_{-i}^T x = 0$ 以及某个 $j$ 使得 $b_j^T x = 1$ 且 $b_{-j}^T x > 1$ , 这里不能大于等于的原因是非退化条件). 其他 X 的开边都有两个端点, 即连接两个极端点. 因此, 两个极端点是相邻的当且仅当他们对应的矩阵有且仅有一列不相同(列的顺序并不重要).

无限边满足 $m - 1$ 个约束条件, 所以只能是 $\eta + k \lambda$ 的形式, 如果约束条件中 $e_{-i}^T x = 0$ 形式的小于 $m - 1$ 个, 则存在 $b_j^T x = 1$ 的约束, 而由于 $B> 0 \Rightarrow b_j > 0$ , 当 $k$ 足够大时一定有 $b_j^T (\eta + k \lambda) > 1$ , 矛盾. 所以无限边的非端点上满足的条件只能是向量中最多只有一维不是零, 所以恰好可以构造 $m$ 条无限边如上述形式.

类似地, 令

$Y = \{y:y \ge 0, Ay - e \ge 0\}. \tag{14}$

Y 的边界定义为 Y 中满足至少一条以下条件的点:

$\begin{align*} &a_i^T y - 1 = 0, & i = 1,2,\cdots,m,\\ &e_j^T y = 0, & j = 1,2,\cdots,n. \end{align*} \tag{15}$

其中 $A^T = (a_1, a_2, \cdots, a_m)$ .

和 X 一样, 假设 Y 满足非退化条件, 所有的定义和引理都类似, 只是 m 和 n 互换了, $(B,I)$ 换成了 $(I, A^T)$ , N(y) 表示对应的矩阵.

令 $Z = (X,Y)$ 是 X 和 Y 的笛卡尔积. $z = (x,y)$ 是 Z 的极端点当且仅当 x 是 X 的极端点且 y 是 Y 的极端点. z 在 Z 的一条开边上当且仅当 x 和 y 其中一个是极端点, 另一个在开边上.

由 (7), 均衡点 $z = (x,y)$ 的均衡条件是 Z 中的点 z 满足

$\begin{align*} &(e_i^T x)(a_i^T y - 1)=0, & i = 1,2,\cdots,m,\\ &(e_j^T y)(b_j^T x -1)=0, & j = 1,2,\cdots,n. \end{align*} \tag{16}$

引理: 非退化问题的均衡点是 Z 的极端点.

证明思路: 均衡点需要满足 (16) 中的 m+n 个约束条件. 所以给出的线性约束(15)和(11)至少要满足 m+n 个. 由非退化条件, x 最多只能满足 m 个, y 最多只能满足 n 个, 取等时正好各自满足 m,n 个条件, 也就是极端点.

所以极端点 z 如此识别: 对于任意 $r = 1,2,\cdots, m+n$ , 要么 (B,I) 的第 r 列在 M(x) 中, 要么 (I, A^T) 的第 r 列在 N(y) 中, 且不能同时满足.

对于给定的 r, 定义 $S_r$ 是 Z 中满足所有 m+n 个约束中除了可能违背 $(e_r^T y)(b_r^T x - 1) = 0$ , 其他都满足的点的集合.

引理: $S_r$ 中的点要么是 Z 的极端点, 要么在 Z 的开边上.

$S_r$ 中的点至少满足 $m+n-1$ 个约束条件, 而 $Z$ 中的点最多只能满足 $m+n$ 个条件. 当满足 $m+n$ 个条件时是极端点, $m+n-1$ 个条件时在开边上.

引理: 恰有一个 Z 的无限边由 $S_r$ 的点构成.

考虑可能违背 $(e_r^T y)(b_r^T x - 1) = 0$ . 需要 $e_r^T y \neq 0, b_r^T x \neq 1$ . 考虑 $y = k e_r$ 对应的极端点 $y_0 = k_0 e_r$ , 它除了非 r 位元素都等于 0 外还满足 $a_s^Ty_0 = 1$ . 然后考虑 $x = ke^s$ , 当 $k$ 足够大时 $(x, y+0)$ 构成了一条 $Z$ 中的一条无限边, $(x_0,y_0)$ 是对应的极端点.

我们记这样的无限边为 $E_0$ .

$Z$ 的开边上的点不可能同时在 $S_r,S_{r'}(r \neq r')$ 中. 且给定一个 $r$ , 可以关联到 $Z$ 中唯一的一条无限边.

引理: z 是 Z 的一个极端点, 也是 $S_r$ 中的点. 存在 Z 的一到两条开边构成了所有 $S_r$ 中的点, 且一个端点是 z. z 是一个均衡点当且仅当存在一条这样的边.

$(e_r^T y)(b_r^T x - 1) = 0$ 时, $z$ 是均衡点(因为满足均衡条件, 另外所有的均衡点都在 $S_r$ 中). 对于均衡的 $m+n$ 个约束条件(两个因式乘积为 0 的形式), 每个都有其中一项等于零, 而另一项不等于零. 假设 $z$ 使得 $e_r^T y$ 取零, 这个端点一共有 $m+n$ 条边连接, 而其中只有 $e_r^T y = 0$ 被违背的边在 $S_r$ 中, 且恰好构成了 $S_r$ .

$(e_r^T y)(b_r^T x - 1) > 0$ 时, 肯定存在唯一的 $t$ , $t$ 对应的乘积的两项因子都是零, 即 $e_t^Tx= 0, a_t^Ty= 1$ . 分别违背这两个条件, 则约束 t 仍然成立, 得到的点仍然在 $S_r$ 中, 且构成了 $S_r$ 的所有点. 此外不可能有点属于 $S_r$ , 否则一定有别的约束条件被违背.

如果 $Z$ 的两条开边有共同的端点, 则称他们是相邻的. 考虑 $S_r$ 中相邻边以及端点组成的序列, 称之为 r-路径.

由之前的引理, $S_r$ 中一定存在 $Z$ 的极端点, 从这个点出发可以有一条或两条 $S_r$ 中的 $Z$ 的开边. 沿着开边有两种情况: 到达另一个极端点或者开边是一条无限边. 在第一种情况中 (到达另一个极端点), 如果是均衡点则算法停止, 否则沿着这个极端点的另一条开边搜索. 所以算法在以下三种情况结束:

到达 $S_r$ 的无限边 $E_0$ ;
到达一个均衡点;
回到之前搜索过的点.

如果算法结束返回, 这条路径称为 r-路径; 如果没有返回, 则到达了均衡点或者无限边. 如果返回 $z$ 时发现是均衡点, 则 r-路径是完全的. 否则可以沿着 $z$ 的另一条边继续寻找均衡点 (寻找其他的均衡点). 这个过程是有限步的, 因为 $Z$ 中的极端点是有限的.

引理: $S_r$ 是非空的. 且 $S_r$ 是有限个不相交的 r-路径的并集。每个 r-路径要么是闭合的r-路径（不含均衡点），要么包含一个或两个均衡点。

现在令 $P_0$ 是包含无限边 $E_0$ 的r-路径.

定理: $P_0$ 包含恰好一个均衡点. 这个点的计算可以通过从无限边 $E_0$ 开始遍历 $P_0$ 得到. 均衡点的数量一定是有限的且为奇数.

每个极端点最多连接两条合法路径, 所以从一头 (开边) 开始遍历总会结束于另一头. 这是由于上文引理 z 是一个均衡点当且仅当存在一条这样的边.

$P_0$ 以外的任意路径不是闭的 r-path 会有两个端点, 每个都是均衡点. 这些端点一定是不同的.

Q: 这里会不会有一个两端都是无限边的 r-路径呢? 这样的话路径上就可能不会有均衡点了?
A: 这是不可能的, 参考 $S_r$ 的定义一个 $S_r$ 中不可能有两个无限边, 上文有提到, 给定一个 $r$ , 可以关联到 $Z$ 中唯一的一条无限边.

对于求解非退化问题, 如果只要要找到一个均衡点, 则考虑找到一条无限边, 从无限边出发遍历 r-路径, 终点一定是均衡点; 无限边的形式是相对简单的, 因此比较容易获得.

一般情形(解决退化问题)

退化情形下有的均衡点可以不是极端点

(i) 原始的数据可以通过类似线性规划理论的扰动得到非退化问题, 且通过上一节的结论依然有效;
(ii) 扰动方案确保扰动后的多面体的任何极端点都定义了原始多面体的一个明确的极端点.特别地，扰动问题的均衡点定义了原始问题的均衡点。特定的扰动方案不是唯一的。使用扰动数据计算极点路径的计算方案是众所周知的，本文不再讨论。

考虑一个如下形式的扰动向量: $e(\epsilon) = (\epsilon, \epsilon^2, \cdots)$ . 定义 $X(\epsilon),Y(\epsilon),Z(\epsilon)$ 如下:

$\begin{align*} X(\epsilon) = \{ x: x\ge 0, B^T x - e + e(\epsilon) \ge 0 \}, \\ Y(\epsilon) = \{ y:y \ge 0, Ay - e + e(\epsilon) \ge 0 \}, \\ Z(\epsilon) = (X(\epsilon), Y(\epsilon)). \end{align*} \tag{17}$

当 $\epsilon > 0$ 时, 这是一个放松的条件, 所以 $Z = Z(0) \subset Z(\epsilon)$ .

引理 1: 存在 $\epsilon_0$ , 使得 $0 < \epsilon < \epsilon_0$ 时, $X(\epsilon)$ 满足非退化条件.

$\begin{align*} &e_i^T x = 0, & i = 1,2,\cdots,m,\\ &b_j^T x - 1 = 0, & j = 1,2,\cdots,n. \end{align*} \tag{11}$

对应的条件是

$d^T x - 1 + \epsilon^k = 0 \tag{18}$

当 $d = e_i$ 时 $k = 0$ , $d = b_j$ 时 $k = j$ .

令 $\bar B = (d_1,d_2, \cdots,d_r)$ 是由 $(B,I)$ 的列组成的矩阵, 令 d 是 $(B,I)$ 中其他某一列, 且是 $\bar B$ 的线性组合:

$d = \Sigma_{i=1}^r t_i d_i \tag{19}$

假设存在 $x$ 使得存在合适的 $k,k_i$ 满足

$d^Tx = 1 - \epsilon^k;\quad d_i^T x = 1 - \epsilon^{k_i}, i = 1,2,\cdots,r$

于是有

$0 = d^T x - \Sigma_{i=1}^r t_i d_i = (1 - \epsilon^k) - \Sigma_{i=1}^r t_i (1 - \epsilon^{k_i}) \tag{21}$

注意到每个不等于 0 的 k 都是不同的, 为了使得等式恒成立, 需要满足 $k = 0, k_i\cdot t_i = 0$ .

$k = 0$ 说明对应的列向量是单位向量, (19) 说明一个单位向量由不同的单位向量线性表出, 这显然是不可能的. 所以等式最多只能对 $\epsilon$ 的 m 个取值成立, 假设不成立, 所以 $X(\epsilon)$ 满足非退化假设.

注意: 这里可以理解为满足非退化的是 $X(\epsilon)$ , 而不是对 $\epsilon$ 的具体取值. 这就像 $sin(kx)$ 线性无关一样. 且在一个区间 $(0,epsilon_0)$ 内对于任意的 $epsilon$ 具体的取值, 非退化条件成立.

引理 2: 存在区间 $(0, \epsilon_1)$ 使得以下成立: M 是 $(B,I)$ 的列组成的非奇异矩阵, $x_0(\epsilon)$ 表示使得 $M = M(x_0(\epsilon))$ 成立的点, 如果对于一些 $(0, \epsilon_1)$ 内的点 $\bar \epsilon$ , $x_0(\bar \epsilon)$ 是 $X(\epsilon)$ 的一个极端点, 那么:

(1) 对于任意 $\epsilon \in (0, \epsilon_1)$ , $x_0(\epsilon)$ 都是 $X(\epsilon)$ 的极端点.

(2) $x_0 = x(0)$ 是 $X$ 的一个极端点.

证明:

令 $f(\epsilon) = \epsilon^n + a_{n - 1} \epsilon^{n-1} + \cdots + a_1 \epsilon + a_0$ 是任意的多项式. 由三角不等式得

$|f(\epsilon)| \le \Sigma_{i = 0}^n |a_i| \text{ for } |\epsilon| < 1 \tag{22}$

对给定的多项式, 令 $r$ 是最小的使得 $a_r \neq 0$ 的 $r$ . 于是

$f(\epsilon) = \epsilon^r(a_r + \epsilon g(\epsilon)) \tag{23}$

应用 (22), 存在区间 $(0,\bar\epsilon)$ 使得 $f(\epsilon)$ 保号(与 $a_r$ 同正负).

对给定的 $\bar \epsilon$ , 令 $x_0(\bar \epsilon)$ 是 $X(\bar \epsilon)$ 的极端点, 并令 $M = M(x_0(\bar \epsilon))$ . M 是非奇异矩阵, 对于 $\epsilon$ 和 $X(\epsilon)$ 给出了 $x_0(\epsilon)$ . 如果 $x_0(\epsilon) \in X(\epsilon)$ , 则是一个极端点. 令 $d$ 是 $(B,I)$ 中不同于 $M$ 的一列, 考虑

$d^T x_0(\epsilon) - 1 + \epsilon^k = f(\epsilon)$

参考 引理1, 当 $\epsilon \in (0,\epsilon_0)$ 时, $f(\epsilon)$ 是一个不为零阶的多项式, 记其主导系数为 $a_r$ . 存在 $\bar \epsilon < \epsilon_0$ , 使得 $f$ 在 $(0, \bar \epsilon)$ 保号.

$(M,d)$ 是有限的, 因此存在一个 $\epsilon_1$ 使得区间 $(0,\epsilon_1)$ 内对于任意 M,d, 对应的 $f$ 保号 (对每种 $(M,d)$ 找 $\bar \epsilon$ 并取最小的那个).

如果 $x\in X(\epsilon)$ , 则 $f(\epsilon) > 0$ , 因此 对于任意 $\epsilon \in (0, \epsilon_1)$ , $x_0(\epsilon)$ 都是 $X(\epsilon)$ 的极端点.

当 $r > 0$ 时 $f(0) = 0$ 约束成立, $r = 0$ 时 $f(0) = a_r$ 符号不改变, 所以 $x_0 \in X$ , 且为一个极端点.

注意: 这里的极端点是指满足 m 个线性无关的约束条件的点, 由于退化性的存在这个点还可能满足更多个约束.

定理 2: 存在一个 (7) 定义的均衡点.

根据引理 2 和前一节的论述, $Z(\epsilon)$ 中可以找到均衡点 $z_0(\epsilon)$ , 令 $\epsilon = 0$ 得到 $z_0 = (x_0,y_0)$ 是原问题的均衡点.

这里不用逼近来获得解, 直接找出 $Z(\epsilon)$ 需要满足的约束等式, 由于是线性无关的, 可以唯一确定 $(x_0,y_0)$ .

总结

文章给出了计算一个均衡点的方法. 实际上均衡点可能不止一个, 比如一条 r-路径上两个均衡点的情况, 以及退化情形下有的均衡点可以不是极端点. 目前的研究还是基于求解一个均衡点, 但是哪怕一个均衡点也并不好求. 算法中需要从无限边开始遍历, 在连续的数轴上这并不容易; 此外非退化情形的扰动只是理论上可行, 实际上扰动多少才能满足要求取决于输入的数据.

有一个不成熟的想法: 既然不管什么情况下找到的均衡点都是极端点, 其实就是编号为 1 到 m+n 的约束对分为 m 和 n 两组, 一共有 $C(m+n,m)$ 中分法, 然后求解对应的线性方程, 验证是否满足所有的约束条件. 这样也可以找到所有的均衡点. 一种思路是直接求解所有不等式约束的极端点, 然后看是否满足互补松弛条件, 这样的想法是最简单的, 实现起来应该也是比较方便的.