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