第12章运筹学课件 对策论.pptx

1、第十二章对策论OperationalResearch(OR)对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介对策现 象和对 策论一、对策现象和对策论对策论(game theory)亦称博弈论或竞赛论，是 研究具有对抗或竞争性质现象的数学理论和方法。它既是 现代数学的一个新分支，也是运筹学的一个重要学科。对 策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般日常生活等有着密切联系，并且处理问题的方法又有明显特色，所以日益引起广泛的 重视。齐王赛马对策现 象的三 要素二、对策现象的三要素1.局中人(players)：参与对抗的各方；2.策略(str

2、ategies)：局中人选择对付其它局中人的 行动方案称为策略；3.赢得函数(支付函数)(payoff function)：各局中人 各自使用一个对策就形成一个局势，一个局势决定了 个局众人 的对策结果（量化）。“齐王赛马”齐王在各局势中的对策结果（单位：千金）对策问题 举例及对 策的分类三、对策问题举例及对策的分类例 1市场购买力争夺问题据预测，某乡镇下一年的饮食品购买力将有 4 000 万元。乡镇企业和中心城市企业饮食品的生产情况是：乡镇企业 有特色饮食品和低档饮食品两类，中心城市企业有高档饮 食品和低档饮食品两类产品。它们争夺这一部分购买力的 结局见下表(单位：万元)。问题是乡镇企业和中

3、心城市企 业应如何选择对自己最有利的产品策略。乡镇策略中心城市企业的策略出售高档饮食品出售低档饮食品出售特色饮食品20003000出售一般饮食品10003000对策问题 举例及对 策的分类例 2销售竞争问题假定企业,均能向市场出售某一产品，不妨假定他们可于 时间区间 0,1 内任一时点出售。设企业在时刻 x出售，企业在时刻 y 出售，则企业的收益(赢得)函数为：若 xy问这两个企业各选择什么时机出售对自己最有利?在这个例 子中，企业,可选择的策略均有无穷多个。对策问题 举例及对 策的分类例 3费用分摊问题假设沿某一河流有相邻的 3 个城市 A，B，C，各城市可单 独建立水厂，也可合作兴建一个大

4、水厂。经估算，合建 一个大水厂，加上敷设管道的费用，要比单独建 3个小水 厂的总费用少。但合建大厂的方案能否实施，显然要看总 的建设费用分摊得是否合理。如果某个城市分摊到的费用 比它单独建设水厂的费用还多的话，它显然不会接受合作 的方案。问题是应如何合理地分摊费用，使合作兴建大水 厂的方案得以实现?对策问题 举例及对 策的分类例 4拍卖问题最常见的一种拍卖形式是先由拍卖商把拍卖品描述一番，然 后提出第一个报价。接下来由买者报价，每一次报价都要比 前一次高，最后谁出的价最高，拍卖品即归谁所有。假设有n 个买主给出的报价分别为 p1,pn,且不妨设 pnpn-1p1,则 买主 n 只要报价略高于

5、pn-1，就能买到拍卖品，即拍卖品实际 上是在次高价格上卖出的。现在的问题是，各买主之间可能 知道他人的估价，也可能不知道他人的估价，每人应如何报 价对自己能以较低的价格得到拍卖品最为有利?最后的结果又 会怎样?对策问题 举例及对 策的分类例 5囚犯难题设有两个嫌疑犯因涉嫌某一大案被警官拘留，警官分别对两 人进行审讯。根据法律，如果两个人都承认此案是他们干的，则每人各判刑 7 年；如果两人都不承认，则由于证据不足，两人各判刑 1 年；如果只有一人承认，则承认者予以宽大释 放，而不承认者将判刑 9 年。因此，对两个囚犯来说，面临着 一个在“承认”和“不承认”这两个策略间进行选择的难题。对策问题

6、举例及对 策的分类对策论中将问题根据不同方式进行分类:(1)根据局中人的个数，分为二人对策和多人对策；(2)根据各局中人的赢得函数的代数和是否为零，分为零和对 策与非零和对策；(3)根据各局中人间是否允许合作，分为合作对策和非合作对策；(4)根据局中人的策略集中的策略个数，分为有限对策和无限 对策。此外，还有许多其他的分类方式，例如根据策略的选择是否与时间有关，可分为静态对策和动态对策；根据对策模型的数 学特征，可分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策等。对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介矩阵对策 的基本理 论二人有限零和对策：（又称矩

