The Shapley value and its algorithmic approximation

This talk addresses how sampling-based approximation methods make the Shapley value usable in large-scale games.

I will explain why stratified sampling dramatically improves precision over naive Monte Carlo methods and how it is typically applied.

The main contribution is a new adaptive stratification paradigm that combines multiple stratifications and refines them based on observed samples.

I will conclude with an experimental study showing when and how these methods outperform existing approaches.