运筹学对策论.ppt

运筹学对策论现在学习的是第1页，共78页2 在日常生活中，我们经常看到一些相互之间的竞争、比在日常生活中，我们经常看到一些相互之间的竞争、比赛性质的现象，如下棋、打扑克、体育竞赛等赛性质的现象，如下棋、打扑克、体育竞赛等。在经济领域，各国之间的贸易谈判，各公司、企在经济领域，各国之间的贸易谈判，各公司、企业之间的市场争夺，各公司、企业之间的加工、订货、业之间的市场争夺，各公司、企业之间的加工、订货、合作谈判等等，都是竞争现象。合作谈判等等，都是竞争现象。在政治方面，国际上政府间的各种外交谈判，各方在政治方面，国际上政府间的各种外交谈判，各方都想在谈判中处于有利地位，争取到对自己有利的结果。都想在谈判中处于有利地位，争取到对自己有利的结果。各国之间或国内各集团之间的战争，是一种你死我活的各国之间或国内各集团之间的战争，是一种你死我活的斗争，双方都千方百计要战胜对方。斗争，双方都千方百计要战胜对方。现在学习的是第2页，共78页3 例：例：两个儿童玩的两个儿童玩的“石头石头剪子剪子布布”游戏和我游戏和我国古代的国古代的“齐王赛马齐王赛马”就是典型的对策论研究的例子。就是典型的对策论研究的例子。在这类行为中，参加斗争或竞争的各方各自具有不在这类行为中，参加斗争或竞争的各方各自具有不同的目标和利益，为了达到各自的目标和利益各方必须考同的目标和利益，为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案，对策论就是研究对策行为中斗争各利或最为合理的方案，对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。的行动方案的数学理论和方法。现在学习的是第3页，共78页4二、二、对策问题的三个基本要素对策问题的三个基本要素 （1 1）局中人局中人：在一场竞赛或斗争中，每一个有决策权在一场竞赛或斗争中，每一个有决策权的参与者的参与者(个人或集团个人或集团)称为一个局中人。只有两个局中称为一个局中人。只有两个局中人的对策现象称为人的对策现象称为“两人对策两人对策”，而多于两个局中人的对，而多于两个局中人的对策称为策称为“多人对策多人对策”。（2）策略策略：一个对策中，每个局中人都有供他选：一个对策中，每个局中人都有供他选择的实际可行的完整的行动方案，我们把一个局中人择的实际可行的完整的行动方案，我们把一个局中人一个可行的自始至终通盘筹划的行动方案，称为这个一个可行的自始至终通盘筹划的行动方案，称为这个局中人的一个局中人的一个策略策略。如果在一个对策中，每个局中人都。如果在一个对策中，每个局中人都只有有限个策略，则称为只有有限个策略，则称为“有限对策问题有限对策问题”，否则称，否则称为为“无限对策问题无限对策问题”。现在学习的是第4页，共78页5 （3）赢得函数（支付函数）赢得函数（支付函数）：一局对策结束时的结：一局对策结束时的结果（如收入或支出）称为果（如收入或支出）称为得失得失。每个局中人在一局对策结。每个局中人在一局对策结束时的得失，不仅与该局中人自身所选择的策略有关，束时的得失，不仅与该局中人自身所选择的策略有关，而且与全体局中人所取定的一组策略有关。所以，一局而且与全体局中人所取定的一组策略有关。所以，一局对策结束时每个局中人的对策结束时每个局中人的“得失得失”是全体局中人所取定是全体局中人所取定的一组策略的函数，通常称作的一组策略的函数，通常称作赢得函数赢得函数（支付函数）（支付函数）。把每个局中人各自所取的一个策略所组成的策略组称为把每个局中人各自所取的一个策略所组成的策略组称为“局势局势”，于是，于是“得失得失”是是“局势局势”的函数。的函数。现在学习的是第5页，共78页6第二节第二节 矩阵对策的基本定理矩阵对策的基本定理 特点特点：局中人只有局中人只有两人两人，分别用分别用局中人局中人和和局中人局中人表示，表示，双方都只有有限个策略可供选择，双方都只有有限个策略可供选择，局中人的局中人的“得失得失”相加等于零，这种对策称为相加等于零，这种对策称为“零零和对策和对策”。在两人有限零和对策中，。在两人有限零和对策中，局中人局中人的所获等于的所获等于局局中人中人的所失。假定在局势的所失。假定在局势(i,j)下下(即即局中人局中人取策略取策略i，局中人局中人取策略取策略j 时所形成的局势时所形成的局势)，局中人局中人的收入或赢的收入或赢得是得是ai j（“aij”是负数时，表示是负数时，表示局中人局中人是支出）。是支出）。的策略集为：的策略集为：的策略集为：的策略集为：一、矩阵对策的数学模型一、矩阵对策的数学模型现在学习的是第6页，共78页7 用矩阵表示为用矩阵表示为(称为称为局中人局中人的的赢得矩阵赢得矩阵或局或局中人中人的的支付矩阵支付矩阵):我我们们称称两两人人有有限限零零和和对对策策为为矩矩阵阵对对策策，记记为为：G G,；S S1 1,S,S2 2；AA 或或 G GSS1 1，S S2 2；AA。现在学习的是第7页，共78页8例例1:设有设有矩阵对策矩阵对策，局中人，局中人的支付矩阵如下：的支付矩阵如下：如果各局中人都不想冒险，必须考虑对方会选如果各局中人都不想冒险，必须考虑对方会选择策略使他得到最差的收入。因此各局中人都选择择策略使他得到最差的收入。因此各局中人都选择理智的决策行为。理智的决策行为。解：解：3 3 1 4 3现在学习的是第8页，共78页9 局中人局中人的各种策略的最差收入是支付阵中各种的各种策略的最差收入是支付阵中各种策略所对应行的最小数。如果不存侥幸心理，他对每策略所对应行的最小数。如果不存侥幸心理，他对每个策略只能期望得到最差的收入。即：个策略只能期望得到最差的收入。即：那么为了得到尽可能好的结局，只能从这些最小数之那么为了得到尽可能好的结局，只能从这些最小数之中的找最大者（中的找最大者（最大的最小者最大的最小者），即选择能在最差的可能），即选择能在最差的可能结果中得到最好结果的策略。即：结果中得到最好结果的策略。即：8，2，9，3即选择策略即选择策略2。现在学习的是第9页，共78页10 同样，局中人同样，局中人的各种策略的最差收入（最大支的各种策略的最差收入（最大支出）是支付矩阵中各列的最大数，即：出）是支付矩阵中各列的最大数，即：局中人局中人选择这些最大数中的最小者。即：选择这些最大数中的最小者。即：16，2，5即选择策略即选择策略2。的最优策略为的最优策略为2,的最优策略为的最优策略为2。现在学习的是第10页，共78页11 定义定义:设设G GSS1 1，S S2 2；AA为矩阵对策为矩阵对策,其中其中S S1 11 1,2 2,m m，S S2 21 1,2 2,n n。A=A=(aij)mnmn，若满，若满足等式足等式：则称纯局势则称纯局势(i*i*，j*j*)为为G G在纯策略下的解（或在纯策略下的解（或平衡局势）。记平衡局势）。记V VG Gai*j*i*j*，称，称V VG G为对策为对策G G的值的值,i*i*，j*j*分别称为局中人分别称为局中人I I、IIII的最优纯策略。的最优纯策略。例例1的对策的对策G G的解为的解为（2 2，2 2），），2 2，2 2分别是分别是局中人局中人I I和和IIII的最优纯策略，的最优纯策略，V VG G=2=2。从从例例1 1中中可可以以看看出出，矩矩阵阵的的元元素素a2222既既是是所所在在行行的的最最小小元素，又是所在列的最大元素，即：元素，又是所在列的最大元素，即：现在学习的是第11页，共78页12 定理定理1：矩阵对策矩阵对策A =(aij)mnmn有解的充分必要条件有解的充分必要条件是：是：存在存在纯局势纯局势(i*i*，j*j*)，使得对一切使得对一切 i=1,2,i=1,2,m,j=1,2,m,j=1,2,n,n均有均有：i=1,2,3,4；j=1,2,3 将将这这一事一事实实推广到一般矩推广到一般矩阵对阵对策，可得如下定理：策，可得如下定理：证明：证明：先证充分性，由于对任意先证充分性，由于对任意i，j均有：均有：故：故：现在学习的是第12页，共78页13另一方面，对任意另一方面，对任意i，j均有：均有：所以：所以：于是：于是：所以：所以：现在学习的是第13页，共78页14再证必要性，若再证必要性，若G有解。有解。而对于所有的而对于所有的 i 而言，必存在一个而言，必存在一个i*使：使：对于所有的对于所有的 j 而言，必存在一个而言，必存在一个j*使：使：因为：因为：于是：于是：现在学习的是第14页，共78页15称满足条件称满足条件 的的(i*,j*)为矩阵对策为矩阵对策G的一个的一个鞍点鞍点。但：但：于是有：于是有：故对一切的故对一切的 i,j 都有：都有：意义：意义：如果如果局中人局中人I I选择策略选择策略i*，局中人局中人IIII不选择不选择策略策略 j*，而选择策略，而选择策略j，则，则局中人局中人IIII的支付只会增多。的支付只会增多。也就是说：策略也就是说：策略j*是是IIII的最优策略。的最优策略。现在学习的是第15页，共78页16 注意：注意：一个矩阵对策一个矩阵对策G如果存在鞍点，鞍点可能不如果存在鞍点，鞍点可能不止一个。但是在不同的鞍点处，支付值相等，都等于止一个。但是在不同的鞍点处，支付值相等，都等于对策的值。（对策的值。（无差异性无差异性）如果如果(i,j)以及以及(k,l l)都是对策都是对策G的鞍点，则的鞍点，则(k,j)与与(i,l l)也是该问题的鞍点。（也是该问题的鞍点。（可交换性可交换性）同样，如果同样，如果局中人局中人IIII选择策略选择策略j*，局中人局中人I I不不选择策略选择策略 i*，而选择策略，而选择策略 i，则，则局中人局中人I I的所获只的所获只会减少。也就是说：策略会减少。也就是说：策略i*是是局中人局中人I I的最优策略。的最优策略。现在学习的是第16页，共78页17G有四个鞍点：有四个鞍点：对策的值为对策的值为V VG G 5。例例2：给定矩阵对策给定矩阵对策G GSS1 1，S S2 2；AA，其中：，其中：现在学习的是第17页，共78页18二、二、矩阵对策的混合策略矩阵对策的混合策略 矩阵对策矩阵对策G有鞍点时，就存在最优解有鞍点时，就存在最优解(最优纯策略最优纯策略)，但，但是否一切矩阵对策问题中，各局中人都有上述意义的是否一切矩阵对策问题中，各局中人都有上述意义的最优纯策略呢最优纯策略呢?答案是否定的。答案是否定的。例例1：石头、剪刀、布石头、剪刀、布不存在上述纯策略意义下的解。不存在上述纯策略意义下的解。现在学习的是第18页，共78页19 对于该例而言，直观的看：双方采用三个纯策略的对于该例而言，直观的看：双方采用三个纯策略的频率均应为频率均应为 13 ：13 ：13。由于每个局中人。由于每个局中人在一局对策中必取某个纯策略，因此采取任何一个在一局对策中必取某个纯策略，因此采取任何一个纯策略的概率都应是纯策略的概率都应是13。一般地，设局中人一般地，设局中人I I以概率以概率x1,x2,，xm来分别选来分别选取他的纯策略取他的纯策略1 1，2 2，m m；而局中人；而局中人IIII以概率以概率y1,y2,，yn来选用自己的纯策略来选用自己的纯策略1 1，2 2，n n。于是：。于是：令令x=(x1,x2,，xm)T ,y=(y1,y2,，yn)T 则称这样的则称这样的x和和y为为局中人局中人I I、IIII的的混合策略混合策略。现在学习的是第19页，共78页20记：记：此时，当局中人此时，当局中人I I以概率以概率 xi采用采用i 时，局中人时，局中人IIII以概以概率率 yj 采用采用 j 时时，支付，支付 ai j 出现的概率为出现的概率为xi yj。于是局中人于是局中人I I收入（赢得）的期望值为：收入（赢得）的期望值为：则称则称 G GSS1 1，S S2 2；EE为为 G GSS1 1，S S2 2；AA的混合的混合扩充。扩充。现在学习的是第20页，共78页21混合策略对策矩阵可表示如下：混合策略对策矩阵可表示如下：混合策略问题的解也是以混合策略问题的解也是以最大最小最大最小化化和和最小最大最小最大化化标准为根据的。标准为根据的。现在学习的是第21页，共78页22 当局中人当局中人I I选择某个混合策略选择某个混合策略 x 时，对于局中人时，对于局中人IIII的任的任意选择意选择 y,I I的期望所获至少是：的期望所获至少是：于是局中人于是局中人I I希望选择希望选择x，使上式最大，保证局中人，使上式最大，保证局中人I I的期望所获不小于：的期望所获不小于：这就是局中人这就是局中人I I的的最大最小化标准最大最小化标准。同理：当局中人同理：当局中人IIII选择某个混合策略选择某个混合策略 y 时，对于时，对于I I的的任意选择任意选择 x，IIII的期望支付至多是：的期望支付至多是：于是局中人于是局中人IIII希望选择希望选择 y，使上式最小，保证局中，使上式最小，保证局中人人IIII的期望支付不多于：的期望支付不多于：这就是局中人这就是局中人IIII的的最小最大化标准最小最大化标准。现在学习的是第22页，共78页23例例1：求解矩阵对策求解矩阵对策G GSS1 1，S S2 2；AA，其中：，其中：如果令：如果令：则得问题的最优解。则得问题的最优解。解：解：设设 X=(x,1x)T,Y=(y,1y)T 且对策的值为：且对策的值为：现在学习的是第23页，共78页24另解另解：（用微分求极值的方法）（用微分求极值的方法）且对策的值为：且对策的值为：现在学习的是第24页，共78页25 定义定义:G GSS1 1,S,S2 2；EE为为矩阵对策矩阵对策G GSS1 1,S,S2 2；AA的混的混合扩充合扩充，若存在，若存在(x*,y,y*)满足等式满足等式：则称则称(x*,y,y*)为为G G在混合策略下的解。称在混合策略下的解。称V VG GE(x*,y,y*)为对为对策策G G的值的值,x*,y,y*分别称为分别称为I I、IIII的最优混合策略。的最优混合策略。定理定理2：混合策略混合策略 x*和和 y*是是G的解的充分必要条件是：的解的充分必要条件是：对一切混合策略对一切混合策略 x,y有：有：称称(x*,y*)是对策问题在混合策略意义下的鞍点。是对策问题在混合策略意义下的鞍点。现在学习的是第25页，共78页26当局中人当局中人I I 取纯策略取纯策略i时，记其赢得函数为时，记其赢得函数为于是于是三、矩阵对策的基本定理三、矩阵对策的基本定理当局中人当局中人IIII取纯策略取纯策略j时，记其赢得函数为时，记其赢得函数为于是于是现在学习的是第26页，共78页27则有：则有：定理定理3：混合策略混合策略 x*和和 y*是是G的解的充分必要条件是：的解的充分必要条件是：对任意的对任意的i,j有：有：现在学习的是第27页，共78页28则则证明：证明：必要性显然，只需证充分性，若对任意必要性显然，只需证充分性，若对任意i,j均有：均有：即：即：所以所以x*和和 y*是是G的解。的解。现在学习的是第28页，共78页29注意到：注意到：可以写成：可以写成：于是于是定理定理3可以改述为：可以改述为：定理定理4：矩阵对策矩阵对策GS1,S2；A有解的充要条件是存在数有解的充要条件是存在数v，使得，使得 x,y 分别是下述两个不等式组的解：分别是下述两个不等式组的解：现在学习的是第29页，共78页30 定理定理5：（对策基本定理对策基本定理）任何矩阵对策）任何矩阵对策G G在混合策略下在混合策略下一定有解。一定有解。证明：证明：由由定理定理3，只需证明存在混合策略，只需证明存在混合策略 x*和和 y*，使得，使得（3）式成立，为此考虑如下两个线性规划：）式成立，为此考虑如下两个线性规划：现在学习的是第30页，共78页31容易验证（容易验证（P）和（）和（D）是互为对偶规划，而且）是互为对偶规划，而且 是（是（P）的一个可行解，）的一个可行解，是是(D)的一个可行解，由线性规划对偶理论可知，的一个可行解，由线性规划对偶理论可知，(P)和和(D)是都存在最优解是都存在最优解(x*，w*)和和(y*,v*)，且最优值，且最优值w*=v*，即，即:i=1i=1，2,2,m,j=1,m,j=1，2,2,n.,n.现在学习的是第31页，共78页32又由：又由：可得：可得：定理定理5的证明是构造性的证明，同时给出了求解方法。的证明是构造性的证明，同时给出了求解方法。现在学习的是第32页，共78页33 定理定理6：设（设（x*，y*）是矩阵对策）是矩阵对策G G解，解，v=V=VG G，则，则现在学习的是第33页，共78页34矩阵对策矩阵对策G GSS1 1，S S2 2；AA。（1）若）若（即（即A中第中第k行的每个元素行的每个元素 A中第中第 l 行的每个元素）行的每个元素）称局中人称局中人I I的策略的策略k优超于策略优超于策略 l；则可在；则可在A中中去掉第去掉第 l 行行，矩阵对策矩阵对策G G的解不变。的解不变。（2）如果：）如果：（即（即A中第中第k列的每个元素列的每个元素 A中第中第l列的每个元素）列的每个元素）称局中人称局中人IIII的策略的策略k 优超于策略优超于策略l。则可在。则可在A中中去掉第第去掉第第 l 列列，矩阵对策矩阵对策G G的解不变。的解不变。优超定理：优超定理：现在学习的是第34页，共78页35第三节第三节 矩阵矩阵对策的求解对策的求解一、一、22对策的方程法对策的方程法则称则称G G为为22222222对策。对策。对策。对策。若若G没有纯没有纯策略下的解，策略下的解，则则G的的最优混合策略最优混合策略x*=(x1,x2)T,y y*=(y1,y2)T 满足下列方程组：满足下列方程组：且其中且其中v=V=VG G .现在学习的是第35页，共78页36例例1：求解求解矩阵对策求解求解矩阵对策G GSS1 1，S S2 2；AA，其，其中：中：解：解：在在A中由于：中由于：第第3行行第第2行行，第第4行行第第1行行，因此从因此从A中中划去划去1，2两行两行，得：，得：现在学习的是第36页，共78页37在在A1中由于：中由于：第第1列列第第3列列，第第2列列第第4列列，因此从因此从A1中中划去划去3，4两列两列，得：得：在在A2中由于：中由于：第第1行行第第3行行，因此从因此从A2中中划去第划去第3行行，得：，得：在在A3中由于：中由于：第第2列列第第3列列，因此从因此从A3中中划去第划去第3列列，得：，得：现在学习的是第37页，共78页38分别求解方程组得：分别求解方程组得：得得 x3=1/3,x4=2/3,y1=1/2,y2=1/2,v=5.由此对于原问题由此对于原问题A而言，最优解为：而言，最优解为：现在学习的是第38页，共78页39二、二、2n和和m2对策的图解法对策的图解法解：解：设局中人设局中人I I 的的混合策略为混合策略为(x,1x)T,局中人局中人I I 的最的最少得益为如下图中由局中人少得益为如下图中由局中人IIII 选择选择1 1,2 2,3 3 时所确定的三条直线时所确定的三条直线2 x 7(1x)v，3 x 5(1x)v，11x 2(1x)v在在x处纵坐标的处纵坐标的最小者，即如图中折线最小者，即如图中折线B B1 1BBBB2 2B B3 3。例例2：求解求解矩阵对策求解求解矩阵对策G GSS1 1，S S2 2；AA，其中：，其中：现在学习的是第39页，共78页40012511237xVV3 31 12 2B B1 1B BB B2 2B B3 3A 所以对局中人所以对局中人I I来说，他来说，他的的策略就是确定策略就是确定x使他的得使他的得益达到最大。按最大最小原则应选择益达到最大。按最大最小原则应选择xOA，而，而AB即为对策的值。为求出即为对策的值。为求出x和对策的值和对策的值 V VG G ，可联立过，可联立过B点的点的两条直线两条直线2 2和和3 3所确定的方程。所确定的方程。现在学习的是第40页，共78页41解得：解得：x 3/11，V VG G=49/11。此外从图中可看出，局中人此外从图中可看出，局中人IIII的最的最优策略只由优策略只由2 2和和3 3组成（不选组成（不选1 1），可由方程组所确定：），可由方程组所确定：解得：解得：y y2 2=9/11，y y3 3=2/11。所以最优解为：所以最优解为：现在学习的是第41页，共78页42例例3：求解矩阵对策求解矩阵对策GS1，S2；A，其中：，其中：解：解：设局中人设局中人IIII 的的混合策略为混合策略为(y,1y)T,局中人局中人II 的的最大支付为如下图中由局中人最大支付为如下图中由局中人 I I选择选择1 1,2 2,3 3 时所确定时所确定的三条直线的三条直线2y7(1y)v，9y6(1y)v，11y2(1y)v在在y处纵坐标的处纵坐标的最小者，即如图中折线上的最小者，即如图中折线上的B B点。点。现在学习的是第42页，共78页43012611297yVVB BA A1 12 23 3 对局中人对局中人IIII来说，他来说，他的的策略就是确定策略就是确定y使他的支付使他的支付达到最小。按最小最大原则应选择达到最小。按最小最大原则应选择y OA，为求出，为求出y和对策的值和对策的值 V VG G，可联立过，可联立过B 点的两条直线点的两条直线1 1和和2 2所所确定的方程。确定的方程。现在学习的是第43页，共78页44解得：解得：y 1/8，V VG G=51/8。此外从图中可看出，局中人此外从图中可看出，局中人IIII的最的最优策略只由优策略只由1 1和和2 2组成（不选组成（不选3 3），可由方程组所确定：），可由方程组所确定：解得：解得：x1 1=3/8，x2 2=5/8。所以最优解为：所以最优解为：现在学习的是第44页，共78页45三、线性规划法三、线性规划法由前面定理可知，对策由前面定理可知，对策G的解满足下列线性规划：的解满足下列线性规划：作变量替换：作变量替换：现在学习的是第45页，共78页46则则于是上述于是上述线性规划线性规划等价于下面的线性规划问题。等价于下面的线性规划问题。由此求解一个对策问题，就相当于求解上面的对偶由此求解一个对策问题，就相当于求解上面的对偶问题：问题：现在学习的是第46页，共78页47例例4：利用线性规划法求解矩阵对策利用线性规划法求解矩阵对策G GSS1 1,S,S2 2；A.A.【注注】如果如果ai j不满足非负性，则存在一个正数不满足非负性，则存在一个正数k，使得，使得ai j+k0 令令B=(bi j)=(ai j+k)，求解对策问题，求解对策问题 SS1 1，S S2 2；BB，可以证明：问题可以证明：问题SS1 1，S S2 2；BB与问题与问题SS1 1，S S2 2；AA的最优策的最优策略相同，且有：略相同，且有：其中：其中：现在学习的是第47页，共78页48解：解：建立相应的线性规划模型建立相应的线性规划模型及及用单纯形法求解后一个问题，先标准化为：用单纯形法求解后一个问题，先标准化为：现在学习的是第48页，共78页49用单纯形表用单纯形表求解求解如下：如下：现在学习的是第49页，共78页50现在学习的是第50页，共78页51由此最优解为：由此最优解为：现在学习的是第51页，共78页52第四节第四节 两人有限非零和对策两人有限非零和对策 例例1：“囚徒困境囚徒困境”甲乙是同案囚犯，被隔离审讯。甲乙是同案囚犯，被隔离审讯。如果两个都抵赖，因为证据不充分，两人都只能判如果两个都抵赖，因为证据不充分，两人都只能判1年。年。如果只有一方坦白，则无罪释放；而另一方则属抗如果只有一方坦白，则无罪释放；而另一方则属抗拒从严，判拒从严，判10年。但如果两人都坦白，则各判年。但如果两人都坦白，则各判5年。年。下表给出了下表给出了“囚徒困境囚徒困境”博弈问题的战略式表述，为博弈问题的战略式表述，为了实现各自的效用最大化，双方格采取何种策略呢了实现各自的效用最大化，双方格采取何种策略呢?坦白1抵赖2坦白1(5,5)(0,10)抵赖2(10，0)(1,1)现在学习的是第52页，共78页53 假设该博弈是一次性的，对于囚犯甲而言，不管乙选假设该博弈是一次性的，对于囚犯甲而言，不管乙选择坦白还是抵赖，他选择坦白都比选择抵赖更好。这种不择坦白还是抵赖，他选择坦白都比选择抵赖更好。这种不管对方选择何种策略，局中人的最优选择总是不变的那个管对方选择何种策略，局中人的最优选择总是不变的那个策略被称为该局中人的策略被称为该局中人的优超策略优超策略。此例中坦白为甲的优。此例中坦白为甲的优超策略，同样道理坦白也是乙的优超策略。结果是，超策略，同样道理坦白也是乙的优超策略。结果是，两个囚徒争先恐后地都选择坦白，各判刑两个囚徒争先恐后地都选择坦白，各判刑5年。从而年。从而(坦坦白，坦白白，坦白)也就构成了该博弈的优超策略均衡（称为也就构成了该博弈的优超策略均衡（称为纳什纳什均衡均衡）。）。现在学习的是第53页，共78页54 囚犯困境反映了一个深刻的问题，这就是囚犯困境反映了一个深刻的问题，这就是个人理性个人理性与与集体理性集体理性的矛盾，如果两个人都抵赖，对局中人组成的的矛盾，如果两个人都抵赖，对局中人组成的集体而言，可谓集体而言，可谓帕累托最优帕累托最优，但是这并不满足个人理性导致，但是这并不满足个人理性导致的纳什均衡的纳什均衡(坦白，坦白坦白，坦白)，因而，这个帕累托改进在静态，因而，这个帕累托改进在静态博弈中办不到。囚徒困境说明纳什均衡并不一定导致帕累博弈中办不到。囚徒困境说明纳什均衡并不一定导致帕累托最优，从而动摇了传统经济学中托最优，从而动摇了传统经济学中个人效用最大化行为必个人效用最大化行为必然导致社会福利最优然导致社会福利最优的基本命题。的基本命题。对囚犯困境问题作进一步分析，不难发现，尽管甲对囚犯困境问题作进一步分析，不难发现，尽管甲与乙各自的最佳选择都是坦白，如果双方均选择抵赖，与乙各自的最佳选择都是坦白，如果双方均选择抵赖，各判刑各判刑1年，显然比双方均坦白时答判刑年，显然比双方均坦白时答判刑5年的结局要年的结局要好，因此，其最佳选择与最优结局并不一致。出现所谓好，因此，其最佳选择与最优结局并不一致。出现所谓的的“囚徒困境囚徒困境”。现在学习的是第54页，共78页55 设对策设对策G的的局中人局中人和和，双方都只有有限个策略，其，双方都只有有限个策略，其中中 在局势在局势(i,j)下下(即局中人即局中人取策略取策略，局中人，局中人取策取策略略j 时所形成的策略组合时所形成的策略组合)，局中人，局中人的赢得值是的赢得值是ai j，局中，局中人人的的赢得值是赢得值是bij。分别用矩阵表示为。分别用矩阵表示为A和和B。的策略集为：的策略集为：的策略集为：的策略集为：非合作两人对策非合作两人对策现在学习的是第55页，共78页56 定义：定义：对于非合作两人对策对于非合作两人对策G，如果，如果i*i*是局中人是局中人对对的策略的策略j*j*的的最优策略，最优策略，j*j*是局中人是局中人对对的的策略策略i*i*的的最优策略，则称局势最优策略，则称局势(i*i*，j*j*)是该问是该问题的一个题的一个纳什均衡纳什均衡（即谁都不愿单独改变策略）（即谁都不愿单独改变策略）。现在学习的是第56页，共78页57 本博弈的本博弈的纳什均衡纳什均衡为为(大猪按，小猪等待大猪按，小猪等待)。例例2：“智猪博弈智猪博弈”猪圈有一头大猪、一头小猪，猪圈有一头大猪、一头小猪，按一下按钮会有按一下按钮会有10个单位的饲料，但按按钮需要个单位的饲料，但按按钮需要2个单位个单位成本。成本。按1等待2按1(5，1)(4，4)等待2（9，1）(0，0)现在学习的是第57页，共78页58 例例3：“夫妻博弈夫妻博弈”丈夫喜欢看球赛，妻子喜欢逛丈夫喜欢看球赛，妻子喜欢逛商场。他们都宁愿在一起，也不愿分开行动。商场。他们都宁愿在一起，也不愿分开行动。本本例例有有两两个个纳纳什什均均衡衡结结果果会会出出现现，要要么么一一起起去去看看球球赛赛，要要么么一一起起去去逛逛商商场场，但但在在一一次次博博弈弈中中究究竟竟会会出出现哪一种？现哪一种？看球赛1逛商场2看球赛1(2，1)(0，0)逛商场2(0，0)(1，3)现在学习的是第58页，共78页59 这这个个博博弈弈也也有有两两个个纳纳什什均均衡衡，一一个个是是(进进攻攻，退退却却)，另一个是另一个是(退却，进攻退却，进攻)。进攻1退却2进攻1(-3，-3)(2，0)退却2(0，2)(0，0)例例4：“斗鸡博弈斗鸡博弈”有两个斗鸡有两个斗鸡A、B，它们各有两，它们各有两个策略：进攻或退却。个策略：进攻或退却。现在学习的是第59页，共78页60(0，300)(0，300)不进入不进入2(10,0)(40,50)进入进入1阻挠阻挠2默许默许1 进入者进入者在位者在位者 这这个个博博弈弈也也有有两两个个纳纳什什均均衡衡，一一个个是是(进进入入，默默许许)，另另一一个个是是(不不进进入入，斗斗争争)，而而(不不进进入入，默默许许)却却不不是是一一个纳什均衡。个纳什均衡。例例5:“市场进入壁垒市场进入壁垒”设想一个垄断企业已占领市场设想一个垄断企业已占领市场(称为称为“在位者在位者”)，另一个企业很想进入市场，另一个企业很想进入市场(称为称为“进入进入者者”)，在位者想保持其垄断地位，就要阻挠进入者进，在位者想保持其垄断地位，就要阻挠进入者进入假定双方在各种策赂组合下的赢得短阵如表所示：入假定双方在各种策赂组合下的赢得短阵如表所示：现在学习的是第60页，共78页61非合作两人对策的解法非合作两人对策的解法 对其他局中人的任一策略组合，找出对其他局中人的任一策略组合，找出局中人局中人i的的最佳策略最佳策略，并在其，并在其得益得益值下值下划线划线。若存在一个策略。若存在一个策略组合，使得所有局中人的得益值下都划了线，则该组合，使得所有局中人的得益值下都划了线，则该策略组合就是一个策略组合就是一个纳什均衡纳什均衡。求纳什均衡的方法如下求纳什均衡的方法如下:现在学习的是第61页，共78页62例例1：囚犯困境囚犯困境(1，1)(10，0 )抵赖抵赖2(0,10)(5,5)坦白坦白1抵赖抵赖2坦白坦白1 甲甲乙乙因此因此(坦白，坦白坦白，坦白)构成了该博弈的纳什均衡。构成了该博弈的纳什均衡。现在学习的是第62页，共78页63例例3：夫妻博弈夫妻博弈 看球赛1逛商场2看球赛1(2，1)(0，0)逛商场2(0，0)(1，3)这这个个博博弈弈有有两两个个纳纳什什均均衡衡，一一个个是是(看看球球赛赛，看看球球赛赛)，另一个是，另一个是(逛商场，逛商场逛商场，逛商场)。现在学习的是第63页，共78页64(0，300)(0，300)不进入不进入2(10,0)(40,50)进入进入1阻挠阻挠2默许默许1 进入者进入者在位者在位者例例5:市场进入壁垒市场进入壁垒 因此因此(进入，默许进入，默许)和和(不进入，阻挠不进入，阻挠)是该问题的是该问题的两个钠什均衡。两个钠什均衡。现在学习的是第64页，共78页65混合策略纳什均衡混合策略纳什均衡 上面介绍了在纯策略意义下非合作两人对策纳什上面介绍了在纯策略意义下非合作两人对策纳什均衡的概念及求解方法，但有些对策不存在纯策略意均衡的概念及求解方法，但有些对策不存在纯策略意义下的纳什均衡，考虑下面的例子。义下的纳什均衡，考虑下面的例子。现在学习的是第65页，共78页66(0，0)(1，1)不救济不救济2(1,3)(3,2)救济救济1游荡游荡2寻找工作寻找工作1 政府政府流浪汉流浪汉 例例6：局中人是政府和一个流浪汉，流浪汉有两个策略：局中人是政府和一个流浪汉，流浪汉有两个策略：寻找工作或游荡；政府也有两个策略：救济或不救济。政府寻找工作或游荡；政府也有两个策略：救济或不救济。政府帮助流浪汉的前提是后者必须试图寻找工作；否则，政府不帮助流浪汉的前提是后者必须试图寻找工作；否则，政府不予以帮助；而流浪汉只在得不到救济时才会寻找工作，如表予以帮助；而流浪汉只在得不到救济时才会寻找工作，如表给出了对策的赢得双矩阵：给出了对策的赢得双矩阵：现在学习的是第66页，共78页67 同样局中人可以考虑按照一定的随机方式来确定同样局中人可以考虑按照一定的随机方式来确定一个策略组合的混合策略。每个局中人作出决策时，一个策略组合的混合策略。每个局中人作出决策时，不是只选用一个纯策略，而是按照预先确定的一组概不是只选用一个纯策略，而是按照预先确定的一组概率来选取他们所有可能采用的策略。率来选取他们所有可能采用的策略。容易理解：当流浪汉选择寻找工作时，政府的最优策容易理解：当流浪汉选择寻找工作时，政府的最优策略是救济；当流浪者选择游荡时，政府的最优策略是不救略是救济；当流浪者选择游荡时，政府的最优策略是不救济；当政府策略为不救济时，流浪汉的最优策略是寻找工济；当政府策略为不救济时，流浪汉的最优策略是寻找工作；当政府选择救济时，流浪汉的最优策略是游荡。总之，作；当政府选择救济时，流浪汉的最优策略是游荡。总之，在纯策略下，没有一个策略组合构成纳什均衡。在纯策略下，没有一个策略组合构成纳什均衡。现在学习的是第67页，共78页68 局中人局中人I以概率以概率x1,x2,xm来分别选取纯策略来分别选取纯策略1,2 ,m；而；而局中人局中人II以概率以概率y1,y2,，yn来选用自己的来选用自己的纯策略纯策略1,2,n。于是：。于是：称称 x=(x1,x2,，xm)T,y=(y1,y2,，yn)T 分别分别为为I和和II的的混合策略混合策略。设设A，B分别为局中人分别为局中人I和和II的赢得矩阵，且都是为的赢得矩阵，且都是为mn矩阵。矩阵。现在学习的是第68页，共78页69则局中人则局中人I和和II的混合策略集为：的混合策略集为：当局中人当局中人I和和II的混合策略分别为的混合策略分别为x和和y时，局中人时，局中人I和和II的期望赢得值分别为：的期望赢得值分别为：现在学习的是第69页，共78页70如果一个混合策略组合如果一个混合策略组合(x*,y*)同时满足：同时满足：且且 则称策略组合则称策略组合(x*,y*)是一个混合策赂纳什均衡，其是一个混合策赂纳什均衡，其中中(x,y)分别是局中人分别是局中人I和和II的任意混合策略。的任意混合策略。例例6中假定政府以概率中假定政府以概率x选择救济概率选择救济概率1x选选择不救济，即政府的混合策略为择不救济，即政府的混合策略为(x,1x)；流浪汉以；流浪汉以概率概率y选择寻找工作，以概率选择寻找工作，以概率1y选择游荡，即流浪选择游荡，即流浪汉的混合策略为汉的混合策略为(y,1y)。那么政府的期望赢得函数为：。那么政府的期望赢得函数为：现在学习的是第70页，共78页71同样，流浪汉的期望赢得函数为：同样，流浪汉的期望赢得函数为：令令得得令令得得现在学习的是第71页，共78页72 这就是说，在混合策略均衡中，流浪汉在对付政府给定这就是说，在混合策略均衡中，流浪汉在对付政府给定的混合策略下，最优策略是以的混合策略下，最优策略是以15 的概率选择寻找工作的概率选择寻找工作,而而以以45 的概率选择游荡，即：的概率选择游荡，即：在混合策略均衡中，政府在对付给定流浪汉的混合策在混合策略均衡中，政府在对付给定流浪汉的混合策略下，最优策略是：略下，最优策略是：由于纳什均衡要求每个局中人的混合策略是在给定对方由于纳什均衡要求每个局中人的混合策略是在给定对方的混合策略下的最优选择，因此策略组（的混合策略下的最优选择，因此策略组（X,Y）构成唯）构成唯一的纳什均衡一的纳什均衡现在学习的是第72页，共78页73 对于上述的混合策略纳什均衡，可以这样来理解：如果对于上述的混合策略纳什均衡，可以这样来理解：如果政府认为流浪汉选择工作的概