9.30 a.m. PUBLIC VIVAVOCE NOTIFICATION: Equilibria in Bimatrix Games and Stochastic Games: Theoretical and Computational Aspects Nagarajan Krishnamurthy Chennai Mathematical Institute. 040511 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 PPADhard (Chen and Deng, 2006). Even when restricted to winlose or {0,1}payoff bimatrix games, the problem remains PPADhard (Abbott, Kane and Valiant, 2005). However, there do exist polynomial time tractable classes of winlose bimatrix games  such as, very sparse games (Codenotti, Leoncini and Resta, 2006) and planar games (AddarioBerry, Olver and Vetta, 2007). We extend the latter result to: (1) $K_{3,3}$ minorfree 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 2person and nperson 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 zerosum 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 (nperson) 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 SERSIT (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.
