The Tractability of the Shapley Value over Bounded Treewidth Matching Games

Gianluigi Greco, Francesco Lupia, Francesco ScarcelloIJCAI 2017 · DOI

TL;DR

This paper tackles the computational complexity of the Shapley value for matching games. The authors prove that computing the Shapley value for these games is tractable (solvable in polynomial time) when the underlying graph has bounded treewidth, extending previous results from trees to a broader class of graphs.

What Problem Does This Paper Address?

Coalitional games are used to model how groups of agents can collaborate to achieve a common goal and how the resulting value should be distributed among them. Matching games are a specific type of coalitional game where the value an agent or coalition can achieve is determined by the size of the maximum matching in the subgraph induced by their members. While the Shapley value is a widely accepted fair distribution concept, computing it for matching games is generally intractable (#P-hard). Previous work showed tractability for graphs with maximum degree two and for trees. However, it remained an open question whether this tractability extended to more complex graph structures like those with bounded treewidth. This paper addresses this gap by proving tractability for matching games on graphs with bounded treewidth.

Methods

The authors leverage a combination of theoretical tools and existing results:

  • Characterization of Marginal Contributions: They establish a crucial link between an agent being "blocked" by a matching (meaning they are exposed and cannot be part of an alternating path to another exposed node) and their marginal contribution to a coalition being zero. This is formalized through a series of lemmas.
  • Monadic Second-Order Logic (MSO) Encoding: The core of their approach involves encoding the conditions for an agent being blocked into an MSO formula. This allows them to rephrase the problem of counting coalitions with zero marginal contribution as a counting problem over MSO formulas.
  • Tractability of MSO on Bounded Treewidth Graphs: They then apply a known "master theorem" (Courcelle's theorem and its histogram variant) which states that MSO formulas can be evaluated (and counted) in polynomial time on graphs with bounded treewidth. This theorem is the key to their tractability result.
  • Implementation and Benchmark: The authors also implemented their algorithm using an MSO solver (Sequoia) and evaluated its performance on synthetic and real-world graph instances across different treewidths, demonstrating practical scalability.

Datasets

Not discussed in the paper. The paper uses synthetic graph instances from three families (trees, ladder graphs, and Halin graphs) and real-world graphs representing author relationships for benchmarking.

Key Insights and Ideas

  • Bridging Graph Structure and Game Theory: The paper elegantly connects graph properties (treewidth) to computational complexity in game theory (Shapley value tractability). This highlights the power of using structural graph properties to tame computationally hard problems.
  • The Power of MSO Encoding: The ability to translate complex game-theoretic conditions (like "blocked node") into formal logic (MSO) is a powerful technique. This allows leveraging existing, highly optimized solvers and theoretical results from logic and graph theory.
  • Generalization Beyond Trees: Extending tractability from trees to the broader class of bounded treewidth graphs is a significant theoretical advancement, opening up the possibility of efficient computation for a wider range of practical scenarios.
  • Practical Validation: The implementation and benchmarking demonstrate that the theoretical approach is not just an academic exercise but can be practically realized, providing valuable insights into performance scaling.

Key Results

  • Polynomial-Time Tractability: The paper proves that the Shapley value for matching games can be computed in polynomial time for any class of graphs with bounded treewidth.
  • Linear-Time Tractability for Banzhaf Value: For the related Banzhaf value, they show an even stronger result: linear-time computability on bounded treewidth graphs.
  • Experimental Validation: The implemented algorithm scales well with graph size for fixed treewidth, and performance degrades as treewidth increases, as expected. The number of blocked coalitions discovered by the MSO solver is shown to be very large, highlighting the computational advantage over naive enumeration.

Limitations and Future Work

  • Weighted Matching Games: The paper focuses on unweighted matching games. The authors note that their approach does not directly extend to weighted matching games, which remains an open problem.
  • Fixed-Parameter Tractability: While polynomial time is achieved, it's an open question whether matching games on bounded treewidth graphs are fixed-parameter tractable (solvable in $f(k) \cdot ||G||^{O(1)}$ time, where $k$ is treewidth).
  • Other Solution Concepts: The paper focuses on Shapley and Banzhaf values. Exploring tractability for other solution concepts on bounded treewidth matching games could be a future direction.

Summary updated

BibTeX
@inproceedings{greco2017tractability,
  author = {Gianluigi Greco and Francesco Lupia and Francesco Scarcello},
  title = {{The Tractability of the Shapley Value over Bounded Treewidth Matching Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/145},
}
Figure