矩阵对策纯策略意义下的解

1、7 对策论7.1 引言引言7.2 矩阵对策纯策略意义下的解矩阵对策纯策略意义下的解7.3 矩阵对策混合策略意义下的解矩阵对策混合策略意义下的解7.4 矩阵对策的解法矩阵对策的解法7.1 引言 在日常生活中，经常可以看到一些具有相互斗争或竞在日常生活中，经常可以看到一些具有相互斗争或竞争性质的行为，如下棋、打牌、体育比赛等。还有企业争性质的行为，如下棋、打牌、体育比赛等。还有企业间的竞争、军队或国家间的战争、政治斗争等，都具有间的竞争、军队或国家间的战争、政治斗争等，都具有对抗的性质。这种具有竞争或对抗性质的行为称为对抗的性质。这种具有竞争或对抗性质的行为称为对策对策行为行为。在这类行为中，各方

2、具有不同的目标和利益。为。在这类行为中，各方具有不同的目标和利益。为实现自己的目标和利益，各方必须考虑对手可能采取的实现自己的目标和利益，各方必须考虑对手可能采取的行动方案，并力图选择对自己最为有利或最为合理的行行动方案，并力图选择对自己最为有利或最为合理的行动方案。动方案。 例如，我国战国时期的例如，我国战国时期的“齐王赛马齐王赛马”就是典型的对就是典型的对策行为。策行为。 对策问题各种各样，所以对策模型也千差万别，但本质上都对策问题各种各样，所以对策模型也千差万别，但本质上都包括三个基本要素：包括三个基本要素： (1) (1)局中人局中人 在一个对策行为中，有权决定自己行动方案的在一个对策

3、行为中，有权决定自己行动方案的对策参加者。对策参加者。 (2) (2)策略集策略集 一局对策中，可供局中人选择的一个实际可一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个行的完整的行动方案称为一个策略策略。一个局中人全体策略构成。一个局中人全体策略构成的集合，称为此局中人的的集合，称为此局中人的策略集策略集。 (3) (3)赢得函数赢得函数 各局各局中人分别选定自己中人分别选定自己的策略构成的策略组的策略构成的策略组称为一个称为一个局势局势。当局当局势势出现出现后，后，对策对策的结果也就的结果也就确定确定了。了。对于对于局势局势s s，局，局中人中人i i可以得到一个赢得可以得

4、到一个赢得H Hi i(s)(s)，它是，它是局势局势s s的的函数函数, ,称称为为局局中人中人i i的的赢得函数赢得函数。 对策的分类对策的分类: : 1) 1)按局中人的多少分为按局中人的多少分为二人对策二人对策和和多人对策多人对策。 2) 2)按策略集中策略的有限或无限，分为按策略集中策略的有限或无限，分为有限对策有限对策和和无限对策无限对策。 3) 3)按各局中人赢得函数的代数和是否为零，分为按各局中人赢得函数的代数和是否为零，分为零零和对策和对策和和非零和对策非零和对策。 我们本章要学习的我们本章要学习的矩阵对策矩阵对策是指二人、有限、零和是指二人、有限、零和对策。对策。7.2 矩

5、阵对策纯策略意义下的解 矩阵对策就是二人有限零和对策。设两个局中人为矩阵对策就是二人有限零和对策。设两个局中人为、，它们各自的策略集为，它们各自的策略集为 S S1 11 1,2 2, ,m m S S2 21 1,2 2, ,n n 当局中人当局中人选定选定纯策略纯策略i i，局中人局中人选定选定纯策略纯策略j j后，就后，就形成了一个形成了一个纯局势纯局势( (i i,j j) )，这样的这样的纯局势纯局势共有共有mnmn个。个。 对任一纯局势对任一纯局势( (i i,j j) )，记局中人记局中人的赢得值为的赢得值为a aijij，则得矩阵则得矩阵 A=A=（a aijij），），称为矩

6、阵人称为矩阵人的的赢得矩阵赢得矩阵。由。由于是零和对策，则矩阵人于是零和对策，则矩阵人的赢得矩阵为的赢得矩阵为- -A A。矩阵对策的矩阵对策的名称正是由此而来。通常把矩阵对策记为名称正是由此而来。通常把矩阵对策记为 G G,;S,;S1 1,S,S2 2;A ;A 或或 G GSS1 1,S,S2 2;A;A 对于对于G GSS1 1,S,S2 2;A;A， 若有等式若有等式 max min amax min aijijmin max amin max aijija ai i* *j j* * i i j j j j i i成立，则称纯局势成立，则称纯局势( (i i* *,j j* *)

7、)为对策为对策G G在在纯策略纯策略意义下的意义下的解解，i i* *和和j j* *分别称局中人分别称局中人、的的最优纯策略最优纯策略。记。记V VG Ga ai i* *j j* *，称称V VG G为为对策对策G G的值的值。 定理定理1 1 矩阵对策矩阵对策G GSS1 1,S,S2 2;A ;A 在纯策略意在纯策略意义下有解义下有解, ,当且仅当存在当且仅当存在纯纯局势局势( (i i* *,j j* *) )，使使对一切对一切i=1,2,i=1,2,m,m，j=1,2,j=1,2,n,n，均有均有 a aijij* *aai i* *j j* *aai i* *j j例：例：G=S

