双矩阵博弈的支持枚举

形式陈述

输入二人有限博弈的有理收益矩阵 $A,B\in\mathbb Q^{m\times n}$ ， $m,n\ge1$ 。行玩家使用概率列向量 $p\in\Delta_m$ ，列玩家使用 $q\in\Delta_n$ ，双方收益分别是 $p^{\mathsf T}Aq$ 与 $p^{\mathsf T}Bq$ 。本算法的基本输出是一个精确Nash 均衡。

支持枚举先猜测哪些动作获得正概率，再核验支持上的最佳回应条件。核心难点不是把两个收益设成相等，而是同时检查概率合法、支持外动作没有更高收益，以及声称在支持内的概率确实为正。

固定一对支持的线性规划

枚举所有非空 $I\subseteq[m]$ 、 $J\subseteq[n]$ ，不预先要求两者大小相等。对每一对求下列线性规划，变量为 $p,q,v,w,\delta$ ：

\max\ \delta

满足

\begin{aligned} p_i&=0 &&(i\notin I),& q_j&=0 &&(j\notin J),\\ \sum_i p_i&=1,& \sum_j q_j&=1,& \delta&\ge0,\\ p_i&\ge\delta &&(i\in I),& q_j&\ge\delta &&(j\in J),\\ (Aq)_i&=v &&(i\in I),& (Aq)_i&\le v &&(i\notin I),\\ (p^{\mathsf T}B)_j&=w &&(j\in J),& (p^{\mathsf T}B)_j&\le w &&(j\notin J). \end{aligned}

$v,w$ 是自由符号变量，不能因收益可能为负而额外规定它们非负。所有系数矩阵已经给定，各约束对决策变量线性，没有 $p_iq_j$ 乘积。

$\delta$ 是正概率的共同裕量。若 LP 可行，则

0\le\delta\le\min\{1/|I|,1/|J|\}.

概率在紧单纯形内；非空支持上的等式又把 $v,w$ 限制在对应收益矩阵的最小与最大条目之间。因此可行域紧，最优值 $\delta^*$ 能够取到。

枚举步骤与退出条件

固定一个可重复的支持枚举顺序。对每对 $I,J$ ：

构造上述 LP，用精确有理 LP 求解器判定不可行或给出最优值与最优解。
若不可行，继续下一对；若 $\delta^*=0$ ，也继续，因为该对没有精确为 $I,J$ 的正支持均衡。
若 $\delta^*>0$ ，返回所得 $(p,q)$ ，以及 $I,J,v,w,\delta^*$ 作为核验证书。

支持对有限，后面的完备性证明保证至少一对被接受。若求解器只返回有限精度近似，或因资源限制未完成，算法应报告尚未取得精确证书，不能把某个固定浮点阈值直接当作 $\delta^*>0$ 的数学判定。

可靠性与完备性

若 $\delta^*>0$ ，则 $p,q$ 恰好以 $I,J$ 为支持。行玩家所有正支持动作收益为 $v$ ，支持外收益不超过 $v$ ，故当前混合收益为 $v$ ，任何纯或混合偏离都不更好。列玩家同理，所以返回的是均衡。

反过来，设存在支持恰为 $I,J$ 的均衡 $(p,q)$ 。取全部正概率中的最小值

\delta_0=\min\bigl(\{p_i:i\in I\}\cup\{q_j:j\in J\}\bigr)>0.

支持最佳回应判据保证收益等式与不等式成立，故它与 $\delta_0$ 构成 LP 可行解，最优值必为正。因此

\delta^*>0 \quad\Longleftrightarrow\quad \text{存在支持恰为 }I,J\text{ 的均衡}.

任意均衡的实际支持非空，总会被枚举。有限 Nash 存在定理再保证某对实际支持存在，所以算法必能返回一个均衡。

若 $\delta^*=0$ ，该弱系统仍有可行概率，并且这些概率仍构成均衡；只是其中至少一方的实际支持严格小于宣称的支持。拒绝它是为了核验“恰好这对支持”，不是在宣告整场博弈没有均衡。

直觉

正支持动作都要“同样好”，支持外动作只要求“不更好”。前者形成等式，后者形成不等式。猜定支持后，双方概率不再相乘地出现在最佳回应条件里，于是一次 LP 就能检查这个猜测。

最大化 $\delta$ 是把严格正概率条件转成闭 LP 的办法。最优值为正，说明可以离开边界；最优值为零，说明系统只能站在某个声称支持的边界上。等式矩阵奇异则可能意味着一整段候选，不能据此直接跳过。

例子与边界

协调博弈的九对支持

沿用 Nash 页的协调博弈，

A=\begin{pmatrix}3&0\\0&2\end{pmatrix}, \qquad B=\begin{pmatrix}2&0\\0&3\end{pmatrix}.

双方各有三个非空支持，共九对。正裕量的三对为：

$I$	$J$	概率 $(p,q)$	$\delta^*$
$\{1\}$	$\{1\}$	$((1,0),(1,0))$	$1$
$\{2\}$	$\{2\}$	$((0,1),(0,1))$	$1$
$\{1,2\}$	$\{1,2\}$	$((3/5,2/5),(2/5,3/5))$	$2/5$

全支持时，行收益相等给 $3q_1=2q_2$ ，列收益相等给 $2p_1=3p_2$ ；结合归一化，得到表中唯一候选，两人收益均为 $6/5$ 。另外两对交叉纯支持不是最佳回应。剩余四对“一方单动作、另一方双动作”要求面对一个纯动作仍有两个相同最高收益动作，本表不满足，所以均不可行。这就检查完九对，而不是只找出三个看起来合理的解。

