Nash Equilibrium Seeking in $N$-Coalition Games via a Gradient-Free Method

Recently, great efforts have been devoted to the research of collaboration and competition among multiple rational decision-makers, of which distributed optimization and Nash equilibrium (NE) seeking in non-cooperative games are the two main lines. In particular, distributed optimization problem is concerned with a network of agents that cooperatively minimize a combination of their local cost functions, which has shown great interests in the applications of parameter estimation, source localization, resource allocation, multi-robot coordination, etc. Non-cooperative game, on the other hand, considers a group of players that are self-interest motivated to minimize their own individual cost function in response to other players’ actions, which has been widely applied in the fields of transportation network control, power network control, electricity markets, smart grids, etc.

This paper subsumes the research of both distributed optimization and NE seeking in non-cooperative games, by considering an $N$-coalition non-cooperative game. In this game, each coalition consists of a number of players. On the one hand, each coalition can be regarded as a virtual player that aims to minimize its cost function by adjusting its actions based on other coalition’s actions in a non-cooperative game. On the other hand, the coalition’s cost function is defined as the sum of the local cost functions associated to the players in the corresponding coalition, and minimization of such cost is realized by the collaboration among the corresponding players. Moreover, it is assumed that the players have no access to the explicit functional form but only the function value of their local costs. A discrete-time gradient-free NE seeking strategy is developed to drive the players’ actions to the NE.

Related Work. Recently, vast results on the design of NE seeking algorithms have been reported to solve matrix games, potential games, aggregate games, generalized games [4, 2, 26, 13], to list a few. For the $N$-coalition game problem, the formulation is related to the problem of two sub-networks zero-sum games (e.g., [3, 6]), where two adversarial networks have opposing objectives with regard to the optimization of a common cost function, being collaboratively minimized by the agents in the corresponding network. Then, the $N$-coalition game problem is essentially an extension of such problem with the number of subnetworks being $N$. To solve the problem, the work in [23] proposed a NE seeking strategy, where a dynamic average consensus protocol was adopted to estimate the averaged gradients of the coalitions’ cost functions, and a gradient play method was implemented to drive the states to the equilibrium. It was further improved in [24] to reduce the communication and computation costs by incorporating an interference graph which characterizes the interactions among the players in each coalition. The $N$-coalition game problem was also studied in [28], where the players are subject to both local set constraints and a coupled inequality constraint, and the associated cost functions are allowed to be non-smooth. A distributed algorithm with the use of projected operators, subgradient dynamics, and differential inclusions was proposed to find the generalized NE. Different from all these works, the authors in [25] proposed an extremum seeking-based approach without the knowledge on the explicit expressions of the players’ local cost functions, which is the most relevant to the problem considered in this paper. However, it should be noted that the methods proposed for $N$-coalition game problems in the existing literature are continuous-time approaches. This paper intends to devise a discrete-time gradient-free NE seeking strategy to drive the players’ actions to the NE.

The newly proposed gradient-free NE seeking strategy follows the idea of Gaussian smoothing to estimate the gradient of a function, which was firstly reported in [7] in convex optimization, and further studied in both distributed optimization [27, 8, 9, 10, 11] and non-cooperative games [12]. This type of methods, including payoff-based methods in [17, 18] and extremum seeking-based methods in [25], can be regarded as non-model based approaches, since the implementation of such algorithms does not require the model information. One advantage of the Gaussian smoothing compared with other non-model based methods is that it can deal with both smooth and non-smooth problem setups. Though this technique has been well studied in [7] and its extensions in [27, 8, 9, 10, 11] for optimization problems, the derived properties cannot be directly applied to non-cooperative game problems due to the couplings in the players’ actions. Moreover, the algorithm based on Gaussian smoothing technique can only drive the players’ actions to the NE of a smoothed game but not the original game. How close between the NEs of the smoothed and the original games has not been studied yet. With the Gaussian smoothing technique, the proposed strategy utilizes the estimated gradient information in a gradient tracking method to trace the gradient of the coalition’s cost function. The gradient tracking technique was widely adopted in distributed optimization to achieve a fast rate of convergence with a constant step-size, see [20, 21, 14, 22], but receives little attention in NE seeking. It should be highlighted that solving $N$-coalition game problems is not equivalent to solving $N$ independent distributed optimization problems among $N$ coalitions, since these $N$ distributed optimization problems are coupled with each other in terms of the players’ actions, and each coalition has only authority of its own action rather than the full authority of the entire decision variables in distributed optimization problems. The action of one coalition will have influence to the actions of other coalitions. Moreover, the cost functions in non-cooperative games are only convex with respect to the player’s own action, rather than the entire decision variable. Such partial convexity also brings in additional challenges in the convergence analysis of the gradient tracking method in non-cooperative games.

