Computing approximate Nash equilibria

The problem of finding equilibria in non-cooperative games and understanding their properties is a central problem in modern game theory. After John Nash proved that every finite game has at least one equilibrium (so-called Nash equilibrium), the natural question arose whether we can compute one efficiently. After several years of extensive research, we now know that the problem of finding a Nash equilibrium is PPAD-complete even for two-player normal-form games, making the task of finding approximate Nash equilibria one of the central questions in the area of equilibrium computation. In this thesis our main goal is a new study of the complexity of various variants of the approximate Nash equilibrium. Specifically, we study algorithms for additive approximate Nash equilibria in bimatrix and multi-player games. Then, we study algorithms for relative approximate Nash equilibria in multi-player games. Furthermore, we study algorithms for optimal approximate Nash equilibria in bimatrix games and finally we study the communication complexity of additive approximate Nash equilibria in bimatrix games.