运筹学课程对策论

对策论

GameTheory

“理智人”间的竞争策略1二、引言三、矩阵对策对策现象对策论对策问题的三个基本要素对策问题的分类具有鞍点的矩阵对策无鞍点的矩阵对策最优混合策略的解法本章主要内容一、对策论导论2

博弈论导论—博弈论的演化历程

最早的对策论思想产生于中国春秋时期，孙武的《孙子兵法》现代经济博弈论起源可以追溯到1944年，由美国著名数学家冯·诺依曼（JohnNeumann）与经济学家奥·摩根斯坦（OscarMorgensten）合著的《博弈论与经济行为》31994：纳什（Nash）、海萨尼（J.Harsanyi）、泽尔腾（R.Selten）

1996莫里斯（JamesA.Mirrlees）和维克瑞（WilliamVickrey）纳什的基本贡献是证明了非合作博弈均衡解及其存在性，建立了作为博弈论基础的“纳什均衡”概念；海萨尼则把不完全信息纳入到博弈论方法体系中；泽尔腾的贡献在于将博弈论由静态向动态的扩展，建立了“子博弈精练纳什均衡”的概念。这两位经济学家的贡献集中于运用博弈论对现实经济问题的解释。博弈论导论—博弈论和诺贝尔经济学奖4这三位作为不对称信息市场理论的奠基人被授予诺贝尔经济学奖，以表彰他们分别在柠檬品市场等不对称信息理论研究领域做出的基础性贡献。这些贡献发展了博弈论的方法体系，拓宽了其经济解释范围。贡献主要在于通过实验室实验来测试根据经济学理论而做出预测的未知或不确定性。是对以博弈论为基础构建的理论模型进行实证证伪工作的一大创举。他们通过博弈理论分析增加了世人对合作与冲突的理解。其理论模型应用在解释社会中不同性质的冲突、贸易纠纷、价格之争以及寻求长期合作的模式等经济学和其他社会科学领域。博弈论导论—博弈论和诺贝尔经济学奖2001：阿克洛夫（Akerlof）、斯宾塞（Spence）、斯蒂格利茨（Stiglitz）2002：弗农史密斯（Smith）2005：奥曼（Aumann）、谢林（Schelling）5约翰·纳什

1928年生于美国约翰·纳什（JOHNF.NASH）美国人(1928-)，由于他与另外两位数学家在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响，而获得1994年诺贝尔经济奖。纳什均衡(完全信息静态博弈)卡内基—梅隆大学科学硕士、普林斯顿大学数学博士。主要研究领域：博弈论和微分几何学。主要贡献：非合作博弈均衡、经济博弈论6约翰·福布斯·纳什7

《美丽心灵》是一部关于一个真实天才的极富人性的剧情片。故事的原型是数学家小约翰-福布斯-纳什(Nash),普林斯顿大学的著名教授，诺贝尔经济学奖的获得者(1994年)，他在博弈理论方面的巨大发现甚至改变了我们的日常生活。但另一方面，纳什也是一个悲剧人物，他的一生为精神分裂症所困。在历经苦痛的人生里，纳什一方面在运用自己那优美绝伦的大脑，另一方面也在与他的大脑进行着顽强的抗争。最终理性为他带来了心灵的和平，纳什终于摘取了科学事业上的桂冠。

8

囚徒困境问题纳什均衡：（坦白，坦白）

-1，-1

-10，0

0，-10

-8，-8囚徒B坦白抵赖坦白抵赖囚徒A坦白从宽，抗拒从严著名博弈问题9

市场进入阻挠

0，300

0，300

-10，0

40，50在位者默许斗争进入不进入进入者纳什均衡：（进入，默许）（不进入，斗争）著名博弈问题10智猪博弈按钮食槽著名博弈问题11假设猪圈里有一头大猪、一头小猪。猪圈的一头有猪食槽，另一头安装着控制猪食供应的按钮，按一下按钮会有10个单位的猪食进槽，但是谁按按钮就会首先付出2个单位的成本，若大猪先到槽边，大小猪吃到食物的收益比是9∶1；同时到槽边，收益比是7∶3；小猪先到槽边，收益比是6∶4。那么，在两头猪都有智慧的前提下，最终结果是小猪选择？？？。12小猪行动等待大猪行动5

14

4等待9

-10

0小猪的选择将是等待13

齐王赛马著名博弈问题齐王与田忌赛马.双方约定:从各自的上中下三个等级

的马中各选一匹参赛;每匹马只能参赛一次;每次比赛双方各出一匹马,负者要付给胜者千金.不同等级的马,高等级优于低等级;同等级的马中,齐王的马优于田忌的马;如何对策???14引言

对策现象各种比赛：体育、棋类等比赛

政治方面：外交谈判经济方面：贸易谈判、争夺市场、各种经营竞争等

具有竞争或对抗性质的现象15对策论

