7.3.4 沙普利值
沙普利值
在一个联盟博弈中,往往会存在无限个分配,其中一些分配之间会存在优超关系,进而可以筛选出一部分分配,这便是核。但是核中可能存在多个分配,也可能出现空集的情况,因此剩余与核仁的概念被提出了,核仁的定义为联盟博弈中的分配选择提供了一条道路。核仁总存在而且唯一,但核仁的求解过于复杂。那么有没有其他方式可以得到联盟博弈的唯一解呢?下面先从一个案例入手。
合理分钱:小明和小方去外面郊游,小明带了5片面包,小方带了3片面包,正当二人准备享用午餐的时候,小王饥肠辘辘地走了过来,想要加入他们一起吃午饭,并拿出了8块钱作为对二人的感谢。午饭后,小王满足地离开了,但小明和小方却在为如何分摊这8块钱而争执,小方说自己带了3片面包,理应分得3块钱,而小明却不同意……
定义7-10(沙普利值)
对于每个联盟博弈〈N,v〉,都存在唯一的沙普利值(Shapley value):
分摊车费:甲、乙、丙3人聚会之后打算一同拼车返回,总价为30元,如图7-10所示。如果不拼车回家,甲打车回家需要10元,乙需要18元,丙需要25元。试问甲、乙、丙3人应如何合理地分摊打车费用[9]。
在这个案例中,丙说:“不如咱们每人出10元拼车吧!”甲则表示不满,自己单独打车也只需要10元,拼车还需要10元。甲补充说:“不如第一段咱们平分,第二段你们平分,第三段丙自己支付。”但乙、丙表示拼车已经为甲绕路,多出来的路程甲却没有付钱。这时候乙说:“咱们这样考虑问题,现在是假设打车的路线是甲到乙到丙,但是还有其他的可能性,不如我们把所有的路线都列出来,按照谁先上车谁付车费,后上车的人补差价的原则,计算出每个人的平均支出,当做最后的费用。”大家都表示同意。
图7-10 甲、乙、丙拼车路线
根据以上思路,可以简单地列出6种情况,如表7-2所示。
表7-2 甲、乙、丙3人的路线情况与对应的效益
表7-2中,给定从甲到丙家的打车费用为18元。假设每种情况出现的概率相等,可以计算出每个人的平均费用,即甲需要效益4.83元,乙需要效益8.83元,丙需要效益15元。
上述案例很生动地使用了沙普利值的思想,解决了3人打车分担费用的问题。
定义7-11(虚拟参与者)
对于一个联盟博弈〈N,v〉,其参与者如果满足对于∀S⊂N\{i},有v(S∪{i})=v(S),则称该参与者为虚拟参与者。
在上述定义中,如果一个参与者为虚拟参与者,那么其是否加入联盟,对于联盟的得益没有任何影响。
定义7-12(虚拟性)
解函数f如果对于博弈〈N,v〉中的虚拟参与者i,f i(v)=0,则称其满足虚拟参与人性质,简称虚拟性。
在上述定义中,虚拟参与者由于没有对联盟做出贡献,所以联盟也不会分配给他任何得益。
定义7-13(有效性)
解函数f如果对于任意博弈〈N,v〉,f(v)都是有效的,则称其满足有效性。
上述定义要求联盟的分配符合群体理性。
定义7-14(匿名性)
解函数f如果对于任意博弈〈N,v〉,∀i∈N,以及∀π∈∏N,都有fπ(πv)=f i(v),则称其满足匿名性。其中,博弈πv定义为,对于∀S∈2N,πv(π(S))≡v(S)。
在上述定义中,如果两位参与者对于联盟的贡献是相同的,那么他们的得益也应该相同,即联盟分配给参与者的效益完全取决于参与者对于联盟的贡献,而不考虑他是谁。
定义7-15(可加性)
解函数f如果对于所有的合作博弈u和v,都有f(u+v)=f(u)+f(v),则称其满足可加性。
上述定义要求两个独立的联盟博弈联合组成的新博弈的值,等于原来两个博弈的值之和。(https://www.daowen.com)
定理7-4 沙普利值是满足虚拟性、有效性、匿名性与可加性这4个性质的唯一解。
这里给出一个证明思路,读者可以自行探究。首先证明沙普利值满足虚拟性、有效性、匿名性与可加性,再证明如果一个解函数f满足上述4个性质,则f=φ即可。
投票博弈:考虑一个投票博弈的场景,其中效益函数如下,试求出该博弈中的沙普利值。
在上述例题中,首先考虑参与者1的沙普利值φ1(v)。该博弈中存在一些联盟,如{1,2},{1,3},{1,4},{1,5},{1,3,4},{1,4,5},{1,3,4,5},在这些联盟中,无论参与者1是否存在,联盟的效益函数都不会变化。换句话说,参与者1对于这些联盟来说是一位虚拟参与者,所以在计算沙普利值时,不需要考虑这些联盟。v(S∪{1})与v(S)存在差异的联盟有{1,2,3},{1,2,4},{1,2,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,2,3,4,5}。由此可以得到
同理,可以得到
沙普利值虽然必然存在且唯一,但是不一定是个分配,即理性约束可能不满足φi(v)≥v(i)。在这种情况下,相应的联盟就不具有稳固性,参与者便会有重组联盟的激励。
定理7-5 对于一个联盟博弈〈N,v〉,如果其满足超可加性,即v(S 1∪S 2)≥v(S 1)+v(S 2),同时满足S 1∩S 2=∅,则沙普利值φ(v)就是一个分配,φ(v)={φ1(v),φ2(v),…,φn(v)}∈E(v)。
为了使沙普利值称为一个分配,需要效益函数满足凸博弈的条件,即对于任何联盟S,T,效益函数都满足v(S)+v(T)≤v(S∪T)+v(S∩T)。下面给出凸博弈的几个特征。
定理7-6 一个联盟博弈〈N,v〉是凸博弈,则存在以下两个定理:
①对于所有的X,Y,Z∈2N,其中X⊂Y⊂N\Z,存在
②对于所有的X,Y∈2N,i∈N,满足X⊂Y⊂N\{i},存在
证明:首先证明定理①成立。根据凸博弈的定义,对于任意联盟S,T,都有v(S)+v(T)≤v(S∪T)+v(S∩T)。这里使用X∪Z来代替S,使用Y来代替T,可以得到
显然,上述公式中由于X⊂Y,所以X∪Z∪Y=Y∪Z。同时,根据交并运算的分配率,存在(X∪Z)∩Y=(X∩Y)∪(Z∩Y)=X。整理后可以得到,v(X∪Z)+v(Y)≤v(Y∪Z)+v(X),即v(X∪Z)-v(X)≤v(Y∪Z)-v(Y)。
其次由定理①可知,当Z={i}时,定理②显然成立。
同时,如果一个联盟博弈是凸博弈,其具有如下两条性质:
①凸博弈的核一定存在,即C(v)≠∅;
②凸博弈的沙普利值一定是一个核,即φ(v)∈C(v)。
3人博弈v4:某研究所甲研究出一种新技术,但是自己不能投入生产。他可以选择与企业乙或者企业丙合作,这样可以得到效益1。如果甲、乙、丙3家联手合作,可以得到效益3。试问如果甲、乙、丙3家合作,应该如何分配合作所得效益?
在这个例子中,可以写出该联盟博弈的效益函数:
该联盟博弈中的核可以写为
由沙普利值的公式,可以计算出联盟博弈中的沙普利值为
上述例子中的联盟博弈是凸博弈,其核非空,同时沙普利值是一个核。
