The Complexity of Computing a Nash Equilibrium 3: Trimming an Approximate Nash Equilibrium Yields a Well-Supported OneResearch Paper
The complexity of computing a Nash equilibrium is usually studied for an approximate equilibrium, because an exact equilibrium of a game with three or more players can require irrational probabilities. Two approximation notions are in use, and results proved for one do not automatically transfer to the other. Daskalakis, Goldberg and Papadimitriou (SIAM J.…