混合策略与混合 策略纳什均衡 混合策略是纯策略的一种自然推广。参与人的一个混合策略将概率分布与他的纯策 略联系在一起。混合策略为参与人的现实世界策略行为提供了很好的抽象，而且丰富了 可能性空间。在本章，我们引入混合策略和混合策略纳什均衡的概念。我们给出并且证 明了一个重要且有用的定理，它为混合策略构成为混合策略纳什均衡提供了必要充分条 件。我们提供了一些例子来帮助读者理解这些重要概念。接下来，我们讨论了混合策略 混合策略与混合策略纳什均衡 中的最大最小值和最小最大值。我们也讨论了混合策略中的优（劣）势，并且说明了反 复删去强劣势策略的做法。 7.1混合策略 考虑策略型博弈T=（N，（S：），（u））。回忆一下，S：的元素称为参与人i （i=l，，n）的行动（actions）或纯策略（purestrategies）。如果参与人i根据既定 概率分布选择S：中的策略，我们就得到了混合策略或称随机策略。在下面的讨论中， 我们假设对于每个i=1，，n，S都是一个有限集。 定义7.1（混合策略）给定参与人i及其纯策略集S：，他的一个混合策略（mixed strategy）或称随机策略（randomizedstrategy）o;是S：上的一个概率分布。也就是说， o;:S→[0，1]是一个映射，它对每个纯策略s;∈S;都指定一个概率o;（s;)，使得 ∑o;(s;）=1 s;ES, 参与人的纯策略，比如s∈S，可以视为参与人i的一个混合策略一对策略s指 定概率1，并且对所有其他策略指定概率0。这样的混合策略称为退化混合策略（de-

generatemixed strategy），记为e（s;）或更简单地记为si。 如果S;={sa，S2，"，Sm），那么显然参与人i的所有混合策略构成的集合是集合 S：上的所有概率分布构成的集合。换句话说，它是集合： △（S;）={（o，，0m）∈Rm：o≥0对于j=1,,m且≥ j=1 上面的集合△（S）称为S;的混合扩展（mixedextension）。使用策略集的混合扩展，我 们可将纯策略博弈T=<N，（S），（u））的一个混合扩展定义为 TME=<N,(△(S)),(U)) 注意，对于i=1，"，n，U：是一个映射，它将混合策略组映到实数上： U:△(S)X··X△(S)→R 给定o∈△（S）（i=1，，n），U（o1，，on）的一种自然定义和计算方法如下。首 先，我们做出标准假设：单个参与人的随机化是相互独立的。这意味着给定混合策略组 （o1，“"，o），随机变量o1，“，O是相互独立的。因此，纯策略组（si，，S）的联合 概率为 o（s1,"",Sn）=IIo;(s) iEN 收益函数U：的定义为 博奔论与机制设计 U;(o1,.,on）=o（s1,.,Sn）u;(s1,.….,Sn) (ss)∈S 注意，U（o1，，o）（i=1，，n）是参与人根据联合分布o选择策略组（s1， s）所带来的期望收益。下面，当不至于出现混淆时，我们将用u：替换U。也就是说， 我们不再写成U（o1，，on），而是简单地写为u（oi，，on）。 的收益矩阵如下： A B A 2，1 0，0 B 0，0 1，2 假设（o1，o2）是一个混合策略组。这意味着是集合S={A，B）上的一个概率分 布，而o2是集合S2={A，B）上的一个概率分布。我们将o和o2分别表示为 01=（01(A)，o1(B))；02=（02(A),o2(B)) 我们有S=S×S2={（A，A)，（A，B)，（B，A)，（B，B）}。现在我们将计算收益函 数u和u2。注意，对于i=1，2， u;(0102）=g（s1,S2）u;(s1S2) (s,S)ES

函数u可以计算为 u（o1，02)=0(A)o2(A)u(A,A)+o(A)o(B)u(A,B)+o（B)o2(A)u（B,A) +o(B)o(B)u(B，B) =2o（A)（A)+（B)o（B) =2o（A)o（A)+（1-（A))（1-o2（A）) 整理可得， u（o1，02）=1+3o（A)（A)-0（A)-o2（A) (7.1) 类似地，我们也可得 u2（01，o2）=2+30（A）o（A)-20（A)-2o（A) (7.2) 假设=（，），=（，）。于是，容易算出 上面两个值相等，原因体现在收益函数的结构上。口 7.2混合策略纳什均衡 第7 我们现在定义混合策略纳什均衡，它是纯策略纳什均衡的自然推广。 章 定义7.2（混合策略纳什均衡）给定策略型博弈T=（N，（S），（u;））以及它的一 混 个混合策略组（o，…，o），若对于所有i∈N， 合策略与混合策略纳什均衡 ui（o，0-:）≥u;（oio=:）对于所有o;∈△（S;） 则（o，"，o）是一个混合策略纳什均衡（mixedstrategyNashequilibrum）。 定义最优反应函数（bestresponsefunctions）b;（·）如下： b;（o-i）={o;∈△（S:）：u;(oi，o-i）≥u;（oio-i）对于所有o∈△（S:）} 给定o-i，b（o-：）是参与人i的所有混合策略构成的集合，其中每个混合策略都是他针 对其他参与人选择o-：行为的最优反应。于是，显然，混合策略组（o，，o）是一 个纳什均衡当且仅当 o∈b;（o-;）对于所有iEN 例7.2（BOS博弈的混合策略纳什均衡）令（o，o2）是BOS博弈的一个混合策 略均衡。于是， u（o²，o）≥u（1，o）对于所有o1∈△（S1） u2（o，02）≥u2（o²o2）对于所有o2∈△（S2） 任何满足上面两组式子的解都是混合策略纳什均衡。若使用上面的表达方法表述式

