策略型博弈 本书主要讨论策略型博弈。在本章，我们用一些例子帮助读者在直觉上理解策略型 博弈。这些例子既有有限博弈，也有无限博弈。这里涉及的博弈主要有硬币配对、石头 剪刀布、巴赫或斯特拉文斯基博弈、学生协作、囚徒困境、公司两难、双寡头定价、公 地悲剧、带宽共享、密封拍卖、庇古网络博弈、布雷斯论。这些例子是现实博弈应用 的缩影。 策略型博弈 4. 1基本知识 我们已在第2章（定义2.1）看到策略型博弈T是一个多元组T=（N，（S;）∈N， （ui）i∈N>，其中：N={1，2，，n}是参与人集，这是一个有限集；S，S2，，S 分别为参与人1到n的策略集；u：S×S×…×S→R（其中i=1，2，"，n）是效 用函数。我们在第3章已看到，通过将相机行动方案映人策略，我们可将展开型博弈转 变为策略型博弈。在本书中，策略型博弈、策略博弈以及标准型博弈这三个术语是同义 的。在不至于混淆的情形下，我们用符号T=<N，（S），（u））表示策略型博弈。 我们把由所有策略组（或称策略向量）组成的集合记为S，集合S为笛卡儿积 SX…XSn。典型策略组通常记为（s1，，S），其中s是参与人i的策略，这里i= 1，，n。我们将笛卡儿积S×……×S1×S+1××S（注意这个积的表达式中不含 S）记为S-i，它由除了参与人i之外的所有其他参与人的策略集组成。我们将S-：中的 典型策略组记为s-i。当我们关注特定参与人i时，使用（si，S-:）来表示策略组比较方 便，其中sESi，S-iES-i。 策略型表示法背后的思想是，参与人的决策问题在本质上是选择一个策略使得该策

略能最有效地反击其他参与人选择的策略。这样的策略称为最优反应策略（bestre- sponsestrategy），它的正式定义如下。 定义4.1（最优反应策略）给定策略型博弈T=（N，（S:），（u;））和策略组s-:∈ S-i，对于参与人i的策略s;ES，如果u（si，S-i）≥u（si，s-）对于所有s∈S成立， 那么我们说s是参与人i对s-的一个最优反应策略。 给定策略组s-：ES-i，参与人i一般有多个最优反应策略。 在策略型博弈中，每个参与人的问题是选择自己的最优策略，而且我们可以认为每 个参与人同时从各自的策略集S1，S2，，S中选择自己的策略。 博弈论文献为策略型博弈提供了很多解释。我们这里提供两种解释，它们都来自 OsborneandRubinstein[i] 第一种解释是，策略型博弈模拟的是只发生一次的事件。每个参与人知道博弈的细 节，并且知道每个参与人都是理性的。所有参与人同时且独立地选择自己的策略。每个 参与人都不知道其他参与人做出的选择。 第二种解释是，每个参与人根据博弈的玩法或者以前类似博弈的玩法猜测其他参与 人的行为。策略型博弈模拟的情形是，在参与人彼此的行动不存在策略联系（strategic link）的条件下，参与人是如何先后行动的。所谓不存在策略联系，是指进行多次博弈 的参与人关注的仅是自己的瞬时收益，而不用考虑他当前的行动对其他参与人未来行为 的影响。注意，如果存在策略联系，那么这就是所谓的重复博弈（repeatedgames）。 展开型表示法（参见第3章）比策略型表示法能够更详细地描述博弈。一个策略型 博 博弈可能对应多个展开型博弈。策略型博弈不能反映博弈的动态性，但它简化了一些类 弈论与机 型的博弈分析。在很多情形下，使用策略型就足够了。 制 4.2同时行动情形下的硬币配对 设计 我们在第3章已考察过这个博弈。回忆一下，在这个博弈中，参与人1和2同时将 自己的硬币放下，正面向上或反面向上。如果两个硬币配对成功（同为正面向上或同为 反面向上），那么参与人2给参与人1一元钱。相反，如果未配对，参与人1给参与人2 一元钱。我们用A表示正面向上，用B表示反面向上。容易看到： N={1,2} S=S={A，B} S=SXS={（A，A)，（A，B)，(B，A)，(B，B)} 收益矩阵为 A B A 1，-1 -1,1 B -1，1 1，-1 这也许是最简单的两人博弈的例子了。它属于两人零和博弈（zero-sumgames）类

