第11章 博弈论.ppt

1、,博 弈 论,Game Theory,主要内容,引言 完全信息静态博弈（有鞍点的博弈、混合策略、纳什均衡） 完全信息静态博弈（非零和的情况、纳什均衡）,1 引 言,在社会活动、经济管理、军事活动中，经常会遇到具有竞争性或利益相对抗的现象，例如下棋、打桥牌、体育竞赛、市场竞争、军事斗争等。竞争的各方总是想用最好的策略击败对方，取得尽可能好的结果，这就是博弈现象。,早期工作 1912年E.Zermelo “关于集合论在象棋对策中的应用” 1921年E.Borel 引入最优策略 1928年J.V.Neumann证明了一些猜想 产生标志 1944年J.V.Neumann和O.Morgenstern 对

2、策论与经济行为 发展成熟 Nash均衡、经济博弈论、信息不对称对策和广义对策,约翰纳什（JOHN F.NASH）美国人 (1928- ),约翰海萨尼（JOHN C. HARSANYI）美国人(1928-),莱因哈德泽尔腾1930年生于德国,1994年，三人获得诺贝尔经济学奖，在非合作博弈的均衡分析理论方面做出了开创性贡献，对博弈论和经济学产生了重大影响。,1996年诺奖授予两位博弈论与信息经济学研究专家莫里斯、维克瑞 2001年诺奖授予阿克洛夫、斯彭斯、斯蒂格利茨，表彰他们在柠檬市场、信号传递和信号甄别等非对称信息理论研究中的开创性贡献 2005年诺奖授予有以色列和美国双重国籍的罗伯特奥曼和美

3、国人托马斯谢林，以表彰他们在博弈论领域作出的贡献,什么是博弈论？,所谓博弈是指局中人按一定规则，在充分考虑其他局中人可能采取的策略的基础上，从自己的策略集中选取相应策略，并从中得到回报的过程。 博弈是一种特殊的决策。在决策论中，决策者的对手是大自然；在博弈论中，代替大自然的是有理性的人，因而任何一方做出决定时，都必须考虑其他对手可能作出的反应。,构成博弈的三个要素：,1.局中人(Players)：是指参与竞争的各方，它可以是一个人，也可以是一个集团，但局中人必须是有决策权的主体，而不是参谋或从属人员。在博弈中局中人可以有两方，称为二人博弈；也可以有多方，称为多人博弈，在多人博弈中又可分为结盟和

4、不结盟的情况。,2.策略(Strategies)：指局中人所拥有的对付其他局中人的手段、方案的集合。在静态博弈中，策略必须是一个独立的完整的行动，而不能是若干相关行动中的某一步。,例如，在齐王和田忌赛马的博弈中，双方都有六个策略： (上,中,下)，(上,下,中)，(中,上,下)，(中,下,上)，(下,中,上)，(下,上,中)，这六个策略形成一个策略集合。 相应每个局中人的策略选择形成的策略组称为一个局势。,3.收益函数(Payoff function)：指一局博弈后各局中人的输赢得失，用正的数字表示局中人的赢得，负的数字表示局中人的损失。显然，收益函数的取值与局中人选定的策略有关，于是一局博弈

5、的“得失”是“局势”的函数。,博弈论的研究建立在下述假设前提下：即参与博弈的各局中人都是理性的。,“博弈中一个理性的决策必定建立在预测其他局中人的反应之上。一个局中人将自己置身于其他局中人的位置，并为他着想从而预测其他局中人将选择的行为，在这个基础上该局中人决定自己最理想的行动。”,博弈的三个要素，即局中人，策略集和收益函数构成了博弈信息，根据不同信息可对博弈做如下分类：,1.按局中人对信息掌握情况分为：完全信息博弈和不完全信息博弈；,2.按局中人采取行动的次序分为：如果同时采取行动或在互相保密情况下采取行动，称为静态博弈；如果采取行动有先后，后采取行动的人可以观察到前面人采取的行动，称为动态

