合作博弈

i 1
显然，作为多人结盟博弈的一个解X，至少必须 是一个合理分配，即 X I(V )
例4：一局博弈，<N,V>，N={1,2,3}，特征函数如下： V(φ)=0，V({1})=V({2})=V({3})=0 V({1,2})=V({1,3})=V({2,3})=0 V({1,2,3})=1
合理分配集合
四、常用解法
1、稳集法 2、核法 3、Shaply值法 4、多目标规划方法
1、稳集
稳集的基本思想
是选择这样一个合理分配的集合作为对策的解：不 在这集合内的任何合理分配总能被这个集合中某个 合理分配所支配，且这个集合内的合理分配互相不 被支配。
定义：对于一个对策，存在一组合理分配 S(V ) I(V ) 满足
S(V)={(1,1,0),(1,0,1),(0,1,1)} 是此博弈的一个稳集。
（1）先验证这三个合理分配间不相互支配。
对任一个 S N, xi yi , i s 不可能成立。
例如对 S 1,2, x1 y1, x2 y2, 在三个分配中任两个之
间不可能同时成立。
（2）设任一 Z (z1, z2, z3) S(V )的合理分配 z1 z2 z3 2 分别讨论 z1 1, z1 1, z1 1 的情况。
（1）X ,Y S(V ) ，则X，Y互相不被支配。 （2）对任合理分配 Z S(V ) ，则必存在X S(V )使X Z
则称这样一组合理分配S(V)为此对策的稳集。 稳集被看作多人结盟对策的一种形式。
例5：有一三人结盟博弈<N,V>，N={1,2,3}， V(S)为
V(φ)=V({1})=V({2})=V({3})=0 V({1,2})=V({1,3})=V({2,3})= V({1,2,3})= 2 很容易证明：
Ｂ 0
110
三、多人结盟博弈的解
多人结盟博弈的解的概念
多人结盟博弈中，每个局中人都希望 通过结盟的形式去得到更多，而博弈解 的问题是如何合理确定这局博弈中每个 局中人的分配收益，博弈解一般用
X＝(x1, x2 ,… xn ) 表局示中n人个之局所中得人。的得失向量，xi 表示第i个
1、合理分配（Imputation）
将此问题转化为三人博弈，其特征函数如下：
S
V(S) 0
{1} {2} {3} {1,2} {1,3} {2,3} 0 0 0 0 0 500
{1,2,3} 1000
局中人2，3，通过合作生产，但由于他们 共有四种原材料只能生产1/2个单位产品，所以 能挣500元。
例3：成本分摊问题（A Cost Game）
1、局中人与结盟
（1） N＝{1,2,…,n}表示局中人集合。 （2）结盟S，表示一个联盟，即一局多人对
策中，一部份局中人联合成一体像一 个“局中人”一样选择策略，这种联合 称为结盟。显然结盟S是局中人集合N 的子集，SN。 （3）2n是局中人可能形成结盟的个数。
2、特征函数 V(S)
（1）V(S)表示当若干局中人联合成一个结盟S时,在 这局博弈中能获得的最大收益值,即当形成结盟S,只 要S内每一个局中人共同策略,选择相应策略结盟S 能保证获得,而与联盟外局人采用什么策略无关。若
条件（2）称为“集体合理性”条件（Group Rationality），
表示对于一个博弈解，所有局中人分配得失之和应等于所
有局中人联合起来形成一个大联盟时得到的收益值，也就
是这局博弈中的最大收益值V(N)。
由超可加性
满足上述两种条件的X=(x1……xn)称为“合理分 配”，即有
I(V ) X R nxi V ({ i} ),nxi V (N ), i N
三个城镇A，B，C欲与附近的一座电站连
接起来，其可能的线路及其成本如下网络图表 示：
100
ＡA
30
电站
50
C
140
BB
பைடு நூலகம்20
这三个镇可相互联合建设，试问如何在这三个 小镇合理分摊这笔建设费？
这个问题的合作博弈对<N,C>，N={A,B,C}，成本 分摊博弈的特征函数V(S)为成本节省，如下表：
S {A} {B} {C} {A,B} {A,C} {B,C} {A,B,C}
作为一个博弈的解X，即在博弈中对N个局中人得失的合 理分配，至少应满足两个条件：
（1） xi V ({i}) n
（2） xi V (N )
i N（个人合理性）
i N（集体合理性）
条件（i11）称为：“个人合理性”（Individual Rationality），
表示局中人i所分配值xi不小于特征函数中规定他至少能得 到的值V(i)。
第五章 多人合作博弈模型
一、问题引入 二、多人结盟博弈的基本概念 三、多人结盟博弈的解 四、常用解法
一、问题引入
例1 ：（爵士乐队博弈，A Jazz Band Gounce）
一位歌手（S），一位钢琴家（P）和一位鼓手（D） 组成一个小乐队在俱乐部同台演出能得到演出费1000元， 若歌手和钢琴家一起演出能得800元。而只有钢琴家和 鼓手一起演出能得到650元，钢琴独奏表演能得300元， 钢琴家没有其它收入。然而，歌手和鼓手在地铁中表演 能挣500元，歌手独奏可以从The Terasses 挣200元， 而鼓手单独什么也挣不到。
问题：如何在这三人爵士乐队中合理分配共同演出费 1000元？
例2： 成本分摊问题（A Cost Game）
三个城镇A，B，C欲与附近的一座电站连接起 来，其可能的线路及其成本如下网络图表示：
100
AＡ
30
电站
50
CC
140
B
20
这三个镇可相互联合建设，试问如何在这三个小 镇合理分摊这笔建设费？
1）当z1 1，z2 z3 1，则必有z2 1，z3 1则(0,1,1) Z 2）当z1 1，z2 z3 1，则有z2 , z3 1或Z (1,1,0)或Z (1,0,1)， 而Z (1,1,0)或Z (1,0,1)时，Z S(v)，故有(0,1,1) Z成立。
3
3）当z1 1，z2 , z3之中必有z2 1或z3 1，反之 zi 2矛盾。
但一个对策中，不可能存在一个合理分配优于另
一个合理分配，即满足 xi yi ,i 1,2, , n ，这是因为
n
n
xi yi V (N )。
1
1
但是对于某一个联盟S，只要满足 xi yi ,i S
成立（这是可能的），则对S联盟而言可认为X分配 优于Y分配，即得出支配概念
定义：对于两个合理分配X，Y，若对于某一联盟S， 有
实际问题中，经济问题的博弈通常是有核的，而在政治 科学的一些多人博弈问题常常是没有核存在，为了解决此 问题，提出弱核的概。
通过求解下列LP问题，求得一个非空弱核。
s.t.
Min
n
*
1
xi
V (N)
is
xi
V (S)
SN
称 C (V ) {X xi V (N), xi V (S) *, S N}
例2:（产品博弈A Production Game）
生从产M11个、单M2位、的M某3、种M产4四品种，原这材个料产中品各的取价一格个要单比位它能的 原材料成本高出1000元，现有三个人，他们拥有这 四种材料情况如下表:
原材料
人
M1
M2
M3
M4
1
1/2
1/2
0
0
2
1/2
0
1
0
3
0
1/2
0
1
问：若这三人联合起来生产这种产品，他们之间该 如何分配所得利润？
I (V ) X (x1, x2, x3) | x1 0, x2 0, x3 0, x1 x2 x3 1
而
X1
(1 2
,
1 3
,
1 ), 6
X2
(1 3
,5 12
,
1) 4
就是其中两合理分配。
2、支配（Domination）
多人结盟博弈求解问题实际是在合理分配集 I(V) 中，按某种准则选择一个或一组合理分配，作为对 策的解。
二、多人结盟博弈的基本概念
多人结盟博弈：局中人多于二人时的博弈称为 多人博弈。这种博弈中如果局中人可以和其它 局中人联合成一体统一行动与其它局中人对抗， 这种博弈称为多人结盟博弈。
这种博弈有三个基本要素: – 局中人N＝{1,2,…,n}； – 结盟S； – 特征函数V（S）。
一般可用<N,V>表示一个多人结盟博弈。
（1）xi yi i S
（2） xi V (S)
iS
S
则称合理分配X通过联盟S支配Y，记为 X Y
解释：
条件（1）表示对于联盟S来讲，X优于Y。
条件（2）表示联盟S有足够的能力保证它的局中人I
通过合作能获得合理分配 xi , i S
定义：在博弈中，只要存在某一联盟S，且X通过S
支配Y，则也称X支配Y，记为 X Y
为
C (V ) X R n nx i V (N ) x i V (S ) S N
i 1
i s
2、核（The Core ）
定义：设 X 是联盟博弈<N,V>的一个合理分配， 若存在一联盟S，使得
V(S) xi
iS
则称联盟S瓦解分配 X。
所以，核是不会被任何联盟瓦解的合理分配的 集合。
例：三人（分别记为1,2,3）有机会分享300元， 分配方案由民主表决通过（少数服从多数），如果 达不成协议则失去这个机会。
核的主要思想也是基于支配概念，即从合理分配 集I(V)中选择一组合理分配，它们对任何联盟来说 都不被其他合理分配所支配，把这组合理分配，称 为“核”，作为博弈的一种解的形式 。
定义：博弈<N,V>，若存在一组合理分配，对任
何联盟S，满足 xi V (S)
iS
S N
称这组合理分配为博弈的核，并用C(V)表示，记
1
所以有(1,1,0)或(1,0,1) Z成立。
稳集作为解，从支配角度具有合理性，但存 在如下问题：
（1）多数结盟博弈可能有多个稳集， （2）有的博弈都不存在稳集
Lucas（1968）举出一个无稳集的10人博弈例子； Lucas和Rboie （1980）又举出一个无稳集的13人博弈的例子。
2、核（The Core ）
根据合理分配、稳集、核的定义有下面关系成立，
C(V ) S(V ) I (V )
即核必定在稳集内，稳集必定在合理分配集合内。
3、沙波利值（The Shapley Value ）
多人结盟博弈的The Shapley Value解的概念 是Shapley在1953年提出的，这个解的概念不同 于前面介绍的核和稳集的概念。用核作为博弈解 的思想是基于选择不被支配的合理分配去作博弈 的解，而稳集是基于选择能支配一切不在这个集 合内的合理分配的合理分配作为博弈的解，而 Shapley则是基于期望边际收入思想上提出的， 他从局中人角度分析在博弈之前，每个局中人应 该期望得到多少。
S=,V()=0。
（2）超可加性
若一个多人博弈的特征函数具有下列性质,即
对任意结盟S,T N,S∩T= ,满足
V(S∪T)≥V(S)+V(T).
称这个多人博弈具有超可加性。
如果特征函数不满足超可加性，博弈中的结盟 是不稳定的。
例1 ：（爵士乐队博弈，A Jazz Band Gounce）
一位歌手（S），一位钢琴家（P）和一位鼓手 （D）组成一个小乐队在俱乐部同台演出能得到 演出费1000元，若歌手和钢琴家一起演出能得 800元。而只有钢琴家和鼓手一起演出能得到 650元，钢琴独奏表演能得300元，钢琴家没有 其它收入。然而，歌手和鼓手在地铁中表演能挣 500元，歌手独奏可以从The Terasses 挣200元， 而鼓手单独什么也挣不到。
特征函数：
v () 0 ; v ({ i} ) 0 ,i 1 ,2 ,3 ;
v ({ i,j} ) 3 0 0 ,i,j 1 ,2 ,3 ,i j; v ({ 1 ,2 ,3 } ) 3 0 0 ;
核作为博弈解的合理性： 核中的分配肯定不会被任何联盟推翻，因此在 联盟博弈中具有稳定性。
核作为博弈解的缺点： 并非每一个博弈均有非空的核。
问题：如何在这三人爵士乐队中合理分配共同 演出费1000元？
这个问题可归为一个三人合作博弈，它 的特征函数V（S）为：
结盟S {S,P,D} {S,P} {S, D} {P,D} {S} {P} {D} V(S) 1000 800 500 650 200 300 0
很容易验证此博弈是具有超可加性的。
C(S) 0 100 140 130 150 130 160 150 V(S) 0 0 0 0 90 100 110 220
博弈<W,V>的特征函数值V(S)，由下式得出
V (S) C(i) C(S) iS
S 2N
150
Ａ
Ｂ
100 150 140
Ｃ
160
130
130
90
Ａ 0
220
100
Ｃ 0