Aspects of communication complexity for approximating Nash equilibria

Abstract

Since it was shown that finding a Nash equilibrium is PPAD-complete [Daskalakis2006], even for 2-player normal form games [Chen2006], a lot of attention has been given to approximate Nash equilibria. Almost all results on approximate Nash equilibria assume full knowledge of the game that is played. This thesis will focus on approximate Nash equilibria in an uncoupled setup, players only have knowledge of their own payoff matrix.

For an uncoupled setup a few lower bound results on the communication complexity are known [Conitzer2004] [Hart2010], but these results only apply to exact Nash equilibria.

In this thesis we will look in different ways at the communication complexity of approximate Nash equilibria in an uncoupled setup. First we will look at small games, where each player can play only a few different actions. For these small games we derive lower- and upper bounds on the approximation in settings with no- or very limited communication. Next we show upper bounds on the communication complexity for general games and lower bounds on the communication complexity for reaching good approximations.

In the next sections we bound the communication that is allowed. For models with no communication we prove that any $\epsilon$-approximate Nash equilbrium will have $\epsilon>0.5$ for any algorithm, in the worst case. Results on one-way communication indicate that finding an $\epsilon$-well-supported Nash equilibrium requires more information than finding an $\epsilon$-approximate Nash equilbrium. In the last section we show a 0.432-approximate Nash equilibrium and a 0.732-WSNE with limited communication allowed. Next to the limited communication these algorithms also have a polynomial running time, which makes them comparable to existing polynomial-time algorithms with no bound on the communication.