型（之所以叫零和博弈，是因为在每个结果中，参与人的博弈之和等于零）。在上面的 博弈中容易看到：当参与人2选择A（B）时，参与人1的最优反应策略为A（B）。另一 方面，当参与人1选择B（A）时，参与人2的最优反应策略为A（B）。 为了理解上面的博弈为何重要，我们考虑下面的情形。有两个公司，称之为公司1 和公司2。每个公司都能生产两种产品，A和B。然而，在任何给定的时点上，任何一 个公司都只能生产一种产品，原因在于开业成本和转换成本很高。相对来说，公司1生 产的产品质量更高，但公司2更擅长营销和广告。因此，如果两个公司生产同一种产品 （A或B），那么公司1赚取了所有利润，公司2亏损。这反映在当策略组为（A，A） 或（B，B）时，公司1的收益为十1，公司2的收益为一1。 另一方面，如果一个公司生产A而另外一个公司生产B，那么由于公司2更擅长营 销和广告，公司2占有了整个市场，导致公司2的收益为十1，公司1的收益为一1。 这两个公司必须同时且独立决定生产哪种产品。这是它们面对的策略决策。这种情形 可用策略型博弈r=<N，S，S2，u，u2〉描述，其中：N={1，2}；S=S2={A，B}； 效用函数参见上表。 4.3石头剪刀布 石头剪刀布是另外一个两人零和博弈的例子，在这个博弈中，每个参与人有三个策 略。事实上，这是一个非常流行的游戏。石头、剪刀和布是三种手势，参与人同时且独 第 4章 立地做出其中一种手势。游戏规则为石头砸烂（击败）剪刀，剪刀切破布，布包住石 头。这个博弈的收益矩阵如下： 策略型博弈 石头 布 剪刀 石头 0，0 -1，1 1，-1 布 1，-1 0，0 -1,1 剪刀 -1,1 1，-1 0，0 4.4BOS博弈 BOS（BachorStravinsky）博弈的名字来自著名音乐家巴赫和斯特拉文斯基。这个 博弈也叫做性别大战（BattleofSexes）博弈。在这个博弈中，参与人希望协作；然而， 在哪个结果更好的问题上，他们的意见不一致。比如，两个参与人（1和2）希望一起 做事（A或B）。参与人1喜欢做A，参与人2喜欢做B。收益矩阵如下： A B A 2，1 0，0 B 0，0 1，2

显然，这个博弈描述的是参与人希望协作但彼此利益冲突的情形。两个参与人都不 喜欢结果（A，B）以及结果（B，A）。他们的选择要么是（A，A），要么是（B，B）。 下面考察这个博弈的公司版本。假设有两个公司1和2。每个公司都能生产两种产品 （A和B），但在任何时点上，每个公司只能生产一种产品。假设A是公司1的利基 （niche）产品，B是公司2的利基产品。如果两个公司都生产A，那么消费者只能购买 A，而且多数愿意从公司1而不是从公司2购买。假设公司1占有2/3的市场。我们可 将这个事实描述为公司1的收益是公司2的两倍。如果两个公司都生产B，情形正好相 反，公司2的收益是公司1的两倍。 另外一方面，如果两个公司决定生产不同产品，那么市场被分割，每个公司都试图 通过增大广告支出来击败对方。事实上，它们竞争的结果可能使得第三方（其他公司） 得利，从而使得公司1和公司2的收益都为零。上页最后一个表描述了这个博奔的收益 结构。 4.5协作博弈 我们已在第1章介绍过这个博弈（学生协作博弈）。该博弈类似BOS博弈，但在这 个博弈中，两个参与人都偏好同一个选择，即事件A。收益矩阵见下表；注意，参与人 偏好结果（A，A）胜于结果（B，B)。 博奔论与机制设计 A B A 10,10 0，0 B 0，0 1，1 这个博弈的公司版本是，两公司生产相同产品且每个公司市场份额相同。产品A 的市场份额是B的10倍。另一方面，如果这两个公司生产不同产品，那么第三个公司 将占有全部市场份额，从而使得公司1和公司2的收益都为零。 由于在每个结果中参与人的收益都相同，这样的博弈也称为相同收益博弈（com monpayoffgames)。 4.6徒困境博弈 这是博弈论中被最广泛研究的问题，它有很多版本，也有很多解释。常见的版本如 下：警察逮捕了两个人，他们涉嫌共同作案。这两个人被关在不同牢房，被分别审问。 他们被告知，如果只有一个人坦白（记为C），那么此人只需坐牢1年，而另外一人要 坐牢10年。如果两人都坦白，那么每人坐牢5年。如果两人都不坦白（记为NC），每 人需要坐牢2年。每个因徒知道对方也知道这些规则。因此，收益矩阵是一个共同 知识。

