对策论
由, 齐王赛马, 引入
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+ 8X2?1
9X1+ 6X2?1
X1,X2?0
? 建立线性模型:
min X1+X2
s.t,5X1+8X2?1 X1= 1/21
9X1+6X2?1 X2= 2/21
X1,X2?0 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
s.t,5Y1+9Y2?1 Y1= 1/14
8Y1+6Y2?1 Y2= 1/14
Y1,Y2?0 1/V= Y1+Y2=1/7
所以,V=7
? 返回原问题,Y1’= Y1V= 1/2
Y2’= Y2V= 1/2
于是乙的最优混合策略为:
以 1/2的概率选 ?1; 以 1/2的概率选 ?2
最优值 V=7.
? 当赢得矩阵中有非正元素时,V?0的条件不
一定成立,可以作下列变换:
选一正数 k,令矩阵中每一元素加上 k得
到新的正矩阵 A’,其对应的矩阵对策
G’= { S 1,S2,A’} 与 G ={ S1,S2,A }
解相同,但 VG = VG’ - k
? 例:求解“齐王赛马”问题(见备课稿)
? 优超原则:
假设 矩阵对策 G ={ S1,S2,A }
甲方赢得矩阵 A=[aij]m?n
-- 若存在两行(列),s 行(列)的各元素
均优于 t 行(列)的元素,即
asj?atj j=1,2… n ( ais ? ait i=1,2… m )
称甲方策略 ?s优超于 ?t ( ?s优超于 ?t)
3.矩阵对策的混合策略 (续 )
-- 优超原则:当局中人甲方的策略 ?t被其它
策略所 优超时,可在其赢得矩阵 A中划去第 t
行(同理,当局中人乙方的策略 ?t被其它策
略所 优超时,可在矩阵 A中划去第 t列)。
如此得到阶数较小的赢得矩阵 A’, 其对
应的矩阵对策
G’= { S 1,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 5.5
6 0 8 8 3
得到
7 3 9 5 9 被第 1列所优超
A1= 4 6 8 7 5.5 被第 2列所优超
6 0 8 8 3
3.矩阵对策的混合策略 (续 )
? 续例 得到
7 3 9
A2= 4 6 5.5
6 0 3 被第 1行所优超
得到
7 3 9 被第 1列所优超
A3=
4 6 5.5
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
3.矩阵对策的混合策略 (续 )
由, 齐王赛马, 引入
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+ 8X2?1
9X1+ 6X2?1
X1,X2?0
? 建立线性模型:
min X1+X2
s.t,5X1+8X2?1 X1= 1/21
9X1+6X2?1 X2= 2/21
X1,X2?0 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
s.t,5Y1+9Y2?1 Y1= 1/14
8Y1+6Y2?1 Y2= 1/14
Y1,Y2?0 1/V= Y1+Y2=1/7
所以,V=7
? 返回原问题,Y1’= Y1V= 1/2
Y2’= Y2V= 1/2
于是乙的最优混合策略为:
以 1/2的概率选 ?1; 以 1/2的概率选 ?2
最优值 V=7.
? 当赢得矩阵中有非正元素时,V?0的条件不
一定成立,可以作下列变换:
选一正数 k,令矩阵中每一元素加上 k得
到新的正矩阵 A’,其对应的矩阵对策
G’= { S 1,S2,A’} 与 G ={ S1,S2,A }
解相同,但 VG = VG’ - k
? 例:求解“齐王赛马”问题(见备课稿)
? 优超原则:
假设 矩阵对策 G ={ S1,S2,A }
甲方赢得矩阵 A=[aij]m?n
-- 若存在两行(列),s 行(列)的各元素
均优于 t 行(列)的元素,即
asj?atj j=1,2… n ( ais ? ait i=1,2… m )
称甲方策略 ?s优超于 ?t ( ?s优超于 ?t)
3.矩阵对策的混合策略 (续 )
-- 优超原则:当局中人甲方的策略 ?t被其它
策略所 优超时,可在其赢得矩阵 A中划去第 t
行(同理,当局中人乙方的策略 ?t被其它策
略所 优超时,可在矩阵 A中划去第 t列)。
如此得到阶数较小的赢得矩阵 A’, 其对
应的矩阵对策
G’= { S 1,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 5.5
6 0 8 8 3
得到
7 3 9 5 9 被第 1列所优超
A1= 4 6 8 7 5.5 被第 2列所优超
6 0 8 8 3
3.矩阵对策的混合策略 (续 )
? 续例 得到
7 3 9
A2= 4 6 5.5
6 0 3 被第 1行所优超
得到
7 3 9 被第 1列所优超
A3=
4 6 5.5
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
3.矩阵对策的混合策略 (续 )