Communication complexity of stochastic games

Krishnamurthy, N. ; Parthasarathy, T. ; Ravindran, G. (2009) Communication complexity of stochastic games International Conference on Game Theory for Networks, 2009 . pp. 411-417.

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...

Related URL: http://dx.doi.org/10.1109/GAMENETS.2009.5137427

Abstract

We derive upper and lower bounds on the communication complexity of determining the existence of pure strategy Nash equilibria for some classes of stochastic games. We prove that pure equilibria of single controller stochastic games and those of SER-SIT (separable reward-state independent transition) games correspond to those of bimatrix games that are constructed from these stochastic games. Hence we extend communication complexity upper bounds of bimatrix games to these stochastic games. For SER-SIT games, we prove an upper bound of O(n2) which is tight and which coincides with that for bimatrix games. Here n is the number of actions of each player in each state. Note that this bound is independent of the size of the actual payoffs. For single-controller games, we obtain an upper bound of min (O(n2|S|), O(|S| n2 log M)) where S is the set of states and M is the largest entry across all payoff matrices. Further, we reduce bimatrix games to stochastic games and hence, the lower bound extends from bimatrix games to stochastic games as well. We also establish the following results while proving upper bounds for SER-SIT games. To prove that pure equilibria of SER-SIT games correspond to those of auxiliary bimatrix games, we show that every SER-SIT game that has a pure equilibrium has a state-independent pure equilibrium too. We also show that we cannot relax the constraints of separable rewards or state independent transitions. We provide counter examples when the game is SER (but not SIT) and SIT (but not SER).

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:90951
Deposited On:15 May 2012 10:00
Last Modified:15 May 2012 10:00

Repository Staff Only: item control page