|
9.30 a.m. PUBLIC VIVA-VOCE NOTIFICATION: Equilibria in Bimatrix Games and Stochastic Games: Theoretical and Computational Aspects Nagarajan Krishnamurthy Chennai Mathematical Institute. 04-05-11 Abstract We propose theoretical as well as algorithmic and complexity theoretic results of bimatrix games and stochastic games. Bimatrix Games: Determining a Nash equilibrium in a bimatrix game is PPAD-hard (Chen and Deng, 2006). Even when restricted to win-lose or {0,1}-payoff bimatrix games, the problem remains PPAD-hard (Abbott, Kane and Valiant, 2005). However, there do exist polynomial time tractable classes of win-lose bimatrix games - such as, very sparse games (Codenotti, Leoncini and Resta, 2006) and planar games (Addario-Berry, Olver and Vetta, 2007). We extend the latter result to: (1) $K_{3,3}$ minor-free games, (2) A subclass of $K_5$-minor free games, namely, $K_5$-minor free games where the triconnected components are planar or $V_8$, and (3) A class of games that contain both $K_{3,3}$ and $K_5$ as minors, namely, games whose triconnected components are $K_5$, $V_8$ or planar. We prove that for Classes (1) and (2), a Nash equilibrium can be computed in unambiguous logarithmic space UL and for Class (3), in nondeterministic logarithmic space NL. Stochastic Games: We propose the concept of dependency graphs of stochastic games and define new classes of 2-person and n-person stochastic games that possess the orderfield property. Further, we show that the orderfield property extends to some mixtures of classes of stochastic games and provide sufficient conditions for mixtures to possess the orderfield property. Schultz (1992) proposed a Linear Complementarity Problem (LCP) formulation for zero-sum discounted Switching Control stochastic games. The question of Lemke processibility of this LCP remained open. We provide counter examples that imply Schultz's LCP formulation is not always processible by Lemke's algorithm. We suggest alternative formulations, the underlying matrix in one of which is $R_0$. Furthermore, we propose Vertical LCP (VLCP) formulations of perfect information stochastic games. We also show that a subclass of switching control (n-person) polystochastic games can be solved via LCPs. Communication Complexity of Stochastic Games: Conitzer and Sandholm (2004) showed that, given a bimatrix game, the communication complexity of determining the existence of a pure strategy Nash equilibrium has an upper bound of $O(n^2)$ and a lower bound of $\Omega(n^2)$, where n is the number of pure strategies of each player. We extend these results to some classes of stochastic games. For SER-SIT (Separable Reward - State Independent Transition) games, we prove an upper bound of $O(n^2)$ which is tight. Here n is the number of actions of each player in each state. For one player control stochastic games, we obtain an upper bound of $min (O(n^2 |S|), O(|S| n^2 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.
|
