Confidence intervals for Shapley value in Markovian dynamic games

Avrachenkov, Konstantin; Cottatellucci, Laura; Maggi, Lorenzo
Research Report RR-12-264

We consider a dynamic multiagent system in which several states succeed each other, following aMarkov chain process. In each state, a different single stage game among the agents, or players, is played, and cooperation among subsets of players can arise in order to achieve a common goal. We assume that each coalition can ensure a certain value for itself. The Shapley value is a well known method to share the value of the grand coalition, formed

by all the players, among the players themselves. It reflects the effective incremental asset brought by each player to the community. Unfortunately, the exact computation of the Shapley value for each player requires an exponential complexity in the number of players. Moreover, we prove that an exponential number of queries is necessary for any deterministic algorithm even to approximate the Shapley value in a Markovian dynamic game with

polynomial accuracy. Motivated by these reasons, we propose three different methods to compute a confidence interval for the Shapley value in the Markovian game. Our approaches require a polynomial number of queries to achieve a polynomial accuracy. We compare our confidence intervals in terms of their tightness and we provide a straightforward sampling strategy to optimize the tightness of one of them.

Systèmes de Communication
Eurecom Ref:
© EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Research Report RR-12-264 and is available at :