Approximating nash equilibria using small-support strategies

Abstract

Finding a Nash equilibrium of a game and in particular a bimatrix game is one of the most central problems in algorithmic game theory. Recently it was proved that it is not possible to solve this problem or give a fully polynomial time approximation scheme for it unless PPAD is in P [5, 2, 3]. I the light of the above results, the question of finding approximate equilibria emerges as an important open problem. Is there a polynomial time approximation scheme for computing an equilibria? What is the best achievable approximation? An α-approximate equilibria is a pair of mixed strategies (X, Y) with payoffs (x, y) such that if the best response to Y has payoff x ′ and the best response to X has payoff y ′ then x ≥ αx ′ and y ≥ αy ′. Like [4], one can adopt an additive notion for the approximation, but it will not affect our result here. Surprisingly, the best approximation algorithm known for this problem is a linear-time algorithm that finds a 1 2-approximate equilibria by examining all strategies with support of size at most 2 [4]. The support of a strategy is the set of pure strategies used to construct it. A natural question is whether it is possible to improve the factor 1 2 by searching over strategies with