2.3 二人策略型博弈纳什均衡的计算方法
本节给出比较常见的双矩阵博弈的纳什均衡的计算方法。在本书涉及的范围内，这些计算方法已经够用。当遇到比较复杂的多人博弈问题时，它们的求解是非常复杂的，而且往往只能用计算机程序计算近似解。有兴趣的读者可以参阅有关“算法博弈论”（algorithmic game theory）的书籍。[1]
2.3.1 2×2双矩阵博弈
最简单的二人策略型博弈就是2×2双矩阵博弈，它的形式如图2-12所示。
容易证明，如果它不存在纯策略均衡，那么它有唯一的混合策略均衡〈（p*，1-p*），（q*，1-q*）〉，其中：
图2-12 2×2双矩阵博弈
如果用向量矩阵记号：
x*=（p*，1-p*），y*=（q*，1-q*）
那么相应的期望赢得为：
π1=x*A（y*）T，π2=x*B（y*）T，其中（y*）T是把行向量y*转置所得的列向量。
我们把这个结果的证明留给读者作为练习。
【例2-9】考虑王老吉（W）与加多宝（J）的产量竞争。假设按市场需求，比较合适的做法是一家选择高产量（H，h）另一家选择低（L，l）产量，问题是这时高产量的利润较高；而当两家都选择高产量时，因为供过于求，市场出清价格会偏低。因此这两家的产量竞争可以用下面的双矩阵定性地表示，如图2-13所示。
图2-13 两家产量竞争的双矩阵
【分析】容易找出两个纯策略均衡：〈H，l〉，〈L，h〉。注意按上面的公式还可以算出一个对称的混合策略均衡：〈（1/3，2/3），（1/3，2/3）〉，即各自随机地以1/3的概率生产高产量，以2/3的概率生产低产量，期望赢得是（7/3，7/3）。把混合策略均衡与纯策略均衡对比，似乎应该更能被两家厂商所同时接受。
练习题1-1（续） 现在我们可以计算练习题1-1的纳什均衡。
【分析】我们已知它的策略型如图2-14所示
图2-14 策略型博弈
容易明白，局中人2的任何纯策略不支持纳什均衡，而当局中人2采用完全混合策略[2]时，局中人1的纯策略开牌-开牌劣于加注-开牌；开牌-加注劣于加注-加注。这个博弈于是可以简化为图2-15。
图2-15 简化后的博弈
使用2.3.1小节中讲到的公式，不难算出原博弈唯一的混合策略纳什均衡〈（0，0，2/3，1/3），（2/3，1/3）〉。两个局中人的期望赢得分别是
π1=
=1/3，π2=-1/3。
2.3.2 2×n，m×2，m×m双矩阵博弈的解法
给出一个有限二人策略型博弈去计算它的至少一个纳什均衡，这个问题博弈论中已经完满解决。计算过程步骤如下：
（1）先逐步删除相对劣策略简化策略型。
（2）用互为最优回应的原则寻找（简化后的策略型博弈）的纯策略均衡。
（3）要计算混合策略均衡，如果（简化后的）策略型是2×n或m×2双矩阵（m，n＞2），那么可以用作图法计算混合策略均衡。可参考【例2-10】。
【例2-10】求下面2×4双矩阵博弈的全部纳什均衡（见图2-16）。
图2-16 2×4双矩阵博弈
这是个2×4双矩阵博弈。容易发现三个纯策略均衡：〈s1，t1〉，〈s1，t3〉，〈s2，t4〉。
现在要计算所有的混合策略均衡。设想局中人1使用混合策略（p，1-p）。当局中人2使用每个纯策略时，她得到的期望赢得是p的线性函数。比如，当她使用纯策略t1时，她的期望赢得是5p+0（1-p）=5p；在博弈双矩阵下方的图中对应于线段t1。类似地，我们可以做出线段t2，t3，t4。每当局中人1选定一个p值，局中人2的最优回应在所有上述线段的上包络折线上（见图2-17加粗的折线）。
图2-17
因为要寻找的是混合策略均衡，即局中人2也使用混合策略均衡，所以只要注意上包络线的折点处。于是，只需检查局中人2混合t4与t3时是否会产生混合策略均衡，以及她混合t2与t3时是否会产生混合策略均衡。
当局中人1混合s1与s2而局中人2混合t2与t4时，我们考虑相应的2×2双矩阵，如图2-18所示。
图2-18 2×2双矩阵
应用2.3.1小节中讲到的公式，容易算得混合策略均衡〈（1/16，15/16），（1/2，1/2）〉，相当于原2×4双矩阵博弈的混合均衡〈（1/16，15/16），（0，1/2，0，1/2）〉。
类似地，当局中人1混合s1与s2而局中人2混合t2与t3时，相当于原2×4双矩阵博弈的混合均衡〈（1/4，3/4），（0，0，1，0）〉。注意，这时局中人2实际使用纯策略t3。
（4）如果化简后的双矩阵是m×m的，可以尝试用类似于“石头—布—剪刀”的求解方法，写出m个包含m个未知数的线性方程，然后求方程组的解。
（5）对于一般的m×n双矩阵博弈，其求解可以化为一个非线性规划问题。我们将在本章附录中简介劳埃德·沙普利（Lloyd Shapley）提出的算法。
2.3.3 非有限博弈的情况
我们知道纳什均衡存在性定理对有限策略型博弈成立，这是因为证明中需要用到策略集合的紧致性。当紧致性不再存在时，纳什均衡的存在性就可能不成立。
【例2-11】两个局中人1和2同时各自说出一个自然数，说出较大的数者赢得对手100美元，如果两个人说出的数相同，结果是和局，这时双方赢得均为0。
【分析】容易明白不存在纯策略均衡：当双方都使用纯策略时，总有一方说出的数是不大于对手的，而这个纯策略就不是他的最优回应。
现在往证也不存在混合策略均衡。用反证法，假设有混合策略均衡并且局中人1的期望赢得非负，又假设局中人1使用的是混合策略（x1，…，xn，…），其中xn是他随机地说出自然数n的概率。因为有
，于是存在充分大的自然数N使得
。这时局中人2如果把原来的混合策略改变为纯策略“说出自然数N”，她的期望赢得就变成
所以，原来局中人2的策略不是对局中人1的策略的最优回应。矛盾说明不可能存在混合策略纳什均衡。
[1] 比如，蒂姆·拉夫加登（Tim Roughgarden，2014）。
[2] 一个混合策略称为完全混合策略，如果它以正概率使用每一个纯策略。