Shapley Value

The Efficiency axiom states that the sum of all assigned Shapley values equals the total value generated by the grand coalition of all players. This ensures the entire surplus from cooperation is fully distributed, with no value created or destroyed.

• Mathematically: Σ φ_i(v) = v(N), where N is the set of all players.
• In FL Context: The total 'value' (e.g., global model accuracy improvement) is precisely allocated among the participating clients. This property is foundational for creating a closed economic system in contribution-based incentive mechanisms.

The Symmetry axiom states that if two players make identical marginal contributions to every possible coalition, they must receive the same Shapley value. Fairness is based solely on contribution, not on arbitrary labels or identities.

• Formal Definition: If v(S ∪ {i}) = v(S ∪ {j}) for all coalitions S not containing i or j, then φ_i(v) = φ_j(v).
• In FL Context: Two clients with statistically identical data distributions and local dataset sizes that provide the same utility to any subset of other clients will be valued equally, preventing bias from non-contributory factors.

The Dummy Player axiom states that a player who adds no marginal value to any coalition receives a Shapley value of zero. Value is assigned only for actual contribution.

• Formal Definition: If v(S ∪ {i}) = v(S) for all coalitions S, then φ_i(v) = 0.
• In FL Context: A client whose local data provides no improvement to any possible combination of other clients' models (e.g., its data is pure noise or already perfectly represented by others) is correctly assigned zero contribution. This property is critical for filtering out non-beneficial participants.

The Additivity axiom states that the Shapley value of a sum of games is the sum of the Shapley values from each individual game. This allows complex valuation problems to be decomposed.

• Mathematically: For any two characteristic functions v and w, φ_i(v + w) = φ_i(v) + φ_i(w).
• In FL Context: If the overall model utility (v) can be expressed as a sum of utilities from different tasks or data modalities (v1 + v2), a client's total contribution is the sum of its contributions to each sub-task. This supports multi-objective or multi-task federated learning scenarios.

While not one of the original four axioms, Marginalism is a fundamental consequence: a player's Shapley value depends only on its marginal contributions to various coalitions. The valuation is completely defined by the incremental value the player brings.

• Core Principle: φ_i(v) is a weighted average of i's marginal contributions, v(S ∪ {i}) - v(S), over all possible subsets S.
• In FL Context: A client's valuation is not based on its data in isolation but on how its data improves models trained on every possible combination of other clients' data. This captures complex, non-linear interactions in data utility.

The Uniqueness Theorem (Shapley, 1953) is the seminal result proving that the Shapley value is the only solution concept satisfying the four axioms of Efficiency, Symmetry, Dummy Player, and Additivity. This provides a rigorous, non-arbitrary foundation for contribution valuation.

• Significance: It guarantees there is no other fair distribution scheme that satisfies all four intuitive fairness principles. Any alternative method (e.g., simpler heuristics) must violate at least one axiom.
• In FL Context: For system architects designing incentive or client selection mechanisms, this theorem justifies the computational cost of Shapley value approximation, as it is the unique theoretically fair solution.

The overarching process of measuring the value each client's data and compute resources provide to the federated model. The Shapley value is a premier method for this valuation, offering a theoretically fair distribution of the total model utility gain among participants. Other valuation metrics include:

• Leave-One-Out Error: Measuring the performance drop when a client is excluded.
• Gradient Norm: Using the magnitude of a client's model update as a proxy for contribution.
• Data Quantity: Simple valuation based on the number of local training samples. Accurate valuation is critical for incentive mechanisms and fairness-aware selection.

A system design element, often economic or reputational, that encourages client devices to participate reliably in federated learning by compensating them for their resources. The Shapley value provides a principled basis for determining fair monetary or reputational rewards. Effective mechanisms must:

• Align Incentives: Reward clients proportional to their true contribution (e.g., via Shapley).
• Prevent Free-Riding: Discourage clients from submitting low-effort updates.
• Ensure Sustainability: Balance the cost of rewards with the value of the improved global model. These mechanisms are essential for long-term, large-scale federated learning deployments.

A client selection approach that incorporates fairness constraints to prevent systematic underrepresentation of devices or data distributions, thereby mitigating bias in the global model. Using Shapley values for selection can promote fairness by choosing clients with historically high marginal contributions. Key techniques include:

• Stratified Sampling: Ensuring selection from all demographic or data strata.
• Proportional Representation: Selecting clients in proportion to their population size.
• Bias Mitigation: Actively correcting for selection bias in the aggregated model. This is crucial for building equitable and robust models.

An online learning framework used to sequentially choose clients (arms) to maximize a reward, such as model improvement, while balancing exploration of new clients and exploitation of known high-performers. The Shapley value can inform the reward function. Common bandit algorithms adapted for federated learning include:

• Upper Confidence Bound (UCB): Selects clients with high estimated reward and high uncertainty.
• Thompson Sampling: Uses a probabilistic model to sample clients based on their probability of being optimal.
• Contextual Bandits: Incorporates client metadata (e.g., device type, data size) into the decision. This approach is ideal for environments with unknown and changing client utilities.

The process of assigning a numerical score to each potential participant based on a utility function that quantifies the expected benefit of their selection. The Shapley value is a theoretically sound utility function. A comprehensive utility function often combines multiple factors:

• Statistical Utility: Expected improvement in model accuracy (e.g., via Shapley, loss reduction).
• System Efficiency: Client's resource profile (compute speed, bandwidth, battery).
• Fairness Contribution: How the client's selection improves demographic representation. Frameworks like Oort explicitly optimize for joint statistical and system utility.

A small, weighted subset of client data (or synthetic proxy data) that approximates the overall federated data distribution. Coresets are used to guide client selection or as a proxy for efficient server-side model analysis. Relationship to Shapley value:

• Selection Proxy: A coreset can be used to efficiently estimate the Shapley value of clients without full retraining.
• Valuation Anchor: Clients whose local data is well-represented in the coreset may be deemed to have higher value.
• Synthetic Data: Coresets can be generated to represent client contributions in a privacy-preserving manner. This concept bridges efficient computation with contribution analysis.