Shapley Value

The Efficiency Axiom states that the entire value generated by the grand coalition (the coalition of all players) is fully distributed among its members. No value is lost or created in the allocation.

• Mathematical Form: Σ φᵢ(v) = v(N), where φᵢ(v) is the Shapley Value for player i, and v(N) is the value of the grand coalition.
• Implication: This ensures the solution is budget-balanced. In machine learning feature attribution, it means the sum of the Shapley values for all features equals the model's prediction for a specific instance minus the average model prediction (the baseline).

The Symmetry Axiom states that if two players contribute identically to every possible coalition, they must receive the same payoff. Fairness is based solely on marginal contribution, not on labels or identities.

• Formal Condition: If v(S ∪ {i}) = v(S ∪ {j}) for every coalition S not containing i or j, then φᵢ(v) = φⱼ(v).
• Practical Role: This prevents bias in allocation. In explainable AI, if two features have identical effects on the model's output across all combinations, they are assigned identical importance scores, ensuring the explanation is invariant to feature renaming.

The Dummy Axiom specifies that a player who adds no marginal value to any coalition should receive a payoff of zero. Their presence or absence does not affect the coalition's outcome.

• Formal Condition: If v(S ∪ {i}) = v(S) for every coalition S not containing i, then φᵢ(v) = 0.
• Key Insight: This axiom enforces a direct link between causal contribution and reward. In feature attribution, a feature that never changes the model's prediction, regardless of what other features are present, correctly receives an attribution of zero, filtering out irrelevant inputs.

The Additivity Axiom states that if a game can be decomposed into two independent sub-games, a player's value in the combined game is the sum of their values in each sub-game. This is crucial for analyzing complex, composite interactions.

• Mathematical Form: For any two games v and w, φᵢ(v + w) = φᵢ(v) + φᵢ(w).
• Critical Application: This axiom enables the practical computation of Shapley values for machine learning models. A complex model's prediction function can be seen as a combination of simpler functions. This linearity property allows for efficient approximation algorithms and is foundational to implementations like SHAP (SHapley Additive exPlanations).

Lloyd Shapley proved that the four axioms—Efficiency, Symmetry, Dummy, and Additivity—uniquely define the Shapley Value formula. No other solution concept satisfies all four simultaneously.

• The Formula: φᵢ(v) = Σ_{S ⊆ N \ {i}} [ |S|! (|N| - |S| - 1)! / |N|! ] * ( v(S ∪ {i}) - v(S) )
• Significance: This theorem provides the mathematical guarantee that the Shapley Value is the only fair allocation method under these universally accepted principles. It transitions the concept from a heuristic to a theoretically grounded standard for fairness in cooperative games and model interpretability.

The translation of these game theory axioms to feature attribution in machine learning provides a robust framework for explainability that alternatives like LIME or simple gradients lack.

• Efficiency ensures local accuracy: the explanation matches the model's output.
• Symmetry & Dummy guarantee consistency and eliminate artifacts.
• Additivity enables the use of Shapley values with model ensembles and complex, non-linear functions.

This axiomatic foundation is why the Shapley Value is considered the gold standard for feature attribution, providing the only method that satisfies all desirable properties for a faithful explanation.

The branch of game theory that studies scenarios where groups of players (coalitions) can form binding agreements to cooperate and achieve outcomes superior to acting alone. It focuses on:

• Characteristic Function: A function v(S) that defines the total payoff a coalition S can guarantee itself, independent of outsiders.
• Core Solution: The set of payoff distributions where no subgroup has an incentive to break away and form its own coalition.
• Solution Concepts: Methods, like the Shapley Value, for proposing a "fair" distribution of the coalition's total gains among its members. The Shapley Value is one of the most prominent and axiomatically justified solution concepts within this framework.

The fundamental building block for calculating the Shapley Value. An agent's marginal contribution to a coalition S is the increase in value that agent creates by joining: MC_i(S) = v(S ∪ {i}) - v(S)

• Key Insight: The Shapley Value is essentially a weighted average of an agent's marginal contribution across all possible orders in which the coalition could be formed.
• Example: In a data science team (Data Engineer D, ML Engineer M, Domain Expert E), M's marginal contribution to the coalition {D} is the additional value M brings when joining D alone, compared to D's solo value.

The Shapley Value is uniquely defined by four desirable properties (axioms) that a fair payoff distribution should satisfy:

• Efficiency: The sum of all agents' Shapley Values equals the total value of the grand coalition: Σ φ_i(v) = v(N).
• Symmetry: If two agents contribute identically to every coalition, they receive the same payoff.
• Dummy Player: An agent who contributes zero marginal value to every coalition receives a payoff of zero.
• Additivity: For two combined games, the Shapley Value of the sum game is the sum of the Shapley Values from each individual game. This axiomatic foundation is what gives the Shapley Value its mathematical rigor and justification as a "fair" method.

An alternative power index from cooperative game theory, often compared to the Shapley Value. While the Shapley Value averages marginal contributions over all orderings, the Banzhaf Index averages over all coalitions.

• Calculation: It counts the number of coalitions for which an agent is a swing player (i.e., their inclusion changes the coalition from losing to winning), then normalizes.
• Key Difference: The Banzhaf Index does not satisfy the Efficiency axiom; the indices sum to a value that is not necessarily the total value of the grand coalition. It is often used in voting theory to measure raw voting power, whereas Shapley is used for fair economic distribution.

The set of all possible payoff distributions to the players such that no coalition has an incentive to defect. Formally, a payoff vector x is in the core if:

1. It is efficient: Σ x_i = v(N).
2. It is coalitionally rational: For every possible coalition S, Σ_{i in S} x_i ≥ v(S).

• Relation to Shapley: The Shapley Value is not always in the core; for some games, it can propose a distribution that some coalition would find unfair. A key research area is determining for which classes of games (e.g., convex games) the Shapley Value is guaranteed to lie within the core, ensuring its stability against coalitional deviations.