7、阵策略）局中人为 2；每局中人的策略集中策略权目有限；在任一局势下，两个局中人的赢得之和总等于零，即 一个局中人的所得值恰好等于另一局中人的所失值，双 方的利益是完全对抗的。记矩阵对策为:G=S1,S2；A 的策略集 的赢得矩阵 的策略集“齐王赛马”即是一个矩阵策略。矩阵对策 的纯策略矩阵对策 的纯策略例6设有一矩阵对策 G=S1,S2;A，其中：采取 1至少得益-8 22 3-10 4-31：采取 最多损失 9 226取大则取 2max min aij=2ij取 小 则 取 2 min max aij=2ji平衡局势(2,2)，这个局势就是双方均可接受的，且对双22方来说都是一个最 稳3 妥

8、的结果。因此，和 应分别是局中人和的最优纯策略。矩阵对 策的纯 策略成立，记其值为 VG，则称 VG为对策的值，称使其成立的ij纯局势(*,*)为 G 在纯策略意义下的解(或平衡局势)，ij称 *和 *分别为局中人和的最优纯策略。定义 1设 G=S1,S2;A 为一矩阵对策，其中 S1=1,m，S2=1,n，A=(aij)mn。若矩阵对 策的纯 策略定理 1 中式子的对策意义是：一个平衡局势(i,j)应具有这*样的性质：当局中人选择了纯策略 *后，局中人为了使其i所失最少，只能选择纯策略 *，否则就可能失的更多；反之，j当局中人选择了纯策略 *后，局中人为了得到最大的赢得*j也只能选择纯策略

9、i，否则就会赢的更少，双方的竞争在局势(i,j)下达到了一个平衡状态。*矩阵对策 G=S1,S2;A 在纯策略意义下有解的充要条件是：存在纯局势(i,j)，使得对任意 i 和 j，有 aij ai j*ai j定理1矩阵对 策的纯 策略例7设有矩阵对策 G=S1,S2;A，其中解有i*=1,3j*=2,4故(1,2)，(1,4)，(3,2)，(3,4)都 是对策的解，且 VG=8矩阵对 策的纯 策略ai j=ai j1 12 2若(i1,j1)和(i2,j2)是对策 G的两个解，则(i1,j2)和(i2,j1)也是对策 G 的解。矩阵对策的值是惟一的，即当一个局中人选择了最优纯策略 后，他的赢

10、得值不依赖于对方的纯策略。一般对策的解可以是不惟一的，当解不惟一时，解之间 的关系具有下面两条性质：性质 1(无差别性)若(i1,j1)和(i2,j2)是对策G 的两个解，则性质 2(可交换性)矩阵对 策的混 合策略设矩阵对策 G=S1,S2,A当max min aij min max aij 时，ijji不存在最优纯策略求解混合策略。二、矩阵对策的混合策略矩阵对 策的混 合策略记则分别称 S1 和 S2 为局中人和的混合策略集(或策略集)；*12对 xS*和 yS*，称 x 和 y 为混合策略(或策略)，(x,y)为混合局势(或局势)。局中人的赢得函数记成称 G*=S1,S2;E 为对策 G

11、 的混合扩充。*定义 2设有矩阵对策 G=S1,S2;A，其中矩阵对 策的混 合策略记其值为 VG，则称 VG为对策 G 的值，称使上式成立的混合局势(x*,y*)为 G 在混合策略意义下的解(或平衡局势)，称 x*和 y*分别为局中人和的最优混合策略。定义 3设 G*=S1,S2;E 是矩阵对策 G=S1,S2;A 的混合扩充。如果*定理 2矩阵对策 G 在混合策略意义下有解的充要条件是：存在 x*S1,y S2，使得对任意 xS1 和yS2，有*E(x,y*)E(x*,y*)E(x*,y)矩阵对 策的混 合策略例8考虑矩阵对策 G=S1,S2;A，其中已知 G 在纯策略意义下无解，故设 x

