夏普利值是博弈论中用于在参与者之间分配合作收益或成本的一种规则。它假设群体按均匀随机的顺序形成,并将每位参与者在这一过程中所作贡献的平均值分配给该参与者。这一概念由劳埃德·S. 夏普利于1953年提出,给出了一种唯一确定的分配方案,满足关于效率、对称性、无关参与者以及博弈组合的一组标准要求。
只要能为每一种可能的参与者组合赋予一个数值来表示其价值,这一概念就适用。其应用包括分摊基础设施成本、衡量投票权力、分配共同收益,以及解释机器学习模型的预测结果。它在数学上的吸引力,在于将直观的边际贡献计算与公理化刻画联系起来。不过,对它的解读仍取决于如何为合作情境建模:夏普利值分配的是博弈所规定的价值,而不是独立确定这一价值应当是多少,也不是界定所有情境下何谓公平。
合作博弈与边际贡献公式
标准框架是一个合作博弈,其中有一个有限参与者集合 ,以及一个特征函数 。每个子集 称为一个联盟,其收益为 。通常约定 。全体参与者组成的大联盟为 ,其收益 就是有待分配的总量。参与者可以代表个人、企业、地区、机器、变量,或其他可明确区分的贡献者。
通常采用的模型是可转移效用博弈:联盟收益以一种共同的数值单位表示,并可在联盟成员之间分配。这一假设直接适用于以货币计量的成本或收入分摊。在其他应用中,计量单位可以是预测性能、信息量,或其他标量。特征函数记录各个联盟能够取得的成果,但其本身并不规定联盟成员如何协商、联盟如何形成,也不说明大联盟是否真的会出现。
对于参与者 ,夏普利值为
方括号内的项是该参与者对联盟 的边际贡献。它的系数表示:在参与者的所有排列顺序中,恰好只有 中的成员排在 之前的顺序所占的比例。这些先于 的参与者有 种排列方式,而后于 的参与者有 种排列方式。
等价地,令 为从 的所有置换中等概率选取的一个置换,令 为排在 之前的参与者集合。则有
这种期望值表示给出了这一分配规则最常见的解释:对参与者在每一种可能的合作顺序、每一个可能位置上的贡献取平均。这些顺序只是数学上用于求平均的工具,不必对应实际发生过的历史过程。
例如,假设两家企业单独经营时分别能获得 20 和 10 的收益,而合作时能获得 50。第一家企业先加入时贡献为 20,后加入时贡献为 40,因此获得的夏普利值分配为 30。第二家企业先加入时贡献为 10,后加入时贡献为 30,因此获得 20。等价地,两家企业各自保留单独经营所得的收益,再平分合作带来的额外剩余 20。当参与者更多时,同样的计算方法也能处理随不同联盟情境而变化的贡献。
一个重要特点是,不同规模的联盟获得的总权重相同。对于每个 ,所有规模为 的前序参与者联盟合计具有 的权重。因此,夏普利值可以理解为:先对每种规模下所有可能的联盟取平均,再对不同联盟规模取平均。
公理化刻画与历史基础
夏普利在《 人博弈的一个值》中提出了这一概念,该文于 1953 年发表于《博弈论论丛》第二卷。这项研究属于约翰·冯·诺伊曼和奥斯卡·摩根斯特恩于 1944 年出版《博弈论与经济行为》之后合作博弈论的发展成果。夏普利并非要描述某种具体的讨价还价程序,而是试图依据一般原则,为博弈中的每个参与者位置确定一个数值。
现代常见的表述采用四条公理。效率性要求将大联盟的全部价值分配完毕:
对称性要求可互换的参与者获得相同的分配。如果对于每个既不包含 也不包含 的联盟 ,都有
则参与者 和 是可互换的。这一要求针对的是他们在整个特征函数中的作用,而不只是他们各自单独的价值或观察到的活动。
零参与者公理规定,若某个参与者对任何联盟的边际贡献均为零,即满足
则分配给该参与者的数值为零。
一种相关表述采用虚设参与者性质:如果某个参与者始终带来相同的增量 ,那么该参与者恰好获得这一数额。可加性要求
其中,两个博弈的相加是对每个联盟的价值分别相加。就实际含义而言,将两项分别给定的活动各自进行分配,再把分配结果相加,应当与先将二者的价值函数相加、再分配总价值所得的结果相同。
在参与者集合固定的有限可转移效用博弈空间上,这些性质唯一确定了夏普利值。其存在性可直接由边际贡献公式得出。效率性成立,是因为沿着任一顺序将边际贡献相加时,中间项会逐项抵消,最终得到从 到 的总增量。对称性可通过交换各个顺序中可互换的参与者得到;零参与者性质和可加性则源于边际贡献所具有的相应性质。
唯一性可以借助一致同意博弈来理解。对于每个非空的 ,定义
要产生这一单位的价值,只需要 中的参与者。因此,对称性、效率性和零参与者要求共同决定了: 中每个成员都必须获得 ,其他所有参与者均获得零。每个博弈都能唯一地表示为这些一致同意博弈的线性组合,因此,可加性将这一分配唯一地扩展到所有博弈。
这一定理的唯一性结论以这些公理为前提,并不意味着所有应用都必须接受它们。对于某些特定制度,可加性、对形式上对称的位置给予同等待遇,或不限制可能形成的联盟集合,未必是合适的要求。改变这些建模假设,就会产生其他分配规则。
交互红利与连续表示
夏普利值也可以理解为对博弈中不同交互成分的分配。以约翰·C. 海萨尼命名的海萨尼红利使这一点得到了明确体现。对于非空联盟 ,其红利为
等价地,一个联盟的红利,就是该联盟的价值减去已分配给其所有真子联盟的红利。由此得到的分解满足
单人联盟的红利代表其独立价值。双人联盟的红利衡量这两人合作所带来的、超出各自独立价值之和的额外贡献。更高阶的红利则代表任何低阶联盟都未能涵盖的贡献。这是一种代数分解:各成分既可以为正,也可以为负,不必对应于可单独观测的生产过程。
在这种表示下,夏普利值具有格外简洁的形式:
每一项交互红利都由参与该交互的参与者均分。因此,在双人博弈中,每个人都获得自身的独立价值,加上两人合作额外价值的一半。当参与者达到三人或更多时,这一规则还会分摊更高阶的互补效应或冗余效应。
考虑一个三人博弈:各单人联盟的价值均为零,各双人联盟的价值均为 6,大联盟的价值为 9。每个双人联盟的红利为 6,三人联盟的红利则为 。每位参与者都属于两个双人联盟,从双人联盟红利中获得 ,同时还从三人联盟红利中获得 。最终每人分得 3。这个负的三方红利修正了双人联盟价值中的重叠部分。
另一种表示将夏普利值与微积分联系起来。定义多重线性扩展
当 时,如果每位参与者 都以概率 独立加入联盟,那么该函数值就等于联盟价值的期望。夏普利值于是可表示为
要理解其中的权重,可以考察某个特定的前序参与者集合 :它对应的权重是 的积分,而该积分恰好等于原公式中的阶乘系数。这一恒等式将夏普利值与集合函数的光滑扩展以及数值积分联系起来。
这种表示并不意味着原博弈必须可微:原博弈的定义域是有限个联盟构成的集合。只有在构造出多项式 之后,才涉及可微性。此外,并非所有基于梯度的归因方法都等同于夏普利分配。两者是否相等,取决于所采用的扩展、积分路径以及对交互作用的处理方式。
联盟稳定性与核
一种分配即使满足夏普利公理,也未必能保持稳定,防止联盟脱离。这种稳定性通过核来研究。核是满足以下条件的分配 所构成的集合:
以及
对于利润分配博弈,第二个条件意味着,任何联盟所得都不少于其独立行动所能获得的收益。如果一个联盟的所得低于其价值,它就有可能通过分配独立行动所得的价值,让所有成员的处境都得到改善。因此,核体现的是分配对各联盟的可行性,以及抵御这类偏离的能力,而非平均边际贡献。
这些标准并不相同。考虑一个三人多数博弈:任何至少包含两名参与者的联盟,其价值均为 1;规模更小的联盟,其价值均为 0。根据对称性,每名参与者的夏普利值均为 。任意两人的所得合计只有 ,但他们独立组成联盟就能获得 1。因此,夏普利分配不属于核。事实上,这个博弈的核是空集:将三个两人联盟的约束相加,可得总分配额必须至少为 ,这与效率性相矛盾。
即使核非空,夏普利值也可能不属于核。假设一名卖方拥有一件不可分割的物品,两名买方中的任何一名与卖方交易,都能创造 10 的剩余。不含卖方的联盟价值为零;包含卖方和至少一名买方的联盟价值为 10。夏普利分配给予卖方 ,给予每名买方 。然而,卖方与任意一名买方的所得合计只有 ,低于其联盟价值 10。相比之下,核要求将全部 10 分配给卖方,每名买方所得均为零。买方之间的竞争带来了一种稳定性要求,它不同于夏普利值所依据的平均原则。
对于凸合作博弈,有一个重要的肯定性结果。这类博弈具有超模性:
等价地说,参与者所加入的联盟越大,其边际贡献就越不会降低。这体现了合作收益递增的特征。
对于凸博弈,每一种参与者排列所对应的边际贡献向量都属于核。由于核是凸集,这些向量的平均值——夏普利值——也属于核。更强的结论是,凸博弈的核恰好是其所有边际贡献向量的凸包。
这些结果区分了几个常被统称为“公平分配”的概念。效率性关注总价值是否得到完整分配,夏普利公理关注是否以一致的方式对待各方贡献,而是否属于核则关乎联盟稳定性。在一些重要的博弈类别中,这些标准可以同时满足,但一般情况下并非如此。此外,即使一种分配是稳定的,也不能据此确定选择该分配的谈判过程,更不能证明参与者会组成大联盟。
成本分摊、投票权力与联盟结构
成本分摊是边际贡献平均法的一项自然应用。设 为向联盟 提供服务的成本,且 。将夏普利公式直接应用于 ,便可按各参与者的平均增量成本确定其应分摊的份额。这些份额之和等于 。另一种做法是用博弈描述相对于分别提供服务所节省的成本,此时得到的分配方案分配的是节省额,而非实际支出。
机场跑道问题说明了这一机制。假设三类飞机所需的跑道建设规格分别对应 10、20 和 30 单位的成本,而为某个联盟服务的跑道必须满足其中要求最高的成员的需求。那么,对于非空的 ,有
第一层 10 单位的成本是三类飞机共同需要的,因此由三者均摊。接下来一层 10 单位的成本仅为第二类和第三类飞机所需,因此由这两类分摊。最后一层 10 单位的成本则全部由第三类承担。因此,按夏普利值计算的成本分摊份额为
这种分层解释可以推广到任意数量、按高低排列的服务需求。其他基础设施博弈可能需要采用不同的特征函数,例如连接指定用户群体所需的最低网络成本。
在投票领域,夏普利和马丁·舒比克于 1954 年提出的夏普利—舒比克权力指数将夏普利值应用于简单博弈。若一个联盟能够通过提案,其价值为 1,否则为 0。在参与者的每一种排列顺序中,都恰好有一名投票者的加入会使逐步形成的联盟从失败转为获胜。这名投票者就是关键投票者;在所有排列等概率出现的条件下,其成为关键投票者的概率就是其权力指数。
对于通过门槛为 3、投票权重为 的加权投票制度,各投票者的指数为 。权重为 2 的投票者在六种排列中的四种里起关键作用;另外两名权重较小的投票者各自在一种排列中起关键作用。因此,投票权力不一定与投票权重成正比。该指数衡量的是特定投票规则下的影响力,而不是选举中的受欢迎程度,也不是实证观察到的谈判成功程度。
一个相关指标是班扎夫权力指数,它对联盟采用不同的加权方式。其未归一化形式对应于以下情形中某位参与者的期望边际贡献:其他每位参与者均以 的概率独立加入联盟。相比之下,夏普利—舒比克指数赋予每一种可能的前驱联盟规模相同的总权重。这些概率模型可能得出不同的权力评估结果。
最后,一些应用中存在预先形成的群体或谈判集团。吉列尔莫·欧文于 1977 年提出的欧文值将夏普利方法推广到给定联盟结构的情形。它考虑群体按某种顺序加入、群体内部成员也按某种顺序加入的各种排列,并对其中的边际贡献取平均。所得结果反映了给定的分组方式;一般而言,它并不等同于将每位参与者都视为不受分组限制的独立参与者时得到的结果。
精确计算与近似计算
夏普利值的公式虽然只涉及有限项,但计算开销可能很大。一个有 名参与者的博弈共有 个联盟。若根据联盟价值表逐一计算每名参与者的夏普利值,并以直接的方式共享中间计算结果,所需算术运算次数的量级为 。枚举全部 种参与者顺序也是一种精确计算方法,但会重复求取许多联盟的价值,通常效率较低。
计算复杂度在很大程度上取决于博弈的表示方式。如果直接给出完整的联盟价值表,该表本身就包含指数数量的条目,因此,即使计算量相对于表的大小是多项式级的,相对于参与者人数仍可能是指数级的。反过来,紧凑的表示方式也可能使专门算法得以应用。加性博弈无需枚举联盟:若 ,则 。稀疏的红利表示也很方便,因为可以将列出的每项红利直接均分给对应的参与者。
加权投票博弈说明了计算难度如何随表示方式而变化。这类博弈的权重与通过门槛可以用很短的输入表示,但要精确计算参与者成为关键一票的情况,可能需要对大量符合条件的子集进行计数。动态规划可以利用整数权重及总权重有界的特点,得到伪多项式算法。但这并不意味着,当权重可以任意大时,这类方法的复杂度相对于权重的二进制编码长度仍为多项式级。在其他博弈中,即使只求取一个联盟的价值,也可能需要求解一个困难的数学优化问题。
一种广泛使用的替代方案是蒙特卡洛方法。独立地从所有排列中均匀随机抽取 个排列,并对每名参与者在这些排列中观测到的边际贡献取平均:
如果联盟价值的求取是精确的,这就是一个无偏估计量。当边际贡献的方差 有限时,其标准误为 。每抽取一个顺序,就能得到所有参与者各自的边际贡献,因此,同一串联盟价值计算结果可以用于估计整个分配方案。
如果参与者 的所有边际贡献都位于 内,则由有界随机变量的集中不等式可得
这是独立抽样条件下针对某一名参与者的界。若要同时为所有参与者提供保证,还需作进一步调整。按联盟规模进行分层抽样、复用联盟价值,以及对相关排列进行耦合,都可以降低计算成本或方差。
实际计算往往涉及两层近似。排列抽样近似的是夏普利值所需的平均运算,而仿真、条件估计或模型训练近似的是联盟价值本身。增加抽样排列的数量可以减少第一类误差,却不会自动消除第二类误差。因此,所报告的精度既取决于分配算法,也取决于定义博弈及求取其价值所采用的程序。
特征归因与预测建模
在模型解释中,参与者通常是输入特征,而博弈描述的是仅有选定特征可用时的预测。对于已拟合的模型 、观测 和随机输入向量 ,一种广泛使用的定义是
这一定义利用条件期望,为观测到 中的特征赋予价值。按照条件化的通常解释,当模型的所有输入均被观测到时,全体参与者组成的联盟的价值为 。因此,沙普利分配满足
由此,预测被分解为基准值与各特征的贡献。
斯科特·伦德伯格和李素仁于2017年提出的 SHAP(沙普利加性解释)框架,推动了这种联系在模型解释中的广泛应用。该框架中的算法针对指定的价值函数,计算或近似计算特征归因值。基于核的方法对采样得到的特征联盟进行加权回归,而专门针对树模型的方法则利用决策树结构,避免穷举所有可能的联盟。这些方法的计算特性与解释含义取决于模型类别,以及对特征缺失所作的假设。
其中一个关键区别在于,移除特征时采用条件分布还是边缘分布。另一种常见的博弈定义为
其中 。这一定义将已观测特征固定,并从缺失特征的边缘联合分布中抽取其取值。与基于条件分布的博弈不同,它通常会打破已观测特征组与缺失特征组之间的依赖关系。当所有特征相互统计独立时,这两种构造一致;当特征之间存在依赖关系时,两者可能给出差异显著的解释。
对于加性线性模型,
基于边缘分布的构造给出
由于相应的联盟博弈是加性的,因此无需分配交互作用的贡献。然而,在基于条件分布的构造中,相关变量可以提供彼此的信息,因此这个简单的、基于系数的表达式通常不再成立。
沙普利方法也可用于全局分析。联盟的价值可以定义为使用某个特征子集时的预测性能、预期损失函数值的降低量,或已解释的变异量。在数据估值中,参与者可以是训练记录或数据提供者;此时,联盟的价值就是使用其数据训练所得模型的性能。这类定义可能带来高昂的重新训练成本,其结果也可能取决于训练过程中的随机性。
即使都采用沙普利公式,这些仍是不同的博弈。局部预测归因分配的是单个观测的预测相对于基准值的偏差。全局性能分配所分配的是针对总体或评估样本的预测效用。训练数据估值分配的则是提供数据所带来的可衡量收益。它们的数值回答的是不同的问题,不能作为可互换的重要性度量。
解释、依赖关系与建模局限
只有明确了参与者以及每个联盟的价值,夏普利值才有唯一的定义。这些要素的选择,可能比采用精确计算还是近似计算方法更为重要。在成本分摊博弈中,所衡量的可能是建设费用、总运营成本、节省的支出,或净社会效益。在预测博弈中,所衡量的可能是输出概率、对数几率得分,或误差的减少量。这些选择会改变被分配的量,所得的夏普利值也未必一致。
尺度的选择很重要,因为夏普利规则对联盟价值是线性的,而并非在任意变换下都保持不变。将所有联盟价值乘以一个常数,所有分配值也会乘以该常数。对联盟价值施加非线性变换,通常既会改变贡献的大小,也会改变贡献的分布。例如,解释分类器的概率输出,与解释同一分类器的对数几率输出,在数学上是不同的,尽管这两种预测所表达的信息彼此相关。
参与者的划分粒度同样重要。将一个参与者拆分为多个子参与者,会改变可能的联盟及加入顺序。这些子参与者的价值之和,未必等于原参与者的价值。因此,在特征解释中,将一个类别变量表示为多个指示变量列,可能会得到与将该变量视为一个整体参与者不同的分配结果。必须明确界定将多个特征合并为一个参与者的博弈;仅仅把单独计算的特征值相加,通常无法得到该博弈的夏普利值。
特征之间的依赖关系揭示了另一种解释上的区别。假设某个模型使用 ,但不使用 ,且这两个变量高度关联。在条件博弈中,观测到 可能会改变模型输出的期望值,因为它提供了关于 的信息。因此,即使特征 没有出现在模型的计算公式中,也可能获得非零的夏普利值。而在边际替换博弈中,模型从未使用的特征,其边际贡献为零。这些结果源于对特征可用性的不同定义,并不意味着空参与者公理存在矛盾。
预测归因也不同于因果推断。观测一个特征、替换模型输入中该特征的数值,以及干预现实世界中生成该特征的过程,是不同的操作。要作出因果解释,就需要额外的结构来说明干预如何影响其他变量。无论是条件期望博弈,还是普通的边际替换,单靠自身都无法确立这样的结构。
最后,夏普利公理并未涵盖与分配有关的所有实质性考量。它们不会自动考虑需求、法定权利、议价能力、历史责任,或支付规则产生的策略性激励。参与者可能有能力更改所申报的成本、将一个身份拆分为多个身份,或影响价值函数。这类行为是否可行、是否有利可图,取决于其所处的机制。夏普利值为给定博弈规定了一种分配方案;要判断激励相容性与制度正当性,则需要另行分析该博弈及其参与者是如何构成的。