Abstract

Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute $\varepsilon$-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis TS08, with an approximation guarantee of $(0.3393+\delta)$, remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a $(\frac{1}{3}+\delta)$-Nash equilibrium, for any constant $\delta>0$. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of TS08, and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.
This paper will appear at ESA 2022.

Arxiv Link: [2204.11525] A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games (arxiv.org)

Biography

Argyrios Deligkas is a Lecturer at Royal Holloway, University of London. Before this, he held postdoctoral positions at the Technion, Israel Institute of Technology and the University of Liverpool, where he got his PhD in 2016. His research interests span over Algorithms and Computational Complexity and he is mainly focused on computational issues of approximate Nash equilibria.

• Admission

Zoom Meeting ID: 846 7170 5376

Password: 368746