清华大学博弈论讲义.ppt

清华诚志,1,博弈论与经济学思维 2003年7月26-27日 湖北襄樊,杨云岗 博士,清华诚志,2,一、介绍博弈论,（一）概念，什么是博弈论 1概念：博弈论 ，又称对策论，是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论，是研究竞争的逻辑和规律的数学分支。简单地说，博弈论是研究决策主体在给定信息结构下如何决策以最大化自己的效用，以及不同决策主体之间决策的均衡。,清华诚志,3,张维迎的定义,“博弈论是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题的”也就是说，当一个主体，好比说一个人或一个企业的选择受到其他人、其他企业选择的影响，而且反过来影响到其他人、其他企业选择时的决策问题和均衡问题。所以在这个意义上说，博弃论又称为“对策论”.,清华诚志,4,2.囚徒困境的例子,A. W. Tucker的囚犯困境(Prisoners Dilemma)： 囚徒B,囚徒A,坦白,抵赖,坦白,抵赖,清华诚志,5,囚徒困境说明了什么,在（坦白、坦白）这个组合中，和都不能通过单方面的改变行动增加自己的收益，于是谁也没有动力游离这个组合，因此这个组合是纳什均衡，也叫非合作均衡。 囚徒困境反映了个人理性和集体理性的矛盾。如果和都选择抵赖，各判刑年，显然比都选择坦白各判刑年好得多。当然，和可以在被警察抓到之前订立一个“攻守同盟“，但是这可能不会有用，因为它不构成纳什均衡，没有人有积极性遵守这个协定,显然最好的策略是双方都抵赖.,清华诚志,6,囚徒困境的意义,“囚徒的两难选择”有着广泛而深刻的意义。个人理性与集体理性的冲突，各人追求利己行为而导致的最终结局是一个“纳什均衡”，也是对所有人都不利的结局。他们两人都是在坦白与抵赖策略上首先想到自己，这样他们必然要服长的刑期。只有当他们都首先替对方着想时，或者相互合谋(串供)时，才可以得到最短时间的监禁的结果。,清华诚志,7,对经典经济学的冲击,“纳什均衡”首先对亚当斯密的“看不见的手”的原理提出挑战。按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。 国富论：“通过追求(个人的)自身利益，他常常会比其实际上想做的那样更有效地促进社会利益。” 从“纳什均衡”我们引出了“看不见的手”的原理的一个悖论：从利己目的出发，结果损人不利己，既不利己也不利他。两个囚徒的命运就是如此。从这个意义上说，“纳什均衡”提出的悖论实际上动摇了西方经济学的基石。,清华诚志,8,怎么看待这个问题,二者是对立统一的，范围不同，在非竞争环境中效率会受到损失；在完全竞争条件下，边际利润等于边际成本，达到效率,清华诚志,9,NASH均衡条件下的行为规则,合作是有利的“利己策略”。但它必须符合以下黄金律：按照你愿意别人对你的方式来对别人，但只有他们也按同样方式行事才行。 所谓“己所不欲勿施于人”。但前提是人所不欲勿施于我。,清华诚志,10,3博弈论的要素,博弈论的提法可能太过于学术化，容易让人们退避三舍。其实它有一个非常通俗的名字-游戏理论（博弈论的英文名字叫做“ “，如果直译，就是“游戏理论“）。博弈论在我国还有一个名字，叫对策论。这些名字都很好理解，博弈字面意思就是赌博、下棋，赌博和下棋当然是游戏了，赌博和下棋的时候常常要千方百计地应付对手，自然是要讲究对策了。,清华诚志,11,参与人 players,一个博弈中的决策主体，他的目的是通过选择行动（或战略）以最大化自己的支付（效用水平）。参与人可能是自然人，也可能是团体，如企业，国家等。 重要的是：每个参与人必须有可供选择的行动和一个很好定义的偏好函数。不做决策的被动主体只能被当作环境参数。,清华诚志,12,虚拟参与人pseudo-player,为了分析方便，自然nature被当作虚拟参与人。 自然代表决定外生随机变量的概率分布的机制。比如房地产开发中市场需求的大小。,清华诚志,13,行动 ACTIONS OR MOVES,参与人在博弈的某个时点的决策变量。 （坦白） N个参与人的行动的有序集称为行动组合 （坦白，抵赖）。,清华诚志,14,行动的顺序,对于博弈的结果非常重要。有关静态和动态博弈的区分就是基于行动的顺序做出的。 同样的行动集合，行动的顺序不同，每个参与人的最有决策就不同，博弈的结果也不同。尤其在不完全信息博弈中，后行动者依赖观察先行动者的行动来获取信息。,清华诚志,15,信息 information,参与人有关博弈的知识，特别是有关自然的选择，其他参与人的特征和行动的知识。 完美信息perfect information:指一个参与人对其他参与人的行动选择有准确的理解，即每个信息集只包含一个值。,清华诚志,16,共同知识common knowledge,所有参与人知道每一步的信息集。,清华诚志,17,战略strategies,参与人在给定信息集的情况下的行动规则，它规定参与人在什么时候选择什么行动。 战略与行动：战略是行动的规则而不是行动本身。 在静态博弈中，战略和行动是相同的。 战略必须是完备的，要给出参与人在每一种可想象得到的情况下的行动选择。,清华诚志,18,支付payoff（效用utility）,在一个特定的战略组合下参与人得到的确定效用水平，或是指参与人得到的期望效用水平。,清华诚志,19,均衡equilibrium,指所有参与人的最优战略的组合。,清华诚志,20,（二）历史沿革,犹太法典(Talmud)中一个男人如何将死后的财产发给三个妻子的难题 . 博弈理论开始于1944年由冯诺依曼（Von Neumann）和摩根斯坦恩（Morgenstern）合作的博弈论和经济行为（The Theory of Games and Economic Behaviour）一书的出版。 世纪年代以来，纳什、泽尔腾、海萨尼等人使博弈论最终成熟并进入实用。,清华诚志,21,三位大师主要的贡献,1950年和1951年纳什的两篇关于非合作博弈论的重要论文，彻底改变了人们对竞争和市场的看法。他证明了非合作博弈及其均衡解，并证明了均衡解的存在性，即著名的纳什均衡。从而揭示了博弈均衡与经济均衡的内在联系。因为在现实世界中，非合作博弈要比合作博弈普遍得多。,清华诚志,22,Selten and Harsanyi,泽尔腾（1965）将纳什均衡的概念引入了动态分析，提出了“精炼纳什均衡”概念；以及进一步刻画不完全信息动态博弈的“完备贝叶斯纳什均衡”,而海萨尼则发展了刻画不完全信息静态博弈的“贝叶斯纳什均衡”（19671968）。总之，他俩进一步将纳什均衡动态化，加入了接近实际的不完全信息条件。他们的工作为后人继续发展博弈论，提供了基本思路和模型,清华诚志,23,（三）分类和主要思想,博弈论根据其所采用的假设不同而分为合作博弈理论和非合作博弈理论。两者的区别在于参与人在博弈过程中是否能够达成一个具有约束力的协议。倘若不能，则称非合作博弈 。 合作博弈强调的是集体主义，团体理性 ，是效率、公平、公正；,清华诚志,24,非合作博弈,而非合作博弈则主要研究人们在利益相互影响的局势中如何选择策略使得自己的收益最大，强调个人理性、个人最优决策，其结果是有时有效率，有时则不然。目前经济学家谈到博弈论主要指的是非合作博弈，也就是各方在给定的约束条件下如何追求各自利益最大化，最后达到力量均衡。,清华诚志,25,例子,比如两家企业、合作建设一条的生产线，协议由方提供生产的技术，方则提供厂房和设备。在对技术和设备进行资产评估时就形成非合作博弈，因为每一方都试图最大化己方的评估值，这时方如果能够获得方关于技术的真实估价或参考报价这类竞争情报，则可以使自己在评估中获得优势；同理，方也是一样。至于自己的资产评估是否会影响合作企业的总体运行效率这样的“集体利益“，则不会非常重视。这就是非合作博弈，参与人在选择自己的行动时，优先考虑的是如何维护自己的利益。,清华诚志,26,顺序和信息,博弈论非常强调时间和信息的重要性，认为时间和信息是影响博弈均衡的主要因素。在博弈过程中，参与者之间的信息传递决定了其行动空间和最优战略的选择；同时，博弈过程中始终存在一个先后问题，参与人的行动次序对博弈最后的均衡有直接的影响。,清华诚志,27,分类,博弈的划分可以从参与人行动的次序和参与人对其它参与人的特征、战略空间和支付的知识、信息，是否了解两个角度进行。把两个角度结合就得到了种博弈：完全信息静态博弈，完全信息动态博弈，不完全信息静态博弈，不完全信息动态博弈,清华诚志,28,博弈的分类及对应的均衡,清华诚志,29,主要思想,博弈论并不是经济学的一个分支，它只是一种方法，这也是为什么许多人将其看成数学的一个分支的缘故。博弈论已经在政治、经济、外交和社会学领域有了广泛的应用，它为解决不同实体的冲突和合作提供了一个宝贵的方法。 在对参与者行为研究这一点上，博弈论和经济学家的研究模式是完全一样的。经济学越来越转向人与人关系的研究，特别是人与人之间行为的相互影响和相互作用，人与人之间利益和冲突、竞争与合作，而这正是博弈论的研究对象。,清华诚志,30,我们从博弈中学习什么,博弈论告诉人们，要学会理解他人都有自己的思想，每个个体都是理性的，所以必须了解竞争对手的思想。商业关系被认为是一种相互作用。但博弈论并不是疗法，并不是处方，它并不告诉你该付多少钱买东西，这是计算机或者字典的任务。博弈论只是提供一些关系的例证，一些有用的解决问题的方法。这种思维方法也许是企业家应该学习的。对于经济学家，也许需要学习它的理论模型，它的实验方式,清华诚志,31,几个例子,1.囚徒困境在经济学和生活中的例子 中东石油输出国 OPEC限产 几乎所有的卡特尔都会遭到失败，原因就在于卡特尔的协定（类似囚犯的攻守同盟）不是一个纳什均衡，没有成员有兴趣遵守。那么是不是不可能有卡特尔合作成功了？理论上，如果是无限期的合作，双方考虑长远利益，他们的合作是会成功的。但只要是有限次的合作，合作就不会成功。比如合作次，那么在第九次博弈参与人就会采取不合作态度- 参与者效用多重性，漂亮女生,清华诚志,32,价格战,厂家价格大战的结局也是一个“纳什均衡”，而且价格战的结果是谁都没钱赚。因为博弈双方的利润正好是零。竞争的结果是稳定的，即是一个“纳什均衡”。这个结果可能对消费者是有利的，但对厂商而言是灾难性的。所以，价格战对厂商而言意味着自杀。 引伸出两个问题，一是竞争削价的结果或“纳什均衡”可能导致一个有效率的零利润结局。 二是如果不采取价格战，作为一种敌对博弈论(rivalry game)其结果会如何呢？每一个企业，都会考虑采取正常价格策略，还是采取高价格策略形成垄断价格，并尽力获取垄断利润。如果垄断可以形成，则博弈双方的共同利润最大。这种情况就是垄断经营所做的，通常会抬高价格。另一个极端的情况是厂商用正常的价格，双方都可以获得利润。,清华诚志,33,有趣的联系,我们又引出一条基本准则：“把你自己的战略建立在假定对手会按其最佳利益行动的基础上”。事实上，完全竞争的均衡就是“纳什均衡”或“非合作博弈均衡”。在这种状态下，每一个厂商或消费者都是按照所有的别人已定的价格来进行决策。在这种均衡中，每一企业要使利润最大化，消费者要使效用最大化，结果导致了零利润，也就是说价格等于边际成本。 在完全竞争的情况下，非合作行为导致了社会所期望的经济效率状态。如果厂商采取合作行动并决定转向垄断价格，那么社会的经济效率就会遭到破坏。这就是为什么WTO和各国政府要加强反垄断的意义所在。,清华诚志,34,占优战略,不论其他参与人选择什么战略，它的最优战略是唯一的，这样的最优战略被称为占优战略。 重复剔除严格劣战略,清华诚志,35,智猪博弈,每次按出10个萝卜，按者支付2个单位成本，大先，（9，1）小先（6，4）同时（7，3） 小猪,大猪,按 等待,按,等待,清华诚志,36,实际生活中的智猪博弈,“搭便车”现象； 公共物品，穷人和富人修路博弈（中产阶级对社会的稳定作用）； 大股东对管理者的监督； 天塌下来有高个子顶着。,清华诚志,37,性别战与先动优势,双均衡的性别战,女 足球 芭蕾,男 足球 芭蕾,清华诚志,38,纯战略与混合战略,如果一个战略规定参与人在每一个给定的信息情况下只选择一种特定的行动，称为纯战略。 如果一个战略规定参与人在给定的信息情况下以某种概率分布随机地选择不同的行动，称为混合战略。,清华诚志,39,监督博弈的纳税检查,A 为应纳税款，C为检查成本， F是偷税罚款。假定 CA+F。不存在纯战略纳什均衡。,纳税人,税收机关 检查 不检查,纳税人 逃税 不逃税,清华诚志,40,纳税检查边际,S 为税务机关检查的概率，E为纳税人逃税概率。给定E，税收机关选择检查与否的期望收益： K(1,E)=(A-C+F)E+(A-C)(1-E) =EF+A-C K(0,E)=0E+A(1-E)=A(1-E) 解K(1,E)= K(0,E)，得：E=C/(A+F)纳税人逃税概率小于E,税收机关的最优决策是不检查，否则则反。,清华诚志,41,逃税边际,给定S，纳税人选择逃税与否的期望收益是： K(S,1)=(-A-F)S+0(1-S)=-(A+F)S K(S,0)=-AS+(-A)(1-S)=-A 解K(S,1)= K(S,0) ，得S=A/(A+F)即，如果税收机关检查的概率小于S,纳税人的最优选择是逃税，否则交税。 混合纳什均衡是S,E,即税收机关以S的概率查税，而纳税人以E的概率逃税。,清华诚志,42,污染博弈 贸易自由与壁垒 博弈论是一个强有力的分析工具。现在，它不仅在经济学领域、在军事、政治、商业征战、社会科学领域以及生物学等自然科学领域都有非常重大的影响，工程学中如控制论工程也少不了它。帮助大家形成博弈论的基本概念，实际上它是非常精深的。现在与它紧密联系的经济学分支是信息经济学。信号游戏、拍卖形式、激励机制、委托人-代理人理论和公共财政学是博弈论和信息经济学研究的重要课题,清华诚志,43,对博弈论的两种极端评价,从20世纪70年代末期，学者们逐渐形成一个共识，当一个人或群体与他或他们的博弈论对手都能以理性的方式做出决策行为的时候，那就是博弈论大显身手的场合。 有人将博弈论比作Mendel的遗传理论和Darwin的自然选择对生物学的影响，或者Newton的天体力学对物理学的奠基作用。 真正的社会并不严格是博弈论的理想对象，无论是股票市场上的投机现象，还是受制于传统文化的惯性影响下的体制选择。如同混沌动力系统理论带给人们的初始兴奋之后，博弈论并不具有有历史上像物理学中理论的预测能力。,清华诚志,44,四.博弈论与运筹学,运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提供理论和方法。 运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。,清华诚志,45,数学规划,数学规划的研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足约束条件下的极大极小值问题。,清华诚志,46,排队论,排队论是运筹学的又一个分支，它有叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等,清华诚志,47,搜索论,搜索论是由于第二次世界大战中战争的需要而出现的运筹学分支。主要研究在资源和探测手段受到限制的情况下，如何设计寻找某种目标的最优方案，并加以实施的理论和方法。在第二次世界大战中，同盟国的空军和海军在研究如何针对轴心国的潜艇活动、舰队运输和兵力部署等进行甄别的过程中产生的。搜索论在实际应用中也取得了不少成效，例如二十世纪六十年代，美国寻找在大西洋失踪的核潜艇“打谷者号”和“蝎子号”，以及在地中海寻找丢失的氢弹，都是依据搜索论获得成功的。,清华诚志,48,五、完全信息动态博弈,纳什均衡的问题：多均衡、单选择性（静态性），不可置信威胁的存在性（市场进入博弈） 泽尔腾剔除了不可置信威胁战略，减少了纳什均衡的个数 扩展型表述的要素：参与人、参与人行动的时点、行动集合、信息，支付函数,清华诚志,49,子博弈精炼纳什均衡,当参与人的战略在每一个子博弈中都构成纳什均衡。每一个子博弈都是最优的。 城市姑娘爱上农村小伙子导致姑娘父亲的反应。 承诺行动（commitment),当事人使自己威胁战略变得可信的行为。,清华诚志,50,例子（要挟诉讼，曾诺行动与精炼均衡的关系）,成功可能性非常小，目的是希望和解得到补偿。,不指控,指控,要求S,拒绝,接受,起诉,放弃,（0，0),P,P,D,P,(S-C,-S),(TX-P-C,-TX-D),(-C,0),清华诚志,51,原告指控的目的本身意味着TX-C-P,只要胜诉的可能大于0，原告将起诉。如果STX+D,被告将接受原告的赔偿请求。S的范围（TX,TX+D),赔偿结果为TX+D/2,清华诚志,52,如果TX+D/2C+P,原告提起诉讼；即使TXC+P仍有可能。（ TX+D/2-C-P，-TX-D/2）案件私了。,清华诚志,53,不完全信息静态博弈,不了解对方的偏好、战略空间及各种战略组合下的利润水