NC C NC -2，-2 -10，-1 C -1，-10 -5，-5 在这种情形下，囚徒应该怎么办？参与人1选择的策略对参与人2选择的最优反应策 略来说应是最优反应，参与人2选择的策略对参与人1选择的最优反应策略来说应是最优 反应。首先，注意到，不管对方如何选择，C（即坦白）都是每个人的最优反应策略： u(C,C)=-5>u（NC,C)=-10；u(C,NC)=-1>u（NC,NC)=-2 u(C,C)=-5>u2(C,NC)=-10;u(NC,C)=-1>u2(NC,NC)=-2 因此，（C，C）是这个博弈的自然结果。然而，对于这两个人来说，（NC，NC）这个 结果最好。在因徒困境中，理性且智能的行为并未导致最好结果，这里的最好结果是指 参与人的效用之和最大。另外，每个人对其他人有负的影响或说负的外部性，因为当其 中一人偏离（NC，NC）而选择策略C时，尽管他的收益增加了（少坐牢一年），但他 的这个行为使得对方坐牢年数增加了8年。 因徒策略的另外一种解释也比较流行。在这种解释中，每个因徒有两个策略：一是 合作（cooperate），二是背叛（defect）。合作策略意味着参与人不坦白从而与对方合作， 因此，合作等价于上面的NC策略。背叛策略意味着参与人坦白从而背叛了对方，因 此，背叛等价于上面的C策略。以后，我们仍使用C和NC策略，而不用合作和背叛这 第 样的说法。 章 策略型博弈 4.7公司两难博弈 根据因徒的困境问题，我们提供它的公司版本博弈。假设有两个公司1和2，每个 公司都能生产两种竞争产品A和B，但在既定的时点上只能生产一种。消费者普遍认为 产品A比B好。然而，环保主义者抵制产品A的生产，他们认为A的生产污染了 环境。 如果两个公司都生产A，那么尽管有抵制运动，它们的收益仍然很高，因为产品A 正好是两个公司的利基产品。另一方面，如果两个公司都生产B，那么它们都能赚取一 些利润，但不如都生产A那么高。 另一方面，如果一个公司生产A，另外一个公司生产B，那么由于环保主义者抵制 产品A，生产A的那个公司的收益为零，生产B的公司占有了整个市场，赚取了很高 的收益。这个博弈的收益矩阵见下表。 A B A 6，6 0，8 B 8，0 3，3

