对策论
由“齐王赛马”引入
1.对策论的基本概念
三个基本要素；
1.局中人：参与对抗的各方；
2.策略集：局中人选择对付其它局中人的行动方案称为策略。
某局中人的所有可能策略全体称为策略集；
3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人 的对策结果（量化）称为该局势对策的益损值）
“齐王赛马”齐王在各局势中的益损值表（单位：千金）
其中：
齐王的策略集: S1={1,2,3,4,5,6}
田忌的策略集：S1={1,2,3,4,5,6}
下列矩阵称齐王的赢得矩阵：
3 1 1 1 -1 1
1 3 1 1 1 -1
A= 1 -1 3 1 1 1
-1 1 1 3 1 1
1 1 1 -1 3 1
1 1 -1 1 1 3
1.基本概念（续）
二人有限零和对策：（又称矩阵策略）
局中人为2；
每局中人的策略集中策略权目有限；
每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。
1.基本概念（续）
记矩阵对策为:
G = {S1, S2, A}
甲的策略集 甲的赢得矩阵
乙的策略集
“齐王赛马”即是一个矩阵策略.
2.矩阵对策的最优纯策略
在甲方赢得矩阵中：
A=[aij]m*n
i行代表甲方策略 i=1,2…m
J列代表乙方策略 j=1,2…n
aij代表甲方取策略i,乙方取策略j,这一局势下甲方的益损值，此时乙方的益损值为-aij（零和性质）。
在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。
2.矩阵对策的最优纯策略(续)
例：有交易双方公司甲和乙，甲有三个策略1，2，3；乙有四个策略1，2，3，4，根据获利情况建立甲方的益损值 赢得矩阵。
-3 0 -2 0
A= 2 3 0 1
-2 -4 -1 3
问：甲公司应采取什么策略比较适合？
甲：
采取1至少得益–3(损失 3）
2 0
3 -4(损失 4）
乙：
采取1甲最多得益2
（乙最少得益-2）
2 3（乙得益-3）
3 0（乙得益 0）
4 3（乙得益-3）
取大则取2
max min aij= 0
i j
取小则取3
min max aij= 0
j i
甲采取策略2 不管乙采取如何策略，都至少得益。
乙采取策略3 不管甲采取如何策略，
都至少可以得益。（最多损失0）
分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。
存在前提：
max min aij = min max aij = v
i j j i
又称（ 2 ，3 ）为对策G={s1,s2,A}
的鞍点。值V为G的值。
3.矩阵对策的混合策略
设矩阵对策 G ={S1,S2,A}
当 max min aij min max aij
i j j i
时，不存在最优纯策略 求解混合策略。
3.矩阵对策的混合策略
例：设一个赢得矩阵如下:
min
5 9 5
A = max 6 策略2
8 6 6 i
max 8 9
min 8 策略1
j
矛盾：甲取2 ，乙取时1，甲实际赢得8比预期多2（乙就少2）这对乙讲是不满意的，考虑这一点，乙采取策略2，若甲分析到这一点，取策略1，则赢得更多为9…
此时，甲，乙方没有一个双方均可接受的平衡局势。
一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-----即混合策略
求解方法：线性规划法
（其他方法：图解法，迭代法，线性方程法等略）
例： 5 9 设在最坏的情况下，
A= 甲赢得的平均值为V.
8 6 （未知）
STEP 1
1)设甲使用策略1的概率为X1′ X1′+X2′=1
设甲使用策略2的概率为X2′ X1′,X2′0
2)无论乙取何策略，甲的平均赢得应不少于V:
对乙取1：5X1’+ 8X2’V
对乙取2：9X1’+ 6X2’V
注意 V>0,因为A各元素为正。
STEP 2
作变换： X1= X1’/V ; X2= X2’/V
得到上述关系式变为：
X1+ X2=1/V (V愈大愈好）待定
5X1+ 8X21
9X1+ 6X21
X1, X20
建立线性模型：
min X1+X2
. 5X1+8X21 X1= 1/21
9X1+6X21 X2= 2/21
X1, X20 1/V= X1+X2=1/7
所以：V=7
返回原问题： X1’= X1V= 1/3
X2’= X2V= 2/3
于是甲的最优混合策略为：
以1/3的概率选1；以2/3的概率选2
最优值V=7.
同样可求乙的最优混合策略：
设乙使用策略1的概率为Y1′ Y1′+Y2′=1
设乙使用策略2的概率为Y2′ Y1′,Y2′0
设在最坏的情况下，甲赢得的平均值为V.
这也是乙损失的平均值，越小越好
作变换： Y1= Y1’/V ; Y2= Y2’/V
建立线性模型：
max Y1+Y2
. 5Y1+9Y21 Y1= 1/14
8Y1+6Y21 Y2= 1/14
Y1, Y20 1/V= Y1+Y2=1/7
所以：V=7
返回原问题： Y1’= Y1V= 1/2
Y2’= Y2V= 1/2
于是乙的最优混合策略为：
以1/2的概率选1；以1/2的概率选2
最优值V=7.
当赢得矩阵中有非正元素时，V0的条件不一定成立，可以作下列变换：
选一正数k，令矩阵中每一元素加上k得到新的正矩阵A’，其对应的矩阵对策
G’= { S1,S2,A’}与 G ={ S1,S2,A }
解相同，但VG = VG’ - k
3.矩阵对策的混合策略(续)
例：求解“齐王赛马”问题（见备课稿）
优超原则：
假设矩阵对策 G ={ S1,S2,A }
甲方赢得矩阵 A=[aij]mn
-- 若存在两行（列），s 行（列）的各元素均优于 t 行（列）的元素，即
asjatj j=1,2…n ( ais ait i=1,2…m )
称甲方策略s优超于t ( s优超于t)
3.矩阵对策的混合策略(续)
-- 优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t行（同理，当局中人乙方的策略t被其它策略所优超时，可在矩阵A中划去第t列）。
如此得到阶数较小的赢得矩阵A’，其对应的矩阵对策
G’= { S1,S2,A’}与 G ={ S1,S2,A }
等价，即解相同。
3.矩阵对策的混合策略(续)
例 设甲方的益损值 赢得矩阵。
3 2 0 3 0 被第3、4行所优超
5 0 2 5 9 被第3行所优超
A= 7 3 9 5 9
4 6 8 7
6 0 8 8 3
得到
7 3 9 5 9 被第1列所优超
A1= 4 6 8 7 被第2列所优超
6 0 8 8 3
3.矩阵对策的混合策略(续)
续例 得到
7 3 9
A2= 4 6
6 0 3 被第1行所优超
得到
7 3 9 被第1列所优超
A3=
4 6
7 3
最终得到 A4=
4 6
3.矩阵对策的混合策略(续)
对A4计算，用线性规划方法得到：
（注意：余下的策略为3，4，1，2）
甲： X* = (0，0，1/15，2/15，0)T V=5
X*’= (0，0，1/3 ，2/3 ，0)T
乙： Y* = (1/10，1/10，0，0，0)T V=5
Y*’= (1/2 ，1/2 ，0，0，0)T
注：
利用有超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）；
线性规划求解时有可能是多解问题。
习题：P343-1，3，4