退化博弈：连续族与不等大支持

取

A=\begin{pmatrix}1&1&0\\1&1&2\end{pmatrix}, \qquad B=\begin{pmatrix}1&1&0\\0&0&1\end{pmatrix}.

写 $p=(t,1-t)^{\mathsf T}$ 、 $q=(a,b,c)^{\mathsf T}$ ，则

Aq=(1-c,1+c)^{\mathsf T},\qquad p^{\mathsf T}B=(t,t,1-t).

若 $0<t<1$ ，两行都被使用，必须令 $c=0$ ；列玩家只使用前两列，要求 $t\ge1/2$ 。若 $t=1$ ，行1最佳仍要求 $c=0$ ，列1、2可以任意混合。若 $t=0$ ，列3唯一最佳，所以 $q=(0,0,1)$ ，行2也确实最佳。因此全部均衡恰为

\left\{ \left( \begin{pmatrix}t\\1-t\end{pmatrix}, \begin{pmatrix}a\\1-a\\0\end{pmatrix} \right): \frac12\le t\le1,\ 0\le a\le1 \right\} \;\cup\; \left\{ \left( \begin{pmatrix}0\\1\end{pmatrix}, \begin{pmatrix}0\\0\\1\end{pmatrix} \right) \right\}.

这包含一个连续参数族和一个孤立纯均衡。图中两个截面分开显示，避免把不同列概率的点误放进同一平面。三对支持尤其有代表性：

$I=\{1,2\},J=\{1,2\}$ ：精确支持对应 $1/2\le t<1$ 、 $0<a<1$ 。等收益方程重复，并不能唯一决定概率；margin LP 的最优值为 $1/2$ ，可取 $t=a=1/2$ 。
$I=\{1\},J=\{1,2\}$ ： $t=1$ 、 $0<a<1$ 都是均衡，支持大小分别为 $1,2$ ，最优裕量为 $1/2$ 。仅枚举等大支持会漏掉这批精确支持。
$I=\{1,2\},J=\{1,2,3\}$ ：行等式强迫 $c=0$ ，列等式强迫 $t=1/2$ 。弱系统可行，但所有可行点的裕量都为零，没有这个精确支持的均衡。

全部 $3\times7=21$ 对支持还可压成下面的分类表。表内省略集合括号，例如 $12$ 表示 $\{1,2\}$ 。

行支持 $I$	正裕量的列支持及最优值	零裕量的列支持	不可行列支持
$1$	$1:1,\ 2:1,\ 12:1/2$	无	$3,13,23,123$
$2$	$3:1$	无	$1,2,12,13,23,123$
$12$	$1:1/2,\ 2:1/2,\ 12:1/2$	$13,23,123$	$3$

第一行的纯行策略使列1、2并列最佳，一个支持大小为1的策略有两个纯最佳回应，已经见证了退化。

非退化为何允许等大支持

二人博弈称为非退化，是指任一支持大小为 $k$ 的混合策略，至多使对手有 $k$ 个纯最佳回应。若均衡支持为 $I,J$ ，则

|I|\le|\operatorname{BR}_1(q)|\le|J| \le|\operatorname{BR}_2(p)|\le|I|,

所以全为等号。由此才可把枚举缩减为等大支持。一般输入没有这项保证；“等式解不唯一”也不能当作无均衡的证据，刚才的连续族正是反例。

推论与应用

(2^m-1)(2^n-1)

对非空支持。每个 LP 的变量及约束数为 $O(m+n)$ ，有理系数编码长度相对于输入位长 $L$ 为多项式。采用精确的多项式位复杂度 LP 算法，总复杂度可界为

O\bigl((2^m-1)(2^n-1)\operatorname{poly}(L)\bigr).

这是一条指数枚举上界，不是强多项式结论，也不保证任意单纯形实现都具有其中的每次求解界。小规模博弈适合用它做完整核验；规模增大时，猜支持的组合成本迅速主导。

若任务是描述全部均衡，每个支持只返回一个最大裕量点会遗漏连续族。可以保存各个接受支持的完整最佳回应线性系统，去掉裕量变量并保留支持内严格正概率条件；这些有限个系统的解集之并才是均衡全集。也可以保留允许零概率的闭系统，得到带重复边界的有限表示。有限的是描述系统数，不一定是均衡点数。

混合策略的支持判据让单方无穷多混合偏离化成有限个纯收益比较；本页再把双方支持选择转成枚举。相比之下，零和矩阵博弈有更强结构，可直接用一对互为对偶的 LP 求共同价值，不必套用通用指数枚举。

参考资料

Bernhard von Stengel, Finding Nash Equilibria of Two-Player Games, author preprint, 2021，§2、Proposition 1 的支持最佳回应，Definition 2、Proposition 3 和 Algorithm 4 的非退化等大支持算法；§9 讨论退化均衡集合。本页的正裕量 LP 是从最佳回应判据直接推导的一般化实现。
Bernhard von Stengel, “Equilibrium Computation for Two-Player Games in Strategic and Extensive Form,” in Algorithmic Game Theory, Cambridge University Press, 2007，§3.2 的支持枚举与退化边界。

形式陈述 ​

固定一对支持的线性规划 ​

枚举步骤与退出条件 ​

可靠性与完备性 ​

协调博弈的九对支持 ​

退化博弈：连续族与不等大支持 ​

非退化为何允许等大支持 ​