基于决策概率逼近的矩阵对策近似求解方法

何炼坚 冷国俊 蒲春霞

【摘要】本文提出一种面向大规模矩阵对策问题，基于决策概率逼近的可快速收敛到近似最优策略的求解方法.

【关键词】矩阵对策;局中人;策略

【基金项目】本论文由国家自然科学青年基金（51605452）资助.

一、引 言

对一般性的矩阵对策问题，通常使用线性规划法，将原问题转化为等价的线性规划问题，利用单纯形或对偶单纯形法求解.该方法的缺点在于，对大规模的矩阵对策问题，求解线性规划的开销太大.

本文提出一种基于决策概率逼近的矩阵对策策略确定方法.该方法依赖于以下准则：一是矩阵对策双方都会根据期望收益最大（或期望损失最小）原则进行分析，即根据每个决策方案的期望收益（或期望损失）来对方案进行比较，从中选择期望收益最大（或期望损失最小）的方案;二是决策方案选择的概率分布是关于其期望收益的单调上升函数（或关于其期望损失的单调下降函数）.

二、基于决策概率逼近的矩阵对策近似求解方法

矩阵对策问题模型包括以下基本要素：

（1）局中人

以I表示局中人的集合;矩阵对策包括两个局中人，因此，I中元素的个数为2.

（2）策略

可供局中人选择的策略集记为Sz（z=1，2），其元素个数分别记为m和n;矩阵对策的m，n均为有限值.

（3）收益函数

局中人1的任一策略和局中人2的任一策略一起形成的策略组称为一个局势，该局势下两个局中人的收益由收益函数确定.所有局势下局中人2的收益构成一个m×n矩阵R，局中人1的收益构成另一个m×n矩阵-R.不失一般性约定矩阵R满足0≤Rij≤1（i=1，…，m，j=1，…，n）.

考虑某一局中人的任一策略，该策略的期望收益是与对方采取的策略有关的.如果能够有效估计对方可能采取的策略，对提升期望收益是有利的.一种合理的想法是，认为对方从其策略集中选择某一策略的概率是關于该策略的期望收益的单调上升函数，即期望收益越大的策略的选择概率越大，期望收益越小的策略的选择概率越小.另一方面，对方计算其某一策略的期望收益时，必须由我方策略选择的概率分布输入，其同样会认为，我方从策略集中选择某一策略的概率是关于该策略的期望收益的单调上升函数.这样就形成了如下迭代计算：

（1）局中人1

针对局中人1的策略选择概率分布，计算局中人2所有策略的期望收益.

使用最新计算出的局中人2所有策略的期望收益，计算局中人2的策略选择概率分布（计算函数要求是局中人2的期望收益的严格单调上升函数）.

（2）局中人2

针对局中人2的策略选择概率分布，计算局中人1所有策略的期望收益.

使用最新计算出的局中人1所有策略的期望收益，计算局中人1的策略选择概率分布（计算函数要求是局中人1的期望收益的严格单调上升函数）.

只要为局中人1（或局中人2）的策略选择概率分布给出一个初始值（从而可以计算局中人2或局中人1的所有策略的期望收益），就可以驱动上述迭代计算，以（1）或（2）为开始.迭代计算应该在判断局中人1和局中人2的策略选择概率分布都收敛的时候终止.

不失一般性，站在局中人1的立场，为局中人2的策略选择概率分布给出初始值，则迭代计算的具体步骤如下：

（1）设置初值

记局中人2关于其策略集中策略的选择概率向量为n维向量g，设定其初值如下：

g（0）=1n，…，1nT.

上面设置选择概率向量初值时，认为各策略的选择概率均等;如果有更多的信息用于判断各策略的选择概率，也可以设置为其他向量值.不同初值的影响在于收敛的速度可能不同.

（2）计算局中人1的策略选择概率向量

如下计算m维向量f和h：

f=Rg，

h=h（0），∑mi=1F（fi）=0时，[F（f1），…，F（fm）]T∑mi=1F（fi），其他情况，

其中

h（0）=[1m，…，1m]T.

这里R是局中人2的收益矩阵;f表示当局中人2的策略选择概率向量为g时，局中人1各策略的期望收益;h为局中人1的策略选择概率向量，满足：

0≤hi≤1，i=1，…，m，

∑mi=1hi=1.

函数F满足：

F（0）=0，且F（x）关于x严格单调上升.

特别的，对函数F（x）=x，有：

h=h（0），∑mi=1fi=0时，

[f1，…，fm]T∑mi=1fi，其他情况，

f，h的计算反映了局中人1的策略选择概率是关于其策略期望收益的严格单调上升函数.

计算h时，当∑mi=1F（fi）=0时h=h（0），实际上这时只要h满足所有分量值属于[0，1]，且其总和为1就可以（由F的定义，∑mi=1F（fi）=0等价于F（fi）=0（i=1，…，m），即局中人1的任意策略的期望收益效用都为最小值0，这种情况下局中人1无论如何选择策略都无法改善处境，一般简单以均等概率选择，即h=h（0））.

