Axiomatic and Probabilistic Foundations for the Hodge-Theoretic Shapley Value

Basic Information

• Paper ID: 2106.15094
• Title: Axiomatic and Probabilistic Foundations for the Hodge-Theoretic Shapley Value
• Author: Tongseok Lim (Purdue University)
• Classification: math.OC cs.GT econ.TH
• Publication Date: October 14, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2106.15094

Abstract

This paper establishes a complete theoretical foundation for the Hodge-theoretic Shapley value extension proposed by Stern and Tettenhorst (2019). The author proves that a set of five axioms—efficiency, linearity, symmetry, a modified null player condition, and an independence principle—uniquely characterize this value on all coalitions, not merely the grand coalition. Simultaneously, the author derives a probabilistic representation that interprets each participant's value as the expected cumulative marginal contribution along a random walk on the coalition graph. These dual axiomatic and probabilistic results unify fairness considerations with stochastic interpretations, positioning the Hodge-theoretic value as a canonical generalization of the Shapley framework.

Research Background and Motivation

Problem Background

Classical Shapley value theory assumes that all participants ultimately form the grand coalition and employs four axioms (efficiency, symmetry, null player, and linearity) to determine a fair allocation of the total value v(N). However, this theory cannot directly assess participant contributions when the game terminates at a partial coalition state S ⊊ N.

Research Motivation

1. Theoretical Gap: Although the Shapley formula can be applied to each subgame, this approach implicitly assumes coalitions grow only toward the target S, failing to capture the complete structure of the larger game involving all participants in N.
2. Practical Necessity: Modern applications (data valuation in machine learning, feature attribution, medical model interpretation, etc.) require assessing participant contributions in partial coalitions.
3. Theoretical Completeness: While the Stern-Tettenhorst framework is innovative, it exhibits two critical deficiencies:
   • Lack of a complete axiomatic foundation that uniquely characterizes values on all partial coalitions
   • Absence of a probabilistic interpretation analogous to the Shapley formula

Core Contributions

1. Complete Axiomatic Characterization: Proposes five axioms (A1-A5) that uniquely determine value allocations across all coalition states, not merely the grand coalition.
2. Probabilistic Representation Theorem: Derives a probabilistic formula based on random walks on the coalition graph, interpreting participant values as expected cumulative marginal contributions.
3. Theoretical Unification: Establishes equivalence between the axiomatic approach and probabilistic interpretation, providing a solid theoretical foundation for the Hodge-theoretic Shapley value.
4. Computational Method: Demonstrates that values defined probabilistically can be efficiently computed by solving the linear system (3.3).

Methodology in Detail

Task Definition

Given a cooperative game v ∈ G_N, assign values Φ_i(v,S) to each coalition S ⊆ N and each participant i ∈ N such that fairness criteria are satisfied and probabilistic interpretation is available.

Core Framework

1. Coalition Graph Construction

Represents the coalition space using a hypercube graph G = (V,E):

• Vertex set: V := 2^N = {S | S ⊆ N}
• Edge set: E := {(S, S ∪ {i}) ∈ V × V | S ⊆ N \ {i}, i ∈ N}

2. Poisson Equation

The balance equation proposed by Stern-Tettenhorst:

Φ_i(v,S) - (1/|N|)∑_{T~S} Φ_i(v,T) = (1/|N|)∑_{T~S} ∂_iv(T,S)

where ∂_iv denotes participant i's marginal contribution.

3. Five-Axiom System

• A1 (Efficiency): v(S) = ∑_{i∈N} Φ_i(v,S)
• A2 (Linearity): Φ_i(αv + α'v', S) = αΦ_i(v,S) + α'Φ_i(v',S)
• A3 (Symmetry): Φ_i(v^{ij}, S^{ij}) = Φ_j(v,S)
• A4 (Null Player): If ∂iv ≡ 0, then Φ_j(v, S∪{i}) = Φ_j(v,S) = Φ_j(v{-i}, S)
• A5 (Independence): For all S ⊆ N{i}, Φ_i(v,S) + Φ_i(v, S∪{i})/2 is constant

Technical Innovations

1. Independence Axiom (A5)

This is the key innovation, requiring that the average value of participant i across states with and without membership in the coalition be independent of the specific coalition S. This condition:

• Supplements the classical Shapley axioms
• Ensures uniqueness of values across all partial coalitions
• Possesses an intuitive fairness interpretation

2. Random Walk Model

A Markov chain defined on the coalition space:

