Shapley Value

The total value generated by the grand coalition of all agents is fully distributed among them. No value is created or destroyed in the attribution process.

• The sum of all individual Shapley values equals the total cooperative payoff
• Ensures complete budget balance in credit assignment
• Mathematically: Σᵢ φᵢ(v) = v(N), where N is the set of all players
• In multi-agent RL, this means the sum of per-agent Q-value contributions equals the joint Q-value

Agents who contribute identically to every possible coalition receive identical payoffs. The Shapley value is blind to identity—only marginal contributions matter.

• If v(S ∪ {i}) = v(S ∪ {j}) for all coalitions S, then φᵢ = φⱼ
• Prevents arbitrary favoritism based on agent labeling
• In cooperative MARL, two agents with interchangeable roles receive equal credit
• Enforces that the attribution depends solely on function, not identity

An agent that contributes nothing to any coalition receives zero credit. This axiom ensures that attribution is earned, not granted by default.

• If v(S ∪ {i}) = v(S) for all S, then φᵢ = 0
• A 'free-rider' agent that never improves team performance gets nothing
• In practice, this penalizes redundant or inactive agents in a multi-agent system
• Provides a natural sparsity mechanism: irrelevant agents are zeroed out

The Shapley value of a combined game is the sum of the Shapley values of its constituent sub-games. This enables modular decomposition of complex reward functions.

• For two games v and w: φᵢ(v + w) = φᵢ(v) + φᵢ(w)
• Allows independent analysis of separate reward components
• In reward decomposition, each sub-reward's attribution can be computed independently and summed
• Critical for scaling Shapley-based explanations to multi-objective RL problems

All four axioms collectively force the Shapley value to be the weighted average of marginal contributions across all possible coalition formation orders.

• Formula: φᵢ(v) = Σ_{S⊆N{i}} [|S|! (|N|-|S|-1)! / |N|!] × [v(S∪{i}) - v(S)]
• The weight represents the probability of agent i joining coalition S in a random permutation
• This is the only attribution method satisfying all four axioms simultaneously
• In explainable RL, this provides the theoretical justification for Shapley Q-values and multi-agent credit assignment

The fundamental challenge of determining which individual agent's action contributed to a shared team reward. In cooperative multi-agent systems, a single scalar reward signal must be decomposed into per-agent feedback signals. Difference rewards compare the actual reward to a counterfactual where an agent's action is replaced with a default, while Shapley Q-values apply the Shapley formula to the joint action-value function, computing each agent's marginal contribution averaged over all possible agent coalitions.

The mathematical foundation from which Shapley Value originates. A coalitional game is defined by a characteristic function v(S) that assigns a payoff to any subset S of players. The Shapley Value is the unique solution concept satisfying four axioms:

• Efficiency: The sum of all players' values equals the grand coalition's payoff
• Symmetry: Identical contributions yield identical values
• Dummy: A player adding zero marginal value receives zero
• Additivity: Values combine across independent games

A computationally efficient alternative to Shapley Value for multi-agent credit assignment. The difference reward for agent i is computed as D_i = R(s, a) - R(s, a_i', a_{-i}), where the agent's action is replaced with a default action or marginalized out. Unlike Shapley, which averages over all 2^N coalitions, difference rewards require only one counterfactual evaluation per agent. The accuracy depends critically on choosing a representative default action that captures the agent's typical behavior.

A family of off-policy evaluation techniques that estimate how a new policy would perform using only historical data, without deployment. In the context of Shapley Value, counterfactual reasoning is essential: computing an agent's marginal contribution requires evaluating the team's performance in hypothetical scenarios where that agent was excluded. Importance sampling and doubly robust estimators correct for distribution shift between the logging policy and the counterfactual policy being evaluated.