4.8公司两难博弈：非对称版本 我们到目前为止考察的博弈，例如硬币配对、石头剪刀布、BOS、协作博弈、囚徒 困境以及公司两难等，都是对称博弈（symmetricgames）。给定一个两人博弈，如果对 于所有siES和所有s2∈S2，我们都有S=S2以及u（si，S2）=u2（s1，S2），那么这个 博弈是对称的。我们现在提供一个非对称博弈。假设有两个竞争公司1和2。在这个博 弈中，每个公司必须同时且独立决定生产A和B中的一种。公司1生产的产品A更好， 如果两个公司都生产A，那么公司1占优。如果两个公司都生产B，那么它们平分利 润。如果其中一个公司生产A，另外一个生产B，那么公司2占优（也许因为它的营销 更激进）。下面的收益矩阵描述了两个公司面对的策略。 A B A 4，1 0，4 B 1，5 1,1 4.9双寡头定价博弈 这是Bertrand（1883）提出的。有两个公司1和2，它们试图使自己的利润最大。 需求x（p）是价格的函数；这是一个连续且严格递减的函数。每单位产品的生产成本为 c，这里c>0。两个公司同时且独立选择自己的价格p和P2。每个公司的销量为 x1(p1，p2)=x(p) 若p1<p2 =x(p1) 若pi=p2 =0 若p1p2 x2(p1，p2)=x（p2) 若p2<p1 =x(p2) 若p1=p2 =0 若p2>p1 这个博弈假设企业仅在产量等于销量时才发生生产成本。给定价格p和p2，两个公司 的效用分别为 u（p1，P2)=（p1-c)x1（p1，P2) u2（p1，p2）=（p2—c）x2(p1，p2) 注意，对于这个博弈，N={1，2}，S=S2=[0，∞o）。这是一个无限博弈，因为策略 集是无限的。

4.10公地悲剧 公地悲剧（tragedyofthecommons）代表一类社会论或社会悲剧。这个博弈涉 及个人和社会在资源使用上的利益冲突问题。一个村庄有n个农民，记为集合N=1， 2，"，n}。每个农民可以养羊（一只）或不养。令1表示养一只羊，0表示不养羊， 则策略集为 S=S2=..=S={0，1} 养一只羊的效用（效用来自羊奶、羊毛等）为1单位。该村庄的草地有限，当农民放牧 一只羊时，羊对环境的破坏等于5单位。这个代价由所有农民均摊。 令s:为每个农民的策略。于是，s∈{0，1}。农民i的收益为 [5（s+···+sn） u;(S1,.",Si,,Sn)=Si n 对于n=2的情形，收益矩阵为 0，0 -2.5，-1.5 -1.5，-2.5 —4，—4 如果n>5，那么每个农民养一只羊比不养的效用高；如果n<5，那么每个农民养一只 策略型博弈 羊比不养的效用低；如果n=5，那么每个农民对养与不养羊无差异。 现在，如果政府对每个农民养一只羊征收5单位污染税，那么收益变为 _5（s+·.+sn） u;(S1,…,Si,…,Sn）=Si——5si n 于是，每个农民宁可不养羊。为了更深人地分析这个社会问题，我们将在第5章和第6 章研究该博弈。 4.11 带宽共享博弈 带宽共享（bandwidth sharing）问题来自Tardos andVazirani2]。某共享信道的最大容量 为1。有n个人使用这个信道，用户i希望传递x单位的流量，其中xE[0，1]。我们有 N={1,2,,n} S=S2=···=S=[0,1] 如果>x：≥1，那么信息无法传递，因为超容了；在这种情形下，每个参与人的收益 iEN

