Möbius transforms and Shapley values for vector-valued functions on weighted directed acyclic multigraphs
This foundational work provides a generalized framework for Shapley values, potentially impacting explainable AI and other domains by allowing analysis of complex hierarchical structures with vector-valued data.
The paper generalizes Möbius inversion and Shapley values to weighted directed acyclic multigraphs and vector-valued functions, addressing the lack of unique determination in this setting by introducing new axioms and projection operators, resulting in a unique explicit formula that recovers classical properties and enables applications in fields like machine learning and explainable AI.
We generalize the concept of Möbius inversion and Shapley values to directed acyclic multigraphs and weighted versions thereof. We further allow value functions (games) and thus their Möbius transforms (synergy function) and Shapley values to have values in any abelian group that is a module over a ring that contains the graph weights, e.g. vector-valued functions. To achieve this and overcome the obstruction that the classical axioms (linearity, efficiency, null player, symmetry) are not strong enough to uniquely determine Shapley values in this more general setting, we analyze Shapley values from two novel points of view: 1) We introduce projection operators that allow us to interpret Shapley values as the recursive projection and re-attribution of higher-order synergies to lower-order ones; 2) we propose a strengthening of the null player axiom and a localized symmetry axiom, namely the weak elements and flat hierarchy axioms. The former allows us to remove coalitions with vanishing synergy while preserving the rest of the hierarchical structure. The latter treats player-coalition bonds uniformly in the corner case of hierarchically flat graphs. Together with linearity these axioms already imply a unique explicit formula for the Shapley values, as well as classical properties like efficiency, null player, symmetry, and novel ones like the projection property. This whole framework then specializes to finite inclusion algebras, lattices, partial orders and mereologies, and also recovers certain previously known cases as corner cases, and presents others from a new perspective. The admission of general weighted directed acyclic multigraph structured hierarchies and vector-valued functions and Shapley values opens up the possibility for new analytic tools and application areas, like machine learning, language processing, explainable artificial intelligence, and many more.