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.