合作n人博弈.doc

合作人博弈 引言 在一个非合作人博中，两个或两个以上的局中人不许可事先商定如何选择策略，不许可把他们的策略结合起来。局中人之间不允许对等到的支付进行任何重新分配，一个局中人不能分享另一局中人得到的支付。 而在合作人博中，则对上述两个方面的问题都不加限制。局中人可以进行充分的合作：可以在事先商定，把他们的策略协调结合起来；可以在终局后重新分配若干个局中人所得的支付的总和。 因此，我们要考虑的有以下几个因素： 首先，由于两个或两个以上的局中人要在某些方面进行合作，他们需要结成一个联盟或合伙(coalition)。这是合作人博弈的一个重要因素；在非合作人博弈中，每个局中人都为自己的最大利益而奋斗，不存在结成联盟的问题。 其次，若干个局中人结成一个联盟后，这个联盟作为一个整体当然希望能够得到尽可能多的收入，即支付。这个最大的支付是联盟的函数。 另外，每个联盟要把得到的总的收入分配给联盟的每一个成员。这就需要用数量来表示这种分配。 在合作人博弈中，各个局中人如何选择策略已浊主要需要考虑的问题。应当强调的乃是联盟的形成。 我们假设，在一个非合作人博弈中，局中人的集是。是的任意子集，称为一个联盟。把中除去中元素后余下的集看成另外一个联盟。以和作为一个零和二人博弈的两个局中人，以中全部成员的一切联合混合策略作为第一个局中人的策略集，中一切的一切联合混合策略作为第二个局中人的策略集，这个零和二人博弈必有一个值。我们以表示这个值。对于的一切子集有定义，并定义 。 我们称为特征函数(chatacteristic function)。特征函数是描述合作人博弈的一个重要因素。 定义 设，是定义在的一切子集(即联盟)的集上的实值函数，并满足条件 ， ， 则称为合作人博弈，为博弈的特征函数。 在本章，我们假定，每个联盟得到的收入可以按照任意方式分配给该联盟的成员。这一条件称为局外支付(side payments)条件。 我们通过一个合作三人博弈的例子来说明如何将博弈写成特征函数的形式。 例1 设合作三人博弈的三个局中人1，2，3各有两个策略和。以表示1，2，3的支付，列出表格。如下 局 中 人 支 付 1 2 3 (a,b,c) 策 略 A A A (1,1,0) A A B (-3,1,2) A B A (4,-2,2) A B B (0,1,1) B A A (1,2,-1) B A B (2,0,-1) B B A (3,1,-1) B B B (2,1,-1) 我们要计算这个博弈的特征函数。 首先，设局中人1，2组成联盟。和之间的零和二人博弈的支付矩阵是 {3} A B {1，2} A A 2 －2 A B 2 1 B A 3 2 B B 4 3 这个矩阵博弈有一个鞍点，鞍点处的支付是3.因此， 其次，令，则。我们得到下列矩阵博弈： {1，2} A A A B B A B B {3} A 0 2 －1 －1 B 2 1 －1 －1 容易看出， 。 再令，则。我们得到下列矩阵博弈： {2} A B {1，3} A A 1 6 A B －1 1 B A 0 2 B B 1 1 显然， 令，则。我们得到下列矩阵博弈： {1，3} A A A B B A B B {2} A 1 1 2 0 B －2 1 1 1 不难算出，在这个矩阵博弈中，以{2}作为第一个局中人，他的最优混合策略是；以{1，3}作为第二个局中人，其最优混合策略是；博弈的值是。因此， 。 再令则。我们有 {1 A B {2，3} A A 1 1 A B 3 －1 B A 0 0 B B 2 0 这个矩阵博弈有一个鞍点，在矩阵的右上角处。因此， . 最后，令，则。我们有 {2，3} A A A B B A B B {1} A 1 －3 4 0 B 1 2 3 2 不难看出， 。 我们求得了特征函数的值如下： ，，，，，，。 特征函数的性质 ， 这里，分别表示联盟和中成员的混合策略按任何方式结合起来所构成的策略集，是局中人在混合策略，下的期望支付。 定理1 设是合作人博弈，则 对于一切，，成立。 上式称为特征函数的超可加性(superadditivity)。当等号成立时，即，如果对于一切，，，有 ， 则称具有可加性。 合作人博弈的特征函数如果具有可加性，这种博弈称为非实质性的(inessential)博弈。它没有什么值得研究的内容。 定理2 合作人博弈的特征函数具有可加性的充要条件是 。 我们主要感兴趣的合作人博弈不是非实质性的博弈，而是特征函数满足 的博弈。这种博弈称为实质性的(e