合作博奔论中的 其他解概念 到目前为止，我们已研究了合作博弈论中的两个重要解概念：核与夏普利值。核是 一个集合解概念，而夏普利值是一个单点解概念。合作博弈论学者还提出了很多其他解 概念。在本章，我们简要讨论下列五个解概念：（1）稳定集；（2）议价集；（3）内核 （kernel）；（4）核仁（nucleolus）以及（5）盖特利点（Gatelypoint）。前面三个是集合 解概念，后面两个是单点解概念。 合作博弈论中的其他解概念 30. 1 稳定集 在介绍稳定集定义之前，我们先引人几个概念。 定义30.1（超额）给定伴随可转移效用的博弈（即TU博弈）（N，v）、联盟C以 及配置x=（xi，，xn），联盟C在x点的超额（excess）e（C，x）是指： e(C，x）=v（C)-∑ iEC 超额e（C，x）是联盟C在向每个参与人iEC分配x：之后剩下的净可转移效用 （nettransferableutility）。如果e（C，x）≥0，这意味着联盟本身能实现它在配置x中的 份额。联盟C在配置处的超额衡量的是联盟C对该配置的不满意程度。 例30.1（分钱博弈（版本3））回忆一下，在这个博弈中：N={1，2，3）；v（1）= v（2）=v（3）=v（23）=0；（12）=v（13）=v（123）=300。考虑配置x=（100，100， 100）。根据超额的定义，可知 e（1,x）=-100,e（2，x）=-100,e（3,x）=-100

e（23,x)=-200,e（12,x)=100,e（13,x)=100,e（123,x）=0 假设y=（200，50，50），那么， e（1,y）=-200，e（2，y）=e（3，y)=-50 e（23，y）=-100,e（13，y)=e（12,y)=50,e（123，y）=0 假设x=（300，0，0），那么， e（1,x)=-300，-e（2，z)=e（3，x)=0 e（23，x）=e（12，x）=e（13，x）=0，e（123，x）=0 我们现在回顾优势转归的定义（参见第27章），并且使用超额概念重新表达之。 定义30.2（优势转归）给定转归x=（xi，，xn）与转归y=（yi，，yn），如 果存在某个联盟CCN使得 (1)e(C，x)≥0， (2)xi>yi,ViEC, 那么我们说转归x优于（dominate）转归y。 定义30.3（非劣势转归）给定转归x=（x1，“，xn），如果其他转归都不优于x， 那么x称为非劣势转归（undominatedimputation）。 我们可以立即注意到，TU博弈的核就是所有非劣势转归组成的集合。 定义30.4（内部稳定性）给定TU博弈（N，v）以及转归集Z，如果 博奔论与机制沿 x,yEZ,C≤N,xi>yi，iEC→e（C,x)<0 那么我们说转归集Z是内部稳定的（internallystable）。 这个性质是说乙中的任一转归都不劣于Z中的任何其他转归。内部稳定性意味着 如果参与人提议Z中的任一转归，那么任何联盟C都不能阻正y，这是因为对于联盟 设 计 C的成员来说，Z中不存在比y严格更好且可行的配置。 定义30.5（外部稳定性）给定TU博弈（N，v）以及转归集Z，如果每个不属于Z 的转归劣于Z中的某个转归，那么我们说转归集Z是外部稳定的（externallystable)。 外部稳定性可以按照下列方式描述：对于博弈（N，v）的每个转归y（其中 yZ)，存在着转归xEZ使得对于至少一个联盟C≤N， xi>yi，Vi∈Ce(C,x)≥0 外部稳定性意味着如果参与人提议一个不属于Z的转归y，那么至少存在着一个能阻止 y的联盟C，该联盟的成员宣称他们在Z中的某个配置比y严格好。 稳定集 这个解概念由冯·诺依曼与摩根斯坦在1944年首次提出。稳定集也称为冯·诺依 曼一摩根斯坦解。 定义30.6（稳定集）TU博弈的稳定集（stableset）是一个满足内部稳定性与外 部稳定性的转归集Z。 例30.2（多数同意规则下的投票博弈）回忆一下，在这个博弈中，N={1，2，3）；

特征函数为 u（1）=v（2）=v（3）=0，v（12）=v（23）=v（13）=v（123）=300 这个博弈的一个可能的稳定集为Z={（150，150，0），（150，0，150），（0，150， 150）}。转归集为 {（x1,x2,x）∈R²:x1≥0；x2≥0；x≥0;x+x2+x=300} 为了感受一下稳定集的定义，我们试着检验下列情形。 ·假设参与人提议转归（300，0，0）Z。现在，转归（0，150，150）EZ意味着 联盟{2，3}将阻止（300，0，0）。 ·现在考察转归x=（100，100，100）Z。转归（150，150，0)∈Z意味着联盟 {1，2}将阻止x。转归（150，0，150）∈Z意味着联盟{1，3}将阻止x。转归 （0，150，150)∈Z意味着联盟{2，3}将阻止x。 另一方面，我们注意到（150，150，0）EZ不劣于（150，0，150），也不劣于 (0，150，150)。 给定TU博弈，稳定集可能存在，也可能不存在。学者们在稳定集的存在性问题上 争论了很长一段时间，直到威廉·卢卡斯（WilliamLucas）于1968年构建了一个不存 在稳定集的十人博弈。这个反例受到了研究者的欢迎。稳定集提供了关于联盟动态的有 价值的观察，然而稳定集也有局限性，原因在于： ·可能有很多稳定集； 第 ·可能不存在稳定集； ·稳定集的结构可能非常复杂。 真 合作博弈论中的其他解 30.2议价集 AumannandMaschler[1]于1964年首次提出了议价集解概念。这个解概念背后的 直觉如下。当参与人对总价值如何分配进行议价并且提出某个分配方案（配置）时，可 能有人对该方案不满意，从而反对该方案。但是，这个反对可能遭受另外一些参与人 （既得利益者）的反对，这称为反反对。给定一个反对，如果不存在任何反反对，那么 概 念 它就是一个合理反对。议价集中的每个转归都具有下列性质：任何参与人都没有对任何 其他参与人的合理反对。我们首先给出反对与反反对的定义。 定义30.7（反对）参与人i对参与人j与收益配置x的反对（objection）是一个 二元组（y，C)，其中，y是另外一个收益配置，C是一个联盟，而且y与C满足 iEC,jC e(C,y)=0 yk>xk，VkEC 例30.3（多数同意规则下的投票博弈）再次考察三人投票博弈。令i=1，j=2， r=（50，100，150）。参与人1对参与人2与收益配置x的反对，是一个二元组（y，