为零。如果x<1，那么假设用户i的收益为 iEN u;（x，，xn）=x:（1-x;）对于所有i∈N jEN 上面的表达式模拟的事实是，参与人的收益与他传递的流量正相关但与总流量负相关。 上式右侧第二项（即括号内的项）说明传递质量随着所用总带宽的增加而下降。注意， 这个博弈是个无限博弈（因为策略集为实数区间）。我们将在第6章证明，站在社会角 度看，这个博弈的均衡结果不是最优的。 4.12密封拍卖 有个人想把一件不可分割的东西卖给n个潜在买者中的一个。这里，N={1， 2，"，n）表示买者集（参与人集）。令vi，U2，"，Un表示参与人对拍卖物的评价 （valuation）。n个买者递交密封报价（bid），每个买者的报价不需要等于评价。假设参 与人i（i=1，，n）的密封报价可为任何正实数。于是，参与人的策略集为 S=（0，∞），i=1，"，n。谁的报价高，谁就得到拍卖物；假设如果多人报出了相同 的最高价，那么谁的标号小，谁就得到拍卖物。令这n个参与人的报价分别为b，b2， ，bn。于是，配置函数（allocationfunction）为 博 1，若对于j=1，…,i-1，b;>b;；对于j=i+1，，n，b;≥b； 奔 yi(b1,..,bn)= 论与机制 10，其他情形 在第一价格密封拍卖中，中标者支付的钱数等于他的报价，未中标者不需要付钱。在第 制 二价格密封拍卖中，中标者支付的钱数等于未中标者所出的最高报价，未中标者不需要 设计 付钱。在这两种拍卖中，参与人的收益或效用为下列形式： ui(b1,·..,bn)=y：(b,·..,bn)（u;—t;(b1,…,bn)) 其中t;（b，，b）是当参与人i的报价为b：（i=1，，n）时，他（指参与人i）支 付的钱数。假设n=4，再假设参与人的评价分别为v=20，v2=20，u=16，v4=16， 报价为b=10，b2=12，b=8，b4=14。于是，对于第一价格拍卖和第二价格拍卖，配 置函数为y（b)=0，y2（b)=0，y3（b)=0，y4(b)=1，其中b=(b，b2，b，b）。对于第 一价格拍卖，参与人支付的钱数分别为t（b)=0，t2（b)=0，t（b)=0，t4（b)=14；对于第 二价格拍卖，参与人支付的钱数分别为t（b)=0，t（b)=0，t（b)=0，t4（b)=12。根据参 与人对拍卖物的评价及其支付的钱数，不难算出各自的效用。 4.13庇古网络博弈 这个例子描述了参与人各自独立行动情形下的自私线路（selfishrouting）问题。 图4一1是一个有向图，它由两个节点S和T以及两条独立路线A和B组成。一定交通

量需要从S到达T。每条线路都伴随着成本函数c（·），它描述了用户从S到达T所需 的成本（例如交通时间）。每条线路的成本取决于该线路上的交通量占总交通量的比例。 假设xE[0，1]表示交通路线占比。在线路A，对于所有xE[0，1]，成本函数为c（x）= x。在线路B，成本函数固定且等于1，即对于所有x∈[0，1]，c（x）=1。上面这种路 由网络称为庇古网络（Pigounetwork）。[3] n,(s) n S 图4一1庇古网络 我们考虑上述网络的简化版本，这个网络有两个用户，即N={1，2}。每个用户 （参与人）有两个策略A和B，它们分别对应路线A和B。因此，S=S2={A，B}。参 与人同时且独立选择自己的路线。面对给定的策略组，参与人的收益有一种自然的定义 方法，即令其等于交通成本的相反数。例如，假设策略组为（A，B），即参与人1选择 线路A，参与人2选择线路B。参与人1的交通成本为，这是因为线路A的交通量占 策略型博奔 选择了线路B；他的收益为一1。因此，这个路由（即线路）博弈的收益矩阵为 A B A -1，-1 B -1，-1 如果有n个用户，则N={1，，n}，S=…·=S={A，B}。令s=（si，……，S） 为所有参与人选择的一个策略组。为了定义收益函数，我们首先将nA（s）定义为在策略 组s中选择线路A的人数。类似地，nB（s）定义为在策略组s中选择线路B的人数。显 然，对于每个策略组s，我们都有nA（s)十nB（s)=n。于是，收益函数为 u;(s)=nA(s) 若si=A n =-1 若si=B 我们将在第6章分析这个博弈。