12、=(x1,x2)和y=(y1,y2)分别为局中人和的混合策略，则局中人的赢得的期望是矩阵对 策的混 合策略取 x*=(1/4,3/4)，y*=(1/2,1/2)，则E(x*,y*)=9/2，E(x*,y)=E(x,y*)=9/2，即有E(x,y*)E(x*,y*)E(x*,y)故 x*=(1/4,3/4)和 y*=(1/2,1/2)分别为局中人和 的最优策略，对策的值(局中人的赢得的期望值)为 VG=9/2。矩阵对 策的基 本定理12设 x*S*,y*S*,则(x*,y*)为对策 G 的解的充要条件是：12设 x*S*,yS*，则(x*,y*)为 G 的解的充要条件是：存在数 v,使得 x*和

13、 y*分别是下列不等式组的解，且v=VG。j=1,2,.,ni=1,2,.,mi=1,2,.,mj=1,2,.,n三、矩阵对策的基本定理定理 3对任意 i=1,m 和 j=1,n，有E(i,y*)E(x*,y*)E(x*,j)定理 4矩阵对 策的基 本定理设(x*,y*)是矩阵对策 G 的解，v=VG，则*(1)若 xi 0,则*(2)若 yj 0,则(3)若*,则 xi=0(4)若,则y*j=0定理 5对任一矩阵对策 G=S1,S2;A，一定存在混合策略意义下 的解。定理 6矩阵对 策的基 本定理设 G1=S1,S2,A 为一矩阵对策，且 A=-AT为斜对称矩阵(亦称这种对 策为对称对策)，

14、则(1)VG=0(2)T1(G)=T2(G)其中，T1(G)和 T2(G)分别为局中人和的最优策略集。定理 7设有两个矩阵对策G1=S1,S2,A1，G2=S1,S2,A2,其中A1=(aij),A2=(aij+L)，L 为一任意常数，则(1)VG2=VG1+L (2)T(G1)=T(G2)定理 8设有两个矩阵对策 G1=S1,S2,A，G2=S1,S2,A,其中 0，为一任 意常数，则(1)VG2=VG1 (2)T(G1)=T(G2)定理 9对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介矩阵对 策的解 法一、图解法例 9用图解法求解矩阵对策 G=S1,S2,A，其中解

15、设局中人的混合策略为(x,1-x)T，x 0,1。02571x132ABB1B2B3图解法解得 x=3/11,VG=49/11。所以，局中人的最优策略为 x*=(3/11,8/11)T下面求局中人的最优策略：局中人的最优混合策略只由 2和 3组成设 y*=(y1,y2,y3)T 为局中人的最优混合策略，则由*E(x*,1)=23/11+78/11=62/1149/11=VG，根据定理 6，112必有 y*=0。又因 x*=3/110,x*=8/110，再根据定理6，可由求得 y2=9/11,y3=2/11。所以，局中人的最优混合策略*为 y*=0,9/11,2/11T方程组 法二、方程组法例

16、10求解矩阵对策 G=S1,S2;A，其中 A为1 2 3 4 5方程组法12 3 4 54严格优于 1，所以划去 1同理，划去第二行，第三列，第四列和第五列剩下的矩阵中第一行优于第三行，所以划去第三行易知 A1没有鞍点，由定理 12.6 求出方程组和的非负解方程组法于是，以矩阵 A 为赢得矩阵的对策的一个解就是：线性规划 法三、线性规划法例 11利用线性规划方法求解下述矩阵对策，其赢得 矩阵为：由定理 5 可知，可将其化成两个互为对偶的线性规划解问题：线性规划 法解上述线性规划，得因此对策问题的解为：对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介二人无限 零和对策一、

17、二人无限零和对策表示方法：G=S1,S2;H其中 S1和 S2中至少有一个是无限集合，H 为局中人的赢得 函数。局中人的至少赢得：局中人的至多所失：二人无限 零和对策ij设 G=S1,S2;H 为二人无限零和对策。若存在 *S1,*S2,使得*记其值为 VG，则称 VG为对策 G 的值，称使该式成立的(i,jij*)为 G 在纯策略意义下的解，*,*分别称为局中人和 的最优纯策略。ij12(*,*)为 G=S,S;H 在纯策略意义下的解的充要条件是：对任意 iS1,jS2,有H(i,j)H(i,j)H(i,j)*定义4定理10二人无限 零和对策例 12 设局中人、互相独立地从 0,1 中分别选