Contributions. The major contributions of this paper are threefold. 1). Different from the existing works on $N$-coalition game problems [23, 24, 28], the problem considered in this paper follows the settings in [25], where the players are assumed to have no access to the explicit functional form, but only the function value of their local cost functions. As the methods proposed for $N$-coalition game problems in all existing literature [23, 24, 28, 25] are continuous-time approaches, this paper is the first attempt to address $N$-coalition game problems with a discrete-time method, where a non-model based NE seeking strategy is proposed via a gradient-free method. 2). This paper adopts the Gaussian smoothing technique to estimate the partial gradient of the player’s local cost function, and a gradient tracking method is employed to trace the gradient of the coalition’s cost function. Since the Gaussian smoothing-based algorithms can only achieve convergence to the NE of a smoothed game but not the original game, we are the first to explicitly quantify the distance between the NEs of the smoothed and the original games as a function of the smoothing parameter. As compared to the existing gradient tracking methods, such as [20, 21, 14, 22], this work is the first attempt to adopt gradient tracking techniques in $N$-coalition games. 3). The convergence property of the proposed algorithm is carefully studied. Under the standard assumptions on the graph connectivity, local cost functions and game mappings, it is derived that the players’ actions driven by the proposed algorithm with a small constant step-size are able to converge to a small neighborhood of the NE at a geometric rate with the error being proportional to the step-size and the smoothing parameter.

Notations. We use $\mathbb{R}$, $\mathbb{R}_{\geq 0}$ and $\mathbb{R}^{p}$ to denote real numbers, non-negative real numbers, and $p$-dimensional column vectors, respectively. $\mathbf{1}_{p}$ ($\mathbf{0}_{p}$) represent a vector with all elements equal to $1$ ($0$), and $I_{p}$ denotes the $p\times p$ identity matrix. For a vector $u$, we use $\|u\|$ for its standard Euclidean norm, i.e., $\|u\|\triangleq\sqrt{\langle u,u\rangle}$ For a vector $a$ or a matrix $A$, we use $[a]_{i}$ to denote its $i$-th entry, and $[A]_{ij}$ to denote its element in the $i$-th row and $j$-th column. The transpose and spectral norm of a matrix $A$ are denoted by $A^{\top}$ and $\|A\|$, respectively. We use $\rho(A)$ to represent the spectral radius of a square matrix $A$. For a totally differentiable function $f(x,y)$, we use $\nabla f(x,y)$ for its total derivative, and $\nabla_{x}f(x,y)$ for its partial derivative with respect to $x$ for a fixed $y$.

In this section, we present the details of the NE seeking strategy.

At time-step $t$, the player $j\in\mathcal{V}^{i}$ in each coalition $i\in\mathcal{I}$ needs to maintain the following variables: the player’s own action variable $x^{i}_{j,t}$, auxiliary action variables $y^{i}_{jk,t}$, and gradient tracker variables $\phi^{i}_{jk,t}$ for $\forall k\in\mathcal{V}^{i}$. A gradient estimator $\pi^{i}_{jk}$ for $\forall k\in\mathcal{V}^{i}$ is also constructed to estimate the partial gradient based on the values of the local cost functions. The algorithm is initialized with arbitrary $x^{i}_{j,0},y^{i}_{jk,0}\in\mathbb{R}$ and $\phi^{i}_{jk,0}=\pi^{i}_{jk}(\mathbf{x}_{0})$. Then, each player $j\in\mathcal{V}^{i},i\in\mathcal{I}$ updates these variables according to the following update laws

where $\pi^{i}_{jk}(\mathbf{x}_{t})$ is the gradient estimator given by (2), and $\alpha>0$ is a constant step-size sequence. Thus, at time-step $t$, agent $j\in\mathcal{V}^{i}$ of coalition $i\in\mathcal{I}$ first update the auxiliary action variables $y^{i}_{jk,t}$, its decision variable $x^{i}_{j,t}$ and gradient tracker variables $\phi^{i}_{jk,t},k\in\mathcal{V}^{i}$ according to the update laws (8), and pass the updated auxiliary action variables $y^{i}_{jk,t}$ and gradient tracker variables $\phi^{i}_{jk,t}$, $k\in\mathcal{V}^{i}$ to its out-neighbors in the same coalition. Then the iteration continues. These procedures are tabulated in Algorithm 1.

