Departmental Colloquium
Wei Zheng
University of Tennessee
Efficient Bayesian Estimation and Inference for Shapley Value via Experimental Design
Abstract: The Shapley value, a fundamental concept in cooperative game theory, provides a fair allocation of cooperative gains or costs among players. However, computing Shapley values for a game with $d$ players requires evaluating all $2^d$ coalitions, which is computationally infeasible for large $d$. This difficulty is exacerbated in modern applications such as artificial intelligence, data science, and genomics, where evaluating the value of even a single coalition can be costly. To enable fast approximation and probabilistic inference of the Shapley value, we propose the Bayesian framework, where the Gaussian process is adopted to infer unobserved coalition values. The posterior distribution of the coalition values are then transformed into that of the Shapley values, allowing both point estimation and uncertainty quantification. We derive theoretical results showing that the computational complexity of posterior evaluation can be reduced from exponential to polynomial order. To further improve efficiency, we integrate experimental design principles to select coalitions that minimize posterior variances. Compared with existing approaches, the proposed method offers three main advantages: (i) support for statistical inference, (ii) accurate estimation of Shapley values using as few as $d^2-d+1$ coalition evaluations, and (iii) robustness across a wide range of cooperative games. Simulation studies and case analyses demonstrate that the proposed approach achieves higher accuracy and efficiency than existing methods under comparable evaluation cost.
Friday April 10, 2026 at 3:00 PM in 636 SEO