运筹说 第132期 | 矩阵对策的基本理论
视频课程已上线！！!
欢迎大家关注同名抖音和哔哩哔哩账号！
上一期我们了解了对策论的基本概念，包含对策行为和对策论、对策现象的三要素、对策问题举例以及对策的分类。
接下来小编将为大家介绍矩阵对策的基本理论，包括矩阵对策的纯策略、矩阵对策的混合策略和矩阵对策的基本定理。
01
矩阵对策的纯策略
矩阵对策即为二人有限零和对策。
“二人”是指参加对策的局中人有两个；“有限”是指每个局中人的策略集均为有限集；“零和”是指有任一局势下，两个局中人的赢得之和总等于零，即一个局中人的所得值恰好等于另一局中人的所失值，双方的利益是完全对抗的。
“齐王赛马”就是一个典型的矩阵对策的例子。该例子中，参加对策的局中人为齐王、田忌两个人；双方都有上、中、下三个等级的马，表示齐王和田忌的策略集均为有限集，即均有6个策略；其中负者要给胜者千金，满足一个局中人的所得值恰好等于另一局中人的所失值，即在任一局势下，两个局中人的赢得之和总等于零。
矩阵对策中，完全信息博弈指的是各参与者（局中人）对其他参与者（局中人）的特征、策略集、赢得函数（支付函数）都了解，据此选择自己的博弈策略。不完全信息博弈指的是至少有一个参与者（局中人）不知道其他参与者（局中人）的赢得函数（支付函数）。在完全信息博弈情况下，如果在每个给定信息下，只能选择一种特定策略，这个策略为“纯策略”；如果在每个给定信息下只能以某种概率选择不同策略，称为“混合策略”。
一般地，用Ⅰ和Ⅱ分别表示两个局中人，设局中人Ⅰ有m个纯策略α1,…,αm，策略集S1={α1,…,αm}；局中人Ⅱ有n个纯策略β1,…,βn，策略集S2={β1,…,βn}。当局中人Ⅰ选定纯策略αi和局中人Ⅱ选定纯策略βj后，就形成了一个纯局势(αi,βj)，这样的纯局势共有m×n个。对任一纯局势(αi,βj)，记局中人Ⅰ的赢得值为aij，其中
A为局中人Ⅰ的赢得矩阵（局中人Ⅱ的支付矩阵）。由于对策为零和的，故局中人Ⅱ的赢得矩阵就是-A。
当局中人Ⅰ,Ⅱ的策略集S1，S2及局中人Ⅰ的赢得矩阵A确定后，一个矩阵对策也就给定了，记为G={S1,S2;A}。在“齐王赛马”的例子中，齐王的赢得矩阵为：
已知矩阵模型，局中人应如何选择对自己最有利的纯策略以取得最大的赢得（或最少损失）。下面用一个例子来分析各局中人应如何选择最有利策略。
例题展示
例5 设有一矩阵对策G={S1,S2;A}，其中
由A可看出，局中人Ⅰ的最大赢得是9，要想得到这个赢得，他就得选择纯策略。由于假定局中人Ⅱ也是理智的竞争者，他考虑到局中人Ⅰ打算出α3的心理，便准备选择β3，使局中人Ⅰ不但得不到9，反而失掉10。局中人Ⅰ当然也会猜到局中人Ⅱ的这种心理，故转而出α4来对付，使局中人Ⅱ得不到10，反而失掉6……所以，如果双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己所得最少这一点，就应该从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据，这就是所谓“理智行为”，也是对策双方实际上可以接受并采取的一种稳妥的方法。
在例5中，局中人Ⅰ在各纯策略下可能得到的最少赢得分别为：-8，2，-10，-3，其中最好的结果是2。因此，无论局中人Ⅰ选择什么样的纯策略，局中人只要以α2参加对策，就能保证他的收入不会少于2，而出其他任何纯策略，都有可能使局中人Ⅰ的收入少于2，甚至输给对方。同理，对局中人Ⅱ来说，各纯策略可能带来的最不利的结果是：9，2，6，其中最好的也是2，即局中人Ⅱ只要选择纯策略β2，无论对方采取什么纯策略，他的所失值都不会超过2，而选择任何其他的纯策略都有可能使自己的所失超过2。
上述分析表明，局中人Ⅰ和Ⅱ的“理智行为”分别是选择纯策略α2和β2，这时，局中人Ⅰ的赢得值和局中人Ⅰ的所失值的绝对值相等，局中人Ⅰ得到了其预期的最少赢得2，而局中人Ⅱ也不会给局中人Ⅰ带来比2更多的所得，相互的竞争使对策出现了一个平衡局势(α2,β2),这个局势就是双方均可接受的，且对双方来说都是一个最稳妥的结果。因此，α2和β2应分别为局中人Ⅰ和Ⅱ的最优纯策略。
定义1
设G={S1,S2;A}为一矩阵对策，其中S1={α1,…,αm}，S2={β1,…,βn}，A=(aij)m×n。若
成立，记其值为VG，则称VG为对策的值，使上式成立的纯局势(αi*,βj*)为G在纯策略意义下的解（或平衡局势），αi*和βj*分别为局中人Ⅰ和Ⅱ的最优纯策略。
从例5还可看出，矩阵A中平衡局势(α2,β2)对应的元素a22既是其所在行的最小元素，又是其所在列的最大元素，即有：ai2≤a22≤a2j，i=1,2,3,4，j=1,2,3，将这一事实推广到一般矩阵对策可得以下定理。
定理推出
定理 1
矩阵对策G={S1,S2;A}在纯策略意义下有解的充要条件是：存在纯局势(αi*,βj*)，使得对任意i和j有：aij*≤ai*j*≤ai*j。
在该定理中，
是通过先从列中取最大值然后再取所有最大值中的最小值得到的。在j*列中，该列aij*的值都小于等于ai*j*。
是通过先从行中取最小值然后再取所有最小值中的最大值得到的。在i*列中，该行的值ai*j*都小于等于ai*j。
元素ai*j*为矩阵A的鞍点。鞍点是零和博弈中一个策略组合点，也是双方均无调整策略动机的均衡点，其特征为该元素在矩阵的第i*行是最小值，同时在第j*列是最大值。在该点上，局中人Ⅰ的最大赢得等于局中人Ⅱ的最小损失。在矩阵对策中，矩阵A的鞍点也称为对策的鞍点。
当局中人Ⅰ选择了纯策略αi*后，局中人Ⅱ为了使其所失最少，只能选择纯策略βj*，否则就可能失得更多；反之，当局中人Ⅱ选择了纯策略βj*后，局中人Ⅰ为了达到最大的赢得也只能选择纯策略αi*，否则就会赢得更少，双方的竞争在局势（αi*,βj*）下达到了一个平衡状态。
例题展示
例6 设有一矩阵对策G={S1,S2;A}，其中
其中
故(α1,β2)(α1,β4)(α3,β2)(α3,β4)都是对策的解，且VG=8。一般对策的解可以是不唯一的，当解不唯一时，解之间的关系具有下面两条性质。
性质
性质1（无差别性）若(ai1,βj1)和(ai2,βj2)是对策G的两个解，则ai1j1=ai2j2。
性质2（可交换性）若(ai1,βj1)和(ai2,βj2)是对策G的两个解，则(ai1,βj2)和(ai2,βj1)是对策G的两个解。
这两条性质表明：矩阵对策的值是唯一的，即当一个局中人选择了最优纯策略后，他的赢得值不依赖于对方的纯策略。
例题展示
例7 某单位采购员在秋天要决定冬季取暖用煤的储量问题。已知在正常的冬季气温条件下要消耗15吨煤，在较暖和较冷的气温条件下要消耗10吨和20吨。假定冬季时的煤价随天起寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为100元、150元和200元，又设秋季时煤价为每吨100元。在没有关于冬季准确的气象预报的条件下，秋季储煤多少吨能使单位的支出最少？
分析：这一储量问题可以看作一个对策问题。把采购员看作局中人Ⅰ，他有三个策略：在秋天时买煤10吨、15吨与20吨，分别记作α1、α2、α3。把大自然看作局中人Ⅱ，它有三个策略：冬季时出现较暖的、正常的与较冷的气候，分别记作β1、β2、β3。此处可把大自然当做理智的局中人来处理。把该单位冬季取暖用煤实际费用（即秋季购煤时的费用与冬季不够时再补够的费用总和）作为局中人Ⅰ的赢得，得矩阵：
故对策的解为（α3,β3），即秋季储煤20吨比较合理。
02
矩阵对策的混合策略
已知，在一个矩阵对策G={S1,S2;A}中，局中人Ⅰ能保证的至少赢得是
局中人Ⅱ能保证的至多所失是
一般，局中人Ⅰ的赢得不会多于局中人Ⅱ的所失，故总有
v1≤v2
当v1=v2时，矩阵对策在纯策略意义下有解。然而，实际中出现的更多情形是v1＜v2，这时，根据定义1，对策不存在纯策略意义下的解。例如，对赢得矩阵为
的对策来说：
于是，当双方各根据从最不利情形中选择最有利的原则选择纯策略时，应分别选择α2和β1，此时局中人Ⅰ的赢得为5，比其预期的至多赢得v1=4还多。原因在于局中人Ⅱ选择了β1，使局中人Ⅰ得到了本不该得的赢得，故β1对局中人Ⅱ来说不是最优的，因此他会考虑出β2。局中人Ⅰ会采取相应的办法，改出α1，以使赢得为6，而局中人Ⅱ又可能仍取策略β1来对付局中人Ⅰ的策略α1，这样，局中人Ⅰ出α1和α2的可能性及局中人Ⅱ出β1和β2的可能性都不能排除，对两个局中人来说，不存在一个双方都可以接受的平衡局势，即不存在纯策略意义下的解。
在这种情况下，一个比较自然且合乎实际的想法是：既然局中人没有最优策略可出，是否可以给出一个选择不同策略的概率分布。如局中人Ⅰ可制定这样一种策略：分别以概率1/4和3/4选取纯策略α1和α2，称这种策略为一个混合策略。同样，局中人Ⅱ也可以制定这样一种混合策略：分别以概率1/2 , 1/2选取纯策略β1，β2。
接下来介绍矩阵对策混合策略及其在混合策略意义下解的定义。
定义2
设有矩阵对策G={S1,S2;A}，其中
则分别称S1*和S2*为局中人Ⅰ和Ⅱ的混合策略集（或策略集）；对x∈S1*和 y∈S2*，称x和y为混合策略（或策略），(x,y)为混合局势（或局势）。局中人Ⅰ的赢得函数记成
称G*={S1*,S2*;E}为对策G的混合补充。
已知对策模型，局中人应如何选择对自己最有利的混合策略以取得最大的赢得（或最少损失）？设两局中人仍如前所述进行理智决策，当局中人Ⅰ选择混合策略时，他的预期所得（最不利的情形）是
，因此，局中人Ⅰ应选取x∈S1*,使得
同理，局中人Ⅱ可保证的所失的期望值至多是
显然，有v1≤v2。
定义3
设矩阵对策G={S1,S2;A}的混合扩充为G*={S1*,S2*;E}。如果
记其值为VG，则称VG为对策G的值，称使上式成立的混合局势(x*,y*)为G在混合策略意义下的解（或平衡局势），称x*和y*分别为局中人Ⅰ和Ⅱ的最优混合策略。
和定理1类似，可以给出矩阵对策G在混合策略意义下解存在的鞍点型充要条件。
定理推出
定理 2
矩阵对策G在混合策略意义下有解的充要条件是：存在x*∈S1*，y*∈S2*，使得对任意x∈S1*和y∈S2*，有
例题展示
例8 考虑矩阵对策G={S1,S2;A}，其中
第一步：判断G是否存在纯策略意义下的解，由前面讨论已知G在纯策略意义下无解。
第二步：采用混合策略来求解。设x=(x1,x2)和y=(y1,y2)分别为局中人Ⅰ和Ⅱ的混合策略，则
局中人Ⅰ的赢得的期望
将x2=1-x1,y2=1-y1代入，
将其进行整理，
取
，
，则
，
，即有
根据定理2可得，该矩阵在混合策略意义下有解，
分别是局中人Ⅰ和Ⅱ的最优混合策略，对策的值局中人Ⅰ的赢得的期望值为VG=9/2。
03
矩阵对策的基本定理
这部分将讨论矩阵对策解的存在性及其性质，给出矩阵对策在混合策略意义下解的存在性的构造性证明，同时给出了求解矩阵对策的基本方法―线性规划方法。
先给出两个记号：
局中人Ⅰ取纯策略αi时，记其相应的赢得函数为E(i,y)，则有
局中人Ⅱ取纯策略βj时，记其相应的赢得函数为E(x,j)，则有
因此有
和
定理推出
定理 3
设x*∈S1*，y*∈S2*，则(x*,y*)为对策G的解的充要条件是：对任意i=1,…,m和j=1,…,n，有
定理3的另一等价形式是定理4。
定理 4
设x*∈S1*，y*∈S2*，则(x*,y*)为对策G的解的充要条件是：存在数v，使得x*和y*分别是下面两个不等式组的解，且v=VG。
证明：用线性规划法求混合策略解的方法（以下为A的赢得矩阵）：
根据矩阵博弈中局中人A的策略是对局中人B策略的最优反应，A是在最不利情况下找最有利的结果，局中人A的期望收益va可表示为：
用线性规划法求混合策略解的方法：
若令
则A的期望收益可表达成线性规划的形式：
令
，已知：
同理，当B采用混合策略，A分别用纯策略α1,…,αn时，B的期望收益为：
对B来说，损失越大越不利，B是从最不利情况下找最有利结果，在局中人B的期望损失vb可表示为：
若令
则B的期望损失可表达成线性规划的形式（最大损失找最小）：
令
，已知
策略A和B是互为对偶的线性规划，因此可以通过线性规划法求解混合策略解。
定理 5
对任一矩阵对策G={S1,S2;A}，一定存在混合策略意义下的解。
证明：由定理3，只要证明存在x*∈S1*，y*∈S2*，使得式E(i,y*)≤E(x*,y*)≤E(x*,j)成立
和
易验证，问题（P）和（D）是互为对偶的线性规划，而且
是问题（P）的一个可行解；
是问题（D）的一个可行解。
由线性规划对偶定理可知，问题（P）和（D）分别存在最优解(x*,w*)和(y*,v*)，且w*=v*。即存在x*∈S1*，y*∈S2* 和数v*，使得对任意i=1,…,m和j=1,…,n，有
或
又由
得到v*=E(x*,y*)，由E(i,y*)≤v*≤E(x*,j)可知E(i,y*)≤E(x*,y*)≤E(x*,j)成立，证毕。
定理 6
设(x*,y*)是矩阵对策G的解，v=VG则根据互补松弛性，有
（1）若xi*＞0，则
（2）若yj*＞0，则
（3）若
，则xi*=0
（4）若
，则yj*=0
证明：由
有
又因为
所以，当xi*＞0时，必有
；
当
时，必有xi*=0，(1)，(3)得证。同理可证(2)，(4)，证毕。
定理 7
设两个矩阵对策G1={S1,S2;A1}，G2={S1,S2;A2}，其中A1=(aij)，A2=(aij+L)，L为任意常数，则
(1)VG2=VG1+L
(2)T(G1)=T(G2)
定理 8
设两个矩阵对策G1={S1,S2;A}，G2={S1,S2;αA}，其中α>0，为任意常数，则
(1)VG2=αVG1
(2)T(G1)=T(G2)
定理 9
设G={S1,S2;A}为一矩阵对策，且A=-AT为斜对称矩阵（亦称这种对策为对称对策），则
(1)VG=0
(2)T1(G)=T2(G)
其中，T1(G)和T2(G)分别为局中人Ⅰ和局中人Ⅱ的最优策略集。
以上就是矩阵对策的基本理论的全部内容了，通过本期学习，大家是否对对策论有了进一步的认识呢？下一期小编将带大家学习矩阵对策的解法，敬请关注！
作者 | 唐京茹 李超凡
责编 | 唐京茹
审核 | 徐小峰
YUNCHOUSHUO！
·知乎｜运筹说·
·bilibili｜运筹说·
·CSDN｜运筹说·
·抖音｜运筹说·
往期推荐
运筹说 第130期 | 对策论引言
运筹说 第129期 | 对策论的奠基人——约翰·冯·诺依曼
2024全球高被引科学家名单公布，经管类相关领域...
运筹说 第128期｜论文速读之多级库存优化工业...
2024年ABS分区更新，聚焦管理科学领域新动态
运筹说 第127期 | 存储论相关模型代码实现
运筹说 第126期 | 存储论经典例题讲解—随机存储模型
运筹说 第125期 | 存储论经典例题讲解1
运筹说 第124期 | 存储论应用研究的一些问题
运筹说 第123期 | 其他随机型存储模型
运筹说 第122期 | 单周期的随机型存储模型
运筹说 第121期 | “一分钱”难倒最年轻...
运筹说 第120期 | 确定型存储模型
运筹说 第119期 | 存储问题及其基本概念
运筹说 第118期 | 存储论奠基人...
2023年JCR影响因子正式发布，点击查看信息...
2023年JCR影响因子正式发布，点击查看工程...
2023年JCR影响因子正式发布，点击查看商业...
2023年JCR影响因子正式发布，点击查看管理...
2023年JCR影响因子正式发布，点击查看能源...
2023年JCR影响因子正式发布，点击查看...
运筹说 第117期 | 论文速读之基于M/M/c...
运筹说 第116期 | 算法介绍之排队论
运筹说 第115期 | 排队论经典例题讲解
运筹说 第114期 | 其他排队模型简介
运筹说 第113期 | M/M/s混合制排队模型
运筹说 第112期 | M/M/s等待制排队模型
运筹说 第111期 | 从“不可能”中找“可能”...
学术前沿 | 爱思唯尔2023年中国高被引...
运筹说 第110期｜生灭过程和Poisson过程
运筹说 第109期 | 排队论基本概念
运筹说 第108期 | 新春送祝福，运筹说全体小编...
运筹说 第107期 | 排队论创始人——
运筹说 第106期｜论文速读之考虑顾客选择...
运筹说 第105期 | 算法介绍之非线性规划
运筹说 第104期 | 2023全球高被引科学家名单...
运筹说 第103期 | 非线性规划经典例题讲解
运筹说 第102期 | 非线性规划—制约函数法
运筹说 第101期｜最新：2022全球前2％顶尖科...
运筹说 第100期 | 库恩塔克条件（KKT条件）的...
运筹说 第99期 | 非线性规划—最优性条件
运筹说 第98期｜无约束极值问题
运筹说 第97期|非线性规划-一维搜索
运筹说 第96期 | 非线性规划基本概念
运筹说 第95期｜非线性规划奠基人——库恩与塔克
运筹说 第94期｜论文速读之基于关键路...
运筹说 第93期 | 算法介绍之网络计划技术
运筹说 第92期｜爱思维尔"高被引学者"
运筹说 第91期 | 网络计划经典例题讲解
运筹说 第90期 | 网络计划-图解评审法
运筹说 第89期 | 网络计划-网络计划的优化
运筹说 第88期 | 新春送祝福，运筹说全体...
运筹说 第87期 | 网络计划-时间参数的计算
运筹说 第86期｜运筹说2022年度总结
运筹说 第85期 | 只有初中学历的数学家
运筹说 第84期 | 网络计划-网络图的基本概念
运筹说 第83期 | 我国网络计划奠基人——华罗庚
运筹说 第82期 | 算法介绍之图与网络分析（二）
运筹说 第81期 | 图与网络分析经典例题讲解
运筹说 第80期｜最小费用最大流问题
运筹说 第79期｜论文速读之双目标岛屿旅行商...
运筹说 第78期 | 最大流问题
运筹说 第77期 | 算法介绍之图与网络分析（一）
运筹说 第76期 | 最短路问题
运筹说 第75期 | 数学家欧拉也玩跨界
运筹说 第74期 | 图与网络分析基本知识梳理
运筹说 第73期 | 图论创始人“数学之王”——欧拉
运筹说 第72期 | 算法介绍之动态规划（二）
运筹说 第71期｜论文速读之时间背包问题
运筹说 第70期 | 算法介绍之动态规划（一）
运筹说 第69期 | 动态规划经典例题讲解
运筹说 第68期｜2022年最新影响因子正式发布...
运筹说 第67期 | 动态规划模型的建立与求解
运筹说 第66期 | 贝尔曼也有“演讲恐惧症”？
运筹说 第65期 | 动态规划的基本概念和基本原理
运筹说 第64期丨动态规划奠基人——理查...
运筹说 第63期｜论文速读之无人机车辆路径问题
运筹说 第62期 | 算法介绍之整数规划（二）
运筹说 第61期 | 整数规划经典例题讲解
运筹说 第60期 | 0-1型整数规划和指派问题
运筹说 第59期 | 不喜欢数学的数学家？
运筹说 第58期 | 算法介绍之整数规划 （一）
运筹说 第57期 | 整数规划的分支定界法
运筹说 第56期 | 整数规划的数学模型&割平面法
运筹说 第55期丨整数规划先驱...
运筹说 第54期 | 目标规划的灵敏度分析
运筹说 第53期 | 智能优化算法介绍之粒子群算法
运筹说 第52期 | 论文速读之搜救资源...
运筹说 第51期 | 目标规划经典例题讲解
运筹说 第50期 | 图解法与单纯形法求解目标规划
运筹说 第49期 | 走近“数理经济学之父—帕累托”
运筹说 第48期 | 新春送祝福，运筹说全...
运筹说 第47期 | 算法介绍之目标规划
运筹说 第46期 | 目标规划-数学模型
运筹说 第45期 | 多目标规划发展及其提出者...
运筹说 第44期 | 2021感谢有你！
运筹说 第43期 | 运输问题硬核知识点梳理—运...
运筹说 第42期 | 算法介绍之运输问题（二）
运筹说 第41期 | 运输问题硬核知识点梳理—表...
运筹说 第40期 | 论文速读之囚犯运输问题
运筹说 第39期 | 运输问题经典例题讲解
运筹说 第38期 | “迟到”的毕业证-趣闻轶事（三）
运筹说 第37期 | 快看经管类2021年全球高被...
运筹说 第36期 | 算法介绍之运输问题
运筹说 第35期 | 运输问题硬核知识点梳理...
运筹说 第34期 | 运输问题发展应用及领域风云人物
运筹说 第33期 | 参数线性规划
运筹说 第32期 | 对偶理论与灵敏度分析—灵...
运筹说 第31期 | 对偶理论与灵敏度分析—对偶...
运筹说 第30期 | 算法介绍之对偶单纯形法
运筹说 第29期 | 对偶理论与灵敏度分析—影子价格
运筹说 第28期 | 论文速读之环境经济学中...
运筹说 第27期 | 重磅统计！2021中国高校...
运筹说 第26期 | 2022泰晤士世界大学...
运筹说 第25期 | 对偶理论经典例题讲解
运筹说 第24期 | 博弈论里有只“大象”？-趣...
运筹说 第23期 | 对偶理论与灵敏度分析—对偶...
运筹说 第22期 | 对偶理论及其提出者—约...
运筹说 第21期 | 算法介绍之列生成算法
运筹说 第20期 | 算法介绍之单纯形法
运筹说 第19期 | 线性规划经典例题讲解
运筹说 第18期 | 快报-ABS最新版出炉，快看...
运筹说 第17期 | 论文速读之线性规划
运筹说 第16期 | 线性规划硬核知识点...
运筹说 第15期 | 趣闻轶事（一）
运筹说 第14期 | 算法介绍之图解法
运筹说 第13期 | 线性规划硬核知识点梳理—数...
运筹说 第12期 | 佳片推荐之 “心灵捕手”
运筹说 第11期 | 线性规划之父 — George ...
运筹说 第10期 | 敲黑板！学习运筹学，怎么能...
运筹说 第9期 | 运筹会议，学术盛宴！群英...
运筹说 第8期 | 巨额奖金？大厂offer？都在这...
运筹说 第7期 | 重磅！学习运筹学不可不看...
运筹说 第6期 | 运筹学自媒体的“百家争鸣”
运筹说 第5期 | 运筹学江湖的形成
运筹说 第4期 | 掌握运筹学软件，走遍天下...
运筹说 第3期 | 学好运筹学，找个工作还不简...
运筹说 第2期 | 运筹学知识学习路线图
运筹说 第1期 | 知识体系