对策论是关于相互影响的决策者的研究。是研究具有竞争或者对抗性质现象的理论与方法。研究对策现象的一种定量分析理论与方法。也称为博弈论参加竞争或对抗的各方具有不同的利益和目标，为了达到各自的利益和目标，各方必须考虑对手的各种可能的行动方案，并力图选择对自己最有利或最合理的方案。16对策问题的三个基本要素

1．局中人（players）一个对策中有权决定自己行动方案的对策参加者称为局中人。通常用I表示局中人的集合，如果有n个局中人，则I＝{1,2,…,n}。

对策论中对局中人的一个重要的假设：每个局中人都是“理性的”、等智力的。

2．策略（strategies）对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。一般每个局中人的策略集S中至少应包括两个策略。17

如“齐王与田忌赛马”中：

齐王有6个策略：{(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)}

田忌有6个策略：{(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)}3.赢得函数(支付函数)（payofffunction）

局势：每个局中人从各自的策略集合中选取一个策略参加对策，形成的一个处于竞争的策略组。如：齐王选策略(上中下)，田忌选策略(中上下)，构成一个局势{(上中下)，(中上下)}。局势的得失总和为0。一局对策的得失，即局中人的得失。叫赢得（支付）函数，对有限策略集，叫赢得（支付）矩阵。18设si是第i个局中人的一个策略，则n个局中人的策略形成的策略组合s＝(s1，s2,…,sn)就是一个局势。若记S为全部局势的集合，则S＝S1×S2×…×Sn当一个局势s出现后，应该为每一局中人i规定一个赢得值(或所失值)Hi(s)。显然，Hi(s)是定义在S上的函数，称为局中人i的赢得函数。在“齐王赛马”中，局中人集合I＝{1,2}，齐王和田忌的策略集可分别用表示。这样,齐王的任一策略αi和田忌的任一策略βj就构成了—个局势sij，如果α1=(上,中,下)，βl＝(上,中,下)．则在局势s11下，齐王的赢得为H1(s11)＝3，田忌的赢得为H2(s11)=-3当局中人、策略集和赢得函数这3个要素确定后，一个对策模型也就给定了。19例：两个赌博参加者甲、乙各出示一枚硬币，在不让对方看见的情况下，将硬币放在桌子上，若两个硬币都呈正面或都呈反面则甲得1元，乙付出1元；若两个硬币一个呈正面另一个呈反面则乙得1元，甲付出1元。局中人：甲、乙策略：si={正面，反面}i=1,2局势：S={(正,反)，(正,正)，(反,正)，(反,反)}支付函数：H1(正,反)=-1，H1(正,正)=1，H1(反,正)=-1，H1(反,反)=1，H2(正,反)=1，H2(正,正)=-1，H2(反,正)=1，H2(反,反)=-120对策问题的分类对策动态对策静态对策结盟对策不结盟对策微分对策联合对策合作对策有限无限二人多人二人多人零和非零和零和非零和零和非零和零和非零和21矩阵对策二人有限零和对策（对抗对策）：局中人2个每个局中人的策略集中的策略数目有限每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。221(上中下)2(上下中)3(中上下)4(中下上)5(下上中)6(下中上)1(上中下)31111-12(上下中)1311-113(中上下)1-131114(中下上)-1113115(下上中)11-11316(下中上)111-113齐王田忌aij23

例：某单位秋季决定冬季取暖用煤的贮量。冬季用煤贮量在较暖、正常和较冷情况下分为10、15和20吨。设冬季煤价也随寒冷程度而变，在上述三种情况下分别为100、150和200元/吨，已知秋季煤价为100元/吨，冬季气象未能予知，问秋季合理贮煤量为多少？设局中人甲为：贮煤量决策者；局中人乙为：未来冬季气候。费用总和=秋季贮煤量费用+冬季补购煤量费用1(较暖)2(正常)3(较冷)1(10吨)-(10×100)=-1000-(10×100+5×150)=-1750-(10×100+10×200)=-30002(15吨)-(15×100)=-1500-(15×100)=-1500-(15×100+5×200)=-25003(20吨)-(20×100)=-2000-(20×100)=-2000-(20×100)=-2000甲乙aij则赢得矩阵为：2425矩阵对策问题解的假设：例：设有一矩阵博弈G={S1，S2；H}，其中H=具有鞍点的矩阵对策26如果双方部不想冒险、都不存在侥幸心理，而是考虑到对方必然会设法使自己所得最少这一点，就应该从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据，这就是所谓“理智行为”，也是对策双方实际上可以接受并采取的一‘种稳妥的方法。

从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据局中人1局中人2H=H=27定义1：设G={S1，S2；H}为一矩阵博弈，其中S1={α1,α2,…,αm}，S2={β1,β2,…,βn}，H=(aij)m×n，若等式成立。记，称vG为博弈G的值，使上式成立的纯局势为纯策略下的解，分别称为局中人1，2的最优纯策略。