（7.1）和式（7.2），则这两个式子分别等价于 3o（A)o（A)-o（A）≥3o（A）（A)-o（A）对于所有1E△（S） 3o（A)o（A)-2o（A）≥3o（A）o（A)-2o（A）对于所有o2E△（S2） 整理可知，上面两个式子分别等价于： o（A){3o（A)-1}≥0（A){3（A)-1}对于所有∈△（S） o（A){3o（A)→2}≥o2（A）{3o（A)-2}对于所有o2∈△（S2） 这里有三种情形： ●情形1：3o2（A)>1。由此得到纯策略纳什均衡（A，A)。 ●情形2：3o2（A)<1。由此得到纯策略纳什均衡（B，B)。 ●情形3：3o2（A）=1。由此得到混合策略纳什均衡（o，o2）： o*(A)=2 0²(B)= o2²(A)=1 3(B)=2 容易验证o∈b（o），o2∈b2（o*）。 7.3混合策略的性质 现在我们证明混合策略的一些有趣性质和结果。首先，我们回顾一下凸组合的 定义。 combination）是一个形如入iyi十入2y2十…十入ny，的加权平均数，其中 0<入;<1,i=1,2,.…,n; 命题7.1令T=<N，（S），（u;）》是一个策略型博弈。则u（o:，o-）可以表示为 下列凸组合： u;（oi0i）=o;（si）u;(Si0-i) 其中 u;(sio-i）=∑（IIo;（s;））u;(SSi） ESij≠i 证明：首先注意到 u;（oi0-i）= ∑（IIo;(s;）)u;(siS-i) (S,s)∈SjEN ∑∑∑（IIo,(s））u(ss-i) SESSES2sESjEN

=∑∑（IIo;(s））o;(s)u;(sis-i) ES;sESj≠i =∑o;(s){∑（IIo;(s;)）u(si，si）} s,ES; ESj≠i 由此立即可得： u;(oi0-i）=o:（s）u;（Sioi) S;ES; 这个结果的含义是，任何参与人i在任一混合策略下的收益都可以视为当他选择纯 策略s：而其他参与人选择混合策略o-：时的收益的凸组合。 现在我们用简单的例子说明凸组合在混合策略环境中的一些重要观察。 例7.3假设N={1，2}，S={x1，x2，x3，x4，x5}， u（0102）=o1（s1）u（s102) =o1（x）u（x1，o2）+o（x2）u（x202）+o（x）u（x302） +o（x）u（x402）+o1（c5）u1（x52） 假设S是一个有限集。令u（x1，o2）=5；u（x2，o2）=u（x3，o2）=10；u（x4，o2）= u（xs，o）=20。首先，注意到上述凸组合的最大值为20，这个最大值是当o（x4）=1 或o（cs）=1或更一般地o（x4）十o（xs）=1时得到的。也就是说，这个最大值是当 o（x）+o（x2）+o1（x）=0，或等价地，当o（x1）=o1（x2）=o1（x3）=0时得到的。另 外，注意到 maxu（01,02）=20； maxu（01,02）=maxu1（s102） E△(S,) E(S) 混合策略与混合策略纳什均衡 令p∈{01∈△（S):u(01o2)≥u(0i，02）o∈△（S）} p(x)+p（x5)=1 p（x)+p（x2)+p（x）=0 (p（x)=p（x2)=p（x3）=0 p（y)=0yargmaxu1(s1，02) SES 根据这个例子，可得到下列重要结果。口 命题7.2给定策略型博弈（N，（S），（u）），于是，对于任何oE×∈N△（S）以 及对于任何参与人证N， maxu;(oi0-i）=maxu;（si,0-i) ∈△(S) s,ES; 而且 piEargmaxu;(oio-i) E△（S;) 当且仅当 p;（x)=0Vxargmaxu;(sio-i) s

证明：第一步是将u（o，o-）表示为一个凸组合： u（oi0-i）=o;（s;）u;（si0-i） s,ES; 凸组合值中的最大者就是最大值。因此， maxu;（oio-i）=maxu;（so-） a;E△(S;) 混合策略o∈△（S）将实现这个最大值当且仅当 Zp;（x）=1,其中X=argmaxu;（sio-i) rEX SES, 上式等价于：p;（x）=0，Vxargmaxu;（si，o-i）。 SES; 7.4策略组成为混合策略纳什均衡的必要充分条件 我们现在证明混合策略纳什均衡策略组的一个极其有用的特征。首先，我们定义混 合策略的支撑这个概念。 定义7.4（混合策略的支撑）令o:为参与人i的任一混合策略。o:的支撑（sup port）（记为（o;））是由o：中所有伴随非零概率的纯策略构成的集合，即： 博奔论与机制设计 （o）={s;∈S:0（s)>0} 定义7.5（混合策略组的支撑）令o=（o1，，o）是一个混合策略组，而且（o） 是o的支撑，i=1，"，n。于是，混合策略组o的支撑（o）是所有单个支撑的笛卡 儿积，即（o）X·X（on）。 定理7.1混合策略组（o，，o）是一个混合策略纳什均衡当且仅当 （1）u;（si，o）都相等，Vs;∈（o）； （2)u;（si，o-）≥u;（si，o=;），Vs∈o（o）且Vso（o）。 在本章余下的内容中，我们将上面的（1）和（2）分别称为条件（1）和条件（2）。 这个定理意味着参与人的任何伴随正概率的纯策略，带给他的收益都相等，而且这个收 益不会小于任何伴随零概率的纯策略带给他的收益（当然前提是所有其他参与人选择他 们的纳什均衡混合策略）。这个定理在很多情形下都非常有用，比如纳什均衡的计算。 我们现在证明这个定理。 证明（必要性） 假设（o，，o）是一个纳什均衡。我们必须证明这个策略组满足条件（1）和 （2）。由纳什均衡的定义可知，对于所有证N， ui(oo=i)≥u;（oio=;）Voi∈△（S;) 这意味着 u;（ooi）=maxui(oio;) 0,E△(S;)

使用前面的命题（7.2），我们可以写出 u;(o，o;）=maxu;(sio-;) 根据命题（7.1）立即可知 Zo（s:）u;（sio;）=maxu;（so）对于所有i∈N ES; s’s 由于对于所有s（o），我们都有o（s）=0，因此上式变为 ∑o（s）u（so）= maxu(sio) 对于所有EN s’s 假设给定数x，，xk，我们有凸组合πx十十πkxk，其中π≠0对于所有 i=1,.….，k，使得π+·….+πk=1以及πx+·….+πkxk=max（x1，，xk），于是，容 易看到 x=x2 xk=max（x1,..,xk) 使用上面的性质，我们得到 u;(So)=maxu;(sio)，Vs:∈（o）,Vi∈N S,ES; 这立即意味着 ui（sio=）=u;（ooi)，s:∈8（o²),Vi∈N 由上式容易看出 u;(sio）≥u;(so),s;∈8（o²）,Vs（o),i∈N 混合策略与混合策略纳什均衡 这就证明了必要性。 （充分性） 假设： （1）u（si，o）有相同的值，比如w，对于所有s∈（o），Vi∈N。 (2)u;(Si，o;)≥u;(si，o;)，s∈（o)，s（o²),i∈N。 为了证明充分性，我们必须证明（o，“，o）是一个混合策略纳什均衡。考虑 对于任何证N， u;（o²o）=Zo（s;）u;（Sio;）（命题7.1) ’s ∑o²（s）u（s）（由于o²（s）=0，Vs（o）) ∑o（s）·w;（条件1) s（0) Zo(s;)w;（Vo;∈△（S;)) S;ES; Zo:（s;）u(si，o）（条件2） S,ES;

=u;（oi0;） 因此，上面的不等式可以写为 ui（oo)≥u;(oio）o∈△（S),Vi∈N 因此，（o，“，o）是一个混合策略纳什均衡。 口必要和充分条件的含义 上面的必要和充分条件有着下列含义： ·给定一个混合策略纳什均衡，每个参与人在他的均衡混合策略中选择任何伴随正 概率的纯策略所带来的收益是相等的（等于均衡时他的收益）。 概率的那些纯策略）是无差异的。当然，如果该参与人仅选择其中一个纯策略，那么对 于其他参与人选择的纳什均衡策略来说，它可能不是一个最优反应。 ·为了验证一个混合策略组是否为纳什均衡，只要考虑参与人偏离纯策略（其他参 与人仍选择他们的均衡策略）所带来的效应就足够了。 另外一个重要含义体现在下列结果上。 命题7.3给定s∈S，令e（s:）表示退化的混合策略，它将概率1指定给s并且 将概率0指定给S：中其他所有策略。策略组（s，"，S）是博弈（N，（S），（u）） （（））>（（）（）） 博 奔论与机制 （u））的一个混合策略纳什均衡。 证明：我们首先证明充分性。令（e（s），…"，e（s））是一个混合策略纳什均衡。这 u;(e(s),e(s=;))≥u;(oie（s=))o;∈△(S;),i∈N 制 设计 u;(s，s)≥u;(os)VoiE△（S),i∈N

u;（ss=i)≥u（e(s),s=)s;ES，Vi∈N u;(s,s;)≥ui(sis;)VsiES,ViEN （s，…，s）是一个纯策略纳什均衡。 上面我们证明了充分性。现在我们证明必要性。给定（s，，s）是一个纯策略纳什 均衡。这 u;(ssi)≥u;(sis)Vs;ES,iEN ui(e(s)e(s;))≥u;(se(s=))Vs;∈S，Vi∈N u（e(s）,e(s=))=maxu;（s;，e（s=))i∈N u（e（s），e(s=;)）=maxu;（oe（s=:))Vi∈N（根据命题7.2) E△(S,) u;(e（s²）),e(s=;))≥u;(oie(s=;))o;∈△(S;),i∈N （e（s*），"，e（s））是一个混合策略纳什均衡。 这个命题意味着，若想找出博弈（N，（△（S:)），（u））的纯策略均衡，只要考察 纯策略博弈（N，（S：），（u））就足够了。

口BOS博弈的混合策略纳什均衡 我们再次考虑BOS博弈，它的收益矩阵如下： A B A 2，1 0，0 B 0，0 1，2 我们首先验证（A，A）是一个纳什均衡。对于这个策略组，我们记 o（A）=1，o（B）=0 o（A）=1,o（B）=0 u（A，02）=2，u（B，0²）=0 定理（7.1）的条件（1）显然为真。条件（2）也为真，因为 u(A,o2）>u（B，o2) 类似地，参与人2也满足这些条件。因此，（A，A）是一个纳什均衡。类似地，（B， B）也是一个纳什均衡。现在我们考察可能的纳什均衡：（（，)，（，)）。我 们记 o*(A)=2 (B)= o2(A)= 混合策略与混合策略纳什均衡 (B)= 我们首先考察参与人1。下面验证条件（1）。 =2 因此，条件（1）得以满足。现在考察条件（2）。条件（2）显然满足，这是因为8（o） 等于整个策略集{A，B}。 现在考察参与人2。我们首先验证条件（1）。 u2(o，B)= 因此，条件（1）得以满足。与以前一样，条件（2）显然得以满足。 下面考察是否还存在着其他纳什均衡。均衡（A，A）对应着支撑（A}×{A}。均衡 (B，B)对应着支撑（B}×{B)。均衡((，)，(，))对应着支撑{A，B}× {A，B}。我们注意到下列事实：

·不存在对应着支撑（A}×{A，B}的纳什均衡。如果参与人1选择A，那么参与 人2必须选择A，这导致了纯策略纳什均衡（A，A）。参与人无法以非零概率选择B。 ·类似地，不存在对应着下列任何一个支撑的纳什均衡： {B}X{A,B} {A,B}X{A} {A,B}X{B} {B}X{A} {A}X{B} ·我们考察是否还存在着其他纳什均衡对应着支撑（A，B}×{A，B）。为了看清 这一点，将（o，o）定义为 o（A）=x，o（B）=1-x o（A）=y，o（B）=1-y 令这个（o，o）为满足x≠0，x≠1，y≠0以及y≠1（0<x<1；0<y<1）的 纳什均衡。于是，根据定理（1）的条件，我们有： u（A，o2）=u（B，0²） u2（o，A)=u2（o，B) 这意味着2y=1-y以及x=2(1-x)。这又意味着y=；x= 博奔论与机制设计 均衡 =(，)，=(，) 上面的均衡与我们以前讨论的均衡相同。因此，这个博弈不存在任何其他均衡。 口协作博奔的混合策略纳什均衡 我们考虑协作博弈，它的收益矩阵为 A B A 10，10 0，0 B 0，0 1,1 我们可以将这个博弈解释如下：两个参与人为同在一所大学的两个学生，策略A对 应着在大学学习，策略B对应着看电影。我们已经看到（A，A）和（B，B）都是纯策略 纳什均衡。它们分别对应着支撑（A}×{A）和（B}×{B}。可以证明，支撑{A}×{B}； {B}X{A}；{A}X{A，B}；{B}X{A，B}；{A，B}X{A}；{A，B}X{B}不能产生任何 纳什均衡。我们现在考察是否存在纳什均衡对应着支撑（A，B}×{A，B}。令o*=（x， 1一x）与o=（y，1-y）（其中x≠0，x≠1，y≠0以及y≠1）构成了一个纳什均衡。 于是条件（2）自然满足（因为在每种情形下，支撑都是整个策略集）。验证条件（1）

可得： u（A，02）=u（B，02） u2（o²，A)=u2（o，B) 上面的式子等价于 10y=1-y 10x=1-x 由此可得：=，=。这表示(=(，)，=(，))也是个纳什均 衡。这个均衡多少有些不符合直觉，然而仔细考察定理7.1中的条件（1）和（2）就能 知道为何它必定是一个纳什均衡。注意，参与人对他们选择策略的概率没有真正的偏 好。真正决定这些概率的是纳什均衡的要求，它要求其他参与人对于他们支撑集中的纯 策略是无差异的。学生们看电影的概率更高而不是在大学学习的概率更高，这难道不常 见吗？这里有趣的事情是，尽管在大学学习能给参与人提供更高的收益，但他们更可能 在电影院相聚（如果这是他们选择的（焦点）均衡）。 7.5混合策略中的最大最小值与最小最大值 我们已在6.6节讨论了纯策略背景下的最大最小值和最小最大值概念。现在我们在 混合策略背景下讨论这些概念。为了方便起见，与以前一样，我们仍用表示最大最小 混合策略与混合策略纳什均衡 值，用表示最小最大值。需要指出，既定参与人在混合策略中的最大最小值未必等 于他在纯策略中的最大最小值。类似的结论也适用于最小最大值。 口混合策略中的最大最小值 给定策略型博弈，参与人的最大最小值是在其他参与人自由选择任何混合策略而导 致的最坏情形下，他仍能保证自已得到的最大收益。这个概念正式定义如下。 定义7.6（混合策略中的最大最小值）给定策略型博弈T=（N，（S），（u;）>，参 与人i（i=1，"，n）在他的混合策略中的最大最小值或称安全值为： U=max u;（oi，0-i) E△（S)∈Xji(S,) 任何能保证参与人i得到这个收益的混合策略o：E△（S）都是他的最大最小混合策略或 称安全混合策略。 注释参与人可能有多个最大最小混合策略。 下面的命题说明，参与人在混合策略纳什均衡中的收益至少等于他在混合策略中的 最大最小值。证明类似6.6节中命题6.1的证明。 命题7.4假设策略型博弈T=（N，（S），（u））有混合策略纳什均衡（o，，o）。 那么

u;(o，.,on）≥U;iEN 其中是参与人i的混合策略的最大最小值。 口混合策略中的最小最大值 在直觉上，参与人i的混合策略的最小最大值是当其他参与人选择对参与人i最不 利的混合策略时他们能施加给参与人的最小收益。它的正式定义如下。 定义7.7（混合策略中的最小最大值）给定策略型博弈T=（N，（S：），（u）），参 与人i（i=1，"，n）在他的混合策略中的最小最大值为： 0= min.. maxu;(oi0-i) ∈Xj（S,)∈△（S;) 任何能把这个收益强加给参与人i的混合策略组。-都是其他参与人针对参与人i的一个 最小最大混合策略组。 与纯策略背景类似，在直觉上，参与人在他的混合策略中的最大最小值必定小于或 等于他在混合策略中的最小最大值。下面的命题形式化了这个事实。证明过程类似6.6 节命题6.2的证明。 命题7.5给定策略型博弈T=（N，（S），（u）>。我们有： NA 博奔论与机制 其中：是参与人i在混合策略中的最大最小值；：是参与人i在混合策略中的最小最 大值。 注释事实上，在两人策略型博弈中，混合策略中的最大最小值等于混合策略中的 最小最大值。值得注意的是，这个结论不适用于纯策略背景。 设计 下列命题说明参与人在混合策略纳什均衡（若存在）中的收益至少等于他的最小最 大值。这个命题的证明类似6.5节命题6.3的证明。 命题7.6假设策略型博弈T=<N，（S），（u））有混合策略纳什均衡（”，，o）， 那么 u;(o，.,o）≥U;i∈N 其中：是参与人i在混合策略中的最小最大值。 注释上面的讨论表明，参与人在混合策略纳什均衡（若存在）中的收益大于或等 于他在混合策略中的最小最大值，而他在混合策略中的最小最大值又大于或等于他在混 合策略中的最大最小值。 7.6混合策略中的优（劣）势 在本节，我们定义混合策略背景下的优（劣）势概念，并且说明如何用删去劣势策 略的做法来简化博弈分析。

口优势策略与劣势策略 假设（N，（S），（u））是一个策略型博弈。我们已在第5章讨论了纯策略背景下 的优（劣）势概念。现在，我们将其推广到混合策略背景。 定义7.8（混合策略中的优（劣）势）给定参与人i的两个混合策略o，o∈△（S）， 若 u;(oi0-i)>ui(oio-i)Vo-i∈Xj≠i△（S;) 则称o强优于o（o:strongly dominateso）。* 若 u;(oio-i)≥u;(oo-i）Vo-i∈Xj≠i△(S;) u;（oi0-i）>ui（oi，o-i）对于某个o-i∈Xj≠i△（S;) 则称o;弱优于o（o:weaklydominateso）。 若 u;(oi0-i）≥u;(oi，o-i)Vo-i∈Xj≠i△（S;) 则称o:极弱优于o（o:veryweaklydominatesoi）。 对于上面各个情形，我们也说：强劣于，弱劣于，极弱劣于oio 定义7.9（优势混合策略均衡）若混合策略o强优于（弱优于）（极弱优于）所 第7 有其他策略∈△（S），则称o是参与人i的一个强（弱）（极弱）优势策略。给定策 章 略组（o，，o），若o是参与人i（i=1，，n）的一个强（弱）（极弱）优势策 略，则（o，，o）称为一个强（弱）（极弱）优势混合策略均衡。 混合策略与混 注释显然，任何优势混合策略均衡也是混合策略纳什均衡。 注释任一参与人的强优势混合策略（若存在）是唯一的。因此，强优势混合策略 均衡（若存在）也是唯一的。 例7.4考虑囚徒困境博弈，它的收益矩阵见图7—1（a)。 合策略纳什均衡 (a) (b) (c) NC C C C NC -2,-2 -10,-1 NC -10,-1 C -5,-5 C -1,-10 -5,-5 C -5,-5 图7-1 囚徒困境问题以及删去强劣势策略 由于对于参与人2来说，策略NC强劣于策略C，他永远都不会选择NC。因此， 可将参与人2的策略NC删去，从而得到图7一1（b）中的简化收益矩阵。现在，对于 参与人1来说，策略NC也强劣于C，删去NC，即可得到图7—1（c）中的简化收益矩 *在本节中，原书作者将强优（劣）势与严格优（劣）势交叉使用，但为了与第5章一脉相承，译者统一使用 强优（劣）势这种称呼。——译者注

