Speaker

Vangelis Markakis, Athens University of Economics and Business

Title

Recent Progress on Approximating Nash Equilibria

Abstract

In this talk, we consider the problem of finding approximate Nash equilibria for bimatrix games.

We will first overview the two more standard notions of approximation in this context, namely $\epsilon$-approximate and $\epsilon$-well-supported equilibria.

Finding the best possible guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria.

The main part of the talk will present algorithms that make progress along this front for both approximation concepts.

For the first notion of $\epsilon$-approximate equilibria, we will discuss a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a $(1/3+\delta)$-Nash equilibrium, for any constant $\delta>0$.

For the stronger notion of well-supported equilibria, we present a different algorithm that improves the currently known approximation guarantee from 0.653 to 1/2.

Our approach is based on linear programming and in particular on exploiting suitably defined zero-sum games that arise from the payoff matrices of the two players.

Furthermore, our algorithm is more intuitive and conceptually much simpler compared to the previous literature. Finally, we will conclude with discussing some related research directions, such as the design of learning methods for reaching Nash equilibria.