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 $\frac{1}{n^c}$-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 $\epsilon$-approximate NE for any given constant $\epsilon>0$ (PTAS). The former result also rules out the smooth complexity being in $\Ptime$, unless $\PPAD \subset \RP$. 


Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity

technical paper

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS 2020

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

Aniket Murhekar

1

1

SHORT BIO

Presentations

Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES