货币贬值太大了,现在的收益要抵得上将来收益的好几倍,因而当事人只好顾及当前收益,力 求当前收益越多越好,而把未来长远利益放在次要位置上。 下面再看一个双头垄断的重复博弈事例。 例2.维持卡特尔 考虑一个简单的重复双头垄断,如果两个厂商都执行古诺博弈均衡策略,则得到利润 (e,r);如果以共同利润最大化决定产量水平,即执行卡特尔行动,则得到利润(丌m,m)。 我们知道,一次性博弈中共同利润最大化的产量不是博弈均衡,每个厂商都有激励去倾销额外 数量的产品,如果他认为其他厂商将保持产量不变的话。但是在重复博弈中,只要贴现率不太 高,合作起来以使共同利润最大化之策略,将是重复博弈的最优解 可以证明,如果这种简单的双头垄断博弈是一次性的,那么每个厂商以古诺产量生产将 是博弈的最优解。但是,如果这个博弈是不断重复的,那么每个厂商都采取按照卡特尔产量生 产的策略,即都选择合作,将是双头垄断重复博弈的最优解。对不合作的适当惩罚,是采取生 产古诺产量水平这一策略。可见,在不断重复的双头垄断博弈中,由于一次性博弈均衡这种惩 罚策略的存在,局中人都将以长远利益为重,来维持卡特尔。 第四节混合策略 并非所有博弈都有严格确定的结局。进一步,实际中博弈局中人常常希望自己的行动隐 秘不被暴露,不被对手觉察。对于这两个问题,目前意义上的策略博弈是解决不了的。在博弈 非严格确定或者局中人希望保守秘密的情况下,局中人的最好做法是采取混合策略,即以一定 的概率采取某种策略。这样做,甚至连局中人自己也不知道每一次行动中究竟采取什么策略, 竞争对手就更不得而知了。而且对于非严格确定的博弈来说,采用混合策略就可求得最优解。 当一种混合策略以概率Ⅰ选择某种策略时,这种策略就是前三节所谈论的“纯”策略,可见混 合策略扩展了策略概念。 混合策略的概念 我们以两人博弈为例,来对混合策略的概念以及采取混合策略时局中人的行动目标进行 解释。至于更一般的多人博弈,将在下一节中讨论。 设G=(S1∫S2g)为有限二人策略博弈,其中S1={si,s2,…,sm}为局中人甲的策略集 合,S2={si,s2,…,s}为乙的策略集合,∫和g分别为甲和乙的收益函数 局中人为了保持自己决策的秘密性,不再象以前那样选择纯策略,而决定采用随机办法 来选择策略。也就是说,局中人对纯策略的选择由某种随机装置来决定,对每个纯策略来说, 采用它只有可能性的大小,也就是用多大的概率来选择各个纯策略。这样,对方就不可能事先 知道究竟选择哪个纯策略,甚至连局中人自己也不可能事先知道,而纯策略是在最后时刻借助 随机装置选择出来的。通过借助随机装置,局中人原来对纯策略的选择变成为现在对各个纯策 略的概率大小的选择。 如果还嫌借助随机装置给出的选择各个纯策略的概率大小具有一定的客观性,怕被对方 估计出来,局中人还可进一步采取主观概率分布,以使对纯策略的选择带有真正的不确定性(参 见第六章关于主观概率的介绍)
第八章 博弈论 238 货币贬值太大了，现在的收益要抵得上将来收益的好几倍，因而当事人只好顾及当前收益，力 求当前收益越多越好，而把未来长远利益放在次要位置上。 下面再看一个双头垄断的重复博弈事例。 例 2．维持卡特尔 考虑一个简单的重复双头垄断，如果两个厂商都执行古诺博弈均衡策略，则得到利润 ( c , c ) ；如果以共同利润最大化决定产量水平，即执行卡特尔行动，则得到利润 ( m , m ) 。 我们知道，一次性博弈中共同利润最大化的产量不是博弈均衡，每个厂商都有激励去倾销额外 数量的产品，如果他认为其他厂商将保持产量不变的话。但是在重复博弈中，只要贴现率不太 高，合作起来以使共同利润最大化之策略，将是重复博弈的最优解。 可以证明，如果这种简单的双头垄断博弈是一次性的，那么每个厂商以古诺产量生产将 是博弈的最优解。但是，如果这个博弈是不断重复的，那么每个厂商都采取按照卡特尔产量生 产的策略，即都选择合作，将是双头垄断重复博弈的最优解。对不合作的适当惩罚，是采取生 产古诺产量水平这一策略。可见，在不断重复的双头垄断博弈中，由于一次性博弈均衡这种惩 罚策略的存在，局中人都将以长远利益为重，来维持卡特尔。 第四节 混合策略 并非所有博弈都有严格确定的结局。进一步，实际中博弈局中人常常希望自己的行动隐 秘不被暴露，不被对手觉察。对于这两个问题，目前意义上的策略博弈是解决不了的。在博弈 非严格确定或者局中人希望保守秘密的情况下，局中人的最好做法是采取混合策略，即以一定 的概率采取某种策略。这样做，甚至连局中人自己也不知道每一次行动中究竟采取什么策略， 竞争对手就更不得而知了。而且对于非严格确定的博弈来说，采用混合策略就可求得最优解。 当一种混合策略以概率 1 选择某种策略时，这种策略就是前三节所谈论的“纯”策略，可见混 合策略扩展了策略概念。 一．混合策略的概念 我们以两人博弈为例，来对混合策略的概念以及采取混合策略时局中人的行动目标进行 解释。至于更一般的多人博弈，将在下一节中讨论。 设 ( , ; , ) G = S1 f S2 g 为有限二人策略博弈，其中 S1 = s1 ,s2 , ,sm 为局中人甲的策略集 合， S2 = s1 ,s2 , ,s2 为乙的策略集合， f 和 g 分别为甲和乙的收益函数。 局中人为了保持自己决策的秘密性，不再象以前那样选择纯策略，而决定采用随机办法 来选择策略。也就是说，局中人对纯策略的选择由某种随机装置来决定，对每个纯策略来说， 采用它只有可能性的大小，也就是用多大的概率来选择各个纯策略。这样，对方就不可能事先 知道究竟选择哪个纯策略，甚至连局中人自己也不可能事先知道，而纯策略是在最后时刻借助 随机装置选择出来的。通过借助随机装置，局中人原来对纯策略的选择变成为现在对各个纯策 略的概率大小的选择。 如果还嫌借助随机装置给出的选择各个纯策略的概率大小具有一定的客观性，怕被对方 估计出来，局中人还可进一步采取主观概率分布，以使对纯策略的选择带有真正的不确定性(参 见第六章关于主观概率的介绍)
这种以某种概率选择的策略就是混合策略,更准确地说,选择混合策略就是选择一个概 率分布,然后按照这个分布给出的概率来选择各个纯策略。假如甲选择策略s′的概率为x; (=1,2,…m),∑mx=1,则向量x=(x1,x2,…xm)代表着甲选择各种纯策略的概率分布, 实际上就表示了甲的一种混合策略。这就是说,混合策略是用概率分布x来表示的,混合策略 的变化完全反映为概率分布x的变化。今后,我们把概率分布x=(x1,x2…,xm)就称为局中人 甲的混合策略。 原来的纯策略s可看成是这样的一种混合策略:以概率1选择策略s以概率θ选择其 他策略s(k≠i,k=1,2,…,m)。如此一来,甲的策略集合由原来的纯策略集合S1扩张成为混 合策略集合X={x∈[0]m:∑mx=l}。同样,局中人乙的选择集合也由原来的纯策略集合S2 扩张成为混合策略集合Y={ν∈[0叮]:∑1y=1}。当甲采取混合策略x,乙采取混合策略y 寸,(x,y)就称为博弈G的混合局势。 在采取混合策略的情况下,局中人的目标是要使预期收益最大化。当甲采取混合策略 x∈X,乙采取混合策略y∈Y时,甲和乙的预期收益分别为E和Eg: E=E(x,y)=∑∑xyf(s1,5)=∑∑xy,=x)ny7=xy i=1 Eg=Eg(x,y)=∑∑xy8(S,S) S Xiva xg) 这里,x和y都写成行向量形式,“”为转置运算。甲的收益函数由原来的∫:S1×S2→R扩 充成为E:X×Y→R,乙的收益函数由原来的g:S1xS2→R扩充成为Eg:X×Y→R。 在策略集合和收益函数都得到扩充以后,原来的纯策略博弈G=(S,∫,S2,g)就扩充成为 混合策略博弈G=(X,玢/;},Eg),而且G可看成是一般的二人博弈,不过这个博弈的收益函 数具有双线性性,即对于任何x,x2x"∈X,y,y,y"∈Y,及任何实数t∈[O,],都成立: Ef(tx+(1-0)x,y)=tE(x,y)+(1-OE(x,y) Eg(x, ty+(1-Dy=tEf(x,y)+(1-DEf(x,y") G的混合局势就是G的局势。博弈G叫做纯策略博弈G的混合扩充。关于混合扩充G,下述 两个事实是明显的: (1)博弈G是常和博弈当且仅当混合扩充G是常和博弈。 (2)如果G是常和博弈,则混合扩充G保持了原来博弈G的收益和 混合扩充G的最优解(均衡),叫做原博弈G的最优混合解(混合均衡)。也即(x*,y*)是G Ef(r*, y*)=max Ef(x, y*) 的最优混合解,是指(x)∈ X xY BEg(x,y)=mxEg(xy当(x)是G的最优 混合解时,x*和y*分别叫做甲和乙的最优混合策略。可以证明: (3)纯策略博弈G的最优解必然是混合扩充G的最优解。 (4)当G是常和博弈时,(x*,y*)是G的最优混合解当且仅当 max Ef(x,y*)=miEf(x*,y)。 从(4)可知,(x*,y*)是常和博弈G的最优混合解当切仅当(x*,y*)是预期收益函数E的 鞍点。应用第二节的鞍点定理,我们得到常和博弈的最优混合解的又一判别条件:
第八章 博弈论 239 这种以某种概率选择的策略就是混合策略，更准确地说，选择混合策略就是选择一个概 率分布，然后按照这个分布给出的概率来选择各个纯策略。假如甲选择策略 si 的概率为 xi (i =1,2, ,m) ， 1 1 = = m i xi ，则向量 x = (x1 , x2 , , xm ) 代表着甲选择各种纯策略的概率分布， 实际上就表示了甲的一种混合策略。这就是说，混合策略是用概率分布 x 来表示的，混合策略 的变化完全反映为概率分布 x 的变化。今后，我们把概率分布 x = (x1 , x2 , , xm ) 就称为局中人 甲的混合策略。 原来的纯策略 si 可看成是这样的一种混合策略：以概率 1 选择策略 si ，以概率 0 选择其 他策略 sk (k i, k =1,2, ,m) 。如此一来，甲的策略集合由原来的纯策略集合 S1 扩张成为混 合策略集合 { [0,1] : 1} 1 = = = m i i m X x x 。同样，局中人乙的选择集合也由原来的纯策略集合 S2 扩张成为混合策略集合 { [0,1] : 1} 1 = = = n i i n Y y y 。当甲采取混合策略 x ，乙采取混合策略 y 时， (x, y) 就称为博弈 G 的混合局势。 在采取混合策略的情况下，局中人的目标是要使预期收益最大化。当甲采取混合策略 x X ，乙采取混合策略 yY 时，甲和乙的预期收益分别为 Ef 和 Eg ： ( ) ( ) T T m n i j m i n j i j i j m i n j i j i j T T m n i j m i n j i j i j m i n j i j i j Eg Eg x y x y g s s x y g x g y xg y Ef Ef x y x y f s s x y f x f y x f y = = = = = = = = = = = = = = = = = = 1 1 1 1 1 1 1 1 ( , ) ( , ) ( , ) ( , ) 这里， x 和 y 都写成行向量形式，“ T ”为转置运算。甲的收益函数由原来的 f : S1 S2 → R 扩 充成为 Ef : X Y → R ，乙的收益函数由原来的 g : S1 S2 → R 扩充成为 Eg : X Y → R 。 在策略集合和收益函数都得到扩充以后，原来的纯策略博弈 G = (S1 , f ; S2 , g) 就扩充成为 混合策略博弈 G = (X,Ef ;Y,Eg) ，而且 G 可看成是一般的二人博弈，不过这个博弈的收益函 数具有双线性性，即对于任何 x, x , x X ， y, y , y Y ，及任何实数 t [0,1] ，都成立： ( , (1 ) ) ( , ) (1 ) ( , ) ( (1 ) , ) ( , ) (1 ) ( , ) Eg x t y t y tEf x y t Ef x y Ef t x t x y tEf x y t Ef x y + − = + − + − = + − G 的混合局势就是 G 的局势。博弈 G 叫做纯策略博弈 G 的混合扩充。关于混合扩充 G ，下述 两个事实是明显的： (1) 博弈 G 是常和博弈当且仅当混合扩充 G 是常和博弈。 (2) 如果 G 是常和博弈，则混合扩充 G 保持了原来博弈 G 的收益和。 混合扩充 G 的最优解(均衡)，叫做原博弈 G 的最优混合解(混合均衡)。也即 (x*, y*) 是 G 的最优混合解，是指 (x*, y*) X Y 且 = = ( *, *) max ( *, ) ( *, *) max ( , *) Eg x y Eg x y Ef x y Ef x y y Y x X 。当 (x*, y*) 是 G 的最优 混合解时， x* 和 y* 分别叫做甲和乙的最优混合策略。可以证明： (3) 纯策略博弈 G 的最优解必然是混合扩充 G 的最优解。 (4) 当 G 是常和博弈时， (x*, y*) 是 G 的最优混合解当且仅当 max Ef (x, y*) min Ef (x*, y) xX yY = 。 从(4)可知， (x*, y*) 是常和博弈 G 的最优混合解当切仅当 (x*, y*) 是预期收益函数 Ef 的 鞍点。应用第二节的鞍点定理，我们得到常和博弈的最优混合解的又一判别条件：
(5)设G=(S1,S2fC)是二人常和博弈,则(x,y*)∈XxY是G的最优混合解的充分必要条 件是E(x*,y*)= max min Ef(x,y)= min max Ef(x,y)。 二.混合策略的意义 有时,给予混合策略一个有意义的解释是困难的。第一节例1所述的便士匹配博弈,由 于收益矩阵没有鞍点,因而没有纯策略意义下的最优解。但由于硬币出现正面或反面,总有 个概率分布情况,因此采取混合策略来把便士匹配博弈加以扩充,然后寻找混合策略意义下的 最优解,这显然是我们大家都能够感觉得到的应该采取的做法。然而对于象双头垄断这样的 些其他经济利益博弈来说,采取混合策略似乎是不现实的。 除了混合策略在一定范围内缺乏现实意义外,还有一些逻辑上的原因导致对混合策略难 以解释。我们用一个例子来说明这一点。 例1.性别博弈( Battle of the sexes) 这里介绍的博弈背后隐藏的故事是一场“性别之战”。茹达( Rhonda,女)和卡夫( Calvin 男)本周末一起欢度良宵,但他们二人的娱乐爱好不同。茹达喜 性别博弈收益表 欢看话剧,而卡夫喜欢看足球比赛。如果他们同时选择看话剧 则茹达可得2个单位的效用,卡夫可得1个单位的效用;如果|茹达、|请剧足球 同时选择看足球比赛,则他们得到的效用正好与此相反;如果}话剧2,0,0 他们选择不同的娱乐,则得不到任何效用。右表给出了茹达和 卡夫的收益情况。我们来看一看茹达和卡夫之间这场“性别之战”博弈的结局究竟如何 首先,让我们寻找该博弈的所有纯策略意义下的最优解。通过对各种策略进行逐一相互 比较,不难看出“(话剧,话剧)”和“(足球,足球)”都是纯策略最优解,即茹达和卡夫选择 相同的娱乐,才是最好的做法。 然后,我们来寻找混合策略意义下的最优解。茹达的收益矩阵∫和卡夫的收益矩阵g为: f=(ui)2x2 01 茹达的预期收益为Ef(x,y)=x1yf1+x1y22+x2yf21+x2y2/2=2xy+x2y2,卡夫的预 期收益为Egx,y)=x1y181+x1y2g12+x2yg21+x2y2g22=x1y+2x2y2。因此,最优混合策 略问题可归结为如下的约束极值问题 max(2x1y1+x2y2):x1≥0,x2≥0,x1+x2=1 max(xy1+2x2y2):y≥0,y220,y+y2=1 应用Kuhn- Tucker条件(参见第七章第八节),上述极值问题的解为x1=2/3,x2=1/3, η=1/3,y2=2/3。这就是说,茹达以概率2/3选择看话剧,以概率1/3选择看足球比赛 卡夫以概率1/3选择看话剧、以概率2/3选择看足球比赛,是性别博弈的最优混合局势。这个 最优解有这样几个特点:第一,茹达和卡夫采取最优混合策略的预期收益都等于2/3:第二, 如果茹达采取最优混合策略x=(2/3,1/3),那么不论卡夫采取什么纯策略,卡夫的预期收益 也都是2/3:第三,如果卡夫采取最优混合策略,那么不论茹达采取什么纯策略,她的预期收 益也都是2/3。这样一来,还有什么理由要求茹达和卡夫双方都采取最优混合策略呢?看来, 要想人们采取混合策略,必须有一些更加令人兴奋的理由 本例说明,从逻辑上讲,采用混合策略没有多少道理。尽管如此,在某些情况下这种逻
第八章 博弈论 240 (5) 设 G = (S1 , S2 , f ,C ) 是二人常和博弈，则 (x*, y*) X Y 是 G 的最优混合解的充分必要条 件是 = = Ef (x*, y*) max min Ef (x, y) x X y Y min max Ef (x, y) yY xX 。 二．混合策略的意义 有时，给予混合策略一个有意义的解释是困难的。第一节例 1 所述的便士匹配博弈，由 于收益矩阵没有鞍点，因而没有纯策略意义下的最优解。但由于硬币出现正面或反面，总有一 个概率分布情况，因此采取混合策略来把便士匹配博弈加以扩充，然后寻找混合策略意义下的 最优解，这显然是我们大家都能够感觉得到的应该采取的做法。然而对于象双头垄断这样的一 些其他经济利益博弈来说，采取混合策略似乎是不现实的。 除了混合策略在一定范围内缺乏现实意义外，还有一些逻辑上的原因导致对混合策略难 以解释。我们用一个例子来说明这一点。 例 1．性别博弈(Battle of the Sexes) 这里介绍的博弈背后隐藏的故事是一场“性别之战”。茹达(Rhonda，女)和卡夫(Calvin， 男)本周末一起欢度良宵，但他们二人的娱乐爱好不同。茹达喜 欢看话剧，而卡夫喜欢看足球比赛。如果他们同时选择看话剧， 则茹达可得 2 个单位的效用，卡夫可得 1 个单位的效用；如果 同时选择看足球比赛，则他们得到的效用正好与此相反；如果 他们选择不同的娱乐，则得不到任何效用。右表给出了茹达和 卡夫的收益情况。我们来看一看茹达和卡夫之间这场“性别之战”博弈的结局究竟如何。 首先，让我们寻找该博弈的所有纯策略意义下的最优解。通过对各种策略进行逐一相互 比较，不难看出“(话剧，话剧)”和“(足球，足球)”都是纯策略最优解，即茹达和卡夫选择 相同的娱乐，才是最好的做法。 然后，我们来寻找混合策略意义下的最优解。茹达的收益矩阵 f 和卡夫的收益矩阵 g 为： = = 0 1 2 0 f ( fi j ) 2 2 ， = = 0 2 1 0 g (gi j ) 2 2 茹达的预期收益为 Ef (x, y) = x1 y1 f11 + x1 y2 f12 + x2 y1 f 21 + x2 y2 f 22 = 2x1 y1 + x2 y2 ，卡夫的预 期收益为 Egx, y) = x1 y1 g11 + x1 y2 g12 + x2 y1 g21 + x2 y2 g22 = x1 y1 + 2x2 y2 。因此，最优混合策 略问题可归结为如下的约束极值问题： + + = + + = max ( 2 ): 0, 0, 1 max (2 ): 0, 0, 1 1 1 2 2 1 2 1 2 , 1 1 2 2 1 2 1 2 , 1 2 1 2 x y x y y y y y x y x y x x x x y y x x 应用 Kuhn-Tucker 条件(参见第七章第八节)，上述极值问题的解为 x1 = 2 / 3 , x2 =1/ 3， y1 =1/ 3, y2 = 2 / 3 。这就是说，茹达以概率 2 / 3 选择看话剧，以概率 1/ 3 选择看足球比赛； 卡夫以概率 1/ 3 选择看话剧、以概率 2 / 3 选择看足球比赛，是性别博弈的最优混合局势。这个 最优解有这样几个特点：第一，茹达和卡夫采取最优混合策略的预期收益都等于 2/3；第二， 如果茹达采取最优混合策略 x = (2 / 3,1/ 3) ，那么不论卡夫采取什么纯策略，卡夫的预期收益 也都是 2/3；第三，如果卡夫采取最优混合策略，那么不论茹达采取什么纯策略，她的预期收 益也都是 2/3。这样一来，还有什么理由要求茹达和卡夫双方都采取最优混合策略呢？看来， 要想人们采取混合策略，必须有一些更加令人兴奋的理由。 本例说明，从逻辑上讲，采用混合策略没有多少道理。尽管如此，在某些情况下这种逻 性别博弈收益表 卡夫 茹达 话剧 足球 话剧 2，1 0，0 足球 0，0 1，2
辑上的毛病不会带来严重问题。例如,假定有一大群人在随机碰面并玩便士匹配游戏,甲是其 中一员。设最初每个人都按概率分布(1/2,1/2)执行唯一的最优混合策略,到最后有些人便厌 倦于执行此混合策略,而决定总是玩正面游戏或总是玩反面游戏。如果决定总出正面的人数等 于决定总出反面的人数,那么各个局中人的选择问题不会有明显变化:每个人仍然理性地以为 他的对手以50%的可能性出正面或反面。也就是说,虽然每个人都决定采取纯策略而总是出 正面或反面,但当甲随机碰到一个局中人时,该人是出正面还是反面,甲不得而知,只能作出 这样的判断:该人出正面的可能性为50%。这等同于该人采取混合策略。 对混合策略的另一种解释是:考虑某人在一次性博弈中出正面还是反面的选择,这个选 择被看作是依赖于一些为对手所不能确定的特殊因素。比如,该人心想“正面”时就出正面, 心想“反面”时就出反面。这种“心想”因素是很难为对手所把握的,一个人可以自我觉察到 自己的心情,但其他人(对手)却难以觉察这个人的心情。因此,每个局中人都会认为其他人 对策略的选择是随机的。这样,采取混合策略就是一件有意义的事情 第五节矩阵博弈的古诺均衡 前面介绍的博弈最优解(均衡)概念,假定了局中人各自独立行动,没有合作。这种非合 作二人博弈均衡概念,最早是由古诺提出来的,称为古诺均衡。无合作意味着局中人之间存在 着利害冲突,互相对抗,互为对手。矩阵博弈(即二人零和博弈)是对这种或对抗状态的简明刻 画,本节就下面就矩阵博弈均衡的存在性与算法问题及其均衡的性质进行讨论 均衡的存在性 收益矩阵的鞍点未必存在,这使得矩阵博弈的均衡未必存在。但当采用混合策略时,情 况就不同了:矩阵博弈的最优混合解总是存在的。下面用 von Neumann(1937)的构造性方法来 证明这一事实,构造性方法本身蕴含着古诺均衡的一种计算方法。 矩阵博弈均衡的存在性,任何矩阵博弈都有混合均衡。具体来说,设G=(S1,S2,∫)为 矩阵博弈,S1={si,s2,…,sm},S2={s1,s2,…,Sm},G=(X,,E)为G的混合扩充,则必存 在(x*,y*)∈X×Y满足E(x*,y)=max{Ef(x,y):x∈H}=mn{E(x*,y):y∈H}。 本定理的证明较长,会令读者感到枯燥。但证明过程给出了古诺均衡的计算方法,学习 掌握这一计算方法是重要的,读者有必要静下心来琢磨一下。 首先注意,令L(x)=mn{E(x,y):y∈Y},U(y)=max{Ef(x,y):x∈H},则(x*,y*)是G 的均衡当且仅当L(x*)=U(y*)。本定理的证明将基于这一事实。另外,可以看出L(x)和U(y) 具有下面三条性质 (1)对任何x∈x,都有Lx)=mnxy=mnx ()对任何yey,都有0()=mx2∑,=m∑m
第八章 博弈论 241 辑上的毛病不会带来严重问题。例如，假定有一大群人在随机碰面并玩便士匹配游戏，甲是其 中一员。设最初每个人都按概率分布(1/2,1/2)执行唯一的最优混合策略，到最后有些人便厌 倦于执行此混合策略，而决定总是玩正面游戏或总是玩反面游戏。如果决定总出正面的人数等 于决定总出反面的人数，那么各个局中人的选择问题不会有明显变化：每个人仍然理性地以为 他的对手以 50％的可能性出正面或反面。也就是说，虽然每个人都决定采取纯策略而总是出 正面或反面，但当甲随机碰到一个局中人时，该人是出正面还是反面，甲不得而知，只能作出 这样的判断：该人出正面的可能性为 50％。这等同于该人采取混合策略。 对混合策略的另一种解释是：考虑某人在一次性博弈中出正面还是反面的选择，这个选 择被看作是依赖于一些为对手所不能确定的特殊因素。比如，该人心想“正面”时就出正面， 心想“反面”时就出反面。这种“心想”因素是很难为对手所把握的，一个人可以自我觉察到 自己的心情，但其他人(对手) 却难以觉察这个人的心情。因此，每个局中人都会认为其他人 对策略的选择是随机的。这样，采取混合策略就是一件有意义的事情。 第五节 矩阵博弈的古诺均衡 前面介绍的博弈最优解(均衡)概念，假定了局中人各自独立行动，没有合作。这种非合 作二人博弈均衡概念，最早是由古诺提出来的，称为古诺均衡。无合作意味着局中人之间存在 着利害冲突，互相对抗，互为对手。矩阵博弈(即二人零和博弈)是对这种或对抗状态的简明刻 画，本节就下面就矩阵博弈均衡的存在性与算法问题及其均衡的性质进行讨论。 一．均衡的存在性 收益矩阵的鞍点未必存在，这使得矩阵博弈的均衡未必存在。但当采用混合策略时，情 况就不同了：矩阵博弈的最优混合解总是存在的。下面用 von Neumann(1937)的构造性方法来 证明这一事实，构造性方法本身蕴含着古诺均衡的一种计算方法。 矩阵博弈均衡的存在性．任何矩阵博弈都有混合均衡。具体来说，设 G = (S1 , S2 , f ) 为 矩阵博弈, S1 ={s1 ,s2 , ,sm }, S2 ={s1 ,s2 , ,sm }，G = (X,Y,Ef ) 为 G 的混合扩充，则必存 在 (x*, y*) X Y 满足 Ef (x*, y*) = max{Ef (x, y*): x X}= min{Ef (x*, y): yY}。 本定理的证明较长，会令读者感到枯燥。但证明过程给出了古诺均衡的计算方法，学习 掌握这一计算方法是重要的，读者有必要静下心来琢磨一下。 首先注意，令 L(x) = min{Ef (x, y): yY}，U(y) = max{Ef (x, y): x X} ，则 (x*, y*) 是 G 的均衡当且仅当 L(x*) =U(y*) 。本定理的证明将基于这一事实。另外，可以看出 L(x) 和 U( y) 具有下面三条性质： (1) 对任何 x X ，都有 = = = = = m i i i j j n n j j m i i i j y Y L x x f y x f 1 1 1 1 ( ) min min ； (2) 对任何 yY ，都有 = = = = = n j j i j i m m i i n j j i j x X U y y f x y f 1 1 1 1 ( ) max max ；
242 (3)对任何(x,y)∈XxY,都有L(x)sEf(x,y)=∑∑xysU() 进一步,假定收益矩阵∫=(f)m的各行已经过调整,使得∫m=max{fn:1≤i≤m} 这个假定并不是说増加了额外的条件,而是说在安排策略集S1中诸策略的编号时,可以让编 号满足这个要求。以下的证明分三步走。第一步:定义基和最优基:第二步:构造最优基 三步:从最优基得出混合扩充G的均衡 第一步:定义基和最优基 首先定义收益矩阵∫的增广矩阵∫如下 1f1f12…fin10…0 f21f2 f2n 0 0 ∫的首行、首列叫做第0行、第0列,即首行行标为0,首列列标为0。用P表示f的第j列 (j=01,2,…n+m),并令Uk=Pn+k(k=12.…,m)。从增广矩阵f的1+n+m列中选出1+m 列,构成一个1+m阶方阵B:B=(B,B1,…,Bm)。如果B满足下面三个条件: (b1)P是B的首列,即B0=P (b2)B是非奇异的矩阵,即行列式B≠0 (b3)B的逆矩阵B中除首行外,其余各行的第一个非零元素皆为正数 则称B是一个基(base)。 如此定义的基必然存在。例如,矩阵Bb=(P,B,U1,…,LUm1)就是一个基。事实上,B0 符合条件(b1)和(b2)是明显的。对于条件(b3),注意Bb的逆矩阵B如下 fm 00 6sJm1-f10…0 fm1-f2101 fml-fm-l1 0 0 而∫m≥fn(=1,2,…,m-1),故B符合条件(b3)。这就证明了Bb是基 现在对于任何一个基B=(B0,B1,…,Bm)来说,用R表示B-的第i行(i=0,…,m)。则 从BB=E(其中E为1+m阶单位阵)知RB=6,这里当i=j时δ=1,而当i≠j时 δ=0(,j=01.2,…,m)。这说明RB1=0(=12,…,m),可见在n+m个内积RP (=1,2,…,n+m)中,至少有m个为零。如果其余n个内积均非正,那么就称B是一个最优基 ( optimal base)。换句话说,基B是最优基,是指RP≤0(=12,…,n+m),即B-的首行 向量与f的后n+m个列向量的内积全非正。 第二步:用迭代法构造最优基 任意指定一个基Bo=(B0,B01,…,Bom)(比如上面的基Bb),从B0出发来构造最优基。 用R表示B的第行,C表示B的第j列,并检查B是否为最优基,即检查不等式 R8P≤0是否对一切j=1,2,…n+m都成立。如果B是最优基,则目的已达到。如果B不 是最优基,则max{R8P:j=1.2,…,n+m}>0,此时需做下面的工作 (1)找出一个P使RBP=max{R8P:j=1,2,…n+m}。若∫的诸列中符合这个条件的 列P不止一个,那么就取列标最小者
第八章 博弈论 242 (3) 对任何 (x, y) X Y ，都有 ( ) ( , ) ( ) 1 1 L x Ef x y x y f U y m i n j = i j i j = = 。 进一步，假定收益矩阵 f = ( fi j)mn 的各行已经过调整，使得 f m1 = max{ fi1 :1 i m}。 这个假定并不是说增加了额外的条件，而是说在安排策略集 S1 中诸策略的编号时，可以让编 号满足这个要求。以下的证明分三步走。第一步：定义基和最优基；第二步：构造最优基；第 三步：从最优基得出混合扩充 G 的均衡。 第一步：定义基和最优基 首先定义收益矩阵 f 的增广矩阵 f 如下： − − − = 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 2 21 22 2 11 12 1 m m mn n n f f f f f f f f f f f 的首行、首列叫做第 0 行、第 0 列，即首行行标为 0，首列列标为 0。用 Pj 表示 f 的第 j 列 ( j = 0,1,2, ,n + m) ，并令 Uk = Pn+k (k =1,2, ,n) 。从增广矩阵 f 的 1+ n + m 列中选出 1 + m 列，构成一个 1 + m 阶方阵 B ： B = (B0 , B1 , , Bm ) 。如果 B 满足下面三个条件： (b1) P0 是 B 的首列，即 B0 = P0 ； (b2) B 是非奇异的矩阵，即行列式 B 0 ； (b3) B 的逆矩阵 −1 B 中除首行外，其余各行的第一个非零元素皆为正数。 则称 B 是一个基(base)。 如此定义的基必然存在。例如，矩阵 Bb = (P0 , P1 ,U1 , ,Um−1 ) 就是一个基。事实上， B0 符合条件(b1)和(b2)是明显的。对于条件(b3)，注意 Bb 的逆矩阵 −1 Bb 如下： − − − − − − − = − − 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 11 1 21 1 11 1 1 m m m m m b f f f f f f f B 而 f m1 fi1 (i =1,2, ,m −1) ，故 Bb 符合条件(b3)。这就证明了 Bb 是基。 现在对于任何一个基 B = (B0 , B1 , , Bm ) 来说，用 i R 表示 −1 B 的第 i 行 (i = 0,1, ,m) 。则 从 B B = E −1 (其中 E 为 1 + m 阶单位阵)知 j i j i R B = ，这里当 i = j 时 i j =1 ，而当 i j 时 i j = 0 (i, j = 0,1,2, ,m) 。这说明 0 0 R Bj = ( j =1,2, ,m) ，可见在 n + m 个内积 R Pj 0 ( j =1,2, , n + m) 中，至少有 m 个为零。如果其余 n 个内积均非正，那么就称 B 是一个最优基 (optimal base)。换句话说，基 B 是最优基，是指 0 0 R Pj ( j =1,2, , n + m) ，即 −1 B 的首行 向量与 f 的后 n + m 个列向量的内积全非正。 第二步：用迭代法构造最优基 任意指定一个基 B0 = (B00 , B01, , B0m ) (比如上面的基 Bb )，从 B0 出发来构造最优基。 用 i R0 表示 1 0 − B 的第 i 行， j C0 表示 1 0 − B 的第 j 列，并检查 B0 是否为最优基，即检查不等式 0 0 R0 Pj 是否对一切 j =1,2, , n + m 都成立。如果 B0 是最优基，则目的已达到。如果 B0 不 是最优基，则 max{ : 1,2, , } 0 0 R0 Pj j = n + m ，此时需做下面的工作： (1) 找出一个 Ps 使 max{ : 1,2, , } 0 0 0 R0 Ps = R Pj j = n + m 。若 f 的诸列中符合这个条件的 列 Ps 不止一个，那么就取列标最小者