Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.05786 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911613581262848 |
|---|---|
| author | Forré, Patrick Jansma, Abel |
| author_facet | Forré, Patrick Jansma, Abel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05786 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Möbius transforms and Shapley values for vector-valued functions on weighted directed acyclic multigraphs Forré, Patrick Jansma, Abel Computer Science and Game Theory Discrete Mathematics Machine Learning Combinatorics 91A12 (Primary) 06A07, 05E99 (Secondary) F.2.2; G.2.1; G.2.2; I.2.0 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. |
| title | Möbius transforms and Shapley values for vector-valued functions on weighted directed acyclic multigraphs |
| topic | Computer Science and Game Theory Discrete Mathematics Machine Learning Combinatorics 91A12 (Primary) 06A07, 05E99 (Secondary) F.2.2; G.2.1; G.2.2; I.2.0 |
| url | https://arxiv.org/abs/2510.05786 |