第4章 联盟博弈及其主要解概念--核

4.1 联盟博弈的基本概念

两人讨价还价问题也许是最简单的合作博弈，我们完全可以在形式上把它推广到n人之间的讨价还价问题（F, v），只不过，这里的F是n维空间中的可行盈利集合。v是n维实值向量。“直接”推广的办法无非是寻求F中的配置x=（x1, x2, …, xn），使得形式上的纳什积

达到最大。然而，事情并非如此简单。在实际事务中，一个焦点仲裁人，只要做到公正，就能比较容易地使谈判的双方坐到谈判桌旁。但是，如果代表各自利益的冲突各方人数比较多的话，焦点仲裁人将面临一件非常棘手的事情。局中人人数越多，需要照顾到的方方面面利益的难度就越大，这就是所谓的众口难调。

首先，我们不难注意到，意见不一致点v的确定就不会像两人问题那样简单。一旦n个人之间的谈判或交易不能达成合作协议，并不意味着n个人都返回到各管各单干的状态，在那种状态，我们可以将他们各自“单干”所获得的盈利作为他们各自的“底线”（在两人讨价还价问题中，常常是这样去认定的）。事实上，即使n个人无法形成一个合作的大联盟，完全有可能在部分人之间形成较小联盟（或称为子联盟）。如果这个联盟中的局中人通过他们组成的子联盟所获得的盈利大于各自单干所得到的盈利，那么从子联盟获得的盈利就可能成为这部分人进行谈判时作为讨价还价的“底线”。当n比较大时，子联盟的各种组成可能也随之增多，子联盟的形式也越发五花八门。这种情况严重地影响到意见不一致点v的选择与确定。在合作博弈中有一个著名的机场跑道成本分摊问题，完全反映了这方面出现的问题。

例4.1 n家航空公司联合建造一个新机场。机场跑道的建设成本显然与飞机的机型有关，不同的机型对跑道的长度与承受压力等有不同的要求。毫无疑问，适应大型飞机的跑道必定适应比较小的机型，但反之不然。为阐述方便起见，不妨假定每家航空公司只拥有单一机型，各航空公司的机型也互不相同。将这些公司按照它们的机型从小到大排列并分别称它们为局中人1,2, …, n。假设它们各自独立修建跑道的成本分别为c1≤c2≤…≤cn。常识告诉我们，n家公司共同修建跑道的总成本为cn，在一般情况下，共同修建跑道将使得每家公司都有可能节省一笔成本费用。这是一个典型的n人合作博弈问题，通过谈判与协商，达成合作协议，可以做到皆大欢喜。然而，倘若谈判破裂，v未必等于（c1, c2, …, cn）。设想一下，如果公司1和公司n形成子联盟，他们商定分摊成本分别为和，那么明显地优于各自独立修建的成本c1和cn。这样一来，在n人谈判过程中，公司1和公司n的“底线”就未必是c1和cn。类似于这样的子联盟可以有许许多多。因此，我们将不得不面临联盟之间相互作用问题的研究和分析。（机场跑道的建设成本与成本分摊问题，不仅需要考虑到飞机的机型大小，还要考虑各家公司对跑道的使用频率，我们这里仅仅考虑最简单的情况。）

当然，影响到意见不一致点的确定从而影响最终分配（或分摊）的因素不完全取决于n人这个封闭圈子里的联盟之间的相互作用，譬如在商务事件中的n人讨价还价问题中，常常存在圈子外的外部机会，使得其中的某些局中人可能希望去探索新的途径，即使在两人讨价还价的过程中也存在这样的情况，我们在第3章中就提到使谈判“破裂”的可能性。

不过在本章中，我们仅着眼于讨论联盟博弈。下面我们介绍联盟博弈的基本概念，并引入一些必要的记号。

n个人参与洽商、谈判、讨价还价等事件，希望能达成合作协议，这是一个合作博弈。以N表示由这n个局中人组成的有限（非空）集合，N={1,2, …, n}。局中人i∈N表示该局中人来自集合N。

研究合作博弈，总是假设n个人之间存在合作的可能性（也就是说，通过合作可以获得更多的盈利）。整个集合中，n个人的联合所构成的联盟称为大联盟。再看子联盟的形成，任何一个局中人“单干”，形成了规模最小的联盟。这种单干式的最小子联盟共有个。另外，任何两个人也都可以组成子联盟，“两人子联盟”的个数为个。类似地，“三人联盟”的个数等于个，…，“k人联盟”的个数为。为了保证所有的“联盟集合”在数学意义下应当具有的完备性，我们引入“空联盟”概念。空联盟∅意指在∅中不包含任何一个局中人，它的个数自然只有个。现在，我们可以计算所有可能的子联盟（大联盟和空联盟是特殊的子联盟）的总个数等于