18、择一 个实数 x 和 y，局中人的赢得函数为 H(x,y)=2x2-y2。对策中，局中人希望 H 越大越好，局中人则希望 H 越小越好。图中给 出了 H(x,y)的等值线，通过对该图的分析，不难看出双方竞争的平衡局势为(1，1)，即 i=1,j=1 分别为局中人和的最*ij优纯策略，VG=1。可以验证，对(*,*)=(1,1)，定理10 的等式是成立的。二人无限 零和对策无限对策的混合策略：局中人和的混合策略 X 和 Y 分别为策略 集 S1和 S2上的概率分布(或分布函数)，混合策略集记为和。若用 x,y 表示纯策略，FX(x),FY(y)表示混合策略X，Y 的 分布，则局中人的赢得函数可以

19、有以下 4 种形式：H(x,y)以及二人无限 零和对策(X*,Y*)为对策 G=S1,S2;H 的解的充要条件是：对任意 X,Y，有 H(X,Y*)H(X*,Y*)H(X*,Y)当 S1=S2=0,1，且 H(x,y)为连续函数时，称这样的对策 为连续对策。定义 5如果有则称 VG为对策 G 的值，称使上式成立的(X*,Y*)为对策 G的解，X*和 Y*分别为局中人和的最优策略。定理 11对任何连续对策，一定有v1=v2。例 13(生产能力分配问题)某公司下属甲、乙两个工 厂，分别位于 A，B 两市。设两厂总生产能力为 1 个单位，两市对工厂产品的总需求也是 1 个 单位。如果 A 市的需求

20、量为 x,则 B 市的需求量为 1-x，这时只要安排 A 厂的生产能 力为 x，就能使供需平衡。但现在不知道 A 市的确切需求 量 x 是多少，如果安排 A 厂的生产能力为 y，则将产生供需 上的不平衡。不平衡的程度可用数值表示为：二人无限零和对策公司的目标是选择 y，使得达到极小。定理12二人无限 零和对策如果以市场需求为一方，公司为另一方，则以上问题可转化 为一个连续对策问题，其中S1=S2=0,1这个对策求解的结果为：公司方的最优策略(为纯策略)是 y*=1/2，即两个厂各生产一半；市场需求方的最优策略(为 混合策略)是：分别以 0.5 的概率取 0 和 1，即要么全部需求 都集中在 A

21、 市，要么都集中在 B 市，且两种情况发生的概率 相等。该对策的值为 VG=2，即当公司和市场均选择各自的 最优策略时，两市中需求大于供给的平均程度为 2。多人非合 作对策二、多人非合作对策所谓非合作对策，就是指局中人之间互不合作，对策略的选择 不允许事先有任何交换信息的行为，不允许订立任何约定，矩 阵对策就是一种非合作对策。一般非合作对策模型可描述为：(1)局中人集合：I=1,2,n;(2)每个局中人的策略集：S1,S2,Sn(均为有限集)；(3)局势：s=(s1,sn)S1Sn；(4)每个局中人 i 的赢得函数记为 Hi(s),一般说来，一个非合作 n 人对策一般用符号 G=I,Si,Hi

22、 表示。多人非合 作对策它的含义是：在局势 s=(s1,sn)中，局中人 i 将自己的策 略由 si换成 si,其他局中人的策略不变而得到的一个新局0势。如果存在一个局势 s,使得对任意 si Si,有0iHi(s)Hi(ss 0)则称局势 s 对局中人 i 有利，也就是说，若局势 s 对局中人 i 有利，则不论局中人 i 将自己的策略如何置换，都不会得 到比在局势 s 下更多的赢得。显然，在非合作的条件下，每个局中人都力图选择对自己最有利的局势。多人非合 作对策iHi(s)Hi(ss 0)则称 s 为非合作对策 G 的一个平衡局势(或平衡点)。ij当 G 为二人零和对策时，(*,*)为平衡局