（3）计算局中人2的策略选择概率向量

如下计算n维向量e，q和g：

e=-RTh，

q=0，…，1C，…，0T，满足G（ej）=0的下标共有C（0

其分量值为1C，其中j为分量下标;

满足G（ej）<0的下标共有n-C（0

其分量值为0，其中j为分量下标

1G（e1），…，1G（en）T，其他情况，

g=g（0），∑nj=1G（qj）=0时，

G（q1），…，G（qn）∑nj=1G（qj），其他情况.

这里-R为局中人1的收益矩阵;e表示当局中人1的策略选择概率向量为h时，局中人2各策略的期望收益;g为局中人2的策略选择概率向量，满足：

0≤gj≤1，j=1，…，n，

∑nj=1gj=1，

q为计算g用到的中间向量.

函数G满足：

G（0）=0，且G（x）关于x严格单调上升.

特别的，对函数G（x）=x，有：

g=g（0），∑nj=1ej=0时，

[e1，…，en]T∑nj=1ej，其他情况.

e，q，g的计算反映了局中人2的策略选择概率是关于其策略期望收益的严格单调上升函数.

计算g时，当∑nj=1G（qj）=0时g=g（0），实际上这时只要g满足所有分量值属于区间[0，1]，且其总和为1就可以（由G的定义，∑nj=1G（ej）=0等价于G（ej）=0（j=1，…，n），即局中人2的任意策略的期望收益效用都为0，由于局中人2策略的期望收益属于区间[-1，0]，这表明局中人2无论如何选择策略都能取得最高的期望收益0，一般简单以均等概率选择，即g=g（0））.

完成上述计算后转（2）.（2）执行完后又会转（3）.

上述（2）（3）之间的往复迭代计算到g，h都收敛后结束.此时g和h分别是局中人1和2的近似最优策略.g和h可能是纯策略，也可能是混合策略.对混合策略不能接受（要求完全确定的策略）的情况，可以在可选的所有纯策略中根据期望收益最大原则（或期望损失最小原则）选择一个（假定对方采用混合策略）.

g，h的收敛判断采用如下方法，记录最近2次计算出的g，h值，并如下计算前后相继的g之间的距离，以及前后相继的h之间的距离：

deviation_g=max1≤j≤n（deviation_gj），

deviation_h=max1≤i≤m（deviation_hi），

其中：

deviation_gj=|gj-gprevj|，gprevj=0时，

|（gj-gprevj）/gprevj|，gprevj≠0时，

deviation_hi=|hi-hprevi|，hprevi=0时，

|（hi-hprevi）/hprevi|，hprevi≠0时.

这里gj为当前g的第j个分量值（j=1，…，n），gprevj为上轮迭代得到的g的第j个分量值（j=1，…，n），hi为当前h的第i个分量值（i=1，…，m），hprevi为上轮迭代得到的h的第i个分量值（i=1，…，m）.

设置整数变量L的初值为0，如下在每次迭代中更新L：

L=L+1，当deviation_g

deviation_h

0，其他.

这里MINEPS为预设精度.

如果L值达到预设门限Lmax（Lmax≥1），那么判断g，h均收敛，迭代结束，否则继续迭代.

说明：不同场景中，g，h的收敛速度是不一样的，为了确保计算在可接受的迭代次数内结束，可以设置迭代次數门限，当迭代次数达到该门限时，无论g，h是否满足收敛条件，都结束迭代计算，并以结束迭代时的g和h分别作为局中人1和2的近似最优策略.

三、数值实验

在一轮计算实验中，设置局中人1和2的策略集合的元素个数范围均为[128，1024]，预设精度为MINEPS=10-3.L值预设门限Lmax=5.判断策略选择概率向量g，h的收敛性.遍历局中人1和2的策略集合元素个数组合（共有（1024-128+1）×（1024-128+1）=804609个），同时在[0，1]范围内随机设置收益矩阵的元素，构建矩阵对策问题.按照前边描述的方法迭代计算矩阵对策问题的近似最优策略（其中函数F，G分别设置为F（x）=x，G（x）=x），记录收敛时的迭代次数.

上述计算实验可以持续进行多轮（每次只有收益矩阵不同）.实验的结果如下：

由上表可以看出，针对较大规模的矩阵对策问题，本文提出的基于决策概率逼近的矩阵对策近似求解方法能够在很少的几次迭代（就我们的实验而言是6或7次）后收敛.

四、结束语

本文提出的基于决策概率逼近的矩阵对策近似求解方法，能够快速收敛到大规模矩阵对策问题的近似最优策略，对博弈决策的实际应用具有重要的意义.

【参考文献】

[1]罗杰，B·迈尔森.博弈论：矛盾冲突分析[M].北京：中国经济出版社，2001.