On The Equilibria of Alternating Move Games
Aaron Roth, Maria Florina Balcan, Adam Kalai, Yishay Mansour
[PDF]
We consider a model of asynchronous infinitely repeated games in which
there is no mechanism enforcing that players make moves simultaneously:
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 opponent's 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 simultaneous 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.