式（4.2）的成立仅需考虑牛顿二项式公式：

在式（4.3）中，令x=y=1，即得式（4.2）。

上述公式告诉我们，实质性的有形的子联盟个数有2n-1个。由式（4.2）的启发，一切子联盟的集成记为2N。其中任意一个子联盟记为S∈2N，用|S|表示联盟S中所包含的成员的个数。一般情况下，S泛指任何子联盟，至于哪一个局中人属于这个子联盟，S并没有明确地表示。区分子联盟的不同之处的关键是它们包含了多少个什么样的局中人。为此，我们借助于特征向量（characteristic rector）这个工具。指示S的n维特征向量记作eS，它的第i个元素为

式（4.4）中，记号i∈N\S表示局中人i来自N但不属于S，这个记号在联盟博弈中常常要用到。显然，大联盟的特征向量为eN=（1,1, …,1）。

至此，我们已经充分关注了合作博弈中的局中人以及他们可能全部或部分合作的子联盟。N加上2N一起，其作用相当于非合作博弈建模过程中的基本要素——局中人集合。接下来，我们需要关注博弈的盈利问题。由于合作博弈很重要的研究内容是联盟之间的相互作用，因此，我们必须了解，对于每一个S∈2N，通过S中的成员的共同努力，他们可以得到的最大共同财富（worth）或盈利是多少，这个值将与一个实数相对应，显然它与S相关联。不同的S对应不同的实数，因此，可以用一个集值函数v（S）将这两者联系在一起。所谓集值函数，首先它是一个函数，其次它的变元是“集合”而不是通常意义下的“点”或“向量”。反映联盟财富的集值函数v（S）在合作博弈中称为特征函数，它表示S中的成员无须求助于N\S中的局中人所能得到的可转移效用或盈利（我们在大部分情况下，研究可转移效用的合作博弈，在需要的时候，将会指出所面临的非转移效用或不可转移效用）的总量。同时，N\S中的任何联盟也不可能阻止S获得v（S）。

有了局中人集合N和特征函数v，我们可以定义具有特征函数的合作博弈。

定义4.1 特征函数形式的合作博弈是一个有序对偶〈N, v〉，它包含了局中人集合N和从2N→R（实数）的特征函数v。

通常，我们以特征函数v来确定博弈，特征函数构成的集合记为GN。因此常用v∈GN指示有序对偶〈N, v〉。特征函数形式的合作博弈〈N, v〉通常称为可转移效用博弈（TU）。当然，合作博弈也可以是不可转移效用的（NTU）。

以N和v就定义了合作博弈，似乎比非合作博弈中最简单的策略型博弈还少了一个要素——策略空间或行动空间。事实上，非合作博弈关心的是策略，需要研究局中人在博弈中如何做出决策以使自己的盈利最大化。但是，在合作博弈中，人们期待的是能得到的最后结果。他们直接关注于最后结局中的盈利或效用，而不考虑得到所期待结局的过程中的具体细节。说得直白一点，我们只关心v（S），而不关心得到v（S）的策略选择。

例4.1就是一个具有特征函数形式的合作博弈，其中N={1,2, …, n}，各个元分别表示不同的航空公司。对于任何S∈2N，他们建立的跑道只需要能够承受S中公司拥有的最大机型就可以了。因此，他们的共建成本为

不过，在这个例子中，v（S）表示的是成本支出，它是负的盈利而不是正盈利。博弈论知识告诉我们，本来，盈利就包括了收益和支出两部分。

例4.2 手套游戏（glove game）

人群N={1,2, …, n}划分为不相交的两个子集L和R, L中的成员每人拥有一只完全一模一样的左手套，R中的成员各拥有一只可与L的左手套匹配的右手套。作为商品，单只手套一文不值。而左右两只手套匹配后得到的一副手套值100元。在任何子联盟中，能匹配成双的手套越多，该联盟的财富就越多。我们可以很容易地把这种情况建模为合作博弈〈N, v〉，其中N={1,2, …, n}是毫无疑问的。对于每一个S∈2N, S中可能包含L的成员也可能包含R的成员，能匹配成对的手套数必定是|S∩L|（S中持左手套的人数）与|S∩R|（S中持右手套的人数）中最小的那个数。因此，相应的特征函数可以定义为