Paper Info
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 1 over nc -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.
Year
DOI
Venue
2020
10.5555/3398761.3398865
AAMAS '19: International Conference on Autonomous Agents and Multiagent Systems Auckland New Zealand May, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-7518-4
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Aniket Murhekar101.35
Ruta Mehta210423.11