A Bayesian Monte Carlo method for computing the Shapley value: Application to weighted voting and bin packing games - Université d'Artois Accéder directement au contenu
Article Dans Une Revue Computers & Operations Research Année : 2021

A Bayesian Monte Carlo method for computing the Shapley value: Application to weighted voting and bin packing games

Résumé

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.
Fichier non déposé

Dates et versions

hal-03958271 , version 1 (26-01-2023)

Identifiants

  • HAL Id : hal-03958271 , version 1

Citer

Sofiane Touati, Mohammed Said Radjef, Lakhdar Saïs. A Bayesian Monte Carlo method for computing the Shapley value: Application to weighted voting and bin packing games. Computers & Operations Research, 2021, 125. ⟨hal-03958271⟩

Collections

UNIV-ARTOIS
14 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More