A Descent-based method on the Duality Gap for solving zero-sum games

Michail Fasoulakis, Evangelos Markakis, Giorgos Roussakis, Christodoulos Santorinaios · 2025

Read A Descent-based method on the Duality Gap for solving zero-sum games by Michail Fasoulakis, Evangelos Markakis, Giorgos Roussakis, Christodoulos Santorinaios (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19138.txt.

Introduction

Michail Fasoulakis and co-authors present an algorithm for finding balanced outcomes in two player zero sum games, in a paper from 2025. Such games, where one gain is the other loss, can be solved by standard tools, but simpler methods are in demand for machine learning use. Their method follows the downhill slope of a gap measure.

That gap, which tracks how far play is from balance, turns out to be a curved bowl shape for the bilinear case. Steepest descent on it shrinks the gap at a geometric rate until play is close to balanced. Tests matched or beat standard methods, even with thousands of strategies per player. The method also serves as a part in solvers for broader games.

Catalog record

CREATORMichail Fasoulakis, Evangelos Markakis, Giorgos Roussakis, Christodoulos Santorinaios
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-19138

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Descent-based method on the Duality Gap for solving zero-sum games Michail Fasoulakis, Evangelos Markakis, Giorgos Roussakis, Christodoulos Santorinaios Abstract We focus on the design of algorithms for finding equilibria in 2-player zero-sum games. Although it is well known that such problems can be solved by a single linear program, there has been a surge of interest in recent years for simpler algorithms, motivated in part by applications in machine learning. Our work proposes such a method, inspired by the observation that the duality gap (a standard metric for evaluating convergence in min-max optimization problems) is a convex function for bilinear zero-sum games. To this end, we analyze a descent-based approach, variants of which have also been used as a subroutine in a series of algorithms for approximating Nash equilibria in general non-zero-sum games. In particular, we study a steepest descent approach, by finding the direction that minimises the directional derivative of the duality gap function. Our main theoretical result is that the derived algorithms achieve a geometric decrease in the duality gap and improved complexity bounds until we reach an approximate equilibrium. Finally, we complement this with an experimental evaluation, which provides promising findings. Our algorithm is comparable with (and in some cases outperforms) some of the standard approaches for solving 0-sum games, such as OGDA (Optimistic Gradient Descent/Ascent), even with thousands of available strategies per player. 1 Introduction Our work focuses on the design of algorithms for finding Nash equilibria in 2-player bilinear zero-sum games. Zero-sum games have played a fundamental role both in game theory, being among the first classes of games formally studied, and in optimization, as it is easily seen that their equilibrium solutions correspond to solving a min-max optimization problem. Even further, solving zero-sum games is in fact equivalent to solving linear programs, as properly demonstrated in Adler [2013] . Despite the fact that a single linear program (and its dual) suffices to find a Nash equilibrium, there has been a surge of interest in recent years, for faster algorithms, motivated in part by applications in machine learning. One reason for this is that we may have very large games to solve, corresponding to LPs with thousands of variables and constraints. A second reason could be that e.g., in learning environments, the players may be using iterative algorithms that can only observe limited information, hence it would be impossible to run a single LP for the entire game. As an additional motivation, finding new algorithms for such a fundamental problem can provide insights that could be of further value and interest. The above considerations have led to a variety of approaches and algorithms, spanning already a few decades of research. Some of the earlier works on this domain have focused purely on an optimization viewpoint. In parallel to this, significant attention has been drawn to learning-oriented algorithms, such as first-order methods. The latter class of algorithms performs gradient descent or ascent on the utility functions of the two players, and some of the proposed variants have been very successful in practice, such as the optimistic gradient and the extra gradient methods Korpelevich [1976] , Popov [1980] . Several works have focused on theoretical guarantees for their performance, and a standard metric used in the analysis is the duality gap. This is simply the sum of the regrets of the two players in a given profile, and therefore the goal often amounts to proving appropriate rates of decrease for the duality gap over the iterations of an algorithm. Our work is motivated by the observation that the duality gap is a convex function for zero-sum games. This naturally gives rise to the suggestion that instead of performing gradient descent on the utility function of a player, which is not a convex function, we could apply a descent procedure directly on the duality gap. It is not straightforward that this can indeed be useful as it is not a priori clear that we can perform a descent step fast (i.e., finding the direction to move to). Nevertheless, it can form the basis for investigating new approaches for zero-sum games. 1.1 Our Contributions Motivated by the above discussion, we propose and analyze an optimization approach for finding approximate Nash equilibria in zero-sum games. Our algorithm is a descent-based method applied to the duality gap function, and is essentially an adaptation of a subroutine in the algorithms of Tsaknakis and Spirakis [2008] , Deligkas et al. [2017] , Deligkas et al. [2023] which are for general games, tailored to zero-sum games and with a different objective function. The method is applying a steepest descent approach, where we find in each step the direction that minimises the directional derivative of the duality gap function and move towards that. In Section 3 we provide the algorithm and our theoretical analysis. Our main result is that the derived algorithm achieves a geometric decrease in the duality gap until we reach an approximate equilibrium. This implies that the algorithm terminates after at most O\Big(\frac{1}{\rho}\cdot\log\Big(\frac{1}{\delta}\Big)\Big) iterations with a \delta -approximate equilibrium, where \rho is a parameter, related to the computation of the directional derivative. We exhibit that the method can also be further customized and show that a different variant also converges after O(\frac{1}{\sqrt{\delta}}) iterations. In Section 4 , we complement our theoretical analysis with an experimental evaluation. Even though the method does need to solve a linear program in each iteration to find the desirable direction, this turns out to be of much smaller size on average (in terms of the number of constraints) than solving the linear program of the entire game. We compare our method against standard LP solvers, but also against state-of-the-art procedures for zero-sum games, such as Optimistic Gradient Descent-Ascent (OGDA). Our findings are promising and reveal that the running time is comparable to (and often outperforms) OGDA, even with thousands of strategies per player. We therefore conclude that the overall approach deserves further exploration, as there are also potential ways of accelerating its running time, discussed in Section 4 . 1.2 Related Work As already mentioned, conceptually, the works most related to ours are Tsaknakis and Spirakis [2008] , Deligkas et al. [2017] , Deligkas et al. [2023] . Although these papers do not consider zero-sum games, they do utilize a descent-based part as a starting point. The main differences with our work is that first of all, their descent is performed with respect to the maximum regret among the two players, whereas we use the duality gap function. Furthermore the descent phase is only a subroutine of their algorithms, since it does not suffice to establish guarantees for general games. Hence their focus is less on the decent phase itself and more on utilizing further procedures to produce approximate equilibria. There is a plethora of algorithms for linear programming and zero-sum games, which is impossible to list here, but we comment on what we feel are most relevant. When focusing on optimization algorithms for zero-sum games, Hoda et al. [2010] use Nesterov’s first order smoothing techniques to achieve an \epsilon -equilibrium in O(1/\epsilon) iterations, with added benefits of simplicity and rather low computational cost per iteration. Following up on that work, Gilpin et al. [2012] propose

Read the complete text