双矩阵博弈的行列式解法探讨
熊义杰
（西安理工大学 经济与管理学院 710054）
摘要
对于双矩阵博弈的求解，流行的书中多只限于画线法、箭头法和严格下策的反复消去法，而这些方法都只适用于解有纯策略纳什均衡双矩阵博弈。对于没有纯策略纳什均衡的双矩阵博弈，如何求得混合策略很多书都只限于2×2的双矩阵博弈，如果矩阵的行列数多于2，用已有的方法就束手无策了。本文笔者基于自己多年《博弈论》的教学经验，提出了一种n×n阶方阵的行列式解法，具有重要的研究参考价值。
关键词：双矩阵博弈 n阶方阵 行列式解法
博弈论也叫对策论，是运筹学研究的一个重要组成部分。
双矩阵博弈流行的术语也叫作完全信息的静态博弈，因为矩阵的每个单元格里有两个元素，所以叫双矩阵博弈更能反映博弈矩阵的数学特征。
对于双矩阵博弈的求解，流行的书中多数都只限于画线法、箭头法和严格下策的反复消去法，而这些方法都只适用于解有纯策略纳什均衡双矩阵博弈。对于没有纯策略纳什均衡的双矩阵博弈，如何求得混合策略很多书都只限于2×2的双矩阵博弈，如果矩阵的行列数多于2，用已有的方法就束手无策了。在这里，笔者基于本人多年《博弈论》课程教学的经验，介绍一种n×n阶方阵的行列式解法，以就教于各位同仁。
1. 矩阵博弈行列式解法的回顾
矩阵博弈博弈论中也叫作二人有限零和博弈，即有两个博弈人，每个博弈人的策略集合中的策略是有限的，两个博弈人赢得的代数和为零。对于所有既约的方阵，要求得两个博弈人的混合策略，都可以使用行列式解法。
所谓既约矩阵，即不存在优超现象的矩阵。优超现象是指这样一种现象，即在一个给定的矩阵中，存在某一行或某一列与另一行或另一列相比要优（大于等于或小于等于）的现象。
【例1】试求解下面的矩阵博弈：
对此矩阵进行观察分析，显然，第4行优超于第1行，第3行优超于第1行和第2行，故可划去第1和第2行，得到：
在A1中，第1列优超于第3列，第2列优超于第4列和第5列，因此划去第3、4、5列，得到：
显然，第1行仍优超于第3行，划去第3行得：
解之，得到：
在存在优超现象的情况下，被保留的策略通常就称作优势策略或优超策略，与优超策略相对应的策略，博弈论中就称之为劣势策略或者也称严格下策策略。划去博弈矩阵中的严格下策，是求解较大的矩阵博弈的一个重要方法，这种方法称之为严格下策消去法。对于任意的一个较大的博弈矩阵，通常都应该先检查是否存在优超现象。如果存在优超的行或列，就可以先运用严格下策消去法。
对于一个既约方阵通常都可采用行列式解法求解，以3×3的矩阵博弈为例。
【例2】试求解博弈 G=(s1,s2;A)，其中：
先求局中人I的混合策略。可先用第1列减第2列，第2列减第3列，得到：
其次，求策略a1的混合比频数。可先划去第1行，计算余下的方阵的行列式的值：1×10－2 ×2＝6；再依次划去第二行、第三行求a2、a3的混合比频数分别为：6和48（行列式的值不计符号），即各个策略的混合比为：1：1：8。
再求局中人II的混合策略。用第1行减第2行，第2行减第3行，得到：
应用类似的方法，可得到三种策略的混合比为：19：7：4。
行列式解法的基本原理并不难理解。以3×3的博弈矩阵为例。由于博弈矩阵为既约矩阵，因此可以肯定与博弈矩阵对应的每一行每一列的混合策略概率均不为0。因此，用行向量（p1,p2,p3）右乘赢得矩阵后可得到3个都等于博弈的值V的方程。这样，采用让方程一等于方程二，方程二等于方程三的方法，可得到两个均等于0的方程。即由
可得到
等式相减后再加上p1+p2+p3=1，于是有：
前两个方程的系数矩阵，也就是行列式解法的第一步。用行列式方法解这个三元一次线性方程组，就得到了行列式解法的第二步。因为，行列式解法的分子需要用向量(0,0,1)T代替求解变量的相应列（分母是系数矩阵的行列式），这就相当于划去了相应的行。
2. 双矩阵博弈的行列式解法
在纯策略均衡条件下，博弈的值也就是均衡局势条件下双方的赢得函数。而在混合策略条件下，双矩阵博弈的值对于不同的局中人来说，则不一定相同，有时候的相等只是一个特例。一般情况下，我们有如下定义：
【定义1】对于用双矩阵形式表示的二人非零和静态博弈，规定A＝（aij）m×n为局中人I的赢得矩阵，其元素由博弈矩阵中的第一个元素构成；规定B＝（bij）m×n为局中人II的赢得矩阵，其元素由博弈矩阵中的第二个元素构成。
令X＝{x | x∈Rm，∑x=1}为局中人I的混合策略集合，Y＝{y | y∈Rn，∑y=1}为局中人II的混合策略集合（Rm和Rn分别表示m维和n维的欧氏空间），设x为m维的行向量，y为n维的列向量，因此，在混合策略（x，y）条件下，局中人I的期望赢得为：
H1（x，y）＝
（1）
局中人II的期望赢得为：
H2（x，y）＝
（2）
如果对于所有的（x，y）∈（X，Y），有：xAy*≤x*Ay* 和 x*By≤x*By* 成立，则局势（x*，y*）就称作双矩阵博弈的混合策略纳什均衡。
根据代数运算法则，上式（1）也可以改写为：
H1（x，y）＝ 
i=1或2或3,…,m （1-a）
这种方式表明，局中人I的期望赢得，可以用局中人II的混合概率把局中人I的某一行加权得到。
同样，根据代数运算法则，上式（2）也可以改写为：
H2（x，y）
（2-a）
这种方式表明，局中人II的期望赢得，可以用局中人I的混合概率把局中人II的某一列加权得到。
因为，这里同样有
。
由上述的推导过程我们不难看出，根据（1-a）式和（2-a）式，由于：H1（x，y）＝∑aijyj， H2（x，y）＝∑bijxi，因此，在m=n的条件下，即赢得矩阵为方阵时，这两个期望值均符合矩阵博弈（即二人有限零和博弈）中行列式解法的特征，因此对于赢得矩阵为方阵的双矩阵博弈，同样可以用行列式解法求解。只是需要特别注意，局中人I的赢得是与局中人II的混合策略联系的，局中人II的赢得是与局中人I的混合策略联系的，也就是说，在求局中人I的混合策略时，需要把局中人II的赢得矩阵按列相减，在求局中人II的混合策略时，需要把局中人I的赢得矩阵按行相减即可。
这种双矩阵博弈的行列式解法，运用混合策略的等值原则也可以得到证明。按照等值原则，对于n×n双矩阵博弈，局中人I混合策略的的选择，就是要使得局中人II的每一列取得相等的收益，由此可得到n个等值的方程式，再加上∑p=1,就是n+1个方程。这样，通过列相减，可得到n-1个都等于0的方程式。这样无疑就是可以使用行列式解法了。而局中人II混合策略的的选择，就是要使得局中人I的每一行取得相等的收益，由此同样可得到n个等值的方程式，再加上∑q=1,就是n+1个方程。这样，通过行相减，可得到n-1个都等于0的方程式。于是也就是可以使用行列式解法了。
【例3】求解下面3×3的双矩阵博弈：
不难看出，该博弈矩阵无纯策略纳什均衡，所以对此3×3的博弈矩阵可采用行列式解法。
将局中人II的赢得矩阵按列相减后得到：
由此，可得到局中人I的三个纯策略的混合比为21：21：21即1：1：1，因此混合概率为1/3,1/3,1/3。
将局中人I的赢得矩阵按行相减后得到：
由此，可得到局中人II的三个纯策略的混合比依然是21：21：21即1：1：1，因此混合概率为1/3,1/3,1/3。
博弈的值分别为：H1=3，H2=3。
这里需要注意的是，在双矩阵博弈中，两个局中人的期望赢得通常并不一定相等，这里的相等只是一种偶然情况。比如，在我们熟悉的警偷博弈中，警察的期望收益是0.8，而小偷的期望收益是0。
下面，给出与博弈的值密切相关的两个定理。
【定理1】对于双矩阵博弈模型，下面的论断等价：
（1）（x*，y*）是纳什均衡；
（2）x*Ay*＝Max.(xAy*)， x*By*＝Max.(x*By)
（3）x*Ay*Em≥Ay*， x*By*En≥x*B，其中，Em是m维的元素均为1的列向量即Em＝（1,1,1,…，1）T，En是n维的元素均为1的行向量即En＝（1,1,1,…，1）。
这一定理的意义很清楚，故证明从略。
【定理2】（x*，y*）是双矩阵博弈的纳什均衡的充分且必要条件是存在两个数（v1*,v2*）使得（x*，y*）和（v1*，v2*）同为下述规划问题的解：
Max. Z＝xAy＋xBy－v1－v2
s.t. Ay≤v1Em
xB≤v2En
xEm＝Eny＝1
x≥0，y≥0
显然，该规划问题在 x*Ay*＝v1*， x*By*＝v2*时，有最大值：
Z＝x*（A＋B）y*－v1*－v2*＝0。
证明从略。
这里的v1*和v2*即分别为局中人I和局中人II的期望赢得值。
该定理揭示了两点：（1）一般情况下，v1*≠v2*；（2）在最优解条件下，Ay*=v1，x*B=v2。这也就证明了我们上述的（1-a）式和（2-a）式的正确性。
不难看出，上述的规划问题属于一个二次规划问题。二次规划即目标函数为自变量X的二次函数约束条件全部为线性函数的规划问题。二次规划是非线性规划中比较简单的一类，比较容易求解。
定理2的提出就为利用计算机求解混合博弈问题奠定了基础。
参考文献
1. 朱·弗登博格，让·梯若尔著；黄涛，郭凯，王一鸣 译；姚洋 校 《博弈论》 ，北京：中国人民大学出版社，2015年5月第1版
2. 于维生 朴正爱 编著：《博弈论及其在经济管理中的应用》，清华大学出版社，2005年1月第1版
3. 熊义杰 编著：《现代博弈论基础》，国防工业出版社，2010年1月第1版