  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, 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 Tsaknakis and Spirakis, and enrich the pool of
strategies from which we build the strategy profiles that we output in certain
bottleneck cases of the algorithm.