C)，其中 y=（125,0,175)，C={1,3} 注意，i∈C，jC；e（C，y)=0；y>x1，y>x 定义30.8（反反对）给定参与人i对参与人j与收益配置x的反对（y，C），参与 人j的反反对（counterobjection）是一个任意二元组（z，D），其中，x是另外一个收 益配置，D是一个联盟，而且与D满足 jED,iD CND≠ e（D,x)=0 k≥xk，VED 2k≥yk，ECnD 例30.4（多数同意规则下的投票博弈）对于例30.3描述的反对，参与人2的反反 对是二元组（z，D)，其中 x=（0,125,175);D={2,3};CnD={3};e（D,x）=0; 22x223x；x3y3 这个例子让我们得到了议价集的定义。口 在给出议价集的定义之前，我们引人一些符号。令博弈（N，）是一个TU博弈， 博奔论与机制设计 假设Q是N的一个划分（partition）。我们定义 I(Q)={x∈R:xi≥u（{i}))Vi∈N,∑x;=u（C)C∈Q} iEC 我们可以立即注意到，如果Q={N}，那么这个划分只有一个部分，即整个集合N；于 是I(Q）正好就是博弈（N，v）的所有转归组成的集合。 定义30.9（议价集）给定TU博弈（N，v）以及N的一个划分Q，议价集（bar- gainingset）是一个满足下列条件的收益配置集xER”： (1）xEI(Q); （2）对于Q中的任意联盟，以及对于任意两个参与人i，jD，存在着针对参与人 i对参与人j与配置x的任意反对的反反对。 例30.5（顶峰博弈）回顾我们以前讨论的顶峰博弈： N={1,2,3，4,5} v（C)=1若1EC且|C|≥2 =1若|C|≥4 =0其他情形 我们已经看到核与夏普利值分别为 61.11.1 C(N,u)=Q；g(N,u)=( 10′10'10'10′10 考虑划分Q={N}。对于这个划分，可以证明议价集为

(1-4入,入，入，入，入)：13 我们可以立即观察到，这个博弈的夏普利值属于议价集。为了验证上面的集合是议价 集，我们需要考察以下三种典型情形： ·情形1：假设各个小参与人得到的收益不完全相同。在这种情形下，小参与人 得到的收益严格小于参与人j的。于是，参与人i将与大参与人1联合起来提出反对； 对这个反对，参与人j无法实施反反对。 ●情形2：假设所有小参与人设法使自己获得的收益大于一。于是，参与人1提出 的反对（例如）为（（，，0，0，0)，{1，2}），对这个反对，参与人3或4或5无 法提出反反对。 l3。于是，每个小参与人可立即提出反对。例如，参与人2提出的反对为 对于这个顶峰博弈，如果Q={{1，2}，{3}，{4}，{5}}，那么集合 第 将是议价集。口 章 例30.6这个例子来自参考文献[2]。考虑下列三人博弈：N={1，2，3}；特征 合作博弈论中的其他解概念 函数为 u（1）=v（2）=v（3)=0，v（12)=60，v（13）=80，v（23)=100，v（123）=105 可以证明：这个博弈的核为空的；夏普利值为 p1（N，u)=25；p2（N，∞）=35；p3（N，u)=45 考虑如果参与人2与3组成联盟（2，3）需要面对的情形。注意，v（23)=100而v（123）= 105，因此如果参与人2与3将参与人1纳人联盟，那么参与人2和3的收益很有可能变 小。另外，联盟变大后，交易成本（议价花费的时间和精力）增加，因此参与人2和3可 能不邀请参与人1加人联盟。这样，我们就得到了下列划分：（{1），{2，3}}。可以证明， 对于这个划分，（0，40，60）是唯一稳定配置。事实上，在上面五种划分（联盟结构） 中，每个划分正好对应着议价集中的一个配置，如表30一1所示。 表30-1 （例30.6中）对应不同划分的议价集 联盟结构（划分） 议价集 {{1})，{2}，{3}} {（0，0，0）} {{1，2}，{3}} {（20，40，0）}

