arXiv:2503.22358v1 公告类型: cross 摘要：Shapley值起源于合作博弈论，已被用于定义衡量数据库事实对得到给定查询答案所作贡献的责任度量。对于非数值查询，通过考虑玩家为事实，财富函数将每个数据库子集分配1或0的方式来进行，这取决于给定子集中的查询答案是否成立。虽然从概念上来说这一点很简单，但这种方法存在一个明显的缺点：在数据复杂性上计算这种Shapley值的问题是#P难问题，即使对于简单的合取查询也是如此。这促使我们重新审视什么是合理的责任感量度，并引入了一种新的责任度量——最小支持的加权和（WSMS）——它们满足直观的性质。有趣的是，尽管WSMS的定义简单且与Shapley值公式毫无明显联系，我们证明了每一种WSMS量度都可以被视为适当定义的合作博弈的Shapley值。此外，对于一类广泛的查询，包括所有合取查询的并集，WSMS量度在数据复杂性上具有可处理性。我们进一步探讨了WSMS计算的组合复杂性，并为各种合取查询的子类建立了（不）可处理结果。