4.14布雷斯论博弈 这个博弈改编自EasleyandKleinberg4]。它说明了布雷斯悖论，后者的名字来自 德国数学家迪特里希·布雷斯。这个论通常与交通网络联系在一起，它说明了一个不 符合直觉的事实一给定一个交通网，在增加额外容量后，结果反而变差（以交通时间 衡量）。图4一2中的交通网由起点S、终点T以及两个中间枢纽A和B组成。要求从S 点到达T点。一条线路经过A点，另外一条经过B点。 S 起点 终点 B 图4-2有4个节点的交通网 不管线路上有多少辆车，从S到B或从A到T都需要25分钟。另一方面，从S到 m是BT路段上的车辆数。假设有n=1000辆车想从S点到达T点。这意味着 N={1，2，…，1000}。策略集为S=…=S={A，B}。给定策略组（s1，·，S）， 令nA（si，，S）表示经过A点（即选择SAT线路）的车辆数，nB（si，，S）表示 经过B点的车辆数。注意，nA（si，"，Sn）十nB（Si，，Sn）=n。由于我们希望使得从 S到T的交通时间最小，因此，参与人的效用可以自然定义为他从S到T所需交通时 间的相反数。容易看到， u(Ss1,.,Sn)=——25-nA(s1,,Sn) 若s=A =25-nB(s1,",Sn) 若s=B 这定义了一个策略型博弈。注意到 u;（A，A,.，A)=u;（B，B，·…，B)=-45 u;（s1，，Sn）=-35当nA（s1，，Sn）=nB（S1，",Sn）=500 现在，为了缓解交通网的拥挤程度，我们打通从A到B的道路，这是一条单向路 段（作为一种退化情形，假设从A到B的交通时间为零）。图4一3描述了增加AB路

段后的新交通网。 S 起点 终点 B 图4一3打通单行道AB后的交通网 现在，每辆车可用的策略有：从S到A到T（称为策略A)；从S到B到T（称为 策略B)；从S到A到B到T（称为策略AB）。因此，我们有S=…=S={A，B， AB）。在按照以前的方法定义nA（s1，"，Sn）、nB（si，，Sn）以及nAB（Si，"，Sn） 之后，我们有 u;(s1,…,Sn) 若si=A 若si=B nA(S,.,Sn)+nAB(S,·.,Sn)nB(S,·.,Sn)+nAB(S,·.,Sn) 若s=AB 策略型博弈 我们将在第5章和第6章分析上面两个博弈，并且说明布雷斯悖论。 4.15小结与参考文献 在本章，我们提供了一些策略型博弈（也称为标准型博弈）的例子，以便让读者看 到如何将现实世界中的策略情形抽象为博弈。我们提供的例子包括： ·硬币配对博弈，这是一个两人零和博弈；石头剪刀布博弈，这是另外一个两人零 和博弈。这些博弈被称为零和博弈的原因在于，在每个博弈结果中，两个参与人的效用 之和等于零。它们也被称为严格竞争博弈（strictlycompetitivegames）。 ·BOS博弈，也称为性别大战博弈，描述的是两个参与人想协作但对结果又有不 同偏好的情形。 ·协作博弈或学生协作博弈。在这个博弈中，两个参与人只有待在一起时各自的收 益才为正；然而，他们待在一起时的各自收益取决于他们选择的行动。 ·囚徒困境。这是一个经典二人博弈，它说明了策略冲突和合作的很多微妙变化。 在这个博弈中，理性且智能的行为没有导致社会最优结果。

·公司两难博弈说明了囚徒困境博弈如何用于模拟两公司试图击败对方的策略 情形。 ·非对称公司的两难描述的是两个公司的收益结构不对称时的策略情形。 ·双寡头定价博弈。这个博弈描述两个竞争公司如何对特定产品定价。 ·公地悲剧。这是一个多人博弈，它说明了在资源使用上存在利益冲突时的情形， 这是一个常见的社会难题。 ·带宽共享博弈。在这个博弈中，参与人为多人，而且策略集是无限的；这个博弈 说明了公共资源使用上的冲突。 ●密封拍卖。在第一价格密封拍卖和第二价格密封拍卖中引人了策略型博弈。 ·庇古网络博弈说明了参与人各自独立行动情形下的自私路由问题。 ·布雷斯论博弈描述了参与人的策略冲突如何导致了交通线路博弈中的著名 悖论。 上面的例子代表了本书所要讨论的主要情形。需要指出，除此之外，还有众多有趣 且流行的博弈例子，但本书未涉及。事实上，本书只讨论了很少一部分流行的例子。下 列文献提供了更多策略型博弈的例子：Osborne[1]，Straffin[5]，Binmore[6]，以及 Maschler,Solan,and Zamir[7]。 本章讨论的内容主要来自下列三本书：Myerson[8]，Mascolell，Whinston，and Green[9]，以及Osborne andRubinstein[1]。Tardos andVazirani2]的论文很好地介绍 了博弈论中的概念，我们的很多例子取自他们的论文。 博 奔论与机 口参考文献 [1]MartinJ.OsborneandArielRubinstein.A CourseinGameTheory.Oxford 制 University Press, 1994. 设计 [2]E.Tardos and V.Vazirani.“Introduction to game theory:Basic solution con- cepts and computational issues".In:Algorithmic Game Theory.Ed.by Noam Nisan, Tim Roughgarden,Eva Tardos,and Vijay Vazirani.Cambridge University Press, 2007，pp.3-28. [3]T.Roughgarden and E.Tardos.“How bad is selfish routing?“In:Journal of ACM49(2)(2002)，Pp.236-259. [4]David Easley and JonKleinberg.Networks,Crowds,and Markets:Reason ingAboutaHighlyConnectedWorld.CambridgeUniversityPress,2010. [5]PhilipD.StraffinJr.GameTheory andStrategy.TheMathematicalAssocia- tion of America,1993. [6]Ken Binmore.Fun and Games:A Text On Game Theory.D.C.Heath& Company,1992. [7]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam- bridgeUniversityPress,2013. [8]Roger B.Myerson.Game Theory:Analysis of Conflict.Harvard University Press,Cambridge,Massachusetts,USA,1997.