续前表 联盟结构(划分） 议价集 {{1，3}，{2}} {（20，0，60）} {{1}，{2，3}} {（0，40，60）} {{1，2，3}} {（15，35，55）} 如果大联盟的价值变为135而不再是105，那么对于{{1，2，3}}这个划分，议价 集正好等于核： {（x，x2，x）∈R²:x≥0,x≥0,x0,x<35，x2<55，x<75,x+x+x=135} 其他联盟结构的议价集与以前相同。口 口关于议价集的一些观察 ·核是博弈（N，）的对应于划分Q={N）的议价集的一个子集（可能为空集）。 ·给定划分Q，如果I（Q）非空，那么对应于Q的议价集也非空。 ●如果博弈（N，v）是超可加的，那么对于任何划分Q，集合I（Q）非空，因此对 应于Q的议价集也非空。[回顾超可加博弈的概念：给定TU博弈（N，v)，如果对于 所有联盟C，DCN， C∩D=Q→u(CUD)≥u(C)+u(D) 博奔论与机制设计 那么博弈（N，v）是超可加的（superadditive）。] ·夏普利值未必属于（对应于任何给定划分的）议价集。因此，在夏普利值意义 上，议价集给出的配置未必是公平的。 30.3内核 这个解概念是由Davis andMaschler3]提出的。TU博弈（N，v）的内核（kernel) 是关于N的划分Q而定义的（这一点与议价集的定义类似）。事实上，与议价集一样， 内核也是I（Q）的子集。内核背后的直觉在于，如果两个参与人i与j属于Q中的同一 个联盟，那么参与人i在不含j的联盟中得到的最大超额，应该等于参与人j在不含 的联盟中得到的最大超额。在定义内核时，我们的重点放在参与人能得到的最大超额 方面。 定义30.10（内核）给定TU博弈（N，v）以及N的划分Q，内核（kernel）是 满足下列两个条件的配置集xER”： (1)xEI(Q); （2）对于每个联盟CEQ以及每对参与人i，jEC， maxe(D,x)=maxe(E,x)。 DCN-j ECN-i iED jEE 例30.7（四人博弈）考虑下列四人博弈：

