@inproceedings{32c60d73851f4f39a6341b819ef6f26d,

title = "Approximate nash equilibria of imitation games: Algorithms and complexity",

abstract = "A two-player finite game is represented by two payoff matrices (A, B), one for each player. Imitation games are a subclass of two-player games in which B is the identity matrix, implying that the second player gets a positive payoff only if she “imitates{"} the first. Given that the problem of computing a Nash equilibrium (NE) is known to be provably hard, even to approximate, we ask if it is any easier for imitation games. We show that much like the general case, for any c > 0, computing a n1c -approximate NE of imitation games remains PPAD-hard, where n is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find ε-approximate NE for any given constant ε > 0 (PTAS). The former result also rules out the smooth complexity being in P, unless PPAD ⊂ RP.",

keywords = "Imitation games, Nash equilibrium, PPAD-hardness, PTAS, Two-player games",

author = "Aniket Murhekar and Ruta Mehta",

note = "Funding Information: ∗The work was supported by NSF CAREER grant CCF 1750436.; 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 ; Conference date: 19-05-2020",

year = "2020",

language = "English (US)",

series = "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS",

publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

pages = "887--894",

editor = "Bo An and {El Fallah Seghrouchni}, Amal and Gita Sukthankar",

booktitle = "Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020",

}