- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1
1 3 1
1
1 1 3
4、优超原理
定义： 若A中第i, k 行有aij akj , j 1 n 称 i 优超于 k 。 记 i k 若A中第j, l列有aij ail , i 1 m 称 j 优超于l 记 j l 。
例： A
1 0 2 2 3 1
局中人乙的最优策略为d2，
对策值V=1
(2) 多鞍点与无鞍点对策
例 设有一矩阵对策如下，求它的解。
6 1 A 8 0 5 4 5 2 6 2 7 6 5 - 1 5 2
局势 ( s1 , d 2 ) ( s1 , d 4 ) ( s3 , d 2 ) ( s3 , d 4 ) 均构成鞍点， 此对策有多个解。
4．收益期望函数
对于一个混合局势(x,y)，用
E ( x , y ) xi ( aij y j ) aij xi y j x T Ay
i 1 j 1 i 1 j 1
m
n
m
n
表示局中人甲在混合局势(x,y)时的收益期望值。 5．混合策略对策模型 对于一个纯策略对策 G ( S , D, A) ，我们用
归一化
1 x x' , w
1 y y' z
例： “剪刀、石头、布” 游戏，
1 1 0 A 1 0 1 1 1 0
A+2
m i n z x1 x2 x3 2 x1 x2 3 x3 1 1 1 1 T 3 x1 2 x2 x3 1 求解 X ( , , ) st x1 3 x2 2 x3 1 6 6 6 xi 0( i 1, 2, 3) 归一化 1 1 1 T X ( , , ) 3 3 3 1 1 1 T 同理， Y ( , , ) 3 3 3
G* ( S * , D* , E ) 表示一个混合策略矩阵对策及
G的一个混合扩充。
二、混合策略对策的解 1．混合策略分析
* * * G ( S , D , E) 对于混合策略对策
局中人甲的策略决策模型为：
* max f ( x ) max min E ( x , y ) E ( x , y ) x x* * * * xS xS yD
称为i的劣策略(Dominated strategy)。
' i
'' i
例： B1 Ⅰ A1 A2 1， 0 0， 3
Ⅱ
B2 1， 2 0， 1 B3 0， 1 2， 0
劣策略
可按如下思路寻找均衡解： 首先找出某个局中人的劣策略（如果存在），剔除该劣 策略，得到新的博弈；再剔除该新博弈中的某个中人的 劣策略。重复进行，直至只剩下唯一的策略组合为止， 这个剩下的策略称为重复剔除的占优均衡（Iterated dominance equilibrium）。
定义：如果对应所有的 si，s
i ' i
i 是i的严格最优选择，即
ui ( s , si ) ui ( s , si ) si , s s
' i
i
则称 si 是i的占优策略(Dominant strategy)。 s 定义：如果对应所有的i， i 是i的占优策略,则称策略组合
例： 矩阵对策赢得矩阵如下，试求它的解。
3 6 A 5 4
解： 3,4 4 VL maxminaij max
5,6 5 VU minmaxaij min
j i
i
j
i 2
j 1
故：该对策无鞍点，即无解。
例：齐王赛马为无鞍点对策
田忌 齐王
1
2
3
2 1 3
2 3 3
3 1 3 2
' 性质1：若G ( S1 , S2 , A)中， i k，构造新的G ' ( S1' , S2 , A' ) ' 其中S1'是S1去掉 k，S2 ＝S2，A'是A中去掉k 行，则：
① VG VG '
β1 β2 β3 β4 β5 β6 （上中下） （上下中） （中上下） （中下上） （下上中） （下中上）
α1 （上中下） α2 （上下中） α1 （中上下） α1 （中下上） α1 （下上中） α1 （下中上）
3 1
1 3
1 1
1 1
-1 1
1 -1
1
-1 1 1
-1
1 1 1
3
1 1 -1
1
3 -1 1
A
'
根据性质3，则X * (0,0,1,0), Y * (1,0,0,0), VG* 2
§3 混合策略对策
一、混合策略对策的基本概念
无鞍点对策的求解方法是采用混合策略，混合策略就 是局中人考虑以某种概率分布来选择他的各个策略。
1．混合策略
T x ( x , x , , x ) , xi 1, xi 0, m维概率向量 1 2 m i 1 m
二、纳什均衡
均衡（Equilibrium）是所有局中人的最优策 略的组合，一般记为：
s ( s ,, s ,, s )
s 是第i个局中人在均衡情况下的最优战略，即 其中，
i
1
i
n
ui ( s , si ) ui ( s , si ) s s
' i ' i
i
前提： 对策双方均理智 结论： 最不利中选最有利
s1 3 A s 2 6 s3 - 5
1 0 -1
2 - 3 4
问：双方局中人采用何策略最佳。
解：可用下述表格表示上述寻找最优纯策略过程:
d1 s1 s2 s3 3 6 -5 6 d2 1 0 -1 1 d3 2 -3 4 4
i i j
（2）局中人乙对每个策略dj的评价值为
dj
* j
评价
g (d j ) max a ij
i
故局中人乙选择策略模型为：
d ming(d j ) minmaxaij Vmin
j j i
3. 纯策略对策模型的解
(1) 鞍点与解 对于一个对策 G S , D, A ，如果有
* maxminaij minmaxaij aij i j j i
V a 称为对策G 之值。 例 上例中 G S , D, A
* ij
则称局势 ( si , d j ) 为对策G的一个鞍点，
*
*
3 A 6 - 5
1 0 -1
2 - 3 4
局势 ( s1 , d 2 )构成一个鞍点， 局中人甲的最优策略为s1 ,
（Ⅰ）
m in
w x1 ' x2 ' xm '
m aij xi ' 1, j 1,2, , n s.t i 1 xi ' 0, i 1,2, , m
（Ⅱ） max
z y1 ' y2 ' yn '
n aij y j ' 1, i 1,2, , m s.t. j 1 y j ' 0, j 1,2, , n
前提假设：“理性”是所有局中人的共同知识 （Common Knowledge）
例：求下面博弈的重复剔除的占优均衡解
0 4 3 1 2 2 3 2 0 4
2 1 2 4
对于A ' min max aij max min aij 2, 即对策解是（ 3 , 1）VG 2。
j i i j
2 3 4 （2） 0
局中人乙的策略决策模型为：
* * min g ( y ) min max E ( x , y ) E ( x , y ) y y合策略矩阵对策的线性规划解法
若所有aij>0（否则，可取一充分大M>0，使得aij +M>0）， 则可用下述两规划 来求解混合策略：
二人有限零和对策
§2 纯策略对策
一、纯策略与混合策略
纯策略是指确定的选择某策略；而混合策略 则指以某一概率分布选择各策略。 二、纯策略对策的解 1. 引例
D d1 , d 2 , d 3 ，其赢得矩阵为： d1 d 2 d 3
例
设一对策 G S , D, A，其中 S s1 , s2 , s3 ，
i
（ si ( s1 , , si 1 , si 1 , , sn ) 表示除 i 之外
所有局中人的策略组成的向量。)
均衡的层次：
占优策略均衡 重复剔除的占优均衡 （纯策略）纳什均衡 混合策略纳什均衡
弱 强
条 件
1. 占优策略均衡
坦白
II 不坦白
考虑“囚犯困境”问题： 坦白 (9, 9) (0, 10) I 不坦白 ( 10, 0) ( 1, 1) 不论同伙选择什么策略，每个囚徒的最优策略是“坦白”。
s ( s ,, s )
1
n
为占优策略均衡。
小猪
2. 重复剔除的占优均衡
考虑智猪博弈问题：
按
等待
大 按 猪 等待
5， 1
9，-1
4，4
0， 0
“等待”是小猪的占优战略，而大猪无占优战略。
定义：令
则
s
' i
s 和 s 为局中人i的两个策略，如果 ' '' ui ( si , si ) ui ( si , si ) si
称为局中人甲的一个混合策略，即局中人甲选择 策略si的概率为xi 。 同理可定义乙的混合策略。
