7.3.3 核与稳定集
在联盟博弈中,所有的分配集合E(v)中都存在无限个分配,其中分配之间可能存在优超关系。对于联盟S而言,如果存在X≻S Y,则该联盟会选择放弃分配Y而选择X。
定义7-6(稳定集)
对于一个n人联盟博弈＜N,v＞,集合S(v)⊂E(v)称为该联盟博弈中的稳定集,如果以下条件成立:①S(v)中的任意分配X都不优于S(v)中的其余分配;②不属于S(v)中的任意分配Y,总可以在S(v)中找到分配X,使得X≻S Y。
在上述定义7-6中:①保证了稳定集的内稳定性,即稳定集内部的任意两个分配之间不存在优超关系,这保证了联盟内部成员不会因利益冲突而导致联盟解体;②保证了稳定集的外稳定性,即稳定集外的任意分配至少被稳定集内的某个分配优超。
商店经营:甲、乙、丙3人拟合伙开商店,每个月可以赢利3 000元,商店正常营业至少需要两个人。求解如何经营该商店,以及怎样分配利润。
在此案例中,可以用如下效益函数表示该联盟博弈问题:
假设3个人的分配为X=(x 1,x 2,x 3),其中x 1+x 2+x 3=v(1,2,3)=3 000。若联盟{1,2}形成,则分配X=(1 500,1 500,0)是合理的。而如果甲要求采取分配(1 500+∈,1 500-∈,0),则乙将会考虑与丙合作经营。同理,如果丙也提出类似的要求,则乙不会与任何人联盟,而甲、丙也不会构成联盟。类似地,Y=(1 500,0,1 500),Z=(0,1 500,1 500)也是合理的分配。而S={X,Y,Z}则构成一个稳定集。其中,对于稳定集S内部,X,Y,Z之间没有优超关系;对于稳定集S外部的其他分配,必被S中的某个分配优超。
定义7-7(核)
对于一个n人联盟博弈〈N,v〉,所有不被优超的分配集合都称为该博弈的核,记为C(v)。
对于核中的分配X,参与者不能通过重组联盟来增加效益。同时,对于联盟博弈的核还存在如下结论:
①C(v)⊆E(v),即核C(v)是分配集合E(v)的一个闭凸集。
②若C(v)≠∅,则C(v)中的向量X作为分配,既满足个体理性,也满足群体理性。
③用核作为联盟博弈的解,但C(v)可能是空集。
定理7-1 对于一个n人的联盟博弈〈N,v〉,分配X=(x 1,x 2,…,x n)是该博弈中的核的充分必要条件为
读者可以思考一下定理7-1的证明过程,可以使用反证法辅助证明。
3人博弈v3:对于一个3人联盟博弈,其效益函数如下,求该联盟中的核。
根据定理7-1,可列出如下不等式:(https://www.daowen.com)
进而求解出
即该联盟博弈中的核C(v)={(2,2,1),(3,2,0),(3,1,1),(4,1,0),(4,0,1)},如图7-9所示,阴影区域即该3人联盟博弈中的核。
值得注意的是,一方面,并不是在所有联盟博弈中都存在一个核,即核C(v)可能是空集,而这也是用核C(v)代替分配E(v)的一个问题;另一方面,用核C(v)代替分配E(v)也是合理的。由于核的稳定性,核中的每一个分配都不存在优超关系,因此不会存在更好的分配,每一个分配都可以执行。那么如何确定联盟博弈中,核一定是非空的呢?
核仁的概念便应运而生,下面首先定义剩余这一概念。
定义7-8(剩余)
在剩余e(S,X)中,如果X是一个分配,则其反映了联盟对于分配的不满意程度。在理想的情况下,联盟的剩余应尽可能小。对于一个分配X,存在2n个联盟,记为Sj(j=1,2,…,2n),故存在2n个剩余e(Sj,X)(j=1,2,…,2n)。对其按从大到小的顺序进行排列,形成2n维向量θ(X)=(θ1(X),θ2(X),…,θ2n(X)),其中θj(X)=e(Sj,X)。θ(X)越小,则表示联盟对分配X越满意。因此对于两个不同的分配X,Y,可以比较其对应的θ(X)与θ(Y),不同于普通的数字之间的比较,这里可以采用字典序比较的方式。
定理7-2 对于向量θ(X)=(θ1(X),θ2(X),…,θ2n(X))与向量θ(Y)=(θ1(Y),θ2(Y),…,θ2n(Y)),如果存在一个下标k,使得θj(X)=θj(Y)(1≤j≤k-1),同时θk(X)＜θk(Y),则θ(X)的字典序小于θ(Y),记为θ(X)≺θ(Y)。
有以上定义与定理为基础,下面给出有关核仁的定义与性质。
定义7-9(核仁)
对于一个n人的联盟博弈〈N,v〉,该博弈的核仁N(v)为N(v)={X|X∈E(v)}。对于∀Y∈E(v),Y≠X,有θ(X)≺θ(Y),即任意取一个X∈N(v),θ(X)都是字典序最小的。
图7-9 3人联盟博弈中的核
定理7-3 对于一个n人的联盟博弈〈N,v〉,核仁具有如下性质:
①核仁N(v)非空,并且只包含一个元素;
②若核C(v)≠∅,则它必定包含核仁,即N(v)⊂C(v)。
其中,第一条性质表示对于每个联盟博弈,有且仅有一个核仁,即核仁存在且唯一,但是从核仁的定义就可以看出,直接求解核仁的过程较为复杂,有兴趣的读者可以尝试求解;第二条性质有助于求解核仁,若要求解,可以先从核的求解出发。