定理1

矩阵博弈G={S1，S2；H}在纯策略意义下有解的充要条件是：存在纯局势，使得对任意i和j，有

≤≤28充分性：29必要性：30定义2（鞍点）设f(x,y)为一个定义在x∈A

及y∈B上的实值函数，若存在x*∈A，y*∈B，使得对一切x∈A

和y∈B有f(x,y*)≤f(x*,y*)≤f(x*,y)则称(x*,y*)为函数f的一个鞍点。鞍点行元素变化趋势列元素变化趋势具有鞍点对策求解：31无鞍点的矩阵对策两小孩玩游戏：1(石头)2(剪刀)3(布)1(石头)01-12(剪刀)-1013(布)1-10甲乙aij赢得矩阵为：（无鞍点）32定义3（混合策略）33定义4（混合局势、混合策略意义下的解、对策值）34例题：35

定理4（存在性定理）：任意一个给定的矩阵对策一定有解，局中人双方总有一个最优混合策略，即：36

定理5：若矩阵对策值为V，则下面两组不等式的解是局中人甲、乙的最优混合策略：37

矩阵对策在混合策略意义下的解总是存在的，求解的基本方法为线性规划法。38

⑴对局中人甲，希望对策的局势值越大越好。若第i行所有元素≥第l行所有元素，即j=1,2,…,n，则甲理智，必采用i纯策略而舍去l纯策略，不影响最优策略和策略鞍点值。此时称i策略为对l策略的优势策略。⑵对局中人乙，希望对策的局势值越小越好。若第j列所有元素≤第k列所有元素，即，i=1,2,…,m，

则乙理智，必采用j纯策略而舍去k

纯策略，不影响最优策略和策略鞍点值。此时称j策略为对k

策略的优势策略。

若存在优势策略，则支付矩阵阶数可降低优势原则：（某一策略对其他策略具有支配作用）39由G得到一个新的矩阵策略G’40原赢得矩阵按优势原则简化后赢得矩阵41第4行优于第1行划去第1行42第3行优于第2行划去第2行43第1列优超于第3列划去第3列44第2列优超于第4列划去第4列45划去第5列1/3第1列+2/3第2列优超于第5列倍数之和不能超过1（概率组合）第1行优超于第3行划去第2行46

解析法：适用于缩减后的支付矩阵为n×n方阵的无鞍点对策问题。

设甲的混合策略为(x1,x2,…,xn)，乙的混合策略为(y1,y2,…,yn)。赢得期望值为：

47⑴甲的期望值方程为：

⑵乙的期望值方程为：

解得甲的最优混合策略为

X*=(x1*,…,xn*);

解得乙的最优混合策略为Y*=(y1*,…,yn*)

对策值V=V*

48例：求两小孩玩游戏对策的最优混合策略无鞍点且不能缩减。

设甲的混合策略为(x1,x2,x3)，乙的混合策略为(y1,y2,y3)。得失期望值为：

49⑴甲小孩的期望值方程为：

⑵乙小孩的期望值方程为：

解得甲的最优混合策略为

X*=(1/3,1/3,1/3),V*=0

解得乙的最优混合策略为

Y*=(1/3,1/3,1/3),V*=0;

甲、乙两小孩均以1/3的同等概率取石头、剪刀、布纯策略，在不考虑其它因素的前提下，多局竞争的结果是最终和局，谁也不占优势，反映双方纯策略实力相等。50例：求齐王与田忌赛马对策的最优混合策略

无鞍点且不能缩减

设齐王的混合策略为(x1,x2,x3,x4,x5,x6)

田忌的混合策略为(y1,y2,y3,y4,y5,y6)

51⑴齐王的期望值方程为：

⑵田忌的期望值方程为齐王的最优混合策略为X*=(1/6,1/6,1/6,1/6,1/6,1/6)V*=1田忌的最优混合策略为Y*=(1/6,1/6,1/6,1/6,1/6,1/6),V*=1

52

拉格朗日乘子法：适用于缩减后的支付矩阵为n×n方阵的无鞍点对策问题。

设甲的混合策略为(x1,x2,…,xn)

乙的混合策略为(y1,y2,…,yn)。得失期望值为：

s.t.

,

即:s.t.

,

53求出最优混合策略和对策值，并且有：

54例：求下列对策的最优混合策略⑴解下列方程组：⑵解下列方程组：无鞍点且不能缩

设甲的混合策略为(x1,x2,x3)，乙的混合策略为(y1,y2,y3)。拉氏函数为：55解得乙的最优混合策略为Y*=(14/45,11/45,20/45),V*=29/45

解得甲的最优混合策略为

X*=(20/45,11/45,14/45),V*=29/45

注意：因为没有顾及变量非负的要求，解析法与拉氏法不是对所有的有解支付矩阵均能得到正确答案。例：求下列对策的最优混合策略。无鞍点且不能缩减56⑴解下列方程组：解