To facilitate the convergence analysis, we first make some notations for easy presentation. Denote that $n_{s}\triangleq\sum_{i=1}^{N}n_{i}^{2}$ and $n_{c}\triangleq\sum_{i=1}^{N}n_{i}^{3}$. For $\forall k\in\mathcal{V}^{i},i\in\mathcal{I}$, define that $\mathbf{y}^{i}_{k,t}\triangleq[y^{i}_{1k,t},\ldots,y^{i}_{n_{i}k,t}]^{\top}\in\mathbb{R}^{n_{i}}$, $\bar{y}^{i}_{k,t}\triangleq\frac{1}{n_{i}}\mathbf{1}_{n_{i}}^{\top}\mathbf{y}^{i}_{k,t}\in\mathbb{R}$, $\bar{\mathbf{y}}^{i}_{t}\triangleq[\bar{y}^{i}_{1,t},\ldots,\bar{y}^{i}_{n_{i},t}]^{\top}\in\mathbb{R}^{n_{i}}$, $\bar{\mathbf{y}}_{t}\triangleq[\bar{\mathbf{y}}^{1\top}_{t},\ldots,\bar{\mathbf{y}}^{N\top}_{t}]^{\top}\in\mathbb{R}^{n}$, $\phi_{t}\triangleq[\phi^{1}_{11,t},\ldots,\phi^{N}_{n_{N}n_{N},t}]^{\top}\in\mathbb{R}^{n}$, $\phi^{i}_{k,t}\triangleq[\phi^{i}_{1k,t},\ldots,\phi^{i}_{n_{i}k,t}]^{\top}\in\mathbb{R}^{n_{i}}$, $\bar{\phi}^{i}_{k,t}\triangleq\frac{1}{n_{i}}\mathbf{1}_{n_{i}}^{\top}\phi^{i}_{k,t}\in\mathbb{R}$, $\bar{\bm{\phi}}^{i}_{t}\triangleq[\bar{\phi}^{i}_{1,t},\ldots,\bar{\phi}^{i}_{n_{i},t}]^{\top}\in\mathbb{R}^{n_{i}}$, $\bar{\bm{\phi}}_{t}\triangleq[\bar{\bm{\phi}}^{1\top}_{t},\ldots,\bar{\bm{\phi}}^{N\top}_{t}]^{\top}\in\mathbb{R}^{n}$, $\pi^{i}_{k}\triangleq[\pi^{i}_{1k},\ldots,\pi^{i}_{n_{i}k}]^{\top}\in\mathbb{R}^{n_{i}}$, $\bar{\pi}^{i}_{k}\triangleq\frac{1}{n_{i}}\mathbf{1}_{n_{i}}^{\top}\pi^{i}_{k}\in\mathbb{R}$, and $\nabla_{x^{i}_{k}}\mathbf{f}^{i}_{\mu}(\mathbf{x})\triangleq[\nabla_{x^{i}_{k}}f^{i}_{1,\mu}(\mathbf{x}),\ldots,\nabla_{x^{i}_{k}}f^{i}_{n_{i},\mu}(\mathbf{x})]^{\top}\in\mathbb{R}^{n_{i}}$. Then, the update laws (8a) and (8c) can be compactly written as

Multiplying $\frac{1}{n_{i}}\mathbf{1}_{n_{i}}^{\top}$ from the left on both sides of (9a) and augmenting the relation into a compact form, we obtain

Now, we are ready for the convergence analysis of the proposed algorithm, which consists of two parts: 1) in Sec. IV-A, we derive the inequality iterations of three major quantities: i) $\sum_{i=1}^{N}\sum_{k=1}^{n_{i}}\mathbb{E}[\|\mathbf{y}^{i}_{k,t}-\mathbf{1}_{n_{i}}\bar{y}^{i}_{k,t}\|^{2}]$, the total consensus error of the auxiliary variables, ii) $\mathbb{E}[\|\bar{\mathbf{y}}_{t}-\mathbf{x}^{*}_{\mu}\|^{2}]$, the gap between the stacked averaged auxiliary variable and the NE of game $\Gamma_{\mu}$, and iii) $\sum_{i=1}^{N}\sum_{k=1}^{n_{i}}\mathbb{E}[\|\phi^{i}_{k,t}-\mathbf{1}_{n_{i}}\bar{\phi}^{i}_{k,t}\|^{2}]$, the total gradient tracking error; 2) in Sec. IV-B, we establish a linear system of these three inequalities to analyze its convergence, and characterize the gap between the players’ actions and the NE of game $\Gamma_{\mu}$, $\mathbb{E}[\|\mathbf{x}_{t}-\mathbf{x}^{*}_{\mu}\|^{2}]$ in terms of the aforementioned quantities, and finally deduce the gap between the players’ actions and the NE of game $\Gamma$, $\mathbb{E}[\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}]$ with the obtained results in Lemma 2-(2).