Confidence Intervals for the Shapley–Shubik Power Index in Markovian Games

Abstract : We consider simple Markovian games, in which several states succeed each other over time, following an exogenous discrete-time Markov chain. In each state, a different simple static game is played by the same set of players. We investigate the approximation of the Shapley–Shubik power index in simple Markovian games (SSM). We prove that an exponential number of queries on coalition values is necessary for any deterministic algorithm even to approximate SSM with polynomial accuracy. Motivated by this, we propose and study three randomized approaches to compute a confidence interval for SSM. They rest upon two different assumptions, static and dynamic, about the process through which the estimator agent learns the coalition values. Such approaches can also be utilized to compute confidence intervals for the Shapley value in any Markovian game. The proposed methods require a number of queries, which is polynomial in the number of players in order to achieve a polynomial accuracy.
Type de document :
Article dans une revue
Dynamic Games and Applications, Springer Verlag, 2014, 4 (1), pp.10-31. 〈http://link.springer.com/article/10.1007/s13235-013-0079-6〉. 〈10.1007/s13235-013-0079-6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01092383
Contributeur : Konstantin Avrachenkov <>
Soumis le : lundi 8 décembre 2014 - 16:04:49
Dernière modification le : samedi 27 janvier 2018 - 01:32:12

Identifiants

Collections

Citation

Konstantin Avrachenkov, Laura Cottatellucci, Lorenzo Maggi. Confidence Intervals for the Shapley–Shubik Power Index in Markovian Games. Dynamic Games and Applications, Springer Verlag, 2014, 4 (1), pp.10-31. 〈http://link.springer.com/article/10.1007/s13235-013-0079-6〉. 〈10.1007/s13235-013-0079-6〉. 〈hal-01092383〉

Partager

Métriques

Consultations de la notice

268