8、1,S2,A -6 1 -8 S1=1,2,3,4 A= 3 2 4 S2=1,2, 3 9 -1 -10 -3 0 6 例如例如 6 5 6 5 1 5 2 -1A= 8 5 5 5 0 2 6 27.3 矩阵对策混合策略意义下的解 先看一个简单的例子先看一个简单的例子: A= 3 6 5 4 一般地，设矩阵对策一般地，设矩阵对策G GSS1 1,S,S2 2;A;A，其中其中 S S1 11 1,2 2, ,m m ，S S2 21 1,2 2, ,n n ， A A（a aijij）m mn n 若向量若向量x x(x(x1 1,x,x2 2, ,x,xm m) )T T和和y y(y(

9、y1 1,y,y2 2, , ,y,yn n) )T T满足满足 x xi i1 1，x xi i0 (i=1,2,0 (i=1,2,m),m) yyj j1 1，y yj j0 (j=1,2,0 (j=1,2,n),n)则则x x和和y y分别称为局中人分别称为局中人和局中人和局中人的的混合策略混合策略。 定理定理 任一矩阵对策任一矩阵对策G GSS1 1,S,S2 2;A;A，一定存在混合策略意义一定存在混合策略意义下的解。下的解。 定理定理 设有两个矩阵对策设有两个矩阵对策 G G1 1SS1 1,S,S2 2;A;A1 1 G G2 2SS1 1,S,S2 2;A;A2 2 其中其中A

10、 A1 1(a(aijij) )，A A2 2(a(aijij+L)+L)，L L为任一常数。则为任一常数。则 (1) (1)G G1 1与与G G2 2同解；同解； (2) (2)V VG2G2V VG1G1+L+L 设有矩阵对策设有矩阵对策G GSS1 1,S,S2 2;A ;A ，其中其中 S S1 11 1,2 2, ,m m ，S S2 21 1,2 2, ,n n ，A A(a(aijij) )m mn n 如果对一切如果对一切j j1,2,1,2,n,n，都有都有a ai i1 1j jaai i2 2j j, , 即矩阵即矩阵A A的第的第i i1 1行元行元素均大于等于第素均

11、大于等于第i i2 2行的对应元素，则称局中人行的对应元素，则称局中人的纯策略的纯策略i i1 1优超优超于于i i2 2； 同样，若对一切同样，若对一切i i1,2,1,2,m,m，都有都有a aijij1 1aaijij2 2, , 即矩阵即矩阵A A的第的第j j1 1列元素均小于等于第列元素均小于等于第j j2 2列的对应元素，则称局中人列的对应元素，则称局中人的纯策的纯策略略j j1 1优超于优超于j j2 2。 当局中人当局中人的某个纯策略被其它纯策略所优超时，可去掉这个的某个纯策略被其它纯策略所优超时，可去掉这个纯策略并在赢得矩阵纯策略并在赢得矩阵A A中划去对应的行。同样，当局

12、中人中划去对应的行。同样，当局中人的某个的某个纯策略被其它纯策略所优超时，也可去掉这个纯策略并在赢得矩阵纯策略被其它纯策略所优超时，也可去掉这个纯策略并在赢得矩阵A A中划去对应的列。中划去对应的列。利用此性质可以对矩阵对策化简。利用此性质可以对矩阵对策化简。例：例：7.4 矩阵对策的解法 (1) 2(1) 22 2矩阵对策的线性方程组法矩阵对策的线性方程组法 所谓所谓2 22 2矩阵对策矩阵对策是指局中人是指局中人的赢得矩阵为的赢得矩阵为2 22 2阶的，阶的，即即 A = A = a11 a12a11 a12 a21 a22 a21 a22 如果此对策有纯策略意义下的解，则很容易求解；如果

13、如果此对策有纯策略意义下的解，则很容易求解；如果没有纯策略意义下的解，则为求出各局中人的最优混合策略没有纯策略意义下的解，则为求出各局中人的最优混合策略可求解下列方程组：可求解下列方程组： a a1111x x1 1a a2121x x2 2v av a1111y y1 1a a1212y y2 2v v a a1212x x1 1a a2222x x2 2v av a2121y y1 1a a2222y y2 2v v y y1 1y y2 21 x1 x1 1x x2 21 1当没有纯策略意义下的解时，方程组一定有严格非负解，即当没有纯策略意义下的解时，方程组一定有严格非负解，即为各局中人的最优混合策略。为各局中人的最优混合策略。例例(2)(2)线性规划法线性规划法 当对策的值大于当对策的值大于0 0时时, ,可利用可利用线性规划法求解矩阵对策。线性规划法求解矩阵对策。构造构造两个两个线性规划问题线性规划问题 min zmin zxxi i i i a aijijx xi i1 (j=1,2,1 (j=1,2,n),n) i i x xi i0 (i=1,2,0 (i=1,2,m),m) max w max wyyj j j j a aijijy yj j1 (i=1,2,1 (i=1,2,m),m) j j y yj j