Marginality Approach to Shapley Value in Games with Externalities

Oskar Skibski, Tomasz Michalak, Michael WooldridgeSSRN 2013 · DOI

Sure, here's a blog-style summary of the paper "Marginality Approach to Shapley Value in Games with Externalities":

TL;DR

This paper introduces a generalized "marginality approach" to extend the Shapley value to games with externalities, where the actions of one player can affect the outcomes for others. By carefully defining how players' contributions are measured in such complex scenarios, the authors show that this approach can uniquely determine a fair distribution of value, encompassing all existing extensions that adhere to Shapley's core principles.

What Problem Does This Paper Address?

Coalitional game theory aims to fairly distribute the gains from cooperation among players. The Shapley value is a cornerstone concept for achieving this, but it traditionally assumes that players' actions don't create "externalities" – that is, one player's contribution doesn't directly impact another's outcome beyond their shared coalition. In reality, externalities are common (e.g., pollution from a joint venture, or the impact of international treaties). Extending the Shapley value to these more realistic scenarios has been a long-standing challenge, as direct translations of its axioms often fail to yield a unique, fair distribution. This paper tackles this by proposing a flexible framework to adapt the Shapley value to games with externalities.

Methods

The core of the paper is the "marginality approach," which reinterprets how a player's contribution is measured. Instead of a simple difference in coalition value, the contribution is now a weighted average of potential outcomes, where the weights (denoted by 'a') capture the probabilities of different coalition formations and player transfers. The authors then:

  • Generalize Shapley's Axioms: They adapt the standard Shapley axioms (Efficiency, Symmetry, Additivity, and Null-Player) to this new framework, showing that these, along with the 'a' weights, uniquely define an "a-value."
  • Prove Universality: A key contribution is proving that this "marginality approach" can generate any value that satisfies the generalized Shapley axioms. This means it's not just one specific extension, but a unifying framework.
  • Analyze Axiom Properties: They investigate how desirable properties of the resulting value (like monotonicity and symmetry) translate into specific conditions on the 'a' weights. This allows for understanding what kind of weights lead to what kind of fair outcomes.
  • Connect to Other Axiomatizations: The paper shows how this approach relates to other existing methods, like those proposed by Young and Myerson, demonstrating its broad applicability.

Datasets

Not discussed in the paper. The paper focuses on theoretical game theory and does not involve empirical data or datasets.

Key Insights and Ideas

  • Externalities Don't Break Shapley, They Just Complicate It: The paper shows that Shapley's core principles can be extended to games with externalities, but the definition of "contribution" needs to become more sophisticated.
  • Weights are Key: The 'a' weights are not just arbitrary parameters; they encode crucial information about how players interact and form coalitions, directly influencing the fairness of the outcome.
  • A Unifying Framework: The "marginality approach" isn't just another extension; it's presented as a comprehensive method that can generate all valid Shapley-like values for games with externalities.
  • Properties Dictate Weights: There's a clear mapping between desirable fairness properties (like monotonicity and symmetry) and the characteristics of the 'a' weights, offering a way to select appropriate weights for specific applications.

Key Results

  • Unique a-Value: For any set of weights 'a', the marginality approach, combined with generalized Shapley axioms, yields a unique value.
  • Completeness: The marginality approach can generate all values that satisfy the generalized Shapley axioms.
  • Axiom-Weight Connections:
    • Weak Monotonicity requires non-negative weights.
  • Strong Monotonicity requires positive weights.
  • Strong Symmetry requires "interlace resistant" weights.
  • Strong Null-Player Axiom requires "expansion resistant" weights.
  • Myerson Equivalence: Myerson's axiomatization for games with externalities is equivalent to Shapley's marginality approach if and only if the weights are both interlace and expansion resistant.

Limitations and Future Work

  • Intuition for Weights: While the paper establishes mathematical conditions for weights, the intuitive interpretation of "interlace resistance" and "expansion resistance" could be further explored.
  • Practical Applications: The paper focuses on theoretical foundations. Future work could explore how to apply these findings to real-world scenarios and how to determine appropriate weights in practice.
  • Stochastic Processes: The authors hint at connections between their work and probability theory, particularly stochastic processes. Further research could delve into how probabilities of coalition formation can inform the choice of weights.
  • Other Axiomatizations: The paper primarily focuses on Shapley's axioms. Exploring how other axiomatic frameworks for games with externalities can be unified or understood through the marginality approach is a potential avenue.

Summary updated

BibTeX
@misc{skibski2013marginality,
  author = {Oskar Skibski and Tomasz Michalak and Michael Wooldridge},
  title = {{Marginality Approach to Shapley Value in Games with Externalities}},
  year = {2013},
  doi = {10.2139/ssrn.2311112},
  howpublished = {SSRN},
}
Figure