N={1,2,3，4}；Q={{1,2}，{3，4}}；i=1,j=2 I（Q={（x，x2x3x）:x≥0,x2≥0,x≥0,x≥0,x+x2=v（12),x+x=u（34)} 博弈（N，v）对应于Q的内核是I（Q）中所有满足下列条件的配置（x1，2，x3，x4）： maxe（D,x)=maxe（E,x) D(1,3,4) E(2,3，4) 1ED 2EE maxe(D,x)=maxe(E，x) 口 D(1,2,3) E二{1,2,4) 3ED 4EE 例30.8（顶峰博弈）对于例30.5中的顶峰博弈，对应于划分{{1，2，3，4， 5}）的内核为{(，，，，)}；对应于划分{{1，2)，{3)，{4)，{5}}的内核 为(2，，0,0，0)}。□ 30.4核仁 TU博弈的夏普利值是一个主要基于某种分配公平性意义上的解概念。核仁（nu cleolus）是一个单点解概念，在这个角度上，它类似夏普利值。核仁主要基于议价方面 的考虑。这个解概念是由DavidSchmeidler[4]于1970年提出的。 回忆一下，联盟C关于配置的超额衡量的是C在配置上的不满意程度。假设 第 我们找到了一个满足minmaxe（C，x）的转归。这是什么意思？这表示我们选定的转归 章 能使最不满意联盟的不满意程度尽可能小。这正是核仁背后的思想，不仅如此，核仁不 合作 仅使最不满意联盟的不满意程度最小，也使第二不满意联盟的不满意程度最小，第三不 博奔论中的 满意联盟的不满意程度最小，以此类推。 例30.9考虑下列三人博弈，这个博弈来自文献[2]。在这个博弈中，N={1，2，3}； 特征函数为 其他解 u（1）=v（2)=v（3）=0，v（12）=60，v（13）=80，v（23）=100，v（123）=105 给定配置=（20，35，50），各个联盟的超额值如下。 概 e（1,x）=-20,e（2,x）=-35,e（3,x）=-50 念 e（12，x）=5，e（13，x）=10,e（23，x）=15 e（123,x)=0。 在上面各个联盟的超额值中，最大的为e（23，x）=15。假设我们试图通过使用（比如） 配置y=（15，35，55）来降低这个超额值。现在，我们注意到， e（12,y)=10,e（13，y)=10,e（23,y）=10 如果我们试图进一步降低这个等于10的超额值，那么至少有另外一个超额值变得大于 10。因此，配置y实现了任何联盟的最小超额。一般来说，可能有多个转归能使第二大 的超额最小，这样我们就得到了上述转归集的一个子集。接下来，我们最小化第三大的

