Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity

A two-player finite game is represented by two payoff matrices (𝐴, 𝐵), one for each player. Imitation games are a subclass of twoplayer games in which 𝐵 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 𝑐 > 0, computing a 1 𝑛 𝑐-approximate NE of imitation games remains PPADhard, where 𝑛 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.