arXiv:2510.05786cs.GTcs.DM2025-10被引 1

将博弈论中的贡献分配方法扩展到复杂图结构与向量值函数,提升可解释性分析能力。

Möbius transforms and Shapley values for vector-valued functions on weighted directed acyclic multigraphs

  • 基于加权有向无环多重图构建向量值函数的Möbius变换与Shapley值新定义
  • 提出弱元素与扁平层级新公理,确保分配结果唯一且满足高效、零玩家等性质
  • 适用于非格结构偏序关系,拓展了机器学习与可解释AI的应用边界

Möbius反演与Shapley值是刻画复杂系统高阶结构的两种数学工具。前者将高阶交互定义为偏序集上的离散导数;后者提供一种合理方式将这些交互归因于系统的‘原子’元素。二者在组合数学、合作博弈论、机器学习及可解释AI中广泛应用。本文同时从两个正交方向推广:1)从实值函数推广到任意阿贝尔群值(特别是向量值函数);2)从偏序集和格推广到有向无环多重图(DAMGs)及其加权版本。经典公理(线性、效率、零玩家、对称性)在更一般设定下不足以唯一确定Shapley值。我们通过引入投影算子,递归地将高阶协同效应回溯至图根节点,并提出两个自然公理:弱元素(零协同联盟可移除而不影响归因)与扁平层级(无中间层级时,归因按边数比例分配)。结合线性公理,这三个公理唯一确定了Shapley值,并自动生成效率、零玩家、对称性及一项新的投影性质。该框架涵盖所有现有格结构定义作为特例,自然处理此前无法处理的非格偏序游戏场景。向量值函数与通用DAMG层次结构的扩展,为机器学习、自然语言处理与可解释AI开辟新应用方向。

原文摘要 · Abstract (English)

Möbius inversion and Shapley values are two mathematical tools for characterizing and decomposing higher-order structure in complex systems. The former defines higher-order interactions as discrete derivatives over a partial order; the latter provides a principled way to attribute those interactions back to the `atomic' elements of the system. Both have found wide application, from combinatorics and cooperative game theory to machine learning and explainable AI. We generalize both tools simultaneously in two orthogonal directions: 1) from real-valued functions to functions valued in any abelian group (in particular, vector-valued functions), and 2) from partial orders and lattices to directed acyclic multigraphs (DAMGs) and weighted versions thereof. The classical axioms, linearity, efficiency, null player, and symmetry, which uniquely characterize Shapley values on lattices, are insufficient in this more general setting. We resolve this by introducing projection operators that recursively re-attribute higher-order synergies down to the roots of the graph, and by proposing two natural axioms: weak elements (coalitions with zero synergy can be removed without affecting any attribution) and flat hierarchy (on graphs with no intermediate hierarchy, attributions are distributed proportionally to edge counts). Together with linearity, these three axioms uniquely determine the Shapley values via a simple explicit formula, while automatically implying efficiency, null player, symmetry, and a novel projection property. The resulting framework recovers all existing lattice-based definitions as special cases, and naturally handles settings, such as games on non-lattice partial orders, which were previously out of reach. The extension to vector-valued functions and general DAMG-structured hierarchies opens new application areas in machine learning, natural language processing, and explainable AI.

可解释性博弈论图结构向量值

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。