The Complexity of Infinitely Repeated Alternating Move Games

摘要: We consider infinite duration alternating move games. These games were previously studied by Roth, Balcan, Kalai and Mansour [10]. They presented an FPTAS for computing approximate equilibrium, conjectured that there is a polynomial algorithm finding exact equilibrium [9]. extend their study in two directions: (1) show even two-player zero-sum games, time equivalent to winning strategy (two-player) mean-payoff game on graphs. The existence of the latter long standing open question computer science. Our hardness result suggests are harder solve than simultaneous while work Roth et al., k ≥ 3, k-player easier analyze setting. (2) optimal equilibria (with respect social welfare metric) can be obtained pure strategies, we present approximated δ-optimal with metric. This extends previous presenting finds much more desirable equilibrium. also if graphs, then computes hence, graphs inter-reducible any 2.