23、势的充要条件是：对任意 i,j,有aij*ai*j*ai*ji若对任意 iI,ziS*，有Ei(xzi)Ei(x)则称 x 为非合作 n 人对策 G 的一个平衡局势(或平衡点)。定义 6如果局势 s 对所有的局中人都有利，即对任意 iI,si Si,有0定义7多人非合 作对策x*TAy*xTAy*xS*21x*TBy*x*TByyS*定理 13(Nash 定理)非合作 n 人对策在混合策略意义下的平衡局势一定存在。对于二人有限非零和对策(亦称为双矩阵对策)，Nash 定理的 结论可表述为：一定存在 x*S1,y S2，使得*多人非合 作对策例14求解 22 阶双矩阵对策，其中解已知 Q=a11

24、+a22-a21-a12=5,q=a22-a12=2,=q/Q=2/5 R=b11+b22-b21-b12=5,r=b22-b21=3,=r/R=3/5代入双矩阵对策解的公式，得y2/5 y=2/5 y2/5y=00y1y=1多人非合 作对策解不等式组，得到对策的 3 个平衡点：(x,y)=(0,0),(3/5,2/5),(1,1)由 E1(x,y)=5xy-2(x+y)+1 E2(x,y)=5xy-3(x+y)+2可得E1(3/5,2/5)=E2(3/5,2/5)=1/5E1(0,0)=1,E2(0,0)=2,E1(1,1)=2E2(1,1)=1三、合作对策合作对策的基本特征是参加对策的局中

25、人可以进行 充分的合作，即可以事先商定好，把各自的策略协调起来；可以在对策后对所得到的支付进行重新分配。合作的形式是 所有局中人可以形成若干联盟，每个局中人仅参加一个联盟，联盟的所得要在联盟的所有成员中进行重新分配。在合作对策中，每个局中人如何选择自己的策略不 是主要研究的问题，应当强调的是如何形成联盟，以及联盟 的所得如何被合理分配（即如何维持联盟）的问题。合作对策合作对策合作对策的可行解是一个满足下列条件的 n 维向量 x=(x1,x2,xn):满足上式的向量 x 称为一个分配。合作对策的两个基本要素是：局中人集合 I特征函数 v（S）其中 I=1，2，n，S 为 I 的任一子集，也就是任

26、何一个可能形成的联盟，v(S)表示的是联盟 S 在对策中的所得。例 15（产品定价问题）设有两家厂商（厂商 1，厂商 2）为同一 市场生产同样产品，可选择的竞争策略是价格，目的是赚得最 多的利润。已知两个厂商的需求函数为Q1=12-2P1+P2 Q2=12-2P2+P1其中，P1，P2分别为两个厂商的价格，Q1，Q2分别为市场对两个厂商产品的需求量（实际销售量）；又知，两家厂商的固定 成本均为 20 元。合作对策（1）厂商 1 的利润函数为：1=P1Q1-20=12P1-2P1+P1P2-202利润最大化时的P1:同理可得：厂商 1 对厂商 2的价 格的反应函数厂商 2 对厂商 1 的价格 的

27、反应函数厂商1定价 4元定价 6元厂商2定价 4元 定价6 元12，1220，44，2016，16不合作：（12，12）（Nash 均衡）合作：（16，16）（双赢）合作对策对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介一、冲突分析的理论基础和发展冲突是具有不同目标的两个或更多的个人或团体为了利益、资 源等进行抗争所造成的一种对立状态。Howard 的偏对策(metagame)理论Bennett 的超对策(supergame,又称为误对策)理论冲突分析 简介Fraser 和 Hipel 在对偏对策进行了改进的基础上，提出了 冲突分析方法。二、冲突分析的建模与分析建模：系