阵，它只有一个元素（一5，一5），这对应于策略组（C，C)，而（C，C）正好是一个 强优势策略均衡。口 例7.5考虑图7—2所示的两人博弈（这个博弈来自ShohamandLeyton- Brown[1]，我们稍微做了一些修改)。 X Y Z A 3，1 0，1 0，0 B 0，1 4，1 0，0 C 1，1 1，1 5，0 图7一2以两人博奔说明如何删去强劣势策略 注意，参与人2的策略乙强劣于X，也强劣于Y。因此，参与人2永远不会选择策 略Z（不管参与人1选择什么策略），因此，策略乙可以删去，从而得到图7一3所示的 简化博弈。 X Y A 3，1 0,1 B 0，1 4，1 C 1,1 1,1 图7一3删去参与人2的策略Z后得到的博弈 现在注意，参与人1的任何纯策略都不劣于他的其他纯策略。然而，策略C强劣于 对A和B指定相等的正概率的那个混合策略。还要注意，在原来的博弈中，策略C不 劣于任何混合策略。当删去一个强劣势策略之后，原来不劣势的策略现在可能变得劣 势。还需要注意，既定纯策略可能不劣于任何其他纯策略，但可能劣于这些纯策略的混 合（mixture）。 X Y A 3，1 0，1 B 0，1 4，1 图7一4删去策略C之后得到的博弈 图7一4画出了删去参与人1的策略C之后得到的博弈。到此，已没有其他策略可 进一步删去。口 口反复删去劣势策略 我们已经看到，删去强劣势策略的做法能简化博弈分析。我们将其如下形式化。考 虑一个有限策略型博弈（N，（S;），（u）>。令k=1，2，，K表示删去强劣势策略的 轮次。对于每个参与人证N，将策略集S定义如下：

·S=S S+≤S，k=1，2，·，K-1。 ·对于k=1，2，，K-1，所有策略s∈S\S+1都是第k轮从i∈N的策略集 S中删去的强劣势策略。 ·在iN的策略集为S的博弈中，S中的任何策略都不是强劣势策略。 上面的步骤定义了反复删去强劣势策略这个过程。我们将策略组构成的集合 {（s1,S2,.".,Sn）:S;∈SK，i=1,..,n} 称为经过反复删除强劣势策略之后剩下的策略。 例7.6考虑图7—2中的两人博弈，其中S={A，B，C}，S2={X，Y，Z}。对 于这个博弈， ·S=S={A，B，C}；S=S2={X，Y，Z}。 ·S²={A，B，C}；S²={X，Y}。 ·S²={A，B}；S={X，Y}。 因此，策略组{（A，X)，（A，Y)，（B，X)，（B，Y)）是经过反复删去强劣势策 略之后剩下的策略。口 注释假设我们在反复删去强劣势策略过程之后已删去了所有伴随o（s）=0的纯 策略s∈S;（i=1，"，n），从而得到由剩下的所有策略组（o，o2，，on）构成的集 合。可以证明这个集合包含所有混合策略纳什均衡。如果我们运气好（例如囚徒困境情 形)，那么这个集合中的每个元素（o1，02，，o）都是纳什均衡。在另外一种极端情 第 形下，这个集合可能包含原来的所有策略组！因此，反复删去强劣势策略有时能够简化 章 纳什均衡的计算。当然，在更多时候，这种做法起不到任何简化作用。 混 注释如果博弈是一个有限博弈，那么反复删去劣势策略过程的轮次也是有限的， 合策 也就是说，经过一定轮次的删除之后，这个过程就终止了。可以证明，删去强劣势策略 略 的先后顺序（先删去哪个，后删去哪个）不会影响这个过程的最终结果。然而，对于弱 与 （极弱）劣势策略来说，删去劣势策略的先后顺序，的确会影响这个过程的最终结果。 混 合策 还需要注意，删去弱（极弱）劣势策略之后得到的简化博弈比删去强劣势策略之后得到 的简化博弈小。 略 纳 什 均 7.7小结与参考文献 衡 给定参与人i，他的一个混合策略是指他的纯策略集上的一个概率分布；混合策略 是参与人将纯策略随机化的一种自然表示方法。下列知识点值得注意。 ·当计算参与人在混合策略组下的期望收益时，我们假设参与人纯策略随机化过程 彼此独立。 ●一个混合策略纳什均衡就是参与人的一个混合策略组（o”，o2，"，o”）（其中 o是参与人i的混合策略），它使得任何参与人单方面偏离自已的均衡混合策略都无利 可图（单方面偏离是指其他参与人不偏离他们的均衡混合策略）。我们也可以将混合策

