On The Equilibria of Alternating Move Games

Aaron Roth, Maria Florina Balcan, Adam Kalai, Yishay Mansour

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:
We conjecture that the problem of computing exact stationary equilibria in alternating move games is in P, but leave the problem open.