博弈论主讲 施锡铨2004年3月第一章 引论应用及例题基本理论博弈论关注的是互相依存（interdependence） 每一个体猜测其他个体的选择是什么？ 每个人将采取什么样的行动？(当最优的行动依赖于 其他人的所作所为时，这个问题尤其令人关注。) 这些行动产生什么样的结局？对于整个群体，这个 结局好吗？ 如果群体不止一次地互相作用，会有任何差异吗？ 如果每一个体对群体内其他个体的特性没有把握， 答案将发生怎样的变化？取自经济学，政治学，财政金融，法律，甚至日 常生活中的若干相互依存性事例 艺术品拍卖 (诸如在克里斯蒂（Christie） 或索士比（Sotheby）拍卖行，那里待售出 自布拉克（Braque）直至维罗内塞（ Veronese）的艺术品)和债券拍卖（美国财 政部为筹措联邦预算支出，以这种方式出 售政府公债） 。 联合国的选举（ 例如，选举新的联合国秘 书长） 。 动物争斗（争夺良好的栖息地以及种类中 稀少的发情期雌性动物，等等）。 自然资源的可持续使用（像石油那样的可 耗尽资源或像森林那样的可重建资源的提 取形式） 。 运动会和工作场所的随机药物检测（选取 少量运动员和工作人员进行核实使用违禁 药物的测试） 。 破产法（详细说明在什么时候和有多少债 权人可以从已破产的公司那儿收账） 。 “毒药”条款（该条款给予管理部门一定的权限 以抵制不受欢迎者试图接管或兼并他们的公司 ） R 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, 35, 3底7, 03, -1 案例研究续：拍卖中的占优策略 竞拍人以她对雷诺依作品的真实估价作为她的最高叫价的 策略是一个占优策略。不管其他竞拍人怎样叫价，你所 能做得最好的办法是，以你认为画所值的价格作为叫价 来。从不同的方式讲，如果你认为画值3000美元，你最 好的办法是闭上你的眼睛，举着你的拍卖牌直到听到拍 卖商宣布的叫价高于3000美元为止 为什么它是个占优策略，与其他几个策略作比较。假使你 决定“节省你的出价”，并且在2500美元处放下拍卖牌。 有两种可能的情况。一种情况是，还有某些人最高叫价 超过3000美元，其次，若最高叫价即赢得雷诺依作 品的叫价是2700美元。现在，你感觉自己象个傻瓜 ！你失去了一幅估价为3000美元的画，而你用（稍高于 2700美元）就可以拥有它。3000美元的最高叫价比起 2500美元的叫价来决不会差些而有时候严格地更好 一些。 总 结 1.策略型博弈由局中人的名单，每个局中人可使用的策略 ，和关于任何策略组合（一个策略对应于一个局中人）的 盈利来描述。 2.每当博弈中有两个局中人，策略型可以很方便地表达为 盈利矩阵。对于更多的局中人情况，符号表示式更方便一 些。 3.每一个展开型博弈可以表示成策略型。每一个策略型博 弈至少有一种展开型表示。 4.不管其他局中人如何做，占优策略比其他每一个策略给 出较高的盈利。 5.当每一个局中人都有占优策略时，博弈存在占优策略解 。 6.艺术品拍卖可以建模为策略型博弈，真实地叫价是该博 弈的占优策略解。第三章 占优可解性 概念 1.劣与非劣策略2.累次剔除劣策略案例研究：选举联合国秘书长 更正式的定义 讨论 概念 1. 劣与非劣策略 定义。 策略s#i 劣于另一个策略s-i，如果对于其他 局中人的每一个策略，后者与s#i 至少一样好， 而对于其他局中人的某些策略，si严格地好于 s#i，以致 如果一个策略不劣于任何其他策略，则称它为非劣 策略。将劣策略认为“坏”策略，而将非劣策略认为“ 好”策略 2. 累次剔除劣策略局中人1局中人2 左 (L)右 (R)上 (U)1, 10, 1中 (M)0, 21, 0下 (D)0, -10, 03 .更多例题例1： 伯川德（价格）竞争 假设双寡垄断市场中的两个公司都可以开出三 个价格中的任一个高，中或低。进一步假设不管哪个公司开价较低的话就可以 得到整个市场。如果两个公司开价相同，他们将平分市场。这 些假设和任何的价格对转换成两个 公司的收益水平。例如，对于公司1，只有当它的价格不高于公司 2的价格，才能有所收益。假定收益由如下盈利矩阵给出公司1公司2高中低 高 6，6 0，100，8 中10，05，50，8 低 8，08，04，4剔除“高”策略后，留给我们如下盈利矩阵 公司1公司2中低中5，50，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投票人投票人AABBABAAN1, 0, 01, 0, 0BAN1, 0, 00, -1, 1投票人采用BNN 投票人投票人AABBABAAN1, 0, 01, -1, 1BAN0, -1, 10, -1, 1现在看到，对局中人，AAN优于BAN，对局中人AAB优于 BAB，而对局中人，BNN优于ANN。从而，我们得到了 IEDS结局为：投票人取AAN，投票人取AAB，投票人 取BNN，A（以票）赢得第轮，而在决赛中继续击败N。 案例研究：选举联合国秘书长 考虑有两个投票人的选举假如为美国与非洲 。投票人1美国首先投票并着手否决三 个候选人A（安南），B（加利），和H（布鲁 特莱特）中的一个。然后，投票人2非洲 否决两个余下的候选人中的一位。假如美国 和非洲关于三个候选人的中意顺序如下： 美国：非洲：非洲HAAHHAHABHHBBAABHABABBHB 美国 A-1, 1-1, 1-1, 1-1, 11, -11, -11, -11, -1 B1, -10, 01, -10, 01, -10, 01, -10, 0 H-1, 1-1, 10, 00, 0-1, 1-1, 10, 00, 0在一轮剔除之后，实际上的博弈成为： 美国非洲HHA A-1, 1 B0, 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）的结 局，该