On the Equilibria of Asynchronous Games
Sep 16, 2009
In this work, we explore the possibility that the hardness of computing Nash equilibria stems from their assumption of synchronous, simultaneous move play. We consider a model of asynchronous infinitely repeated games in which there is no mechanism enforcing that players make moves simultaniously: instead, a random player gets to take an action at each time step, with full knowledge of the past history of the game. This model is strategically equivalent to an alternating move game, and has several nice structural and computational properties as compared to the standard model of simultaneous move games. We show that: + All but a negligible fraction (smaller than any inverse polynomial) of matrix games admit equilibria in which both players play according to a pure stationary strategy: a unit memory strategy that depends only on the opponents last action. + There is a PTAS to compute pure epsilon-approximate equilibria in stationary strategies in any game that admits equilibria in pure stationary strategies. + There is an FPTAS to compute pure (non-stationary) equilibria in any alternating move game, even for n > 2 players. (No such FPTAS exists for simultanious move repeated games with n > 2 players unless P = PPAD.) We conjecture that the problem of computing exact stationary equilibria in alternating move games is in P, but leave the problem open. This is joint work with Nina Balcan, Adam Kalai, and Yishay Mansour.