资源描述
博弈论,主讲 施锡铨,2004年3月,第一章 引论,应用及例题 基本理论,博弈论关注的是互相依存（interdependence）,每一个体猜测其他个体的选择是什么？ 每个人将采取什么样的行动？(当最优的行动依赖于其他人的所作所为时，这个问题尤其令人关注。) 这些行动产生什么样的结局？对于整个群体，这个结局好吗？ 如果群体不止一次地互相作用，会有任何差异吗？ 如果每一个体对群体内其他个体的特性没有把握，答案将发生怎样的变化？,取自经济学，政治学，财政金融，法律，甚至日常生活中的若干相互依存性事例,艺术品拍卖 (诸如在克里斯蒂（Christie）或索士比（Sotheby）拍卖行，那里待售出自布拉克（Braque）直至维罗内塞（Veronese）的艺术品)和债券拍卖（美国财政部为筹措联邦预算支出，以这种方式出售政府公债） 。 联合国的选举（ 例如，选举新的联合国秘书长） 。,动物争斗（争夺良好的栖息地以及种类中稀少的发情期雌性动物，等等）。 自然资源的可持续使用（像石油那样的可耗尽资源或像森林那样的可重建资源的提取形式） 。 运动会和工作场所的随机药物检测（选取少量运动员和工作人员进行核实使用违禁药物的测试） 。 破产法（详细说明在什么时候和有多少债权人可以从已破产的公司那儿收账） 。,“毒药”条款（该条款给予管理部门一定的权限以抵制不受欢迎者试图接管或兼并他们的公司） R&D开支（譬如，制药公司的研究开发费用） 第一次世界大战的壕沟战（在法德之间的边界地区，当军队连续数月地互相对峙时，掘进到敌方的战壕里去） OPEC（石油卡特尔，控制着世界石油产量的一半，因此，在决定人们支付油价方面拥有重要的发言权 群体项目（诸如为你们的博弈论课程准备案例研究）,博弈论,分析在一群举止行为颇具策略的理性人之间的相互作用的正规方法。,博弈论是考虑以下每一项条款的正规方法：,群体在任何博弈中有不止一个决策者；每一个决策者称为局中人 相互作用任何单个局中人的行为直接影响到群体内至少一个其他的局中人。 策略单个局中人在决定自己所取的行动时，会考虑到相互依存性。 理性在考虑到这种相互依存性时，每一个局中人会选择自己的最优行动。,来自日常生活中的例子,致力于一项群体项目，为博弈论课程准备案例研究：“群体”包括一起做案例的学生。他们之间的“相互作用”来自于这样的事实：为了写一篇论文，需要付出一定的工作量；因此，如果一个学生偷懒，另外的某个人在论文到期前的夜晚不得不投入额外的几个小时。“策略”运用包含了估计群体内总想占别人便宜者的可能性，“理性”参与需要对较好分数的好处与额外工作的成本仔细地进行比较。,（奥林匹克运动会中）中随机药物检测：“群体”由比赛运动员和国际奥林匹克委员会（IOC）组成。“相互作用”是两方面的，一方面是运动员之间的相互作用他们做出在训练安排中和不管什么情况下一样服禁药的决策；另一方面是在运动员与IOC之间的相互作用，后者需要维护运动的声誉。“理性策略”的应用需要运动员根据获胜的机会以及如果服用了兴奋剂之后被逮到的机会之间进行比较而作出决策。类似地，它要求IOC根据检测成本和清白声誉的价值而制定药物检测的程序和相应的惩罚措施。,经济与财政金融的例子,制药公司的R&D效果：某些评估表明，研究与开发（R&D）经费支出占美国制药公司年销售额的20%之多。以及平均来说，一种新药的开发成本大约为3亿5千万美元。公司自然关心诸如资金投入哪一条生产线，新药定价应多高，如何缩减与新药开发相伴的风险，等等问题。在这个例子中，“群体”是药物公司全体组成的集合。“相互作用”起因于药的最先开发者将获得最大的收益（由于专利权的缘故）。如果R&D经费的选取大小使得在确知竞争者对这条新药生产线进行投资的前提下能最大化从新药开发中得到收益，那么 “R&D” 经费是策略性的和是理性的。,债券拍卖：正常情况下，美国财政部通过拍卖形式处理政府证券*。主要的投标人是投资银行，如莱曼兄弟（Lehman Brothers） 或摩里尔林奇（Merrill Lynch）等（他们转而将证券出售给他们的客户）。因此，“群体”就是投资银行组成的集合。（实际上，从一次拍卖到又一次拍卖，这些投标人极少发生改变。）他们“互相作用和影响”着，因为其他人的标价决定了一个投标人是否分配到任何债券，也可能决定了投标人支付的价钱。如果投标基于可能的竞争上和在支付太多与得不到任何债券的风险之间达到适当的平衡，那么，“出价”是“理性的”和“策略的”。 * 这些证券是公债和国库债券，以及公共部门（或者他们的代理人，例如共同基金信托公司或养老基金等）所拥有的准金融债券。这些证券承诺在一个固定的周期（譬如，三个月，一年，或五年）后支付一笔钱。另外，他们也可能承诺在证券有效期内定期地支付固定额的钱款。,来自生物学与法律方面的例子,动物习性：刚过去的25年里，博弈论更吸引人的应用之一已经深入生物学领域，特别是关于动物之间争斗和竞争的分析。通常野生动物不得不为了稀少资源（诸如具繁殖能力的雌性动物或者动物的尸体）而竞争；于是，为了发现这些资源或者为了从发现者那儿夺取资源，它们会有所付出。问题在于这种做法会导致代价昂贵的争斗。这里，“局中人群体”是眼睛盯着同一猎物的所有动物。由于资源的有限性，它们互相影响着。假如它们考虑竞争对手做出反应，选择就是“策略”，如果由于这种“策略”满足了它们的短期目标，譬如解决了饥饿，或者满足了它们的长期目标，譬如保持了物种的繁衍不绝，这样的选择是“理性的”。,破产法：在美国，一旦公司宣告破产，它的财产不再由单独的债权人扣押，而代之以安全保管，直至公司与它的债权人达成某种程度的谅解。但是，债权人可以在破产宣告之前促使法庭去收帐 (虽然通过这种做法债权人可能逼迫公司陷入破产)。这里，债权人“群体”内的“相互作用”来自于这样的事实：个别债权人能够成功地依法占有的钱就不再可能属于其他任何一个人。“策略”的选取需要估计其他债权人可能有多大耐心，而“理性的”选择包含了在早收账与逼迫公司不必要的破产之间的权衡。,例题,1. 拿子游戏 (Nim和Marienbad) 这是两个室内游戏，玩法如下。有两堆火柴，和两个局中人。游戏从局中人1开始，此后局中人轮流行动。在每个局中人的轮次里，他可以从两堆火柴的任一堆中拿走任何数量的火柴。只要任何一堆中尚有剩余的火柴，则要求每个局中人拿走一定数量且不能空手而返，但每个轮次只能从一堆中取火柴。 在“拿子游戏”Nim中，无论那个局中人，取走最後火柴者算赢。而在Marienbad，谁拿走最后的火柴，那么这个局中人就算输。,2. 投票,假设有两个竞争议案，这里表示为与，3个议员，投票人1，2和3，他们投票决定是否通过这些议案。结局可能会是两种中的某一个：要么通过和中的一个，要么议员们没有通过任何一项议案（延缓而以原来法律代替）。投票过程如下：首先，让议案A与议案B互相竞争；然后，竞争的获胜方与原来法律互相竞争，为简便起见，我们将原法律称为“都不赞成”（或者N）。在两轮投票中的每一轮，获多数票的法案算胜出。三个议员在可适用的选择中有如下偏好： 投票人1： 投票人2： 投票人3： （这里， 表示“喜欢议案A甚于喜欢议案B”）,3. 囚徒困境,克雷卡尔文 认罪 不认罪 认罪 5，5 0，15 不认罪 15，0 1，1,总 结,博弈论是研究相互依存性的。它研究局中人群体中的互相作用，这些局中人根据策略地分析群体内其他人可能做什么而进行理性的选择。 博弈论可以应用于诸如自然资源的使用，选取联合国秘书长，动物习性，和OPEC的生产策略等广泛不同的问题。 博弈论的创建追溯到150年前。但是，学科的主要发展是近代的，大约在最近50年期间，使得博弈论成为经济学与数学范围内最年轻的学科之一。 如拿子游戏和囚徒困境这种博弈的策略分析可以揭示理性局中人将达到的结局。对于整个局中人群体来说，这些结局并不总是称心的。,博弈的规则：,每个博弈通过一组规则进行，规则必须说明四件事： “谁”（Who）在参与策略地互相作用的局中人群体。 他们以“什么”（What）来参与每个局中人可使用的策略供替代的行动或选择。 每个局中人“何时”（When）行动（以什么顺序） 从参与博弈所作的选择中，他们得到（或失去）“多少”（How much） 关于规则的共同知识 每一个局中人知道博弈的规则，并且这一现象是众所周知的。,“谁”，“什么”，和“何时”：展开型,展开型 规则的一种图形表示式。主要的画图形式称为博弈树，是由一个根和若干枝依次排列组成。,信息集和策略,在展开型里怎样表示同时行动,信息集 决策结的集合，局中人不能区分这些决策结 策略 局中人的策略是指在局中人需要做出选择的信息集处可采取的行动。,策略是行动的蓝图，在每一个决策结告诉局中人如何去选择。由于局中人在任何一个信息集里不能区分决策结，策略详细说明了在每一个结所做的行动。,正则（或策略）型,博弈规则中另一种表示方式称为正则型或策略型 策略型 有关“局中人，他们每一个人可使用的策略，和每人的得益”的完整的一览表。,冯诺伊曼摩根斯坦效用函数,拿子游戏 Nim 假设在一堆中有2根火柴，在另一堆中有1根火柴。记这个布局为（2，1）。与赢相联的盈利数必定高于对应于输的盈利数；假设这些数分别为1与-1。,策略型表示式如下：,1 / 2 lL lR rL rR u 1, -1 1, -1 1,-1 1, -1 m -1, 1 -1, 1 -1, 1 -1, 1 d 1, -1 -1, 1 1, -1 -1, 1,投票博弈,假如一个投票人所赞成的议案通过，她得到的盈利为1。如果她的第二个选择通过，则盈利为0，如果她最不赞同的抉择通过，此时她的盈利是-1。,投票人2,投票人3,B,B,B,B,A,B,A,A,A,投票人1,投票人2,投票人3,A,N,0, -1, 1,1, 0, 0,囚徒困境,局中人1,局中人2,c,n,n,c,-15, 0,-1, -1,博弈的展开型,策略型 1 2 c n c -5, -5 0, -15 n -15, 0 -1, -1,总 结,1博弈规则必须明确说明局中人是“谁”，每个局中人可使用的选择是“什么”，和从局中人群体所作的一组选择中，每个局中人得到“多少”。 2博弈规则有两种主要的表示式，展开型和策略型。 3展开型是博弈的图形表示，它明确地说明了局中人选择的顺序，每个局中人有多少次选择（以及每次她可适用的选择），和对于任何选择序列每个局中人最终的盈利。 4策略型是这样的表示式，其中明确地说明了局中人的选择（策略）和每组选择集带来的的盈利。你可以把策略型视为博弈型式，局中人对所有的策略只做一次选择的。 5博弈中的盈利应当被视为冯诺伊曼-摩根斯坦效用。对于不确定情况，盈利应当在不确定性的所有可能解上取期望值而计算得到。,第2章 策略型博弈,策略型博弈 案例:艺术品拍卖的策略型 占优策略解 案例研究续：拍卖中的占优策略,策略型博弈,博弈的策略型由三项内容所确定： 1. 博弈中局中人的名单. 2. 每个局中人可使用的策略集. 3. 与任何策略组合（每个局中人一个策略）相对应的盈利.,盈利是冯诺依曼-摩根斯坦效用。最简单的博弈类型是两个局中人有两个策略的博弈。 策略型 : 局中人2 北 南 局中人1 高 1 , 2 1 , 2 (高,北), (高,北) (高,南),(高,南) 低 1 , 2 1 , 2 (高,北), (高,北) (高,南), (高,南),当局中人多于两个，以及每个局中人有两个以上的策略时，对策略型的三个分量使用下述符号： 局中人将标记为1，2，N。一个局中人代表将表示为第i个局中人。 局中人i的策略通常表示为si，一个特定的策略表示si*或si#。除了局中人i以外的所有其它局中人的策略选择记为s-i。 i 将表示局中人i的盈利(或冯诺依曼-摩根斯坦效用)函数。对于策略组合，s1*，s2*，sN*，其中每一个局中人相应于一个策略，局中人i的盈利将表示为i (s1*，s2*，sN*)。,囚徒困境 （c = 认罪，nc = 拒绝认罪）,卡尔文克雷 c nc c 0, 0 7, -2 cn -2, 7 5, 5,性别争端（F = 足球，O = 歌剧）,丈夫妻子 F O F 3, 1 0, 0 O 0, 0 1, 3,抛硬币打赌（Matching pennies） ( h = 正面, t = 反面),局中人1局中人2 正面 反面 正面 1，-1 -1，1 反面 -1，1 1，-1,鹰-鸽（或懦夫博弈） （t = 强硬, c = 退让）,局中人1局中人2 t c t -1, -1 10, 0 c 0, 10 5, 5,投票,对每一个投票者，在这个博弈中的策略有三个部分：在第一轮中如何投票和第二轮中如何投票，而在第二轮中的投票本身有两个分量。第一个分量是，如果议案A在第一阶段通过后在第二轮中投票人如何投票，第二分量是，如果（在第一轮中）议案B通过后，该投票人又将如何投票。特别地，每个投票人有下述8个策略可供选择*。 AAN; AAB; ANB; ANN; BAN; BAB; BNB; BNN; *当然，投票人知道她在第一轮中自己是怎样投票的。原则上，她的策略也可以根据这个信息。目前我们将略去这种复杂性，因为这样的话，每一个策略中分量的个数将增加到5替代原来的3。（为什么？）,与展开型的等价性,两种表示博弈的方式是等价的：每一个展开型博弈可以写成策略型且反之亦然。,案例：艺术品拍卖的策略型,艺术品拍卖：描述 假如我们被带入位于纽约洛克菲勒中心的索士比派克伯尼特的大型拍卖场之一。拍卖商站在房间前面的讲台上。她的旁边有一对随从举着待拍卖物件的影像。设想待拍卖的物件是雷诺伊（Renoir, 18411919）的一组绘画；你很想拥有标号为“#264”的那件可爱的咖啡吧景色。你必须开始做如下的事。 注册：如果你打算投标，必须在商品展销室的入口处注册。那里你将得到一块写有编号的拍卖牌。（为了注册，恐怕你需要一张信用卡。) 出价程序：一旦轮到标号#264，“你出价所必须做的就是举起你的拍卖牌并等待拍卖商理会你，你不必叫出你出价的数通常由拍卖商以10%的增量自动确定高一些的出价。你不必坐的毕恭毕敬；抓耳挠腮不能算作为一个出价（除非你与拍卖商事先就做了安排）。如果没有人超过你的出价，就是说，没有其他的拍卖牌举起，那么拍卖商敲下小木槌以结束拍卖。”,艺术品拍卖：策略型,局中人：注册的那些人 策略：考虑局中人策略的一个简单方法是认定局中人愿意举牌的最高价。 结局：最后一个举牌的拍卖者赢得雷诺依作品（抓耳挠腮者不能得到）。 盈利：赢者将付多少钱？,占优策略解,定义. 如果不管其他局中人选择什么样的策略，局中人i的策略si的盈利严格地大于他的所有其他策略的盈利，换言之， i (si, s-i) i (si, s-i) 对一切si和s-i成立 其中s-i是除了局中人i以外的其他局中人选择的策略向量。那么我们称策略si强优于局中人i的所有其他策略.,考虑局中人1，我们称该局中人的策略b记作s1b优于其他策略s1a，意指针对局中人2的两个策略来说，s1b比s1a 更好一些；于是 1(s1b , s2a) 1(s1b, s2a) 1(s1b , s2b) 1(s1a , s2b) 第一个不等式指出了，如果局中人2采用了他的第一个策略，那么s1b比s1a 产生较高一些的盈利；第二个不等式指出了即使局中人2选择他的第二个策略，同样的事实也成立。,定义. 如果局中人i的策略si，对于其他局中人的每一个策略来说，至少与他的另一个策略s#i一样地好，而对于其他局中人的某个策略来说，si严格地好于s#i，即 则称策略si（弱）优于策略s#i。 在这种情况，我们称s#i为劣策略。如果si弱占优于其他任何一个策略si，那么si被称为弱占优策略*。 * 同样的定义应用于强优。如果公式3.1中令si =si#，称策略si强优于策略。于是策略si#称作强劣的。,占优策略解,当每一个局中人都有占优策略时，博弈就有一个占优策略解。 一个策略的组合，如果每一个局中人的策略都是占优策略，那称这个策略的组合为占优策略解。 例如，囚徒困境中（认罪，认罪）构成了一个占优策略解。 左 右 顶 7, 3 5, 3 底 7, 0 3, -1,案例研究续：拍卖中的占优策略,竞拍人以她对雷诺依作品的真实估价作为她的最高叫价的策略是一个占优策略。不管其他竞拍人怎样叫价，你所能做得最好的办法是，以你认为画所值的价格作为叫价来。从不同的方式讲，如果你认为画值3000美元，你最好的办法是闭上你的眼睛，举着你的拍卖牌直到听到拍卖商宣布的叫价高于3000美元为止 为什么它是个占优策略，与其他几个策略作比较。假使你决定“节省你的出价”，并且在2500美元处放下拍卖牌。有两种可能的情况。一种情况是，还有某些人最高叫价超过3000美元，其次，若最高叫价即赢得雷诺依作品的叫价是2700美元。现在，你感觉自己象个傻瓜！你失去了一幅估价为3000美元的画，而你用（稍高于2700美元）就可以拥有它。3000美元的最高叫价比起2500美元的叫价来决不会差些而有时候严格地更好一些。,总 结,策略型博弈由局中人的名单，每个局中人可使用的策略，和关于任何策略组合（一个策略对应于一个局中人）的盈利来描述。 每当博弈中有两个局中人，策略型可以很方便地表达为盈利矩阵。对于更多的局中人情况，符号表示式更方便一些。 每一个展开型博弈可以表示成策略型。每一个策略型博弈至少有一种展开型表示。 不管其他局中人如何做，占优策略比其他每一个策略给出较高的盈利。 当每一个局中人都有占优策略时，博弈存在占优策略解。 艺术品拍卖可以建模为策略型博弈，真实地叫价是该博弈的占优策略解。,第三章 占优可解性,概念 劣与非劣策略 累次剔除劣策略 案例研究：选举联合国秘书长 更正式的定义 讨论,概念 1. 劣与非劣策略,定义。 策略s#i 劣于另一个策略s-i，如果对于其他局中人的每一个策略，后者与s#i 至少一样好，而对于其他局中人的某些策略，si严格地好于s#i，以致,如果一个策略不劣于任何其他策略，则称它为非劣策略。将劣策略认为“坏”策略，而将非劣策略认为“好”策略,2. 累次剔除劣策略,局中人1 局中人2 左 (L) 右 (R) 上 (U) 1, 1 0, 1 中 (M) 0, 2 1, 0 下 (D) 0, -1 0, 0,3 .更多例题,例1： 伯川德（价格）竞争,假设双寡垄断市场中的两个公司都可以开出三个价格中的任一个高，中或低。 进一步假设不管哪个公司开价较低的话就可以得到整个市场。 如果两个公司开价相同，他们将平分市场。这些假设和任何的价格对转换成两个公司的收益水平。 例如，对于公司1，只有当它的价格不高于公司2的价格，才能有所收益。,假定收益由如下盈利矩阵给出,公司1公司2 高 中 低 高 6，6 0，10 0，8 中 10，0 5，5 0，8 低 8，0 8，0 4，4 剔除“高”策略后，留给我们如下盈利矩阵 公司1公司2 中 低 中 5，5 0，8 低 8，0， 4，4,例3：投票博弈,投票博弈：采用多数规则，三个投票人挑选两个议案A或B中的一个。通过了第轮的方案再面临与维持原状N（“都不”）进行决赛。三个投票人的真实偏爱如下： 投票人1： 投票人2： 投票人3：,每一个策略有三个分量：策略A（后面跟）AN是指“投A的票而反对B，然后在第轮中投A的票（反对N），或投N的票（反对B）。”至于盈利，让我们使用约定，如果他最愿意的方案通过，则获盈利1，第二喜欢的通过，盈利为0，如果第三喜欢（即，最不喜欢）方案通过，则他的盈利为-1。 在第轮中真实地投票优于非真实性投票；于是，对投票人1来说，AAN优于ANN, ANB，和AAB。类似地，BBN优于BNN, BNB, 和BAB。由同样的逻辑推理，对于局中人2，作为第轮中的投票策略，AB优于NB, NN, 和AN；对局中人，第轮的投票策略NN优于其他策略。可以看到如果投票人在第轮中真实地投票，那么在那个阶段，A击败N，而B输给N。,剔除了（第轮非真实的）劣策略后，策略型如下 投票人采用ANN 投票人投票人 AAB BAB AAN 1, 0, 0 1, 0, 0 BAN 1, 0, 0 0, -1, 1 投票人采用BNN 投票人投票人 AAB BAB AAN 1, 0, 0 1, -1, 1 BAN 0, -1, 1 0, -1, 1 现在看到，对局中人，AAN优于BAN，对局中人AAB优于BAB，而对局中人，BNN优于ANN。从而，我们得到了IEDS结局为：投票人取AAN，投票人取AAB，投票人取BNN，A（以票）赢得第轮，而在决赛中继续击败N。,案例研究：选举联合国秘书长,考虑有两个投票人的选举假如为美国与非洲。投票人1美国首先投票并着手否决三个候选人A（安南），B（加利），和H（布鲁特莱特）中的一个。然后，投票人2非洲否决两个余下的候选人中的一位。假如美国和非洲关于三个候选人的中意顺序如下： 美国： 非洲：,非洲 HAA HHA HAB HHB BAA BHA BAB BHB 美国 A -1, 1 -1, 1 -1, 1 -1, 1 1, -1 1, -1 1, -1 1, -1 B 1, -1 0, 0 1, -1 0, 0 1, -1 0, 0 1, -1 0, 0 H -1, 1 -1, 1 0, 0 0, 0 -1, 1 -1, 1 0, 0 0, 0 在一轮剔除之后，实际上的博弈成为： 美国非洲 HHA A -1, 1 B 0, 0 H -1, 1,占优可解性的更正式的定义,考虑有N个局中人的策略型博弈；局中人i的策略用si来表示；令Si表示局中人i的策略集。 在第轮，局中人i的劣策略集表示为 Di(I)，换言之， Di(I) = siSi: si是劣策略 理性的局中人不会采用劣策略。就是说，不启用 Di(I)中的策略，这对i = 1, 2, , N均成立。 进入第轮，局中人i可以在留给自己的策略集 Si Di(I)中作进一步的决定，看看它们当中是否又有哪些现在成为劣策略了。一个策略si# 现在成为劣的，是指：假定每一个其他局中人也都在第轮中剔除了劣策略之后，在Si Di(I)中存在另外一个，它始终至少与si#一样地好，而在某些时候严格地好于si#。,于是，,其中，S-i D-i(I)是除了局中人i以外的所有局中人的非劣策略组合的集合 1 。记局中人i在第轮中或者在第轮中为劣的所有策略的全体为Di ()。一旦知道了没有一个局中人会采用属于Di ()中的策略，继续剔除任何这样的步骤，现在又成为劣的那些策略。通过这种做法，又建立了一个在前三轮中为劣策略的集合；称这个集合为Di ()。如此等等。 1 尤其S-i D-i(I)包含了策略向量（s1, , si 1, si + 1, , sN），其中每一个策略sj都是非劣的。,假如我们最终达到这样一个状态，剩给每一个局中人的只有一个策略，即，假定经过T轮剔除之后，剩下的集合Si Di(T)，恰好包含了一个策略，并且这一事实对i = 1, 2, N都成立。在那种情况，这些每个人剩下的单一策略构成的向量称为累次剔除劣策略（IEDS）的结局，该博弈则称为占优可解的。假如这样的情况不发生如果在某一轮，对某些局中人，尽管仍然留下多个策略，但是没有更多的策略可以被剔除博弈就称为没有IEDS解。,没有人会采用劣策略是合理的假设。没有局中人会采用，那些一旦其他的劣策略被剔除之后成为了劣策略的策略，这件事看来也是合理的。没有一个局中人会采用只是在15轮剔除劣策略之后才转变成的劣策略，这件事似乎就不太合理。这是因为它假定，每个人都同意在连续（14次）高次数地剔除行动中所有的人都是理性的。如果其他局中人某一次理性的“失误”可能代价昂贵的话，这尤其成问题。考虑下述博弈： 12 左 中心 右 顶 4，5 1，6 5，6 中间 3，5 2，5 5，4 底 2，5 2，0 7，0,理性的层次,剔除的顺序（和非唯一的结局）,当策略是劣的但不是强劣的，剔除的顺序就要紧了。考虑下面的博弈。 12 左 右 顶 0，0 0，1 底 1，0 0，0,不存在性。,不是所有的博弈都是占优可解的。例如，在性别争端、扔硬币打赌和布鲁特上校中，不存在劣策略，因而，不存在IEDS结局。在以下博弈中，每一个局中人都有一个劣策略“差”可是在剔除那个策略后留下来的是一个只有非劣策略的22博弈。 12 左 中 差 顶 1，-1 -1，1 0，-2 中 -1，1 1，-1 0，-2 差 -2，0 -2，0 -2，-2,总 结,1. 没有一个理性的局中人会采用劣策略，他宁愿采用一个非劣的策略。而且一个理性的局中人不认为他的对手会采用劣策略。 2. 劣策略的剔除可以导致一系列连锁反应，逐步缩小一组局中人采取行动的范围。如果存在一个最终唯一预测，则称它为IEDS解。 3. 当在IEDS解中包含有许多轮次的剔除时，有理由去关心其预测的合理性。,第4章 纳什均衡,定义 例题 案例研究 IEDS和纳什均衡之间的一般关系,局中人i的策略与其他局中人的策略向量，如果它们满足 对所有si， 则称是关于的最优反应。 策略向量s* = s1* , s2*, sN*, 如果满足条件： 对所有i与所有si 则称s*是纳什均衡。,定义：,性别争端,丈夫妻子 足球（F） 歌剧（O） 足球（F） 3，1 0，0 歌剧（O） 0，0 1，3,伯川德定价,公司1公司2 高（H） 中（M） 低（L） 高（H） 6，6 0，10 0，8 中（M） 10，0 5，5 0，8 低（L） 8，0 8，0 4，4,案例研究：动物王国中的纳什均衡,荒漠蜘蛛的故事，雌蜘蛛在网里产卵，由于这样的网很难搭建，因此，网是稀少的。生物学家看到雌蜘蛛经常为已有的蜘蛛网争斗或者几乎是争斗；两只雌性并排在网前，并且作出诸如猛烈地摇晃网这样的威胁姿态（虽然它们很少有真正的肉体接触），当一只蜘蛛撤退而留下另一只单独地占有蜘蛛网时，冲突就得到了解决。 生物学家试图解释有关动物争斗的两个特定程式的事实： 多数冲突无需战斗而得到解决。此外，冲突的胜利者常常从失败者那儿“以不同的方式获得”某种维持生命必需的东西。 当奖励较高时，战斗的可能性更大。,蜘蛛1蜘蛛2 认输（c） 战斗（f） 认输（c） 5，5 0，10 战斗（f） 10，0 x，x,IEDS和纳什均衡之间的一般关系,命题 考虑任何具有IEDS结局的博弈。必定是这样的情况： IEDS结局是纳什均衡。但是，不是每一个纳什均衡可作为IEDS结局而得到。,总 结,1.如果关于对手的策略选择，局中人i的一个策略选择为他产生了最高可能的盈利。那么，这个策略选择就是关于对手该策略选择的最优反应。 2.如果在一个策略组合里，每一个局中人的策略选择是关于他对手选择的最优反应。那么这个策略组合是纳什均衡。 3.在所有的博弈理论中，纳什均衡是最普遍的求解方法。它可以有各种各样的方式来产生。 4.纳什均衡已经被用来解释野生世界动物之间的可观察到的习性形式。 5.任何IEDS解必定是纳什均衡，但是，存在着可能不是IEDS解的纳什均衡。 6.同样的事情对于占优策略解是真实的；它一定是纳什均衡，但相反的含义未必成立。,第5章 应用：古诺特双头卖主垄断,基本模型 古诺特-纳什均衡 卡特尔解,基本模型,古诺特提出的模型中，两家公司关于同类产品在市场上竞争。 两家公司在市场上面临单纯的需求曲线，假设需求曲线为 Q = P 其中 0, 0。而Q = Q1 + Q2是由公司1和公司2生产的总量。需求曲线的另一种理解方式是，如果Q=Q1+Q2是双寡头自身之间生产的量，由此产生的价格是 我们通过记 和 来简化这个（逆）需求曲线的表达式；即，从这个观点出发我们将使用的逆需求函数为 P = a b Q,假设每家公司的成本函数相同，并且每单元成本不随生产的单元数变化。更正规一些，每家公司具有常数边际成本函数；生产数量Qi的成本为cQi，其中c 0是常数边际成本，i = 1，2。 每家公司将生产多少？为做出该决策，每家公司必须采取两步： 1. 对另一家公司的生产量进行预测。这一步将给于公司一个有关可能的市场价格的想法；例如，如果它认为对手将生产大量产品，那么，不管它自己生产多少，价格将偏低。 2.决定生产的数量。为做出这个决定，公司必须权衡从增加产量得到的好处那样，它将出售较多产品以及这样做所需要的成本即，这些大量的产品将以较低价格出售（而它们不得不以较高的总成本生产）。当两家公司满意地解决了这两件事时，将得到工业范围的或纳什均衡。,古诺特-纳什均衡,最大化利润的生产量 公司1最优反应函数,卡特尔解,作为对比，如果两个公司如卡特尔那样地运作，即，如果它们对于它们的生产决策进行协调，我们来计算它们将生产的产量，如果公司经营为卡特尔，可以合理地假设它们以最大化它们的联合利润或总利润这样的方式来设置生产目标。预先指定生产“配额”为Q1与Q2；它们的选择是使得总利润最大化：,每家公司的 价格 每家公司的 生产数量 利润 注意到如果公司如卡特尔那样经营，它们比起在纳什均衡里的产量生产得少一些；卡特尔的产量是古诺特-纳什均衡产量水平的75%。在纳什均衡中，两家公司比起它们象卡特尔那样经营来利润较低（因为在纳什均衡里，它们过度地生产）。,第6章 应用：公共问题,公共问题 简单的模型 社会最优性 在人口众多时问题更糟,公共问题存在着两个关键性的特征：,(几乎）每个人的享用。限制享用是行不通的（考虑环境问题）和不可取的（考虑国家公园）。 资源枯竭。使用资源的人越多或者每个人使用资源越密集未来的资源就越少。,简单的模型,假如我们有大小为y 0的公共财产资源。两个局中人中的每一个可以提取一个非负量c1或c2用于消费，当然，假设c1 + c2 y。在他们试图过度消费的事件中，假定总量简单地由他们平分；即，每个人最终消费 y/2 。当总的消费量少于y时，剩余量y (c1 + c2),形成了未来资源的基底，未来的消费出自于这个量。为使事情简便，将未来紧缩成恰好还有一个周期的消费；即，在这个模型中有两个时间周期。,在第2个周期中，每一个局中人必须确定从可利用量 y (c1 + c2) 内有多少可供消费。因为再也没有下面的周期了，因此没有理由对在第2周期可用的量节省任何部分。于是每个局中人将乐意尽可能多地消费，因而，在第2周期，他们平分余下的总量每个人得到 。,我们回到第1周期，如果局中人1消费c1，他这样做的效用将取为log c1，局中人1必须确定他从资源的可利用储备中可以消费多少。他的效用依赖于局中人2选择的消费量，因为后者（部分地）决定了剩下来的资源基底的大小。如通常情况，局中人1对局中人2的消费有个猜测，并且在该基础上决定他自己的消费水平。换句话说，局中人1的最优反应问题是,局中人1的最优反应消费量是,同样的推理，求出局中人2的最优反应函数,或,纳什均衡为 c1*= c2*= y/3,社会最优性,定义 消费模式 ，如果它们使两个局中人的效用之和最大化，即，如果它们是下述问题的解： 则称 是社会最优的。 这种方法可求得社会最优解为 。,在这种情况，正好一半资源用于第1个周期与纳什均衡相比，那里用于第1个周期的资源有三分之二之多。在该意义下，在纳什均衡中我们对资源存在过分地榨取；即，我们经受了公共问题的悲剧。,在人口众多时问题更糟,如果局中人1猜测其他人在第1个周期消费的量将是，那么他的效用-最大化消费由下列最优化问题确定： 纳什均衡 在纳什均衡中的总消费量是 。结果，在第1周期后留下的量是y/(n+1)。当N变大时，第2周期可使用的资源量变得微乎其微。在人口众多的情况下加剧了公共问题的悲剧。,第7章 混合策略,定义 含义 混合策略可以优于某些纯策略 混合策略能虚张声势 混合策略和纳什均衡,定义,假设局中人有M个纯策略，s1, s2, ,sM。这个局中人的一个混合策略是分布在他的纯策略上的概率分布；即，它是一个概率向量(p1, p2, , pM)，其中pk 0, k = 1, 2, , M，且 特别简单的混合策略是每一个纯策略为等可能的，即 。,计算期望盈利分两步走：,第一步，对每一个纯策略的盈利使用采取该策略的概率进行加权。 第二步，把加权了的盈利合计在一起。 定义 现在假设其他局中人也采用混合策略；假如，以概率q取策略s#-i，而以概率1 q采用策略s*-i。那么局中人i的期望盈利等于,讨论使用混合策略而不使用纯策略的含义,定义。 考虑由概率向量（p1, p2, , pM）给出的混合策略。这个混合策略的支撑由所有那些（在这个战略行动中）具有正概率的纯策略构成。 一个混合策略的期望盈利就是组成这个混合策略支撑部分的纯策略盈利的平均值。如果这个支撑中每一个纯策略的盈利不相同，那么剔除具有最高盈利的纯策略之外的所有其他纯策略必定可以提高平均数，即，必定增加期望盈利。换句话说，如果策略s1和s3对于s#-i可产生最高盈利，那么，只包含这两个纯策略的混合策略将比也包含了策略s2, s4, , sM在内的任何一个混合策略产生更高的盈利。,含义。,（a）混合策略（p1, p2, , pM）是关于s#-i的最优反应，当且仅当它的支撑中的每一个纯策略本身是关于s#-i的最优反应 （b）在那种情况，在这个支撑上的任何混合策略都是最优反应。,混合策略可以优于某些纯策略 混合策略能虚张声势 混合策略和纳什均衡,没有混合策略，纳什均衡未必一定存在。,第8章 零和博弈,定义和例题 稳妥地参与：最大最小 充分地参与：最小最大 实施纳什均衡策略：既稳妥又充分地参与,1. 零和博弈,零和博弈是这样的一个博弈，不管两个局中人采取的是什麽样的策略向量，他们的盈利总是相加为零；就是说，对所有的策略s1和s2，成立 1(s1, s2) + 2(s1, s2) = 0 在（两人）零和博弈中，局中人2的盈利正好是局中人1的盈利的负值。,例1: 扔硬币打赌,例2: 壁球,1 2 向前（F） 后退（B） 前面（f） 20，80 70，30 后面（b） 90，10 30，70 在每一格中，分别为局中人1和局中人2赢的百分比。例2是从任何角度都很象零和博弈的一类博弈中的一个例子。这类博弈称为常数和博弈。在这类博弈中，两个盈利合计总是等于常数。,2. 稳妥地参与：最大最小,在零和博弈中，当且仅当局中人1干得差时，局中人2干得好。对于任意策略s1，存在局中人2可以选择的策略b(s1) ，使得他的盈利可能最高而同时使得局中人1的盈利最低。策略b(s1) 形式上定义为,在传统方法中，局中人1认定，不管她采取何种策略，局中人2将正确地预测并且采取一个（使局中人1）最差或赢利最小化的策略b(s1)。因此，为了有把握（或稳妥）地参与，局中人1应该取策略s1，它使局中人1最差情况下的盈利比起她采取其它任何一个策略的最差情况盈利要好一些。,在选择自己最好的“最差盈利”时，重要的是局中人1完全有理由同时考虑混合策略。毕竟，回想起当我们研究壁球游戏时，我们发现稍许有点虚张声势会使局中人得处境好一些；如果她击球落点是在球场前面和后面之间的混合，她赢的百分比就会高一些。 现在我们来给出保证盈利（或者最差情况下的最高盈利）的正式定义。这个盈利称为最大最小盈利并记为m1：,如果策略p* 满足 p*, b(p*) = m1，则称p*为局中人1的稳妥策略。,注1：由于策略b(p)使得局中人1的盈利最小化，因此，它是局中人2对付p的最优反应（因此使用这个记号）。所以，稳妥的方法是，局中人预期她的对手采取最优反应并且防范任何随之发生的不利结局。 注2：稳妥方法给予局中人1一个单方面手段去参与博弈。她知道，如果采取一个稳妥策略p*，她不可能比m1更差。如果事实上她的对手没有采用最优反应，那么她的盈利只能更高一些。这不像最优反应行为，该行为要求局中人1彻底地全面考虑问题：我在对什么作出最优反应？当然，这样的单方面策略的实施可能产生很高的代价；稳妥地参与可能不像采用最优反应那样有利。那种可能性将是下面小节的主题。,3. 充分地参与：最小最大,代替采用防止最差情况结局，局中人1可以通过采用最优反应从而“更加积极地”对付局中人2的策略。人们可以认为这是更乐观的办法；试图预测对手的行动并且对此作出最优的反应。与之相联的概念称作最小最大盈利；它是局中人1的最优（反应）盈利中最差的一个（将它记为M1）：,这里， (s1, q)是当局中人1采取纯策略s1和她的对手采用混合策略q时她的期望盈利。,命题1 （最小最大优于最大最小）。局中人1的最小最大盈利至少和她的最大最小盈利一样高，即M1 m1。不管我们考虑的是纯策略或者是混合策略，该陈述都是正确的。 命题2（一个局中人的最小最大是另一个局中人的最大最小）。局中人1的最小最大盈利正好是局中人2的最大最小盈利（的负值），即 M1 = - m2 = b (q*),q* (反过来，局中人2的最小最大盈利是局中人1的最大最小盈利的负值。),4. 实施纳什均衡策略：既稳妥又充分地参与,定义: 一对混合策略，如果对所有纯策略s1和s2，有,则 构成零和博弈的纳什均衡。,命题3（稳妥和充分地参与）。 令 构成零和博弈的纳什均衡。那么 和 是稳妥策略，并且最大最小（和最小最大）盈利互相相等且等于 。反之，假使最小最大和最大最小盈利相等。那么稳妥策略构成了博弈的纳什均衡。,第9章 展开型博弈和后推归纳,展开型 策略，混合策略，和事件结 完美信息博弈 后推归纳法 与策略型中IEDS的联系 案例研究 ：“毒药”和其他收购威慑,剧院博弈,1. 展开型,为了让“树”描绘博弈，其结点和枝需要满足三条性质： 1单一的出发点。重要的是知道博弈从何处开始，所以必须有一个，也只能有一个出发点。因而，如图11.3那样的情况是不允许的。 2 无循环。重要的是在博弈运行中，我们不要陷入僵局；树枝循原路折回并造成一个循环一定是不可接受的。 3 单方向前进。重要的是，对于博弈如何进行下去不能模棱两可，因此，必定不存在二个或多个枝导向同一个结。,为保证这三条性质，在前结点上强加下述限制：,1结点不能是自身的前结点。 2前结点的前结点也是前结点：如果结点是的前结点，依次结点是的前结点，那么也是的前结点。 3前结点可以排序：如果和都是的前结点，必定是或者是的前结点，或者反过来。 4必定存在一个共同的前结点：考虑任意两个结，和，它们之间没有一个是另一个的前结点。那么，必定存在一个结点，它是和双方的前结点。,策略，混合策略，和事件结,策略 局中人的策略是行动的一个完全的，有条件的计划。说它是有条件的，因为如果博弈到达某个决策结后，它告诉局中人从这个结点出发后顺沿哪条枝。说它是完全的，因为它告诉局中人在每一个有关的决策结上选择什么策略。,混合策略,混合策略定义的方式以与策略型完全相同；它就是在纯策略上的一个概率分布。因此在序贯的剧院博弈中，局中人1的混合策略有两个数p和q给定，他们分别是选择b 和选择c的概率（而1 p q 是选择s的概率）。局中人2的混合策略由33- 1 个数给定，每个数对应于指派给每个纯策略的概率。,事件结,我们也可以在展开型内建立不确定性，这种不确定性是博弈本身所具有的（与之对立的是局中人通过混合策略引进的不确定性）。例如，乘地铁需要的时间可能依赖于在地铁系统中是否存在一个高峰时间的延迟。对这种可能性建模的一个方法是允许第三类型的结点，称之为事件结；这是一个其枝表示若干随机可能性的结点。,2.完美信息博弈,完美信息的博弈 具有如下性质的展开型博弈：在每一个信息集中正好有一个结。 一个完美信息的博弈是不存在（具有多个结的）信息集的展开型博弈。,例1：进入,考虑下述经济模型。一家公司譬如，“可口可乐”正在盘算是否进入一个新市场比方说是前苏联(FSU)在那里，市场由它的竞争对手“百事”所独占。新市场的潜在赢利影响“可口可乐”的决策，而这主要依赖于“百事”对“可口可乐”进入它的市场将做出怎样的反应。如果“百事”发动一场广告大战，花费大量金钱用于改善设施，以排他性协议捆住零售商换句话说，反应“强硬”那么“可口可乐”将会遭受损失。另一方面，如果“百事”不发动这样强硬的反击毕竟这样做代价昂贵“可口可乐”将赚到钱。在图11.6中，E(进入)和O(呆在外面)表示“可口可乐”的抉择，而T（强硬）和A（宽容）指“百事”在如何制止“可口可乐”的进入方面的两个选择。注意，在每一对盈利中的第一项是“可口可乐”的盈利。,例2：进入,对于（稍微）复杂一些的模型，我们考虑如下变体。假设在“百事”的决策之后，“可口可乐”有进一步的决策可做；它必须决定自己是否发动一场积极的广告战并花费大量资金于设备方面，采取诸如此类的行动。换句话说，假使在看到了“百事”的反应之后，“可口可乐”本身将不得不行为“强硬”或“宽容”,例3：（不完美信息）进入,假设，万一“可口可乐”进入FSU市场，“可口可乐”和“百事”两家将对在这个市场上投资多少作出决策。即，行为或者“强硬”或者“宽容”。但是，例2不同，假定这些决策是同时策划的（这个事实使得这种情况不是完美信息的博弈）,3. 后推归纳,我们感兴趣的问题是，例1和例2中行为的合理预测是什么？这实际上是关于序贯理性的问题。它包含了理性，因为在考虑到局中人所想的将会是博弈的未来行为，因此，他将在决策结上选择他可使用的最优行动。它包含了序贯性，因为局中人将推断未来将会怎样，并且知道在未来，局中人将以同样的方式推理。尤其，在随后结点上的决策者，考虑到他对博弈今后未来的猜想，反过来选择可采用的最优行动。,注意到“可口可乐”的每一个策略必定有三个分量。第一个分量告诉我们“可口可乐”是否进入市场，第二个分量告诉，如果“百事”反应“强硬”，它是否会行为“强硬”，而第三个说明了如果“百事”宽容的话，“可口可乐”将采取的行动。例如EAT表示（1）进入，（2）以宽容对付强硬的“百事”，（3）采取强硬策略对付宽容的“百事”。但是，“百事”正好有二个策略要么反应强硬，要么宽容“可口可乐”。,百事 T A 可口可乐 ETT -2, -1 0, -3 ETA -2, -1 1, 2 EAT -3, 1 0, -3 EAA -3, 1 1, 2 OTT 0, 5 0, 5 OTA 0, 5 0, 5 OAT 0, 5 0, 5 OAA 0, 5 0, 5,该策略型基本上有三个纯策略纳什均衡：,1其“百事”取T，而“可口可乐”取它呆在外面的（四个）策略中的任何一个的纳什均衡，OTT, OTA, OAT, 和OAA。 2(ETA, A)其结局为，“可口可乐”进入而两家公司都宽容。 3(EAA, A)跟第二个均衡有相同的结局。,承诺的力量,在生活中，通常，只有少量的选择总比有较多的选择要差一些。你也许认为这对博弈也应该是对的。但是，展开型博弈，尤其是完美信息博弈，提供了少量（选择）可以蕴含更多（均衡盈利）的例子。这种陈述最初听起来似乎自相矛盾，但是直觉上的确很易明白。如果局中人在后面有许多选择，比起如果她有少数几个选择来，在未来的行为可以相当地不同。反过来，这种行为将影响她同时也影响其他局中人的当前措施。这种变化基本上对于具有增加了的选择的局中人可能是有利的或者有害的。,只强硬的“百事”,假如我们以下述方式简化这个（已经简单的！）例子：在“可口可乐”进入FSU 市场之后，“百事”除了采取“强硬”之外别无其他选择。（即，我们通过剔除“宽容”而缩减了“百事”的选择可能）。,只强硬的“可口可乐”,假如我们以下述方式修改例子：在“可口可乐”进入FSU市场之后，除了强硬之外，“可口可乐”没有其他的选择（即，假定“可口可乐”少了一个选择：它不能宽容）。,后推归纳法,科恩（和策墨罗）定理。每一个具有有限个结的完美信息博弈有后退归纳解。事实上，如果对每一个局中人，不存在相同的两个盈利，那么存在唯一的后退归纳解。,5. 与策略型中IEDS的联系,博弈展开型中的后退归纳解与在策略型中用累次剔除劣策略（IEDS）求解博弈得到完全相同的结果。,6.案例研究 ：“毒药”和其他收购威慑,法律“毒药”1 假设没有“毒药”条文，那个博弈就如例1那样南诺福克（Norfolk Southern）必须决定是否反对CSX-联合铁路公司的联盟。一方面，如果他们决定反对（并提出一个股份报价），CSX-联合铁路公司要么可以通过拒绝谈判，或抬高自己的条款，等等采取强硬策略，要么他们可能宽容并达成某种三边协议。另一方面，假使有“毒药”条文，博弈就如例1那样：CSX-联合铁路公司达成协议采取强硬措施。 此外，现在假设CSX-联合铁路公司必须作一最初选择，决定是否用“毒药”来武装自己。于是展开型就如图所见到的那样（注意，在盈利向量中的第一项是第一个行动者的盈利，即，CSX-联合铁路公司的盈利）。,没有“毒药”，CSX-联合铁路公司将会宽容，从而南诺福克进入，于是前者的利润为2。设立“毒药”，南诺福克将选择不收购，因而CSX-联合铁路公司将得到利润3。显然，CSX-联合铁路公司乐意采取“毒药”，这一承诺使他们获得额外的1千万美元利润。,法律“毒药”2,你认为如此过分的事情很好，但是在实际中难道南诺福克不会提出收购计划吗？好吧，那样的话也许展开型中的盈利稍有不同。考虑下图。如前一样，不设立“毒药”，CSX-联合铁路公司的盈利是2。现在，虽然，尽管有“毒药”，南诺福克发现进入仍是有利可图的（因为它得到了利润0.5）。CSX-联合铁路公司获得利润2.5，这仍然比他们不采用“毒药”而得到的2好一些。,因此后退归纳结局是CSX-联合铁路公司宁愿采用“毒药”条文，南诺福克愿意提出一个股份报价（发动对联合铁路公司的收购），CSX-联合铁路公司采取强硬措施。这个例子反映了在铁路货运危机中实际发生的事情。,第10章 应用：研究和发展,R&D模型 后退归纳：模型分析,R&D模型,假如在一个行业有两家公司，RCA与索尼(Sony)此后称为公司R和公司S每一家都在为生产HDTV而进行R&D。在HDTV可以进入市场之前有若干必须成功地完成的阶段。为了使分析容易处理，我们做一些简化假设： 1. 可以度量离最终目的的距离，例如，我们可以说，公司S处于离项目完成还有n步 。 2. 两家公司在任何一个周期都可以前进1步，2步 或3步后完成项目。 3. 向前移动一步花费2（百万）美元，向前移动二步花费7（百万）美元，和向前移动三步花费15（百万）美元。 4. 无论哪家公司最先完成所有步骤的则获得专利；专利值20（百万）美元。,卡特尔，第1步 证实下面的陈述：因为两家公司中只有一家将获得专利，它只支付其中的一家去做R&D。 卡特尔，第2步 证实下面的陈述：无论哪一家公司做R&D，它将花费最少可能的资金，并且一次向前进展一步。而且，被选中的公司将是比较接近于完成的那一家。,后退归纳：模型分析,5. 两家公司轮流决定在R&D花费的资金；如果RCA在这个周期作出R&D决策，直到它知道索尼接下去的R&D资助后它才作进一步的决策。而且，索尼在RCA宣告之后的周期里作出它的通告。 假设5把专利竞争转入完美信息博弈；我们来看
展开阅读全文