[9]AndreuMas-Colell,Michael D.Whinston,andJerryR.Green.Microeconomic Theory.OxfordUniversityPress,1995. [10]Noam Nisan,TimRoughgarden,Eva Tardos,and VijayVazirani (Editors). AlgorithmicGameTheory.CambridgeUniversityPress,2007. [11]MartinJ.Osborne.AnIntroduction to Game Theory.TheMIT Press,2003. 4.16习题 （1）本章介绍了一些博弈，但限于篇幅，未能纳人一些有趣的博弈例子。请考察其 他一些博弈，例如鹰鸽博弈、冷战、污染控制、古诺定价博弈、ISP路由博弈等，读者 可参考文献[10,11,5,6,7]。 （2）有n个参与人。每个人在集合（1，，K）中选择一个数，其中K是一个既 定的正整数。然后计算被选中那些数的平均数，谁选中的数最接近这个平均数的2/3， 谁就获胜，从而得到1元奖金；如果出现多人获胜的局面，则这些获胜人均分1元奖 金。将这个问题表达为一个策略型博弈。 （3）对于庇古网络博弈，写出n=3和n=4时的策略型。 （4）考虑下列策略型博弈（网络构型博弈）。网络节点为参与人：N={1，2，，n）。 参与人i的策略集S是由N{i}的所有子集组成的集合。参与人在给定节点上的一个策 略是决定他所希望链接的其他节点。一个策略组对应着一个特定的网络或图。假设是 第 一个链接（link）上的每个节点得到的利益（其中0«1)，而c是每个节点为维持该 章 链接而承担的成本（其中c>0）。另外，假设d是一个k跳（k-hop）关系得到的利益， 策略型博弈 其中k是所涉两个节点之间最短路径的长度。一个链接只有在双方都同意时才能建立， 但可单方面终止。给定一个策略组形成的一个图g，令节点i的效用u：（g）为 u;(g)=∑o(e)-c.d;(g) j≠i 而l（g）是节点i和j之间最短路径中链接的个数，d;（g）是节点i的阶（degree）。假 设节点数为n，写出对应于下列图形的策略组并计算所有单个节点的效用。 ·完全图（completegraph）； ●直线图； ●星形图。