7.1.3 纳什均衡的计算
纳什均衡是博弈论中一个重要的基本数学问题，也是当前理论计算机科学中一个活跃的研究领域。在本文中，我们将介绍三种纳什均衡的求解算法，它们分别是支撑枚举算法、Lemke-Howson 算法以及 Lipton-Markakis-Mehta 算法。前两种算法属于精确求解算法，而最后一种则是近似算法。
7.1.3.1 支撑枚举算法
考虑策略型博弈Γ = 〈𝑁, (𝑆𝑖), (𝑢𝑖)〉。给定参与者𝑖的一个混合策略
𝜎𝑖，𝜎𝑖的支撑（记为𝛿(𝜎𝑖)）是一个集合，其中包含𝜎𝑖中概率为正的所有纯策略𝑠𝑖：
𝛿(𝜎𝑖) = {𝑠𝑖 ∈ 𝑆𝑖: 𝜎𝑖(𝑠𝑖) > 0}.
对于一个混合策略组𝜎 = (𝜎1, … , 𝜎𝑛)，我们可以自然地定义𝜎的支撑为𝛿(𝜎𝑖)（其中𝑖 = 1, 2, … , 𝑛）的乘积：
𝛿(𝜎1, … , 𝜎𝑛) = 𝛿(𝜎1) × … × 𝛿(𝜎𝑛).
这个集合包含了当参与者根据自己的策略选择时，所有伴随正概率的纯策略组合。我们可以立即注意到，每个混合策略纳什均衡必定对应一个支撑。对于有限博弈，由于支撑个数是有限的，因此我们可以考察每个支撑，看看哪个支撑能够产生纳什均衡。
设𝑋𝑖 ⊆ 𝑆𝑖为𝑆𝑖的一个非空子集，表示我们当前的猜测：在纳什均
衡中，参与者𝑖的哪些策略具有正概率。换言之，我们当前猜测纳什均衡的一个支撑为𝑋1 × 𝑋2 × … × 𝑋𝑛。如果存在对应于此支撑的纳什均衡，那么根据上述结果，必定存在数𝑤1, … , 𝑤𝑛和混合策略𝜎1, … , 𝜎𝑛使得以下条件成立：
𝑤𝑖 = 𝑢𝑖(𝑠𝑖, 𝜎−𝑖), ∀𝑠𝑖 ∈ 𝑋𝑖, ∀𝑖 ∈ 𝑁.
展开可得：
𝑤𝑖 = ∑ [∏ 𝜎𝑗(𝑠𝑗)] 𝑢𝑖(𝑠𝑖, 𝑠−𝑖).
𝑠−𝑖∈𝑆−𝑖
𝑗≠𝑖
上述条件断言，如果每个参与者𝑖选择混合策略𝜎𝑖 中的任何伴随正概率的纯策略，则每个参与者得到的收益𝑤𝑖必定相等。接下来，我们还需要满足：
𝑤𝑖 ≥ 𝑢𝑖(𝑠𝑖, 𝜎−𝑖), ∀𝑠𝑖 ∈ 𝑆𝑖\𝑋𝑖, ∀𝑖 ∈ 𝑁.
上式展开，可得
𝑤𝑖 ≥ ∑ [∏ 𝜎𝑗(𝑠𝑗)] 𝑢𝑖(𝑠𝑖, 𝑠−𝑖), ∀𝑠𝑖 ∈ 𝑆𝑖\𝑋𝑖, ∀𝑖 ∈ 𝑁.
𝑠−𝑖∈𝑆−𝑖
𝑗≠𝑖
上述条件确保𝑋𝑖中的纯策略产生的收益不小于𝑆𝑖\𝑋𝑖中的纯策略产生的收益。接下来，我们有：
𝜎𝑖(𝑥𝑖) > 0, ∀𝑥𝑖 ∈ 𝑋𝑖, ∀𝑖 ∈ 𝑁.
上述条件表明参与者𝑖（对于所有𝑖 ∈ 𝑁）混合策略的支撑中的每个纯策略都有正的概率。接下来的一组约束为：
𝜎𝑖(𝑥𝑖) = 0, ∀𝑥𝑖 ∈ 𝑆𝑖\𝑋𝑖, ∀𝑖 ∈ 𝑁.
上述条件断言，对于每个参与者𝑖（对于所有𝑖 ∈ 𝑁），若该策略不在他的混合策略的支撑中，则该纯策略的概率为零。最后，我们需要满足：
∑ 𝜎𝑖(𝑥𝑖) = 1, ∀𝑖 ∈ 𝑁.
𝑥𝑖∈𝑆𝑖
上述条件保证了每个𝜎𝑖都是𝑆𝑖上的一个概率分布。
我们需要找到𝑤1 ，…，𝑤𝑛 以及𝜎1(𝑥1) ∀𝑠1 ∈ 𝑆1 ，𝜎1(𝑥2) ∀𝑠2 ∈
𝑆2，…，𝜎1(𝑥𝑛) ∀𝑠𝑛 ∈ 𝑆𝑛使得以上所有约束条件满足。此时，(𝜎1, … , 𝜎𝑛)是一个纳什均衡，𝑤𝑖是参与者𝑖在该纳什均衡中的期望收益。另一方面，如果不存在满足以上条件的解，那么没有解对应着支撑𝑋1 × 𝑋2 ×
… × 𝑋𝑛。以上所有约束条件涉及的未知数个数为𝑛 + ∑𝑖∈𝑁|𝑆𝑖|，方程个数为𝑛 + 2 ∑𝑖∈𝑁|𝑆𝑖|，其中𝑛对应着𝑤1, … , 𝑤𝑛，而|𝑆𝑖|对应着变量𝜎𝑖(𝑠𝑖)，
𝑠𝑖 ∈ 𝑆𝑖。即使只有 2 个参与者，且每个参与者有 3 个策略，也会有 8 个变量和 14 个方程。如果参与者个数大于 2，那么不仅面对更多的 方程，还必须处理非线性（由于∏𝑗≠𝑖 𝜎𝑗(𝑠𝑗)的存在）。对于两人博弈，这些方程构成了所谓的线性互补问题（linear complementarity problem， LCP）。当参与者为 3 人或 3 人以上时，这些方程构成了所谓的非线 性互补问题（nonlinear complementarity problem，NLCP）。我们在这里 不提供关于这两个问题的更多细节；有兴趣的读者可以参考 Murty[5] 。
7.1.3.2 Lemke-Howson 算法
现在，我们将介绍另一种算法[6] ，该算法与之前需要求解线性规划的算法本质上不同，它是一种组合算法，用于处理离散属性。首先，我们将纳什均衡的求解归约到对称博弈中，因为在一般二人博弈中，求解纳什均衡的算法会更加复杂。接着，我们将描述该算法在对称博弈前提下的情况，因为这种情况下的算法描述更加简明。Savani和 Von Stengel[7] 已经证明，利用 Lemke-Howson 算法求解纳什均衡的最坏情况下的时间复杂度是指数级的。
在考虑对称的二人博弈𝐶 ∈ [0,1]𝑛×𝑛时，其中，非负矩阵𝐶不存在全为零的行。我们的目标是确定在纳什均衡状态下最优响应所对应的最优收益的取值。为此，我们放松了策略分布之和为 1 的限制，并假设最优收益为 1。这样，我们得到了2𝑛个约束条件，即，𝐶𝑧 ≤ 1，其
中𝑧 ≥ 0。这些约束条件所定义的区域是一个凸多面体𝑃（由于非负矩阵𝐶 不存在全为零的行 ）。 我们假设凸多面体𝑃 是非退化的
（nondegenerate），𝑃上的所有顶点都满足上述2𝑛个不等式中恰好有𝑛个取等号。非退化假设是优化领域中的常用假设，因为退化情况出现的概率非常小。即使出现了退化情况，我们也可以通过对矩阵𝐶中的所有元素添加一个极小的随机扰动，以极大概率使得凸多面体𝑃成为非退化的。
在多面体𝑃中，每个点都对应一个混合策略。具体地，对于𝑃的一个顶点𝑧 ∈ 𝑃，如果其包含纯策略𝑖 ∈ 𝑁，那么满足(𝐶𝑧)𝑖 = 1或𝑧𝑖 = 0，我们称该顶点包含纯策略𝑖 ∈ 𝑁。由此得到以下引理：
引理 11 𝑥是对称博弈𝐶的一个对称纳什均衡，如果𝑃上的顶点𝑧 ≠
0，并且顶点𝑧包含所有的纯策略𝑖 ∈ 𝑁成立。其中
𝑥𝑖
𝑧𝑖
∑
=
𝑛
𝑖=1
.
𝑧𝑖
证明：首先，𝑥是良定义的（由于𝑧 ≥ 0且𝑧 ≠ 0）。其次，由于顶
点𝑧包含所有的纯策略，我们由𝑧𝑖 ≥ 0能得到(𝐶𝑧)𝑖 = 1且由(𝐶𝑧)𝑖 = 1
能得到𝑧𝑖 ≥ 0。这意味着玩家 1 在混合策略𝑧支撑中的纯策略是玩家 2
的策略𝑧的最优响应。因此，玩家 1 的混合策略𝑧是玩家 2 的混合策略
𝑧的一个最优响应。由对称性可以推断对称博弈𝐶的一个对称纳什均衡是𝑧。∎
前述已证明，若多面体𝑃的顶点涵盖所有纯策略，则对应纳什均衡。接下来需证明存在此类顶点。我们采用构建有向图的方法来猜测最终纳什均衡的支撑。该有向图中每个顶点的出度和入度至多为 1，因此可进行有向路径遍历。
首先，选定一个策略（以策略 1 为例）。然后考虑所有不含策略
1 的顶点以及包含所有纯策略的顶点的集合𝑉。从集合𝑉中的顶点𝑣0 =
0初始，在顶点集𝑉中逐步构造出路径〈𝑣0, 𝑣1, … 〉。设多面体𝑃非退化，
根据定义，顶点𝑣0有𝑛个相邻顶点，每个顶点与𝑣0仅有一个取等号的约束条件不同。选出不含策略 1 的顶点，即同时不满足(𝐶𝑧)1 = 1和
𝑧1 = 0的点𝑣1。虽然𝑣1不含策略 1，但𝑣1有𝑛个相邻顶点，故𝑣1一定包含某个策略𝑖两次，即(𝐶𝑧)𝑖 = 1且𝑧𝑖 = 0。对这两个条件进行放松，可得到两个顶点，其中一个顶点为𝑣0，另一个顶点为𝑣2，若某个顶点𝑣2包含所有纯策略，则算法停止。由引理 11，此时找到了一个纳什均衡。若不满足，则继续沿着路径寻找，直到找到一个顶点𝑣𝑗包含所有纯策略。
随后，分析 Lemke-Howson 算法是否能找到纳什均衡，即 Lemke- Howson 算法是否会在满足条件的顶点𝑣𝑗处停止。若否，由于多面体
𝑃的顶点数有有限多个，因此唯一可能是路径在某几个顶点处形成有
向环。根据算法描述，每个路径上的顶点至多有一个前序和一个后继。若出现环，只可能回到𝑣0点。然而，由于𝑣0只有一个相邻顶点不含策略 1，这种情况是不可能的。若不出现此情况，由于多面体上的顶点数有限，算法一定在某一时刻停止。此时我们必定找到一个包含所有纯策略的顶点，即能够找到一个纳什均衡。至此，我们证明了 Lemke- Howson 算法必定能够找到纳什均衡。
7.1.3.3 Lipton-Markakis-Mehta 算法
先前提及的两种算法均为精确求解纳什均衡的方法，接下来，我们介绍一种近似算法。
Lipton、Markakis 和 Mehta [8] 在其研究中证明了存在支撑数较小的近似纳什均衡。具体而言，对于给定的𝜀 > 0，对于任意的每个参与者各自拥有𝑛个纯策略的二人博弈，至少存在一个𝜀-近似纳什均衡，其中两人的支撑数仅为𝑂(log 𝑛/𝜀2)。为了说明，我们对混合策略𝑥独立地随机采样𝑘次，形成一个多重集𝑆，然后在𝑆中随机选择一个纯策略得到一个𝑘-经验策略。该经验策略是通过从分布𝑥来进行博弈。 Lipton-Markakis-Mehta 算法指出：只需将所有可能出现的多重集枚举
出来，并将其对应的经验策略应用于博弈问题中进行验证。这种方法 的时间复杂度为𝑛𝑂(log 𝑛/𝜀2)，也被称为准多项式时间（quasi-polynomial time）。与支撑枚举算法类似，该方法亦能获得所有近似纳什均衡的解。
概率法在证明稀疏支撑的近似纳什均衡存在性方面也得到了更多应用。例如，Barman[9] 提出了另一个相关结果。近期，Rubinstein [10] 证明，假设某种较为温和的假设成立，Lipton-Markakis-Mehta 算法的时间复杂度是近乎最优的。