32博弈论 供他或她利用的选项,如果两个结点是在相同的信息状态下被同一局屮人所控 制,那么两个结点后继的行动标号集必须是相同的。例如,跟随2的上结点的 枝上的行动标号集必须与跟随2的下结点的枝上的行动标号集相同。(如果我 们在她的下结点上增加标记为“反加注”的第三枝前对其上结点未做相应的增 加,这将意味着,当且仅当局中人1有一张黑色牌时,局中人2才可以反加 注,但是,在她不知道局巾人1所持牌的颜色而无从知道这个选择项是否存在 之际,她又何以实施这个选项呢?为了得到…个有意义的博弈,我们将不得不 在2的两个决策点处都包含“试试反加注”这一枝,只要这两个结点具有相同 的信息标号。)另一方面,跟随结点“1.a”的枝上的行动标号与跟随结点 “1.b”的枝上的行动标号不必保持一致,这是因为局屮人1能够区分这两个 结点。假如行动标号不是一一对应,局中人1将仍然知道他的选项是什么,因 为他(通过看牌的颜色而)知道他处在哪个结点上。 因为对于具有信息标号相同的两个或两个以上的结点的局中人来说,其选 择的真正对象是行动,所以对枝指定行动标号的方式是非常重要的。这个博弈 的趣味性来自这样一个事实,即对2来说,在其上结点选择放弃是较好策略, 在其下结点选择对抗是较好策略,但问题在于当她决定是对抗还是放弃之际 她并不知道自己正处在局路径的哪个结点上。另一方面,如果我们交换一下局 中人2在其上结点的两个行动标号,而保持图2·2中其余一切不变,那么,所 得到的博弈就彻底不同了。如此修改后的树图将表示一个非常没有趣味的博 弈,其中的局中人2显然会选择对抗,因为对抗将使她从红色牌中得到1的 42支付,而从黑色牌中得到+2的支付,然而放弃只能使她从红色牌中得到-2 的支付,而从黑色牌中得到-1的支付。 为了给出展开型博弈严格的一般定义,我们需要用更准确的术语。按照数 学上图论的语言,一个图( graph)是由一个有限的结点(或点)集与一个枝 集一起构成的,每个枝连接一对结点。从集合论上讲,一个枝也可以与其所连 接的两结点所构成的集合等同。一条路径(path)就是形如 |= 1k=1,2 的一个枝集,其中m≥2且每个x是图中不同的结点。我们可以说这样的 个路径连接( connects)结点x1与xm6树(tre)就是这样的一个图,其中每 对结点有且仅有一条该图中的枝路径相连。一个根树( rooted tree)又是这样 的一个树,其中有一特定的结点被规定为此树的根(rot)。在本书中,总是 把根表示在树图的最左端。当我们说到一个给定结点的路径(path)时,我们 指的是连接这个结点与根的唯一路径。根树的某个结点处的一个选择(atcr native)是指连接此结点与另结点的枝,但这个枝不能在到该结点的路径上 个结点或枝x跟随( follows)另一个结点或枝y,当且仅当y处在到x的路 径中。一个结点x直接最随( immediately follows)一个结点y,当且仅当x
第二章基本模型 跟随y,并且y处有一个选择连接了x与y。根树的一个终结点( terminal node)就是一个没有任何选择跟随的结点。 对于任一正整数n,一个n人展开型博弈( n1- person extensive- form game) r‘是对每个结点和每个枝都规定标号的一-棵根树,且满足下列5个条件 1.每个非终结点有集:0,1,2,…,n}屮的一个局中人标号( player abel)。局中人标号为0的结点称为机会结点( chance nodes)。集合1,2, n}表示这个博弈的局中人集,并且对此集中的每个i,其有局中人标号 i的结点都是被局中人i所控制的决策结点( decision notes) 2.机会结点处的每个选择具有一个规定其概率的标记。在每个机会结点, 这些选择的机会概率( chance probabilities)都是非负数,且其和为1 3.一个局中人所控制的每个结点都有第二个标号,这个标号规定了局路径43 到达这个结点时该局中人将拥有的信息状态( information state)当局路径到 达某局中人所控制的个结点时,该局中人只知道当前结点的信息状态。也就 是说,属于同一局中人的两个结点具有相同信息状态的充分必要条件是,当这 两个结点屮任何一个在博弈进行中发生时,此局中人不可能对这两个结点所表 示的局势加以区分。在木书的记号中,仟何一个结点上的局中人标号与信息标 号之间是用小数点间隔开的,其左边是局中人标号,其右边是信息(状态)标 号,因此“i.k”表示的结点是决策者i以信息状态k行动的一个结点。 4.被一个局中人所控制的一个结点,其每个选择都具有一个行动标号 ( move label)。进一步说,对于任意两个具有相同的局中人标号和信息标号的 结点r和y,以及对于结点x处的任何一个选择,在y处一定有且仅有一个与 此选择具有相同行动标号的选择。 5.在每个终结点,都有一个指定n个实数的n维向量(a;, (u;)i…0的标记。对于每个局中人;,当此终结点是博弈的结果时,数u 是局中人i以某种效用尺度度量的支付( payoff)。 一般地,我们假定展开型博弈满足一个被称为完美记忆( perfect recall 的附加条件。这个条件断定,只要决策者一行动,他就会记起在此博弈中他先 前知道的全部信息,包括他自已过去的所有行动。这个完美记忆的假定可以被 正式地定义如下。 6.对于任何一个局中人i及其控制的任意三个结点x、y和z,以及x处 的任一选择b,如果y和z具有相同的信息状态且y跟随x和b,那么就存在 某个结点w及其某个选择c使得z跟随着w和c,局中人i控制着w,w与x 具有相同的信息状态,而且c具有与b相同的行动标号(当然有可能是v=x 和c=b)。也就是说,如果两个决策结点y和z对决策者来说是不可区分的 那么,对于t在y所能记起的任何一个过去的决策结点和行动,他在z也一定 有一个与之不可区分的决策结点和行动被记起。(作为一个不具有完美记忆博 弈的例子,假设图22中标有“2.0”的结点被换成“1.0”,则所得到的博弈
34博弈论 表示了一个相当奇异的局势,其中局中人1控制了所有的决策结点,但在他决 44定对抗还是放弃时,他不能记起以前他在决定是否加注时所知道的信息。也可 参见第4章的图43) 如果一个博弈中没有两个结点具有相同的信息状态,那我们就说这个博弈 具有完美信息( perfect information)。也就是说,在一个具有完美信息的博弈 中,每当局中人行动时,他总是知道所有其他局中人和机会以前的行动,以及 他自己以前的行动。图2·4中的傅弈具有完美信息,但图2·2和图2·3给出的 博弈都不具有完关信息。 在展开型博弈屮,局中人的一个策略( strategy)是为这个博弈中每个可 能的信息状态都确定了一个行动的某种规则。从数学角度而言,一个策略是 个将信息状态映射为行动的函数。对每个局中人i,令S1表示在这个博弈中 的可能信息状态集,而对S;中的每个信息状态s,令D表示i在具有信息状 态s的结点行动时,可供其利用的行动集,于是,局中人i在展开型博弈中的 策路集就是X∈sD,。 在我们的简单摊牌博弈中,局中人1具冇4个策略,记他的策略集为 Rr, Rf. Fr. Ff 其中第一个大写字表示在结点“1,a”(有一张红色牌)所标明行动的首字 母,第二个小写字母表示在结点“1b"(有一张黑色牌)所标明行动的首字 母。例如,Rf表示的策略为“若是红色牌则加注;若是黑色牌则摊牌”;而Rr 表示的策略为“不论牌是红色还是黑色都加注”。值得指出的是,局中人1的 策略是对局中人1的所有可能偶然事件都规定了一个行动的完整规则,尽管实 际上只会有一个偶然事件确实发生。局中人2只有两个可能策略,用“ (表示若1加注则对抗)和“P”(放弃)表示,这是因为局中人2只有一种可 能的信息状态。 作为另外的两个例子,考虑图23和图24。在图2·3给出的一个博弈 中,局中人2必须在没有观察到1的行动时就在L和R之间进行选择。对于 局中人2的任一选择L或R,局中人1都是选择T为更好,因此,在图2·3 所表示的博弃中,局中人1应该选择T。当局中人1选择了T,局中人2可以 通过选择L得到支付2。 图2·4与图2·3唯一的不同在于其局中人2的两个结点具有不同的信息状 45态,因此,在这个博弈中,局中人2在从L和R(或和r)之间做出选择之前 已经观察到了1的实际选择。于是,在这个博弈中,局中人1有一个影响2的 选择机会。对局中人2来说,如果她观察到了T,选择L将是更好的(因为2 >0);如果她观察到了B,选择r将会更好(因为1>0)。因此,局中人1应 该预料到他能从选择T中得到支付2,而从选择B中得到支付3。因而,在图 24所表示的博弈中,局中人1应该选择B。在局中人1选择了B之后,局中
第二章基本模型35 人2应该选择r而得到支付1。 L22 ●4,0 图 图2·3 注意到在图23中,局中人2的策略集只是{L,R|,而在图24中她的 策略集却是L,Lr,Re,Rr}(先写在结点2.2处的行动,后写在结点2.3 处的行动)。因而,此博弈一个扩大局中人2的策略集的信息结构变化,可能 会改变局中人1的最优行动,并从而实际降低局中人2的期望支付。 如果我们观看一次图24中的博弈,我们将会观察到局中人2的行动(L 或R或或r),但我们将不能观察到2的策略,因为我们不能看到局中人2在 她的另一信息状态下会做什么。例如,若局中人1选择了B,则局中人2被观46 察到的反应在策略Rr和策略Lr两者之下都是同一个(r)。然而,为了解释在 图24中局中人1为什么应该选择B,其关键是要认识到局中人2应理性地遵 循策略Lr(“若T则L,若B则r"),且局中人1应该能明智地预期到这一点。 如果能预期到局中人2会遵循策略Rr(“若T则R,若B则r”),那么局中人 就可以通过选择T以获得支付4而改善其境况。 2.2策略型和正规表示 表示一个博弈的一种较简单的方式就是利用策略型。为了定义一个策略型 博弈,我们只需要明确这个博弈的局中人集、每个局中人可利用的选择集,以 及局中人的攴付依赖于其所选择选项的方式 形式上,一个策略型( strategic-form)博弈就是任何一个具有如下形式的 r=(N,(C):∈N,(u1);∈N) 其中N是一个非空集,对N中的每一个i,C:是一个非空集,且v:是从 ∈NC到实数集R的一个函数。这里,N是这个博弈的局中人集。对每个 局中人i,C是可供局中人讠利用的簟賂( strategies)[或纯策賂( pure strate
36博弃论 gies)]集。在策略型博弈进行时,每个局中人i都必须在集C中选择一个 策略。一个策略组合( strategy profile)就是N中所有局中人可以选择的策略 的一个组合。设C是由所有可能的策略组合所组成的集,则 C=XO 对于C中任一策略组合c=(c)∈N,如果c是局中人所执行的策略组合,那 么v;(c)就表示此时局中人i在这个博弈中将得到的期望效用支付。在我们 研究—一个策略型博弈时,我们通常假定所有局中人都是同时地选择他们的策 略,故在策略型博弈的分析中没有时间元 如果-个策略型博弈的局中人集N和所有策略集C都是有限的,那这个 弈就是有限的( finite)。在阐述博弈论的基本思想时,除非另有规定,我们 般都假定博究具有这里所说的有限性。 展开型博包含了在这个博弈实际进行中随着时间变化而可能发生行动和 47事件序列的全囿描述.就这个意义而言,展开型博弈是一个动态模型。另·方 而,策略型博弈则忽略了所有的时间问题,并把所有的局中人视作同时选择他 们的策略,从而在这种意义上,策略型博弈是一个静态模型。显然,如果时间 问题对我们的分析而言不是本质问题,那么从我们的模型中除去时间因素就可 能是个实质性的概念简化。为了实现这样的简化,冯·诺依曼和摩根斯特恩提 出了一个对任何给定的展开型博『构造-个策略型博弈的程序。 为了说明这个程序,冉考虑一下图2.2所示的那个简单摊牌博弈。现在假 设局中人1和2知道他们明大将玩这个博弈,但每个局中人今天就在事先计划 他或她的行动了。局中人1不知道他明天抽的牌将是什么颜色,但现在他可以 计划抽到一张红色牌他该怎么办和抽到一张黑色牌他该怎么办。也就是说,如 我们所见,局中人1在这个展开型博弈中的可能策略集是C1=iRr,R「,Fr, Ff,其中第一个字母表小如果他拙到一张红色牌(在标号1.a的结点)时的 行动,而第二个字母表示在其抽到一张黑色牌(在标号1.b的结点)时的行 动。局中人2今天不知道局中人1将加注还是摊牌,但她今天可以计划在1加 注时是对抗还是放弃。因此,局中人2今天可从中选择的策略集是C2=|M P,其中M表示策略“若1加注则对抗”,而P表示策略“若1加注则放弃”。 即使我们知道了每个局中人所计划要用的策略,但由于我们不知道抽出的 那张牌将是红色牌还是黑色牌,所以我们仍然不能预测这个博弈的实际结果。 例如,如果局中人Ⅰ选择策略Rf(若是红色牌则加注,若是黑色牌则摊牌), 局巾人2选择的策略是M,那么1的最后支付将是:若是红色牌则为+2(因 为这时1要加注,2将对抗,且1将获胜);或者是黑色牌则为-1(因为1将 摊牌认输)。不过,由于我们知道红色牌与黑色牌出现的概率各为1/2,所以 当这两个策略在博弈中使用时,我们能够对每个局中人计算期望支付。于是, 当局中人1计划使用策略Rf而局中人2计划使用策略M时,局中人1的期望