6、博弈。,我们只研究完全信息静态博弈。,完全信息是指所有局中人对其他局中人各自策略集以及不同局势下的收益函数都有完全的了解。,2 完全信息静态博弈(一),设博弈中只有局中人A，B； 局中人A的策略集为 局中人B的策略集为,21 二人零和博弈,博弈的三个要素的矩阵表示（局中人A的收益）,局中人A的收益函数可用如下的矩阵表示：,二人零和博弈也称为矩阵博弈。,博弈可表为,例1 写出“石头、剪子、布”游戏的收益矩阵。石头赢剪刀1分，布赢石头1分，剪刀赢布1分。,解：甲的策略集为石头，布，剪刀 乙的策略集为石头，布，剪刀,例2 写出齐王和田忌赛马中齐王的收益矩阵。 （赢一场得一千金）,解：,齐王的收益矩阵

7、：,22 具有鞍点的博弈,通过下面的例3说明，什么是局中人的最优纯策略，如何求出这个纯策略以及博弈解和博弈值的概念。,例3：,博弈过程的描述：从收益表中可知，甲方的最大收益是19，他当然希望得到这个值，于是甲使用策略 对付乙。但是乙方已估计到甲方的心理而使用策略 对付甲，使他不但得不到19，反而要输掉12。此时甲也估计到乙方的心理，使用策略 ，使乙得不到12反而输掉6。当甲方使用策略 时，乙方使用任何策略都要输，当然他希望输得少一些，因此乙方只能使用策略 ，这时甲赢得2，乙输掉2，达到了平衡，博弈结束。,我们注意到，博弈论是研究有理智的局中人在每一个局势下采取的行动。他们在选择策略时，要考虑到

8、对方总是采取对自己最不利的策略来对抗。基于这一原则，最优策略不是冒险性的结果，而是审慎的留有余地的周密安排。 如果双方都不存在冒险心理，为了达到最佳结局，甲必须计算他的每个策略与乙的各策略博弈后的结果，从而求出使用每个策略带来的最坏收益，再从这些最坏收益中选出一个最大收益值，这个值对应的行策略就是甲方的最优纯策略。,同样乙方应从收益表中每列找出最大正数（恰为乙方输掉的数值），为了减少损失，应从这些数字中求出最小数，它所对应的列策略为乙方的最优纯策略。,计算过程如下：,几点说明：,1.在有鞍点的矩阵博弈中，鞍点可以不唯一。例如：,2.策略的优超性。,说明：这种做法可能会丢掉一些最优解，但不会影响

9、博弈的结论，如果上面的不等式有严格不等式，就不会出现丢解的现象了。,利用优超性化简收益矩阵,利用策略的优超性化简下面的矩阵博弈，并求出局中人的最优纯策略和博弈值。,3.有鞍点的博弈是少数情况，大量的博弈问题不存在鞍点，齐王的收益矩阵就不存在鞍点。,博弈问题的实例1：甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来。如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，否则重新开始。写出该对策中各局中人的策略集合及甲的收益矩阵，并回答局中人是否存在某种出法比其他出法更为有利。,课堂讨论题目,博弈问题的实例2：某城市由汇合的三条河分割为三个区，城市居民中40%住在A区，

10、30%住在B区，30%住在C区。现有甲、乙两公司要在市内修建超级市场，甲公司建两个，乙公司建一个。每个 公司都知道，如果在一个区内建两个超市，则两个市场平分该区业务；如果某区建一个超市，则独揽该区业务，若某区无超市其业务平均分散在三个超市中，每个公司都想把超市建在营业额最多的地方。 (1)将该问题表达成一个矩阵博弈，并写出甲公司的收益矩阵； (2)甲、乙两公司的最优策略是什么？在两公司都取得最优策略时，它们各占有多大的市场份额？,23 无鞍点矩阵博弈的混合策略,1. 22无鞍点矩阵博弈的特殊解法,例4,该矩阵博弈显然不存在鞍点。对他们的博弈过程作出如下的描述：,2. 无鞍点矩阵博弈的线性规划解

11、法,例5,解：设A的混合策略为 B的混合策略为,解：L2得最优单纯形表如下,例6 求齐王与田忌赛马中双方的最优混合策略,解：齐王的线性规划为,解得齐王的最优混合策略为,问题：理论上齐王应赢得一千金，但是实际比赛中他为什么输掉一千金？,在无鞍点的矩阵博弈中，双方采取何种纯策略是应当保密的。,3.无鞍点矩阵博弈的布朗(Brown)算法,布朗(Brown)算法是一种近似算法，给定局中人A的收益矩阵,算法步骤：,（1）甲方任选一行，然后乙方选择与该行中最小元素相对应的那一列； （2）在第（1）步里乙方所选的列中，与最大元素相对应的行即为甲方应选的行； （3）乙方把到目前为止甲方选择的各行求和，并选择与