超额，最小化第四大的超额，以此类推，直到正如文献[4］所示的，我们最终得到唯 一转归。这个唯一转归称为核仁。 口核仁的定义 考虑任意配置x=（1，，n），令ek（x）为任意联盟在配置x产生的第k大的超 额。这意味着下列集合的基数（cardinalities）满足： {C≤N:e(C,x)≥ek(x)}≥k {C≤N:e(C,x)>ek(x)}<k 现在，配置x属于核C（N，v）意味着e（x)≤0。假设我们用J（k）表示所有使得e最 小的转归组成的集合，其中e是第k大的超额，用I（N，v）表示博弈（N，v）的所有 转归组成的集合。于是， J(1)=argmine（x) rEI(N,) 如果核非空，那么J（1)≤C（N，v)。我们将J（2)，J(3)，，J（2II－1）定义 如下： J（k）=argminek（x）对于k=2，3，·,21N1-1 xEJ(k-1) Schmeidler[4]证明集合J（2INl－1）是一个单点集，这个点称为TU博弈（N，v）的 博 核仁。 弈论 注意，当核非空时，对于核中的任何转归，所有超额都为零或负。为了找到核仁， 与机 我们在核中选择的转归，要能使（负）超额的绝对值尽可能地大。在几何上，核仁是核 制 中的一点，它离核壁（类比一下细胞壁）的距离尽可能地大。在直觉上，核仁是核最深 设计 处的点。我们还可以观察到这个解概念的其他方面（更多细节，读者可以参考文献 [2]]。 ●核仁总存在且唯一。 ·如果核非空，核仁属于核。 ·核仁总属于大联盟的议价集。另外，它总属于内核。 ·核仁未必总等于夏普利值。 ·核仁可以通过求一系列线性规划的解计算出来。 30.5盖特利点 这个解概念是由DermotGatelyL5]于1974年提出的。类似核仁，盖特利点也是基 于参与人的议价能力。假设我们有一个TU博弈（N，v)，其中N={1，2，"，n）。 我们主要关注参与人i。如果参与人i退出大联盟，这可能导致参与人遭受损失（或获 得收益）。假设x=（x1，，n）是大联盟的原配置。于是，参与人i退出大联盟导致 他的损失为x：一v（{i}）。其余参与人的联合损失为

（{？}N) 参与人i造成的破坏可用所谓的破坏倾向（propensitytodisrupt）d：（x）衡量； d（x）的定义为 ∑xj-u(M{i}) d（x）= xi-u（{i}) 盖特利点是一个转归，它使得最大破坏倾向最小化。可以证明，当所有参与人的破坏倾 向相等时，我们就得到了盖特利点。 例30.10考虑下列三人博弈：N={1，2，3}； v（1）=v（2）=v（3）=0，v（12）=4，v（13）=0，v（23）=3，v（123）=6 对于配置=（2，3，1），参与人的破坏倾向分别为 d（x）= d2（x）=1，d（x）=1 2’ 破坏倾向为 第 30章 可以证明，上面的配置是盖特利点。口 我们现在给出一些关于盖特利点的观察。 合作博弈论中的其他解概念 ·如果核非空，盖特利点未必属于核。 ·通过考察联盟的破坏倾向而不是参与人个体破坏倾向，我们可以推广盖特利点这 个概念。由此得到的解概念称为破坏性的核仁（disruptivenucleolus）；可以证明，如果 核非空，那么破坏性的核仁属于核。 30.6小结与参考文献 合作博弈论有多种解概念。本章研究了五种解概念。这些解概念基于下列名词： ●转归：TU博弈的转归是一个配置x=（x1，，x），它使得各个x;之和等于大 联盟的价值（N)，而且每个x不小于（{i}）。 ·超额：联盟C在配置x处的超额等于v（C)一x。这可以描述为联盟C的不满 iEC 意程度。 ·优势转归：给定两个转归x=（x1，，x）与y=（y，，yn），如果存在着联 盟C，使得C在x处的超额为非负，而且使得x>y，Vi∈C，那么我们说转归x优于 转归y。