略纳什均衡定义为一个混合策略组（o，o2，“，o”），使得任何参与人i（i=1，， ·给定一个有限策略型博弈，它的任一混合策略纳什均衡都可以用下面两个条件描 述：（a）任何参与人i，在所有其他参与人选择他们的均衡混合策略o-：情形下的期望效 用都等于参与人i在他的均衡混合策略中选择任何伴随非零概率的纯策略所得到的效 用。（b）上面这个期望效用大于或等于参与人i在他的均衡混合策略中选择任何伴随零 概率纯策略所得到的效用（前提是所有其他参与人选择他们的均衡混合策略）。上面的 特征对于计算有限博弈的混合策略纳什均衡非常有用。 在考察了混合策略纳什均衡之后，我们讨论了混合策略背景下的最大最小值和最小 最大值概念。我们得到的重要结果是，参与人在混合策略纳什均衡中的收益不会小于他 在混合策略中的最小最大值，而这个最小最大值又不会小于他在混合策略中的最大最小 值。另外，在两人博弈中，参与人在混合策略中的最大最小值等于他在混合策略中的最 小最大值。 我们还讨论了混合策略背景下的优（劣）势概念，以及反复删去劣势策略的做法。 本章讨论的材料主要来自Myerson[2]，Osborne andRubinstein[3]，以及Mas- chler, Solan, and Zamir[4]。 在本章，我们隐含地假设策略集都是有限集，而且我们对混合策略所下的定义仅针 对这种有限博弈。然而，通过对无限策略集指定概率分布，混合策略也可以自然地推广 博 到无限策略集的情形。 奔 论 与 衡，这一点我们将在第10章详细讨论。无限博弈未必存在着混合策略纳什均衡。计算 机 纳什均衡是一个很有趣的议题。我们将在第11章考察这个问题。在第12章，我们讨论 制 设 与纳什均衡计算相关的计算复杂性问题。 计 本章关于混合策略背景下的优（劣）势材料主要来自Osborne[5]，Shohamand Leyton-Brown1]，以及Myerson2]。上面一些问题的证明也可以在这些参考文献中 找到。 口参考文献 [1YoamShoham andKevinLeyton-Brown.MultiagentSystems:Algorithmic, Game Theoretic,and Logical Foundations.Cambridge UniversityPress,New York, USA,2009. [2]RogerB.Myerson.Game Theory:AnalysisofConflict.Harvard University Press,Cambridge,Massachusetts,USA,1997. [3]MartinJ.Osborneand ArielRubinstein.A CourseinGameTheory.Oxford UniversityPress,1994. [4]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam bridgeUniversityPress,2013. [5]Martin J.Osborne.An Introduction to Game Theory.The MIT Press,2003.

7.8习题 （1）令S是任一有限集，它有n个元素。证明由S上的所有概率分布构成的集合 △(S)是一个凸集。 （2）给定策略型博弈（N，（S），（u）），证明对于任何两个混合策略o和o， ui(oo-i)>u;（oio-i）Vo-i∈△（S-i) 当且仅当 ui(os-i)u;(ois-i)Vs-i∈S-io （3）证明博弈（N，（S），（u））中的任何强优势策略必定是一个纯策略。 （4）找出下列硬币配对博弈的混合策略纳什均衡： H T H 1，-1 -1，1 T -1，1 1，-1 另外，计算混合策略中的最大最小值和最小最大值。确定每个参与人的最大最小混合策 略，以及其他参与人用于对付每个参与人的最小最大混合策略。 第7 （5）找出下列“石头剪刀布”博弈的混合策略纳什均衡： 章 混合策略与混 石头 布 剪刀 石头 0，0 -1，1 1,-1 布 1,-1 0，0 -1,1 剪刀 -1，1 1，-1 0，0 合策略纳 另外，计算混合策略中的最大最小值和最小最大值。确定每个参与人的最大最小混合策 略，以及其他参与人用于对付每个参与人的最小最大混合策略。 什均衡 （6）考虑下列两人零和博弈，其中a，b，c，d都是实数，而且a>b，d>c，d>b， a>c。计算这个博弈的所有混合策略纳什均衡。另外，计算混合策略中的最大最小值和 最小最大值。确定每个参与人的最大最小混合策略，以及其他参与人用于对付每个参与 人的最小最大混合策略。 A B A a,-a b，-b B C，-C d,-d （7）找出下列博弈的混合策略纳什均衡：