12、最小和元素对应的列； （4）甲方把到目前为止乙方选择的列求和，并选择与最大和元素对应的行。如果要求迭代的次数已达到，转第（5）步，否则转回第（3）步；,（5）分别计算博弈值 的上界 和下界,（6）令 是甲方选择i行的次数比例； 是乙方选择j列的次数比例。 分别为甲、乙的近似混合策略。,例7 用布朗算法求解矩阵博弈（迭代10次）,24 纳什均衡(Nash equilibrium),纳什均衡是博弈论的基础。在二人零和博弈中，双方寻求的最优解是一种均衡解，达到这种均衡时，无论是纯策略解还是混合策略解，只要其他局中人不改变自己的策略，则任何一方单独改变自己的策略只能带来收益或效用的减少，因此这些均衡解

13、也称为纳什均衡。换言之，纳什均衡是一种策略组合，它是每个局中人的策略对其他局中人策略的最优反应。纳什证明了在任何非合作有限博弈中，都存在至少一个纳什均衡。,3 完全信息静态博弈(二),现在研究二人非零和博弈,31 用划线法求具有纯策略的纳什均衡,例8 二人博弈如下表所示,解：先利用策略的优超性简化双元矩阵。,纳什均衡是每个局中人策略对其他局中人策略的最优反应。对于A来说，针对B分别采取策略 时， A的最优反应分别是策略 其收益值分别是5、6、4。按划线法，在这几个数字下分别划一横线；对于B来说，相对于A采取的策略 ，B的最优反应策略是 ，分别在对应的收益值6,6下划横线。 如果收益值 下都有横

14、线，这一对值就是纳什均衡解，对应的策略组合为 本题中，纳什均衡解为(4,6)，对应的策略组为,纳什均衡解为(4,6)，对应的策略组为,32 著名的博弈例子,例9 囚徒困境问题：（1950年数学家塔克任美国斯坦福大学教授，在给一些心理学家讲演时，对当时正在研究的博弈问题作了形象的描述）设有甲、乙两名嫌疑因同一桩罪行被捕，警方希望他们坦白并提供对方犯罪证据，规定如两人均坦白各判刑3年；如一方坦白另一方不坦白，坦白一方从轻释放，不坦白一方判刑8年；如两人均不坦白，由于犯罪事实证据不足，罪名不能成立，只能每人各判1年，分析甲、乙两名犯罪嫌疑人的各自策略和纳什均衡解。,解：,根据划线法纳什均衡解是(坦白

15、,坦白)。但是从表中明显看出，两名犯罪嫌疑人最好的结局是(-1,-1)，即双方均不坦白。如何理解这一矛盾的结果呢？ 本例因双方都担心对方会坦白，对自己不利，损失很大，所以均采取坦白的策略。 这个例子说明，就个人利益和群体利益而言，在考虑最优解时，出发点不同，结果也不同，个人的理性选择与群体的理性选择是不一致的。在某些情况下，群体的理性选择要比个人角度选得好。,通俗地说，集体利益不一定和个人利益相矛盾，从集体来考虑最优，有时比各自去考虑最优还好些。如果每个人只考虑自己自由行动，社会就会乱作一团，而道德、法律的约束使大家都受益。在商业竞争中，为争夺市场，各自竞相削价，结果是大家受损。如果能共同协商

16、，合理分配市场，对每一方都有好处。这是在多人博弈中，要讨论的联盟、合作问题。,33 混合策略下的纳什均衡解,例10,从表中看出甲队的策略甲2劣于甲1，乙队的策略乙1劣于乙2，根据策略优超性可将它们从表中删除，得下面的表：,用划线法得不到纯策略的纳什均衡解，只能使用线性规划解法求混合策略解。,求解两个线性规划分别得到下面的结果：,34 多重纳什均衡和聚点,很多博弈问题具有一个以上的纳什均衡，这种情况下如何判断或预期最终结局呢？可使用聚点的概念。,聚点(focal point)：是指一些现实生活中的局中人依据一些信息或理性，在某个特定均衡上的协同。,例11 一对恋人商量周末活动安排，是看足球赛还是听音乐会，已知不同策略组合