• Transition probability: p_{S,T} = 1/|N| if T ~ S
• Permits participants to join and leave coalitions
• Initial state: X_0 = ∅

3. Path Integral Representation

Expected total contribution of participant i reaching coalition S:

Ψ_i(v,S) = E[∑_{t=1}^{τ_S} ∂_iv(X_{t-1}, X_t)]

Main Theoretical Results

Theorem 4.1 (Uniqueness Characterization)

There exists a unique mapping Φ satisfying axioms A1-A5 and initial condition Φ(v,∅) = 0, and this mapping is precisely the solution to Poisson equation (3.3).

Theorem 5.1 (Probabilistic Equivalence)

Φ = Ψ, meaning the axiomatically defined value and the probabilistically defined path integral value are completely identical.

Experimental Validation

Glove Game Example

For a 3-person glove game (participant 1 has a left glove, participants 2 and 3 have right gloves):

• Classical Shapley value: ϕ_1(v) = 2/3, ϕ_2(v) = ϕ_3(v) = 1/6
• Hodge-theoretic value provides complete value tables for all partial coalitions

Two-Person Game Direct Calculation

The author provides detailed direct calculations of Ψ values in two-person games, verifying consistency with solutions to the Poisson equation.

Related Work

Classical Theoretical Foundations

• Shapley's (1953) original four-axiom system
• Axiomatic tradition in cooperative game theory

Modern Extensions

• Applications of combinatorial Hodge theory to game theory (Candogan et al., 2011)
• Game-theoretic interpretations of graph Poisson equations (Jiang et al., 2011)
• Pioneering work by Stern-Tettenhorst (2019)

Application Domains

• Feature attribution and data valuation in machine learning
• Medical model interpretation
• Sustainable energy cost allocation
• Social network analysis

Conclusions and Discussion

Main Conclusions

1. Complete Characterization: The five-axiom system uniquely determines the Hodge-theoretic Shapley value
2. Probabilistic Interpretation: The random walk model provides intuitive probabilistic meaning
3. Theoretical Unification: Establishes equivalence between axiomatic and probabilistic approaches
4. Computational Feasibility: Linear system solving provides practical computational methods

Theoretical Significance

• First complete characterization of solutions to Poisson equations on graphs
• Extends Shapley theory from the grand coalition to the entire coalition lattice
• Unifies fairness principles with stochastic process interpretations

Limitations

1. Computational Complexity: Linear system solving may face computational challenges for large-scale games
2. Model Assumptions: Uniform transition probabilities may not suit all practical scenarios
3. Application Validation: Requires more empirical validation of the theoretical framework's effectiveness

Future Directions

1. Develop efficient computational algorithms for large-scale games
2. Apply the framework to practical problems (economics, political science, machine learning)
3. Investigate extensions with non-uniform transition probabilities
4. Explore analogous theories on alternative graph structures

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Provides the complete theoretical foundation missing from the Stern-Tettenhorst framework
2. Methodological Innovation: Independence axiom A5 is a key innovation with profound theoretical significance
3. Dual Perspective: Unification of axiomatic and probabilistic methods strengthens theoretical persuasiveness
4. Rigorous Proofs: Employs combinatorial Hodge theory tools for mathematically rigorous proofs

Weaknesses

1. Practical Validation: Lacks verification through large-scale real-world applications
2. Computational Efficiency: Insufficient discussion of computational complexity in large-scale settings
3. Model Limitations: Uniform random walk assumption may be oversimplified

Impact

1. Theoretical Contribution: Provides important theoretical extension to cooperative game theory
2. Interdisciplinary Value: Possesses application potential in machine learning, economics, and related fields
3. Methodological Significance: Demonstrates how abstract mathematical tools can be applied to game-theoretic problems

Applicable Scenarios

• Cooperative games requiring assessment of partial coalition contributions
• Model interpretation and feature attribution in machine learning
• Node importance evaluation in network analysis
• Cost/benefit allocation problems in economics

References

• Shapley, L. S. (1953). A value for n-person games.
• Stern, A. & Tettenhorst, A. (2019). Hodge decomposition and the shapley value of a cooperative game. Games and Economic Behavior.
• Candogan, O. et al. (2011). Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research.

This paper provides a complete theoretical foundation for the Hodge-theoretic Shapley value. Through innovative axiomatic methods and probabilistic interpretation, it successfully extends classical Shapley theory to the entire coalition space, possessing significant theoretical value and broad application prospects.