Coalitional Game Theory

The fundamental incentive for cooperation. A game is superadditive if the value created by two disjoint coalitions working together is at least the sum of what they could achieve separately.

• Formal definition: v(S ∪ T) ≥ v(S) + v(T) for all disjoint S, T ⊆ N
• Interpretation: The whole is greater than the sum of its parts
• Practical implication: In ML, this justifies why including more features never reduces the total predictive power available
• Counterexample: A game without superadditivity has no incentive for grand coalition formation

The Efficiency axiom requires that the total value generated by the grand coalition (all players) is fully distributed among the players, with nothing left over and no deficit.

• Formal definition: Σᵢ₌₁ⁿ φᵢ(v) = v(N)
• SHAP translation: The sum of all feature attributions exactly equals the difference between the model prediction and the baseline
• Why it matters: Ensures explanations are complete — no unexplained contribution is hidden
• Audit significance: Compliance officers can verify that 100% of a decision is accounted for

Players who contribute identically to every possible coalition must receive identical payoffs. This is the fairness axiom.

• Formal definition: If v(S ∪ {i}) = v(S ∪ {j}) for all S ⊆ N \ {i,j}, then φᵢ(v) = φⱼ(v)
• SHAP translation: Two features with identical effects on the model receive identical SHAP values
• Practical example: If age and years_of_experience have the exact same marginal contribution in every feature subset, they get equal attribution
• Discrimination safeguard: Prevents arbitrary bias in feature importance assignment

A player who contributes nothing to any coalition receives zero payoff. This is the axiom of non-entitlement.

• Formal definition: If v(S ∪ {i}) = v(S) for all S ⊆ N \ {i}, then φᵢ(v) = 0
• SHAP translation: Features that never affect the model prediction get SHAP values of zero
• Missingness property: Directly corresponds to the SHAP requirement that absent features have zero attribution
• Debugging utility: Non-zero SHAP for a supposedly irrelevant feature signals data leakage or spurious correlation

The value assigned to a player across two separate games played simultaneously equals the sum of what they would receive in each game individually.

• Formal definition: φᵢ(v + w) = φᵢ(v) + φᵢ(w) for any two games v and w
• SHAP consequence: SHAP values are additive across models — the explanation of an ensemble is the average of individual model explanations
• Computational benefit: Enables decomposition of complex models into interpretable components
• Ensemble transparency: Random forest SHAP = weighted average of individual tree SHAP values

The marginal contribution of player i to coalition S is the additional value gained when i joins: v(S ∪ {i}) − v(S). The Shapley value is the weighted average of these marginal contributions over all possible coalition orderings.

• All 2ⁿ⁻¹ subsets are considered for each player
• Weighting: Each coalition size gets equal total weight, with permutations within a size uniformly weighted
• SHAP computation: Each feature's value is masked in and out across all feature subsets
• Computational challenge: Exact computation is NP-hard, motivating KernelSHAP and TreeSHAP approximations

A solution concept that fairly distributes the total payout of a coalition to each player based on their marginal contribution across all possible coalitions. In ML, the 'players' are input features and the 'payout' is the model prediction. The Shapley value for feature i is the weighted average of its marginal contribution over all feature subsets.

• Axiomatic Foundation: Uniquely satisfies Efficiency, Symmetry, Dummy, and Additivity
• Computational Cost: Exact computation is O(2^n), requiring approximation for high-dimensional data
• Origin: Lloyd Shapley, 1953

The difference in a model's prediction when a specific feature is added to a subset of other features. For a coalition S not containing feature i, the marginal contribution is:

v(S ∪ {i}) - v(S)

This value captures the incremental predictive power that feature i brings to the coalition. Shapley values compute the weighted average of this difference over all 2^(n-1) possible subsets, ensuring the contribution is evaluated in every possible context.

A fundamental Shapley axiom requiring that the sum of all feature attributions exactly equals the difference between the model's prediction and the baseline value. Mathematically:

Σ φ_i = f(x) - E[f(X)]

This guarantees completeness — no predictive value is lost or created in the explanation. For SHAP, this means the waterfall plot always reconciles perfectly from the expected model output to the final prediction.

A Shapley property stating that if a model changes so a feature's marginal contribution increases or stays the same in all coalitions, its Shapley value should not decrease. This ensures monotonicity of attributions with respect to model behavior.

• Practical Implication: If retraining a model makes a feature more important, its SHAP value must reflect this
• Violation Example: Some heuristic feature importance methods (like gain-based measures) can violate consistency
• SHAP Guarantee: All SHAP methods satisfy consistency by construction

The power set of all feature subsets forms the coalition structure over which Shapley values are computed. For n features, there are 2^n possible coalitions. Key considerations:

• Empty Coalition: Represents the baseline prediction with no feature information
• Grand Coalition: The full feature set producing the actual model output
• Sampling Strategy: KernelSHAP samples coalitions according to a Shapley kernel weight that prioritizes small and large coalitions
• Feature Ordering: The Shapley value averages over all n! possible orderings of features joining the coalition

A class of explanation models that express a prediction as a linear sum of individual feature contributions relative to a baseline. The form is:

g(z') = φ_0 + Σ φ_i z'_i

where z' is a binary vector indicating feature presence, φ_0 is the baseline, and φ_i are the attribution values. SHAP is the only additive feature attribution method that satisfies the Shapley axioms of local accuracy, missingness, and consistency simultaneously.