本章研究的解概念有： ·稳定集：TU博弈的稳定集是一个满足内部稳定性与外部稳定性的配置集（事实 上，该配置集为转归集）。内部稳定性表示乙中的任一转归都不劣于Z中的任何其他转 归。外部稳定性表示每个不在乙中的转归，劣于乙中的某个转归。 ·议价集：给定参与人集N的某个划分Q，对应于Q的议价集是一个转归集，这 个转归集中的每个转归都有下列性质：任何参与人都不会反对这个转归，因为如果他反 对，其他参与人会提出反反对。 ·内核：给定参与人集N的某个划分Q，内核包含的收益配置满足下列条件：如 果参与人i，j属于Q中的同一个联盟，那么参与人i在不含j的联盟中得到的最大超额 等于参与人j在不含i的联盟中得到的最大超额。 ·核仁：核仁总属于内核，而且是使得最不满意联盟的不满意程度最小化的唯一转 归，不仅如此，这个转归还使得第二不满意联盟的不满意程度最小化，第三不满意联盟 的不满意程度最小化，以此类推。 ·盖特利点：盖特利点是使得参与人最大破坏倾向最小化的转归，这里的破坏是指 参与人退出大联盟。 对于这些解概念，何时使用哪一种要根据具体情况具体分析。解概念的计算通常比 较难，特殊情形除外。 本章内容主要来自以下教材：Myerson[6]，Straffin[2]，以及Maschler，Solan， andZamir[7]。更多细节也可以参考上述文献。Straffin[2]对于本章五种解概念都给出了 博 说明性的例子。本章讨论的解概念也可以参考下列原始文献：稳定集[8]，议价集[1]， 奔 论 内核[3]，核仁[4]，盖特利点[5]。 与 解概念的计算是一个重要议题。Chalkiadakis，Elkind，andWooldridgeL9详细讨 机 制 论了这个重要主题。 设 计 口参考文献 [1]R.Aumann and M.Maschler.“The bargaining set for cooperative games".In: AdvancesinGameTheory.PrincetonUniversityPress，1964,pp.443-476. [2]PhilipD.StraffinJr.GameTheoryandStrategy.TheMathematicalAssocia- tion ofAmerica,1993. [3]M.Davisand M.Maschler.“Thekernel of a cooperative game”.In:Naval ResearchLogisticsQuarterly12(1965)，pp.223-259. [4]David Schmeidler.“The nucleolus ofa characteristic functiongame”.In:SI- AMJournalonAppliedMathematics17(1969)，pp.1163-1170. [5]Dermot Gately.“Sharing the gains from regional cooperation:A game theoret- icapplicationtoplanninginvestmentinelectricpower”.In:InternationalEconomic Review 15(1974)，pp.195-208. [6]Roger B.Myerson.GameTheory:Analysis of Conflict.Harvard University Press,Cambridge,Massachusetts,USA,1997. [7]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam

bridgeUniversityPress,2013. [8]JohnvonNeumannand OskarMorgenstern.TheoryofGames andEconomic Behavior.PrincetonUniversityPress,-1944. [9]Georgios Chalkiadakis,EdithElkind,andMichaelWooldridge.Computation al Aspects of CooperativeGameTheory.Morgan&Claypool,2011. 30.7习题 （1）对于多数同意规则下的投票博弈（例30.2），计算其他稳定集（若存在）。 （2）对于五人顶峰博弈，证明：与划分{{1，2，3，4，5}）对应的内核为 {（，，，)}，与划分{{1，2}，{3}，{4)，{5}}对应的内核为 (3）证明五人顶峰博弈的核仁为(，，，，)。 （4）考虑下列三人超可加博弈：N={1，2，3}；v（1）=u（2)=v（3）=0，v（12）= a，u（13)=b，v（23）=c，v(123）=d，其中0≤a，b，c≤d。计算这个博弈的核仁与盖 特利点。 第 （5）给定下列三人博弈：N={1，2，3}；（1）=v（2）=v（3）=0，（12）=4， v（13)=0，v（23)=3，v（123）=6。计算这个博弈的核、夏普利值、内核、核仁、盖特 章 利点。 合作博弈论中的其他解概念 （6）（编程题）考察计算解概念时涉及的计算议题。试着构建有效率的算法来确定 解概念。