A B A 2，2 1,2 B 2，1 1,1 另外，计算混合策略中的最大最小值和最小最大值。确定每个参与人的最大最小混合策 略，以及其他参与人用于对付每个参与人的最小最大混合策略。 （8）找出下列博弈的混合策略纳什均衡： A B A 6，2 0，0 B 0，0 2，6 如果上表中的每个数字都乘以2，均衡会变化吗？ （9）考虑如下的任何两人博弈（其中a，b，c，d是任意实数）： A B A a，a b，c B c，b d,d 已知该博弈有一个强优势策略均衡。对于下列论断，判断对错并证明：上面的强优势策 略均衡是该博弈的唯一可能的混合策略均衡。 （10）这个博弈称为猜平均数博弈。有n个参与人。每个参与人在集合（1，，K} 博奔论与机 中选一个数。谁选的数越接近于平均数的2/3，谁就获胜，从而获得1元奖金，若出现平 局，这1元奖金就由那些获胜的所有参与人平分。将这个问题形式化为策略型博弈。证明 该博弈有唯一混合策略纳什均衡，在这个均衡中，每个参与人都选择了纯策略。 制 （11）给定下列两人博弈，其中 设计 S=[0,1],S=[3,4] u（x，y)=-u2（x，y)=｜x-yl（x，y)∈[0,1]×[3,4] 计算这个博弈的混合策略纳什均衡。 （12）给定策略型博弈，其中：N={1，2}；S=S2=[a，b]×[a，b]，这里a，b 都是正实数，而且a<b。也就是说，每个参与人同时在矩形[a，6]×[a，6]中选择一 点。将收益函数定义为 u（s1，S2）=-u2（s1，S2）=d（s1，S2） 其中d（si，S2）是si点和s2点之间的欧几里得距离。计算这个博弈的所有混合策略纳 什均衡。 （13）对于庇古网络博弈（参见第4章和第6章），分别计算n=2和n=3时的所有 混合策略纳什均衡。你能将这个结果一般化吗？ （14）一种商品，两个卖者1和2，三个买者A、B和C。 ·A只能向1购买。 ·C只能向2购买。

·B可以向1购买，也可以向2购买。 ·每个买者的预算（最大支付意愿）为1，希望购买1单位。 ·每个卖者的供货都充足。 ·每个卖者在实数区间[0，1]选择一个报价。令s和s2分别为卖者1和2的 报价。 ·显然，A以价格s买1的商品，C以价格s买2的商品。 ·对于买者B，如果s≤s2，B会买1的商品；否则，他会向2购买。 我们已在第6章证明了这个博弈没有纯策略纳什均衡。请问它有混合策略纳什均 衡吗？ （15）考虑单人博弈，其中N={1}，S=[0，1]。注意，集合[0，1]是紧的 （compact）。将效用函数定义为一个不连续的映射： u（s1）=s1若0≤s1<1 =0若s=1 证明这个博奔不存在混合策略均衡。 （16）考虑单人博弈，其中N={1}，S=[0，1)，注意集合[0，1）不是紧的。将 效用函数定义为一个连续映射： u（s）=sVs∈[0，1] 证明这个博弈也不存在混合策略均衡。 第 （17）使用混合策略纳什均衡的必要和充分条件，计算下列博弈的所有混合策略纳 什均衡： 章 混合策略与混今 A B A 20，0 0,10 B 0，90 20，0 （18）证明下列命题： 合策略纳什均衡 ●假设策略型博弈r=<N，（S），（u））有混合策略纳什均衡（，，o）。那么 u;(o,,o）≥ui∈N 其中是参与人i在混合策略中的最大最小值。 ·考虑策略型博弈T=（N，（S），（u））。那么 NA 其中u是参与人i在混合策略中的最大最小值，：是参与人i在混合策略中的最小最 大值。 ●假设策略型博弈T=（N，（S），（u））有混合策略纳什均衡（o，"，o）。那么 ui(oi,",o）≥U;Vi∈N 其中：是参与人i在混合策略中的最小最大值。

·给定一个两人策略型博弈，参与人在混合策略中的最大最小值等于他在混合策略 中的最小最大值。 (19）给定博弈（资料来源：Myerson[2]） X Y Z A 2，3 3，0 0,1 B 0，0 1，6 4，2 对其使用反复删去强劣势策略过程。 （20）给定博弈（资料来源：Myerson[2]） X Y A 3，2 2，2 B 1,1 0，0 C 0，0 1，1 对于这个博弈使用下列删去弱势策略的步骤，观察结果。你能从其中推断出什么？ ·删去C（然后删去Y）； ·删去B（然后删去X）； ·同时删去B和C。 （21）给定博弈（资料来源：OsborneL5]） X Y Z A 1,1 1,1 0,0 B 0，0 1，2 1，2 使用这个博弈说明反复删去弱劣势策略而得到的最终结果取决于删去弱劣势策略的先后 顺序。 （22）给定策略型博弈（N，（S：），（u;）），假设我们在反复删去强劣势策略过程之 后，已删去了所有伴随o（s）=0的纯策略s∈S：（i=1，，n），从而得到由剩下的所 有策略组（o1，02，“，o）构成的集合。证明这个集合包含所有混合策略纳什均衡。