Distributed Nash Equilibrium Seeking in Non-Monotone Games over the Simplex

Tatiana Tatarenko, S. Rasoul Etesami · 2025

Read Distributed Nash Equilibrium Seeking in Non-Monotone Games over the Simplex by Tatiana Tatarenko, S. Rasoul Etesami (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-2507-13244.txt.

Introduction

Tatiana Tatarenko and Rasoul Etesami (2025) study how players in a game can find a Nash equilibrium without a central coordinator. They focus on convex games played over the simplex, where each player's choices are weights that sum to one. Such games can be non-monotone, a setting where standard methods struggle. The authors soften each player's payoff with a Shannon entropy term. They then show how solutions of the softened game relate to equilibria of the original game.

That link turns the search into a multi-objective optimization problem. Studying its stationary points revealed structure the authors could exploit. From it they built two distributed heuristic algorithms. Each player updates from local information only, yet the group moves toward an approximate equilibrium. The work gives both a new description of near-equilibria in this game class and practical methods to compute them across a network.

Catalog record

CREATORTatiana Tatarenko, S. Rasoul Etesami
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-13244

Browse the full library · About the Tower of Babel

Full text

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

Distributed Nash Equilibrium Seeking in Non-Monotone Games over the Simplex Tatiana Tatarenko, S. Rasoul Etesami Abstract In this work, we present a novel characterization of approximate Nash equilibria in a class of convex games over the simplex. To achieve this, we regularize the utility functions using the Shannon entropy term, connect the solutions to the regularized game with the set of Nash equilibria, and formulate a multi-objective optimization problem to solve the regularized game. Based on the obtained properties of the stationary points in this optimization problem, we formulate two distributed heuristic algorithms to compute an approximate Nash equilibrium of the original game. Keywords –Approximate Nash equilibria, convex games, quantal response, entropy regularization, distributed optimization. I Introduction Game-theoretic optimization addresses a specific class of problems arising in multi-agent systems, where each agent, called a player, chooses its action from a local action set to maximize its local utility function. These utility functions are coupled through the decision variables (actions) of all players in the system. Applications of game-theoretic optimization can be found in areas such as electricity markets, communication networks, autonomous driving systems, and smart grids [ 1 , 2 , 3 ] . Solving a game-theoretic optimization problem involves finding a stable joint action, called a Nash equilibrium , from which no agent has any incentive to unilaterally deviate. In the case of convex games , Nash equilibria are equivalent to solutions of a specific variational inequality defined for the game’s pseudo-gradient over the joint action set [ 4 ] . Such variational inequalities can be efficiently solved under the assumption that the pseudo-gradient possesses monotonicity properties [ 5 , 6 ] , or when a Minty solution exists in the game [ 7 ] . In recent years, much work has been devoted to the development of distributed procedures that leverage only local agents’ information to achieve a solution in such games [ 8 , 9 , 10 , 11 ] . While monotone games or games with a Minty solution can be efficiently solved either centrally or in a distributed setting, solution approaches for non-monotone convex games are not well-studied. Moreover, it is known that the problem of approximating a mixed Nash equilibrium in a general two-player, non-zero sum normal form game is PPAD-hard (see [ 12 ] ) 1 1 1 PPAD-hard problems belong to the class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. For more details on this class, see [ 12 ] and the references therein. . The recent paper [ 13 ] studies the optimistic mirror descent algorithm and demonstrates that it either converges to a Nash equilibrium or that the average correlated distribution of play is a strong coarse correlated equilibrium . Some works have addressed a specific subclass of such games, namely Rank-1 games , where a Nash equilibrium can be solved using polynomial-time algorithms [ 14 ] . Despite the well-established impossibility results, current works continue to seek heuristics for circumventing computational obstacles in general convex games. In particular, the work [ 15 ] presents an optimization approach based on the specifically defined Nikaido-Isoda function to calculate stable states in unconstrained games. The paper [ 16 ] , in turn, formulates a non-convex stochastic optimization problem to approximate a Nash equilibrium in normal-form games. The main idea in [ 16 ] involves the regularization of locally convex utility functions using the Shannon entropy term, where the resulting regularized game possesses Nash equilibria. Moreover, each Nash equilibrium in the regularized game is an approximate solution to the original one and belongs to the interior of the joint action set. This condition implies a reformulation of the corresponding variational inequality as a nonlinear system of equations, which leads to the formulation of a non-convex optimization problem. I-A Contributions and Organization Inspired by the idea in [ 16 ] , we continue characterizing approximate Nash equilibria in a class of convex games over the simplex and formulate novel distributed heuristic algorithms to identify such points. Our contributions are summarized as follows: • We formulate a multi-objective optimization problem in the regularized game (see ( 20 )), where each player controls a number of objective functions, and provide a result characterizing approximate Nash equilibria ( \epsilon -NE) as points at which the gradients of the objectives are equal to zero (Lemmas 3 - 4 ); • We further analyze the set of common stationary points of the introduced multi-objective optimization problem and demonstrate that this set is equal to the set of \epsilon -NE in the game, given an appropriate choice of the regularization parameter (Lemma 5 ); • Based on the results above, we propose two heuristics aimed at approximating Nash equilibria in the game under consideration. The paper is organized as follows. Section II defines the problem of game-theoretic optimization in a class of convex games over the simplex, introduces the notion of an approximate Nash equilibrium ( \epsilon -NE), and presents important preliminary results on the regularized game obtained in the work [ 16 ] . Section III formulates a multi-objective optimization problem, whose solution set is equal to the set of approximate Nash equilibria, and analyzes the stationary points of the objective functions. Section IV leverages this analysis and presents two heuristic algorithms for computing an approximate Nash equilibrium. Section V presents some simulation results, whereas Section VI concludes the paper. I-B Notations The set \{1,\ldots,N\} is denoted by [N] . For any function f(x):K\to\mathbb{R} and a column vector x=(x_{1},\ldots,x_{N}) , where x_{i}\in\mathbb{R}^{n_{i}} , we define the partial derivative \nabla_{i}f(x)=\frac{\partial f(\mathbf{x})}{\partial x_{i}} as the derivative with respect to the x_{i} -th coordinate of the vector x=(x_{1},\ldots,x_{N})\in\mathbb{R}^{\sum_{i=1}^{N}n_{i}} . We use \mathrm{Proj}_{\Omega}(v) to denote the projection of a vector v\in\mathbb{R}^{d} onto a set \Omega\subseteq\mathbb{R}^{d} . We denote the dot product in \mathbb{R}^{n} by \langle\cdot,\cdot\rangle . II Optimization-based Reformulation for Concave Games over the Simplex We consider a noncooperative game denoted by \Gamma=\Gamma(N,\{\Delta_{i}\},\{f_{i}\}) , consisting of N players, each with their local action set \Delta_{i} and local utility function f_{i}:\Delta=\Delta_{1}\times\dots\times\Delta_{N}\to\mathbb{R} . We denote by x_{i}=(x_{i}^{1},\ldots,x_{i}^{n_{i}+1}) an action of player i chosen from \Delta_{i} . We let x=(x_{i},x_{-i}) denote an action profile from the joint action set, where x_{-i} represents the joint action of all players except player i . In this work, we focus on games where each action set \Delta_{i} and utility function f_{i} possess the following structure. Standing Assumption 1 . Each action set \Delta_{i} is the (n_{i}+1) -dimensional simplex defined as follows: \Delta_{i}=\Big\{x_{i}=(x_{i}^{1},\ldots,x_{i}^{n_{i}+1})\in\mathbb{R}_{+}^{n_{i}+1}:\ \sum_{j=1}^{n_{i}+1}x_{i}^{j}=1\Big\}. Each utility function f_{i}(x) , for i\in[N] , is a polynomial function of degree 2 and has the form f_{i}(x)=\sum_{k\neq i}x_{i}^{T}Q_{ik}x_{k}+\sum_{j=1}^{N}r_{j}^{T}x_{j}, where each Q_{ik} is an (n_{i}+1)\times(n_{k}+1) dimensional matrix with the (j,l) -entry being q_{ik}^{jl} , for j=1,\ldots,n_{i}+1 and l=1,\ldots,n_{k}+1 , and r_{i}=(r_{i}^{1},\ldots,r_{i}^{n_{i}})\in\mathbb{R}^{n_{i}} is a vector. Example . The following games satisfy Assumption 1 above: 1. Any game with two players and finite action sets in mixed strategies is an example of a game over the simplex that satisfies Assumption 1 . 2. Another example of a game over the simplex where Assumption 1 holds is stable matching games in mixed strategies with waiting list feedback , as presented in [ 17 ] (see equation (30) therein). Definition 1 . A joint

Read the complete text