A Bayesian Monte Carlo method for computing the Shapley value: Application to weighted voting and bin packing games. (January 2021)

• Record Type: Journal Article
• Authors: TOUATI, Sofiane; RADJEF, Mohammed Said; SAIS, Lakhdar
• Is Part Of: Computers & operations research. Volume 125(2021)
• Publication Date: 2021-01
• Subjects: Cooperative game -- Shapley value -- Approximation -- Bayesian inference -- Monte Carlo method -- Weighted voting game -- Bin packing game; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105094
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Shapley value approximation, with ensured property. New approach combining Monte-Carlo and Bayesian methods. Application for games with desired monotonous Shapley value. Application to the weighted voting and bin packing games. Abstract: The Shapley value is one of the most important solution concepts in cooperative game theory, it satisfies uniqueness and fairness properties while its main drawback lies in its high computational complexity. A number of approximation methods have been provided to overcome such intractability. Monte Carlo type methods are the most general and practical approaches approximating the Shapley value thanks to coalitions sampling. Their efficiency depends on the associated sampling and approximation steps. Most of the contributions focus on the sampling step that suffers from a loss of information and the difficulty to deliver a value satisfying certain expected properties such as efficiency and monotonicity. In this paper, we propose an improvement of the approximation step. It associates a Bayesian approach to that of Monte Carlo, to derive a Shapley value approximation, preserving certain expected properties essential for handling real-world applications. We develop our approach for a class of games with binary marginal contributions. We apply it for the calculation of the Shapley value for the weighted voting and bin packing games.