28、统分析人员要以系统的方式将所掌握的有关冲突的 全面信息描述出来稳定性分析：根据建立的模型和所能获得的数据，确定冲突 可能的解决方案（冲突的可能的解必须对参加冲突的各方面都 是稳定的(即没有再改进的必要)）冲突分析的建 模与分 析选手(player)方案或选择(option)策略(strategy)结果(outcome)古巴导弹 危机的案 例分析三、古巴导弹危机的案例分析1.模型的建立时间点：美国刚在古巴发现苏制导弹的 1962 年 10月17 日附近。选手：美国和苏联方案：美国有两个方案：对古巴的导弹基地进行空袭(简称空袭)或实行军事封锁(简称封锁)，美国可任选一个方案，或两个 都选，或都不选

29、(即通过外交等途径解决冲突)。苏联的方案是撤出部署的导弹(简称撤出)或进一步激化局 势(简称激化)，如用导弹袭击美国，或既不撤出也不激化，即维持现状。古巴导弹危 机的案例分 析古巴导弹危机中美国和苏联的方案及结果注：“1”表示选择了一个方案，“0”表示没有选择该方案方案美国空袭010101010101封锁001100110011苏联撤出000011110000激化000000001111十进 制数01234567891011古巴导弹危机中美国的偏好序列古巴导弹危机中苏联的偏好序列古巴导弹 危机的案 例分析古巴导弹 危机的案 例分析2.稳定性分析偏好序列下面标出的数字表示了由该结果进行单方面改进

30、所得 到的结果(称为 UI)。所谓一个单方面改进是指一个选手在当前 结果下，假定其他选手的策略不变所能得到的更好的结果。古巴导弹 危机的案 例分析对任一给定的可行结果，可以确定以下四种稳定性，(1)合理稳定如果对一个结果 q 来说，选手 A 不存在单方面改进，即该选手 所选择的策略已经是另一选手选定策略下的最佳策略，则结 果 q 对选手 A 来说是合理的，具有合理稳定性，记为“r”。(2)相继稳定如果对一个结果 q 来说，选手 A 的所有单方面改进都会由于选 手 B 所采取的可靠行动而导致一个还不如不改动的结果(所谓 可靠行动是指采取行动的选手可以得到比原来更好的结果)，这种由于试图有所改进反

31、而得到更差结果的情况，阻止了选 手进行单方面的改进所造成的稳定性称为相继稳定，记为“s”。古巴导弹 危机的案 例分析(3)不稳定当选手 A 没有可靠行动来阻止选手 B 在结果 q 下的全部单方 面改进时，则称结果 q 对选手 B 是不稳定的(即还有可能再 得到改进)，记为“u”。(4)同时稳定如果两个选手同时从对他们都不稳定的一个结果 q 出发而改 变策略的话，可能会导致一个对他们中的一个或两个都不 利的结果，也就是可能受到同时制裁，这时，称结果 q是同 时稳定的，在“u”上再加一个“/”，这种情形并不普遍，但进行稳定性分析时仍是要考虑的。古巴导弹 危机的案 例分析(8)结束如果一个结果对所有

32、选手来说是稳定的，即具有上述三种稳定性 之一，则称该结果为一个均衡，它构成了冲突的一个可能解。在有两个选手 A，B 的冲突中，对选手 A 的结果 q 的稳定性分析可 按以下步骤进行：(1)选手 A 的结果 q 有无单方面改进是(2)对选手 A 的单方面改进，选手 B 是否有单方面改进是是是(3)选手 B 的所有单方面改 进对 A 来说是否比 q 更好否(4)除了 q,选手是否 还有单方面改进否否否(7)q 对选手 A 是不稳定的(5)q 对选手 A 是相继稳定的(6)q 对选手 A是合理的 考虑是否进行同时稳定性的检验古巴导弹 危机的案 例分析3.古巴导弹危机的分析结论 该冲突有两个均衡：结果 4 和6结果 6 对苏联是合理的，对美国是相继稳定的，因此它很可能 就是冲突的结局。冲突分析中选手的偏好不需要具有传递性，而且偏好序列 也不要求严格有序，允许有同等的偏好；对偏好程度也不必量化，只要求能给出顺序比较。再有，只有当一个选手的行动会导致对 其自身有利的结果时，他才会考虑制裁另一个对手。这些主要特 点都使得冲突分析比经典的对策论、偏对策等更切合实际，更能 灵活地适应各种环境，从而更具有优越性。