Hélène Le Cadre
email: helene.lecadre@vito.be

Yuting Mou

Hanspeter Höschle

Parametrized Inexact-ADMM Based Coordination Games: A Normalized Nash Equilibrium Approach

Keywords: Game theory, Generalized Nash games, Normalized Nash equilibrium, Parametrized Inexact-ADMM, Coordination Game

Generalized Nash equilibrium problems are single-shot Nash equilibrium problems, whereby the decisions of all agents are coupled through a shared constraint. Such games are generally challenging to solve as they might give rise to a very large number of solutions. In this context, spanning many equilibria can be interesting to provide meaningful interpretations. In the literature, to compute equilibria, equilibrium problems are classically reformulated as optimization problems, potential games, relaxed and extended games. Applications of these reformulations to an economic dispatch problem under perfect and imperfect competition are provided. Unfortunately, these approaches only enable to describe a very limited part of the equilibrium set. To fill that gap, relying on normalized Nash equilibrium as solution concept, we provide a parametrized decomposition algorithm inspired by the Inexact-ADMM to span many more equilibrium points. Complexifying the setting, we consider an information structure in which the agents can withhold some local information from sensitive data, resulting in private coupling constraints. The convergence of the algorithm and deviations in the players' strategies at equilibrium are formally analyzed. In addition, the algorithm can be used to coordinate the agents on one specific equilibrium with desirable properties at the system level. The coordination game is formulated as a principal-agent problem, and a procedure is detailed to compute the equilibrium that minimizes a secondary cost function capturing systemlevel properties. Finally, the Inexact-ADMM is applied to a cellular resource allocation problem, exhibiting better convergence rate than vanilla ADMM, and to compute equilibria that achieve both system-level efficiency and maximum fairness.

Introduction

Context of the Problem

In several real-life problems, players share common resources and each player's feasible strategy space depends on the other players' actions. For example, in an electricity market, there are coupling constraints due to the underlying power flow equations. Similar constraints exist in a transportation or telecommunication networks and general deregulated economy problems [START_REF] Altman | Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach[END_REF][START_REF] Altman | Equilibrium, Games, and Pricing in Transportation and Telecommunication Networks[END_REF]. In this paper we focus on such class of noncooperative games, known as generalized Nash games or generalized Nash equilibrium problems (GNEP). In GNEP, the shared coupling constraint is internalized in the agents' optimization problems; therefore giving rise to possible asymmetric valuations of the associated dual variables [START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF][START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF]. The resulting market is then considered as being incomplete, and some financial instruments need to be put in place to hedge the risk resulting from asymmetric valuations and uncertainty [START_REF] Shilov | Risk-Averse Equilibrium Analysis and Computation[END_REF][START_REF] Ralph | Risk Trading and Endogenous Probabilities in Investment Equilibria[END_REF][START_REF] Ehrenmann | Risk Adjusted Discounted Cash Flows in Capacity Expansion Models[END_REF]. As the agent coordination to reach an equilibrium is not easy to enforce [START_REF] Wang | Learning Near-Pareto Optimal Conventions in Polynomial Time[END_REF], various refinements of the generalized Nash equilibrium (GNE) as solution concept have been introduced in the literature. Variational equilibria (VE) were introduced as a refinement of GNEs [START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF], leading to a form of selection, requiring that the coupling constraint dual variables are aligned among the players. All these refinement concepts lead to focus on subsets of the set of GNEs. For example, it is well known in the literature that the set of VEs is a subset of the set of GNEs [START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF][START_REF] Altman | Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach[END_REF][START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF]. Potential game formulation can be interpreted as another refinement of the GNE [START_REF] Monderer | Potential Games[END_REF]; also focusing on only a subset of the GNEs.

In most cases, GNE computation is not amenable to any closed-form expression. Relying on equilibrium solution concepts introduced earlier, existing algorithms for equilibrium computation focus on a specific GNE. In contrast, the approach we develop in this paper allows to span many more equilibrium points, and to select equilibria among the set of GNEs, with desirable system-level properties.

Related Work Review

When dealing with single-shot Nash equilibrium problems, a common practice is to reformulate Nash equilibrium problems as optimization problems, which can be solved via decomposition methods. We will check that such a reformulation is indeed straightforward for a specific class of noncooperative games in which the coupling constraint is externalized in an "insider" agent's optimization problem. Considering the coincidence of the KKTs, the Nash equilibrium problem (NEP) is proved to be equivalent to its optimization reformulation where the market players' optimization problems are all concatenated with the "insiders" agent's shared coupling constraint [START_REF] Höschle | An ADMM-Based Method for Computing Risk-Averse Equilibrium in Capacity Markets[END_REF][START_REF] Murphy | A Tutorial on Building Policy Models as Mixed -Complementarity Problems[END_REF][START_REF] Murphy | A Mathematical Programming Approach for Determining Oligopolistic Market Equilibrium[END_REF]. In case the reformulated optimization problem is too big to be solved in one piece, distributed optimization methods can be used to compute equilibria of the Nash game. A comprehensive review of distributed optimization methods for large-scale optimization problems is provided in [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF]. In fact, the majority of (partial) equilibrium models under imperfect competition can be cast as optimization problems, by adding appropriate terms accounting for the players' market power exertion to the social welfare function [START_REF] Egging-Bratseth | Solving Oligopolistic Equilibrium Problems with Convex Optimization[END_REF]. These added terms are calibrated by designing an optimization problem that has the same KKT conditions as the imperfect equilibrium problem. Practically, this means that for problems sharing similar structure, KKT conditions would not need to be derived anymore; only the equivalent reformulated optimization problem would need to be implemented and can be solved using off-the-shelf solvers. This reformulation relies on a broad result in noncooperative game theory which states that every NEP can be reformulated as an optimization problem if and only if the NEP has a potential game structure [START_REF] Scutari | Convex Optimization, Game Theory, and Variational Inequality Theory[END_REF].

GNE computation has attracted a great interest amongst economists, game theoreticians, and automatic control practitioners. In general, GNEP formulations do not admit closed-form solutions and many algorithms have been proposed to compute solutions numerically. As a first approach, (generalized) potential game reformulation of GNEP can be solved using best-response algorithms. Unfortunately, convergence of best-response algorithms is hard to prove, even for well-behaved problems [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF]. Another approach relies on the exploitation of the reformulation of the GNEP as a (generalized) potential game that can be interpreted as an optimization problem, thus allowing to apply standard optimization algorithms like the interior-point method, bundle methods or subgradient projections, etc. To reformulate a GNEP as an optimization problem, it is also quite classical to use Nikaido-Isoda functions. The resulting optimization problem is then minimized by means of gradient-descent algorithms or relaxation-based algorithms [START_REF] Yu | Distributed Learning for Stochastic Generalized Nash Equilibrium Problems[END_REF]. However, the convergence of these algorithms to equilibrium is hard to assess and they generally share high computational complexity [START_REF] Yu | Distributed Learning for Stochastic Generalized Nash Equilibrium Problems[END_REF]. Weighted potential game reformulation is also rather classical. In [START_REF] Suzuki | Market Equilibrium as a Constrained Optimal Solution[END_REF], the reformulated problem can be interpreted as a weighted social welfare maximization problem in which the agents coordinate (up to a certain weight scaling) to reach a social welfare optimum. Each weight profile corresponds to a distinctive optimum. Hence, computing an equilibrium becomes equivalent to determining the appropriate weight profile. Fictitious play process can also apply and is proved to converge to an equilibrium for ordinal potential finite games [START_REF] Monderer | Potential Games[END_REF]. Recently, an active stream of research in engineering and automatic control concentrates on the applications of power decomposition methods from the optimization literature to compute GNEs. Yin et al. in [START_REF] Yin | Nash Equilibrium Problems with Scaled Congestion Costs and Shared Constraints[END_REF] consider VE in monotone games and propose a primal-dual distributed algorithm. Similarly, Paccagnan et al. address decentralized computation of VEs for aggregative games with quadratic utility functions [START_REF] Belgioioso | Distributed Generalized Nash Equilibrium Seeking in Aggregative Games on Time-Varying Networks[END_REF][START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF]. In [START_REF] Salehisadaghiani | Distributed Nash Equilibrium Seeking: A Gossip-Based Algorithm[END_REF], a distributed primal-dual algorithm for learning GNEs is proposed for networked games. An extension to the case where the players do not know their utility function is proposed in [START_REF] Zhu | Distributed Robust Adaptive Equilibrium Computation for Generalized Convex Games[END_REF]. The implementation of these algorithms requires that each player exchanges some information with her neighbors through a communication graph, while the information exchanges are coordinated through a communication protocol. Tatarenko and Karmgarpour [START_REF] Tatarenko | Learning Generalized Nash equilibria in a class of convex games[END_REF] bypass the need for coordination or information exchange during each step of the algorithm. They develop a payoff-based approach for computing GNEs in a class of convex games with jointly convex coupling constraints, and prove its almost sure convergence to VE under the existence of a strictly convex potential function. All these approaches have in common that they focus on the development of distributed approaches to compute one VE and require strong assumptions on the structure of the GNEP such as strong monotonicity, the existence of a strictly convex potential, etc., to guarantee the convergence of the algorithms.

NEP GNEP

GNE set spanning

Figure 1: Within single-shot Nash equilibrium problems, the set of Nash equilibrium problems (NEP) is contained in the set of generalized Nash equilibrium problems with only private coupling constraints (GNEP0), which is itself contained in the set of generalized Nash equilibrium problems with private and global coupling constraints (GNEP), i.e., NEP ⊂ GNEP0 ⊂ GNEP holds [START_REF] Dorsch | On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization[END_REF]. Existing methods relying on centralized algorithms enable to describe only a very limited part of the generalized Nash equilibrium (GNE) set, in a limited time. This leads us to consider distributed algorithms. However, best response, (asymmetric) gradient projection, distributed payoff-based learning require strong conditions to converge and can only reach a specific GNE. In this paper, we propose a parametrized distributed augmented Lagrangian algorithm inspired by the Inexact-ADMM to span many more equilibrium points, and to select equilibria among the set of GNEs, with desirable system-level properties.

Yet more complex, spanning the full set of GNEs is considered as a challenge from a computational point of view [START_REF] Facchinei | Distributed Algorithms for the Solution of (Generalized) Nash Equilibrium Problems[END_REF][START_REF] Tatarenko | Learning Generalized Nash equilibria in a class of convex games[END_REF]. Equilibrium selection relying on criteria such as stability, efficiency, system-fairness [START_REF] Kameda | Nash Equilibrium Based Fairness[END_REF], etc., is another challenging topic. Nabetani et al. suggest two parametrized variational inequality (VI) approaches respectively called price-directed and resource directed, to capture all the GNEs [START_REF] Nabetani | Parametrized Variational Inequality Approaches to Generalized Nash Equilibrium Problems with Shared Constraints[END_REF][START_REF] Oggioni | A Generalized Nash Equilibrium Model of Market Coupling in the European Power System[END_REF]. However, these approaches are computationally intensive and, depending on the structure of the game, enable the spanning of a very limited part of the set of equilibria [START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF].

Contributions

To overcome the computational limitations of the parametrized variational simulation approaches [START_REF] Nabetani | Parametrized Variational Inequality Approaches to Generalized Nash Equilibrium Problems with Shared Constraints[END_REF], we propose in this paper a parametrized version of Inexact-ADMM (I-ADMM) relying on the normalized Nash equilibrium (NNE) as solution concept, to span the set of GNEs. Furthermore, the tuning of the algorithm scaling factors that characterize the players' sensitivity to the coupling constraint, enables the coordination of the agents on equilibria that satisfy certain desirable criteria that can be captured through the minimization of a secondary (system-level) cost function [START_REF] Altman | Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach[END_REF]. We prefer parametrized I-ADMM over vanilla ADMM, because of its better convergence rate in convex settings [START_REF] Hager | Convergence Rates for an Inexact-ADMM Applied to Separable Convex Optimization[END_REF]. Complexifying the setting, we assume that the players can withhold some local information from sensitive data, resulting in private coupling constraints. We establish the global convergence of the parametrized I-ADMM, and quantify the deviation in the players' strategies at equilibrium caused by this information structure 2 . Our contribution to the literature on equilibrium problems is summarized in Figure 1. More details on the different reformulations and algorithms used to compute GNEs will be given in Section 3.

In this paper, we provide a detailed review of reformulations and algorithms to solve GNEP, that is enriched with applications to an economic power dispatch problem under perfect and imperfect competition, and to a cellular resource allocation game. On the methodological side, our contribution is three-fold:

(1) To the extent of our knowledge of the literature, this paper is one of the first paper going beyond the study of VE (a special subset of GNEs), and explicitly addressing the multiplicity of equilibria.

(2) We provide an algorithm to span the set of equilibria of GNEPs with private and global coupling constraints. We prove the convergence of the algorithm under mild assumptions. In addition, the impact of the information structure in which the players can withhold some local information from sensitive data, on the players' strategies at equilibrium, is quantified.

(3) The algorithm gives the possibility of coordinating the agents to converge to one specific equilibrium which minimizes a secondary cost function, capturing desirable properties at the system level. The coordination game is formulated as a principal-agent problem, and a procedure is detailed to compute the GNE that additionally minimizes a secondary (system level) cost function.

Organization of the Paper

The remainder of the paper is organized as follows. The generic GNEP is formulated in Section 2. Classical solution concepts interpreted as refinements of GNE are recalled. They will serve as guiding line of our work. In Section 3, we detail classical reformulation methods that are used to solve Nash equilibrium problems. Sequentially, we focus on NEP reformulation as an optimization problem, then, when coupling constraints are introduced in the players' feasibility sets, a classical approach is to try to reformulate the GNEP as a generalized potential game. Finally, other reformulations relying on relaxed formulations of the game or extended game formulations can be used. Section 3 is enriched with two illustrative problems (Problems 1, 2) dealing with economic power dispatch under perfect and imperfect competition. Focusing on a relaxed formulation of the GNEP, Section 4 introduces the parametrized I-ADMM. Convergence is established under mild assumptions. Assuming that the players can withhold some local information from sensitive data, the deviation in the players' strategies at equilibrium is upper bounded. An illustration is provided for a cellular resource allocation problem under competition, that can be interpreted as a coordination game, in Problem 3. In Section 5, we explain how the tuning of the scaling factors by a principal can be interpreted as an incentive design problem, which enables to determine the GNE that additionally minimizes a secondary (system-level) cost function. We conclude in Section 6.

Problem Statement

We formulate the generic problem in a deterministic setting. Let N be a set of N agents. For each n ∈ N , let X n := {x n ∈ R mn |Φ n (x n ) ≤ 0} for some continuously differentiable function Φ n : R mn → R, ∀n ∈ N , represents agent n's strategy set, with m = n∈N m n , x n ∈ X n be her strategy, and Π n : R m → R be her objective function. We use the following notation: by x we denote the tuple (x 1 , x 2 , ..., x N ), x -n denotes the tuple (x 1 , ..., x n-1 , x n+1 , ..., x N ) which contains the actions of all the agents except n. Each agent's optimization problem incorporates local constraints (Φ n (x n ) ≤ 0, ∀n ∈ N ) that depend only on her own strategy. The local constraints set X n are non-empty, compact, convex. In addition, the N optimization problems are coupled through a coupling constraint (1b), which can take one of the two forms described below:

(a) The coupling constraints are defined through private coupling constraints K n (x n , x -n ) ≤ 0, ∀n ∈ N , which depend on the actions of agent n and of the other agents, while the expression of K n remains private to agent n. This case requires the introduction of a private coupling constraint set C n ⊆ R m , ∀n ∈ N , which is assumed to be non-empty.

(b) The coupling constraint set mixes private coupling constraints and a global coupling constraint K(x n , x -n ) ≤ 0, which is shared among the agents. Formally, this leads to the requirement that

x ∈ C := {x ∈ R m |K n (x n , x -n ) ≤ 0, ∀n ∈ N , K(x n , x -n ) ≤ 0} ⊆ R m
while the coupling constraint set C is assumed to be non-empty.

Case (b) is the most general [START_REF] Nabetani | Parametrized Variational Inequality Approaches to Generalized Nash Equilibrium Problems with Shared Constraints[END_REF]. It can arise in some settings in which the agents do not want to share local information from sensitive data. This information structure gives rise to private coupling functions (K n ) n∈N [START_REF] Rasouli | An Efficient Market Design for Electricity Networks with Strategic Users Possessing Local Information[END_REF][START_REF] Salehisadaghiani | Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers[END_REF], while the agents' objective functions and feasibility sets depend on the other agents' actions. Both Cases (a) and (b) will be illustrated in our problem descriptions.

The generic problem statement is presented in Section 2 in the framework of Case (a) when K n = K, ∀n ∈ N , or equivalently in Case (b) when no private coupling constraints hold, because it leads to a natural economic interpretation of the Lagrangian dual variable associated with the global coupling constraint. Considering an information structure in which the players can withhold some local information from sensitive data in Section 4 requires us to replace the global coupling constraint with private coupling constraints. Parametrized I-ADMM introduced in Section 4 can be used to compute equilibria that arise under this information structure.

The set of GNEPs involving only private coupling constraints (Case (a)) is denoted GNEP 0 . We define GNEP as the set of GNEPs that involve a mix of private and global coupling constraints (Case (b)). As depicted in Figure 1, we have the following inclusions: NEP ⊂ GNEP 0 ⊂ GNEP [START_REF] Dorsch | On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization[END_REF]. Indeed, NEP consists of those problems from GNEP, where the constraint functions of different players' optimization problems only depend on the player's own decision variables, i.e., the choice of the other players has no influence on the single player's feasibility set. Thus, the coupling in NEP is only due to the dependence of the players' objective functions on the other players' decision variables. The class GNEP 0 is the subclass of GNEP, where only local and private coupling constraints occur in the definition of the players' feasibility sets.

We now introduce the generic game that will be considered throughout this paper. Note that two versions of the noncooperative game will be introduced: (1) below assumes no private coupling constraints; whereas [START_REF] Hager | Convergence Rates for an Inexact-ADMM Applied to Separable Convex Optimization[END_REF], that will be introduced in Section 4, assumes that the agents own some local information they might not want to share, that impacts the coupling constraint definition hence giving rise to a GNEP with private coupling constraints. Formally, each agent n ∈ N solves the following optimization problem, parametrized in the decision variables of all the other agents in N :

A n (x -n ) max xn∈Xn Π n (x n , x -n ), (1a)
s.t. K x n , x -n ≤ 0. λ n (1b)
We introduce the feasibility set of strategies for player n, FS n (x -n ) := {x n ∈ X n |(x n , x -n ) ∈ C} and FS := n FS n (x -n ) as the joint feasibility set. For simplicity, we made the assumption that C ⊆ X := n X n . It might be worth observing that the set FS defined as the product of FS n is not necessary equal to the original constraint set C. The resulting game G is a generalized Nash game (equilibrium problem) with shared coupling constraints (GNEP) [START_REF] Harker | Generalized Nash Games and Quasi-Variational Inequalities[END_REF][START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF][START_REF] Scutari | Convex Optimization, Game Theory, and Variational Inequality Theory[END_REF].

From NEP to GNEP

A commonly adopted equilibrium notion that generalizes Nash equilibrium in the presence of coupling constraints is the notion of generalized Nash equilibrium (GNE) [START_REF] Harker | Generalized Nash Games and Quasi-Variational Inequalities[END_REF]. We formally introduce its definition below.

Let SOL(P ) refers to the solution set of an optimization problem P .

Definition 1 (Generalized Nash equilibrium (GNE)). [START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF][START_REF] Harker | Generalized Nash Games and Quasi-Variational Inequalities[END_REF] A strategy tuple

x = (x 1 , x 2 , ..., x N ) is a generalized Nash equilibrium (GNE) of G if x n ∈ SOL A n (x -n ) , ∀n ∈ N .
Equivalently, a GNE is a vector x such that x n solves the system KKT n for each n.

We now introduce another solution concept: the variational equilibrium (VE), which is a specific kind of GNE [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF].

The notation VI(FS, F ) denotes a variational inequality with mapping F and a set FS ⊆ R m , where F : R m → R m is the function obtained by stacking together the gradients of the utility function of each player, with respect to her own strategy; it is given by F

(x) := ∇ xn Π n (x) n , ∀x ∈ R m .
Definition 2 (Variational equilibrium (VE)). [START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF][START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF] A strategy tuple x is said to be a variational equilibrium (VE) of G if x is a solution of VI(FS, F ), i.e., x n solves the maximization problem A n (x -n ). Equivalently, x n solves the system KKT n for each n and, in addition, such that the Lagrangian multipliers associated with the coupling constraint (1b) are equal, i.e.:

λ n = λ n , ∀n, n ∈ N , n = n .
The term "variational" refers to the variational inequality problem associated with such an equilibrium. Indeed, if we define the set of admissible solutions as FS, then x ∈ FS is a variational equilibrium if and only if it is a solution of [START_REF] Harker | Generalized Nash Games and Quasi-Variational Inequalities[END_REF]:

∇ xn Π n ( x), x -x ≤ 0, ∀x ∈ FS, ∀n ∈ N . (2)
The set of solutions of VI(FS, F ) will be denoted SOL(FS, F ).

Rosen considers another solution concept, where the dual variables of the shared constraints are equal among all agents up to a constant endogenously given factor r n that depends on agents [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF]. Rosen [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF] was the first to highlight the possibility of redundancy of multipliers when the constraint was shared -he termed the shared multiplier GNE as a normalized equilibrium. The fact that the GNE with shared multipliers was actually a solution of a related VI was a new insight in the context of such games [START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF].

Definition 3 (Normalized Nash equilibrium (NNE)). [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF] A strategy tuple x is a normalized Nash equilibrium (NNE) if every block x n solves the maximization problem A n (x -n ) and the dual variables associated with the coupling constraint (1b) are linked according to the following relations λ n = λ rn , ∀n ∈ N . The scaling factors (r n ) n enable interpretations of the GNEs. Indeed, they can be used to coordinate the agents on an equilibrium that checks some specific desirable properties like market based efficiency (by guaranteeing the maximization of the social welfare function), stability, systemfairness, etc. [START_REF] Altman | Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach[END_REF][START_REF] Altman | Equilibrium, Games, and Pricing in Transportation and Telecommunication Networks[END_REF].

Remark 2.1. A class of "restricted GNE" that can be considered as an extension of the NNE has been introduced in [START_REF] Fukushima | Restricted Generalized Nash Equilibria and Controlled Penalty Method[END_REF] and a controlled penalty method is detailed to compute a restricted GNE. Unfortunately, such an approach does not enable to automatically go through all the solutions.

The following assumption will be used in the remainder of the paper.

Assumption 1. The utility functions Π n (x n , x -n ) are concave in x n for all feasible x -n . The local constraint sets X n are non-empty, compact, convex. The global constraint set C is non-empty.

The next proposition presents the connection between the set of GNEs and the set of VEs solutions of G. Proposition 1. [START_REF] Kulkarni | On the Variational Equilibrium as a Refinement of the Generalized Nash Equilibrium[END_REF], Th.7 Under Assumption 1, every variational equilibrium belongs to the set of generalized Nash equilibria solutions of G.

Proposition 1 guarantees that the set of VEs, SOL(FS, F ), is a subset of the set of GNE solutions of the noncooperative game G, e.g., x * ∈ SOL(FS, F ) ⇒ x * n ∈ SOL A n (x * -n ) , ∀n ∈ N . Depending on the context, the set of GNEs can be far larger than the set of VEs. Furthermore, each GNE can be characterized by considering the scaling factor r introduced in Definition 3 for NNE. We recall this classical result in the proposition below.

Proposition 2 (Link between normalized and generalized Nash equilibrium). [START_REF] Nabetani | Parametrized Variational Inequality Approaches to Generalized Nash Equilibrium Problems with Shared Constraints[END_REF] Each r gives rise to a generalized Nash equilibrium.

Proposition 3 (Existence of normalized Nash equilibrium). [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF], Th. 3 Under Assumption 1, there exists a normalized Nash equilibrium solution of the noncooperative game G for every r ∈ R N + . Following Propositions 1, 2, 3 it is easy to see that the set of VEs is included in the set of GNEs. Furthermore, VEs are GNEs with scaling factors r = 1. NNE solution concept enables GNE characterization in terms of scaling factors r. The link between the different solution concepts (VE, NNE, and GNE) is depicted in Figure 2.

Remark 2.2. [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF], Th. [START_REF] Belgiosio | A Distributed Proximal-Point Algorithm for Nash Equilibrium Seeking in Generalized Potential Games with Linearly Coupled Cost Functions[END_REF] The uniqueness of the normalized Nash equilibrium for given scaling factors r is proved under diagonally strict concavity of the weighted social welfare n∈N r n Π n (x n , x -n ). Link between the different solution concepts of equilibrium that will be used to parametrize our algorithm. Variational equilibrium set is included into generalized Nash equilibrium (GNE) set. Normalized Nash equilibrium solution concept can be used to characterize through the r scaling factor vector, equilibria in the GNE set. Each r ∈ R m + gives rise to a GNE.

Economic Interpretation of the Lagrangian Dual Variable

In this section, we formulate the GNEP (1a)-(1b) as a mathematical program with complementarity constraints (MPCC). We recall that agent n's local constrains are incorporated in the set

X n := {x n ∈ R mn |Φ n (x n ) ≤ 0)
, and define µ n ≥ 0 as the associated dual variable.

The MPCC formulation can provide an interesting interpretation of the GNEP in terms of pricing. It gave rise to important applications in transportation science, telecommunication [START_REF] Altman | Equilibrium, Games, and Pricing in Transportation and Telecommunication Networks[END_REF], and energy markets [START_REF] Ruiz | A Tutorial Review of Complementarity Models for Decision-Making in Energy Markets[END_REF]. To that purpose, we write down the Lagrangian function associated with the parametrized optimization problem A n (x -n ):

L n (x, λ n ) = -Π n (x n , x -n ) + λ n K(x n , x -n ) + µ n Φ n (x n ). ( 3
)
To determine solutions for the noncooperative game, we compute KKT n conditions associated with Lagrangian function [START_REF] Anand | Information and Organization for Horizontal Mutlimarket Coordination[END_REF]. Taking the derivatives of the Lagrangian function L n with respect to x n for all n ∈ N , the first order stationarity conditions write down as follows (provided

∇ xn K(x) = 0): ∇ xn L n (x, λ n ) = 0 ⇔λ n = ∇ xn Π n (x n , x -n ) -µ n ∇ xn Φ n (x n ) ∇ xn K(x n , x -n ) , ∀n ∈ N . (4)
The complementarity constraint takes the following form:

0 ≤ λ n ⊥ -K(x n , x -n ) ≥ 0 ⇔ λ n K(x n , x -n ) = 0, λ n ≥ 0, ∀n ∈ N , (5a) 0 ≤ µ n ⊥ -Φ n (x n ) ≥ 0 ⇔ µ n Φ n (x n ) = 0, µ n ≥ 0, ∀n ∈ N . (5b)
In the pricing literature, the Lagrange multipliers associated with the shared coupling constraint can be interpreted as shadow prices for the use of the shared resource: if a price is set on agent n such that when other players are at equilibrium, the agent pays K(x n , x -n )λ n (x -n ), then x is an equilibrium in the game with coupling constraint G [START_REF] Bazaraa | Nonlinear Programming: Theory and Algorithms[END_REF]. Yet this pricing is not scalable since for the same use of the resources the price may vary from agent to agent and it further depends on the chosen equilibrium [START_REF] Altman | Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach[END_REF][START_REF] Altman | Equilibrium, Games, and Pricing in Transportation and Telecommunication Networks[END_REF]. For billing purposes one would prefer λ n not to depend on x nor on n in case discrimination between the agents is not allowed, but to be a constant.

Example 1 (Two node toy network). In Figure 3, we consider a two node toy network, with a finite capacity line joining the two nodes. Assume that each node maximizes selfishly her utility function by determining the quantity of traffic to sell/buy to satisfy her local demand, while a global coupling constraint (1b) measures the line congestion. The dual variables λ n , n = 1, 2 associated with the global coupling constraint (1b) can be interpreted as the valuation that agent n has of the congestion of the line or, as a price. Then, two scenarios can arise:

• Price discrimination is allowed, which implies that λ 1 = λ 2 . Under this scenario, the nodes are charged based on their contributions to the line congestion. In terms of equilibrium interpretation, NNE (Definition 3) is the appropriate solution concept. Such a setting gives rise to an incomplete market. Completing the market, that is adding additional traded products defined through financial instruments, should reduce the space of dual variables and eventually lead to a single vector of dual variables [START_REF] Ralph | Risk Trading and Endogenous Probabilities in Investment Equilibria[END_REF][START_REF] Shilov | Risk-Averse Equilibrium Analysis and Computation[END_REF].

• Price discrimination is not allowed, which implies that λ 1 = λ 2 . Such a scenario requires a third-party player to enforce the coordination between the nodes when computing their prices. VE (Definition 2) is the appropriate solution concept.

λ 1 λ 2 K(x1, x2) ≤ 0

Reformulations of Equilibrium Problems

Equilibrium problems are challenging to solve. Indeed, it is generally difficult to compute equilibrium. Common approaches in the literature consist in reformulating equilibrium problems using game properties (potential form, submodularity property) or relying on relaxed and extended game formulations. In this section, we give an overview of these different reformulations. Practical illustrations are presented on a stylized economic dispatch problem under complete and incomplete competition.

Reformulation of a NEP as an Optimization Problem

Let f be a concave and continuously differentiable function on FS, and FS a closed and convex subset of R m . A concave constrained optimization problem takes the generic form:

max x∈R m f (x), (6a)
s.t. x ∈ FS. (6b)
We recall the well-known result of maximum principle.

Proposition 4 (Maximum principle). [45]

A feasible point x * ∈ F S is a solution of the optimization problem (6a) if and only if it solves the V I(FS, ∇f ), i.e.,

(y -x * ) T ∇f (x * ) ≤ 0, ∀y ∈ FS. (7)
From Proposition 4, an optimization problem can be formulated as a VI. Doing the reverse, we want now to know under which conditions it is possible to reformulate an equilibrium problem formulated as a VI, as an optimization problem.

Proposition 5 (NEP reformulation as an optimization problem). [START_REF] Scutari | Convex Optimization, Game Theory, and Variational Inequality Theory[END_REF] NEP formulation as a VI(FS, F ) gives rise to an optimization problem if and only if there exists f such that F = ∇f . This last condition is equivalent to check that the Jacobian matrix of F is symmetric.

NEPs equivalent reformulations as optimization problems are studied, among others, in [START_REF] Höschle | An ADMM-Based Method for Computing Risk-Averse Equilibrium in Capacity Markets[END_REF] where the equivalence is justified by KKT comparison, and by adding appropriate terms to the social welfare function, interpreted as market players' market power exertion, enabling potential game formulation [START_REF] Egging-Bratseth | Solving Oligopolistic Equilibrium Problems with Convex Optimization[END_REF].

In Problem 1, the NEP is reformulated as an optimization problem. Problem 1 is classically used in power systems to model economic dispatch [START_REF] Höschle | An ADMM-Based Method for Computing Risk-Averse Equilibrium in Capacity Markets[END_REF][START_REF] Ruiz | A Tutorial Review of Complementarity Models for Decision-Making in Energy Markets[END_REF]. It constitutes a stylized representation of the (partial) equilibrium model used in [START_REF] Egging-Bratseth | Solving Oligopolistic Equilibrium Problems with Convex Optimization[END_REF]. The equilibrium is computed by solving a quadratic optimization problem using an off-the-shelf solver.

Problem 1. The "insider" problem

We consider an economic dispatch problem with a set of agents n ∈ N , comprising production agents and demand agents treated as production agents with a negative production quantity. The marginal cost function, the production capacity lower and upper bounds of n are denoted as M C n (q n ) and Q n , Q n respectively, where q n refers to the quantity of energy sold on the market. Given the market clearing price λ, each agent n ∈ N maximizes her utility function measuring the profit resulting from selling electricity minus the production cost, by determining the quantity of electricity to produce, subject to production capacity constraints:

max q n Π n (q n ) = q n • λ - q n 0 M C n (q)dq, (8a)
s.t. Q n ≤ q n ≤ Q n . µ n , µ n (8b)
An "insider" agent is responsible for the clearing of the market, captured through a shared coupling constraint:

n∈N q n = 0. (λ) (9)
Note that the demand agent has a negative production quantity, so (9) guarantees demand and supply balance. The shadow variable (interpreted as a clearing price) λ, associated with this coupling constraint, is then shared with the agents in N . The shared coupling constraint is embedded in a social welfare maximization problem, which is described by (10a)-(10b).

max q SW = n∈N q n • λ - q n 0 M C n (q)dq , (10a)
s.t. Q n ≤ q n ≤ Q n , ∀n ∈ N , µ n , µ n . ( 10b
)
Problem (8a)-(8b) and the coupling constraint (9) gives rise to a NEP. The associated relevant solution concept is that of Nash equilibrium.

The noncooperative game (8)-( 9) can be formulated as an optimization problem described by (9)-( 10). This statement is justified by the equivalence of the KKT conditions of (8)-( 9) to that of (9)- (10).

The Lagrangian function of (8a)-(8b) writes down as follows (according to the convention of a minimization problem):

L n (q n ) = q n 0 M C n (q)dq -q n • λ + µ n • (Q n -q n ) + µ n • (q n -Q n ).
The KKT condition of agent n ∈ N is described as:

M C n (q n ) -λ -µ n + µ n = 0, 0 ≤ µ n ⊥ q n -Q n ≥ 0, 0 ≤ µ n ⊥ Q n -q n ≥ 0.
We can also write (9) as a complementarity constraint:

λ • n∈N q n = 0. ( 11
)
Aggregating the KKT conditions of the N agents together with [START_REF] Dorsch | On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization[END_REF], we arrive at the KKT conditions of the social welfare maximization problem (9)- (10). Substituting (9) into (10a), we obtain a simplified form for the social welfare at equilibrium:

SW = - n∈N q n 0 M C n (q)dq. ( 12
)
As we consider both demand and production agents, at equilibrium (q n ) n (and therefore, marginal costs) can be negative or positive -implying that SW can still remain positive.

For the numerical analysis, we further assume that the marginal cost function takes the following form:

M C n (q n ) = 2 • a n • q n + b n ,
where a n and b n are positive parameters. Then Π n (q n ) is rewritten as:

Π n (q n ) = -a n • q 2 n -(b n -λ) • q n . ( 13
)
Since a n > 0, SW = n∈N Π n (q n ), both Π n (q n ) and SW are strictly concave. In addition, the feasibility sets are affine. Consequently, there is a unique solution to this problem.

We use the values presented in Table 1 to carry out the case study and the market clearing is shown in Figure 4. The quantities (both productions and demands) are ordered based on merit order principle. The blue curve captures the supply, while the red curve represents the demand. We prove that Problem 1 ( 8)-( 9) admits a unique Nash equilibrium which determines the clearing price and quantity. This result relies on the problem equivalent reformulation as an optimization problem.

Contrary to NEPs, GNEPs are often not amenable to a closed-form solution and GNEPs may admit a very large (even an infinite) number of solutions. This will be illustrated in Problem 2 below. Algorithmic approaches relying on best-response processes are classically used to compute equilibrium. However, in the absence of game specific properties, their convergence is hard to establish [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF], and they do not enable the automatic spanning of the full set of GNEs.

Reformulation of a GNEP as a Generalized Potential Game

Potential game property of noncooperative games typically guarantees good convergence of best-response procedures. This property can also be used to reformulate a GNEP as an optimization problem.

We start by studying the properties of a specific generalized potential game that involves no coupling between the utility functions of the agents. It will be illustrated in Problem 2.

Assumption 2. In the parametrized optimization problem (1), each agent's utility function depends only on her own decision variables, i.e.:

Π n (x n , x -n ) = Π n (x n ).
Proposition 6 (Efficiency). Under Assumptions 1 and 2, the set of variational equilibria coincides with the set of social welfare optima.

Proof. This result relies on the comparison of the KKTs of the GNEP, which take the following form:

λ = ∇ xn Π n (x n ) -µ n ∇ xn Φ n (x n ) ∇ xn K(x n , x -n ) , ∀n ∈ N , 0 ≤ λ ⊥ -K(x n , x -n ) ≥ 0, ∀n ∈ N , 0 ≤ µ n ⊥ -Φ n (x n ) ≥ 0, ∀n ∈ N ,
with the KKTs of the social welfare maximization problem obtained as taking the sum of the utilities of all the agents:

max x∈X n Π n (x n ), s.t. K(x n , x -n ) ≤ 0.
It is straightforward to check that these two sets are the same. As a result, the set of solutions of both problems coincide.

Proposition 7. Assuming λ n = λ m , ∀n, m ∈ N , n = m, the outcome of G is a generalized Nash equilibrium that coincides with a variational equilibrium.

Proof. It follows from the KKT n computation in ( 4) and (5a)-(5b), and the VE definition introduced in Definition 2.

If players' utility functions depend only on their own decision variables, the (general) equilibria solutions of the noncooperative game G are efficient and represent an ideal situation where perfect competition leads to full coordination of the agents. Furthermore, it is straightforward to see that the noncooperative game can be reformulated as a generalized potential game, the definition of which is recalled below. Definition 4 (Generalized potential game (GPG)). [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF] G is said to be a generalized potential game (GPG) if there exists a function P : R m → R, such that for all n ∈ N and for all x -n such that

A n (x -n ) is non empty, it holds ∀x n , xn ∈ A n (x -n ), Π n (x n , x -n ) -Π n (x n , x -n ) = P (x n , x -n ) -P (x n , x -n ).
In case the feasibility sets of strategies are decoupled, Definition 4 coincides with that of a potential game as introduced by Monderer and Shapley [START_REF] Monderer | Potential Games[END_REF].

We investigate under which conditions a GNEP can be reformulated as a GPG. Being able to formulate a noncooperative game as a GPG means that it can be solved as an optimization problem [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF]. For GPG, all the algorithms coming from the optimization literature like the interior-point method, bundle methods or subgradient projections, can be used to compute equilibria. However, in practice, it might be difficult to apply them (size of the problem, communication constraints, etc.). The GPG formulation also enables an easier characterization of equilibrium (existence, uniqueness) since it relies on the analysis of an optimization problem.

Following Definition 4, a game is potential if the difference that each player encounters by unilaterally changing her strategy can be captured by the difference of a single scalar function P , called the potential. Formally, forall n, forall x n , xn ∈ A n (x -n ), we have the following relation:

Π n (x n , x -n ) -Π n ( xn , x -n ) = P (x n , x -n ) -P (x n , x -n ).
The set of all strategies that maximize P is a subset of the equilibria set. This set does not depend on a particular potential function. Thus, at least technically, the potential defines a refinement concept [START_REF] Monderer | Potential Games[END_REF].

Assumption 3. Assume that there exists a function P such that:

∇ xn P (x n , x -n ) = ∇ xn Π n (x n , x -n ), ∀n ∈ N .
Proposition 8 (Optimization problem reformulation). Under Assumption 1 and 3, x * is a variational equilibrium of G if and only if it is a maximizer of P (x).

Proof. Propositions 1 ensures that the VE exists and is the unique solution to VI(FS, F ). Assumption 1 implies that P (x) is concave and that FS is convex and compact. This guarantees that P (x) reaches a maximum in C. The point x is a maximizer of P in C if and only if ∇ x P (x), yx ≤ 0, ∀y ∈ FS. By definition of the mapping F and Assumption 3, this inequality is equivalent to F (x), yx ≤ 0, ∀y ∈ FS, i.e., x ∈ SOL(FS, F ).

In Problem 2, the GNEP is reformulated as a GPG. Equilibria are computed using a bestresponse procedure.

Problem 2. Peer-to-peer energy trading

This special class of generalized Nash game is inspired from the work done in [START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF]. In this problem, we consider a local energy community, consisting of different agents with heterogeneous preferences. Each agent could be a producer, consumer or prosumer, and they are allowed to trade with their neighbours subject to the trade capacity limit. Formally, each agent in node n ∈ N solves the following optimization problem by optimizing her demand D n , self-generation G n , and bilateral trades with her neighbors in Γ n , (q mn ) m∈Γn :

max Dn,Gn,(qmn)m∈Γ n Π n D n , G n , q n , (16a)
s.t. D n ≤ D n ≤ D n , (µ n , µ n ) (16b) G n ≤ G n ≤ G n , (ν n , ν n ) (16c)
q mn ≤ κ mn , ∀m ∈ Γ n , (ξ nm ) (16d)

q mn ≤ -q nm , ∀m ∈ Γ n , (ζ nm ) (16e)
D n = G n + ∆G n + Q n , (λ n ) (16f)
where ∆G n is the renewable (solar PV power) generation at node n, q n = (q mn ) m∈Γn are the trading decisions of agent n. Precisely, q mn , ∀m ∈ Γ n is the quantity exchanged between n and m in the direction from m to n. If q mn ≥ 0, then n buys q mn from m; otherwise (q mn < 0) n sells -q mn to m. We also define Q n := m∈Γn q mn as the net import at node n. Energy surplus is either bought by an aggregator and sold on the wholesale electricity market in exchange for a compensation intended for the prosumers with energy surpluses [START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF], or directly sold by the prosumers on the wholesale electricity market [START_REF] Shilov | Risk-Averse Equilibrium Analysis and Computation[END_REF]. In the network, each line is constrained in capacity. Let κ nm ∈ [0; +∞[ be the equivalent interconnection capacity3 between node n and node m, such that q nm ≤ κ nm , κ nm = κ mn .

The utility function of agent n can be decomposed into three parts: the usage benefit perceived by agent n:

U n (D n ) = -ã n (D n -D n ) 2 + bn ,
where Dnbn ãn ≤ D n ≤ D n + bn ãn is the target demand fixed exogenously by agent n, and ãn > 0, bn > 0; the self-generation cost:

C n (G n ) = 1 2 a n G 2 n + b n G n + d n ,
with a n , b n , d n positive production cost parameters; and the total trading cost function:

Cn (q) = m∈Γn c nm q mn ,
where c nm > 0, sometimes called price differentiation parameter [START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF], captures agent-specific preferences. Therefore, the utility function of agent n takes the following form:

Π n D n , G n , q = U n (D n ) -C n (G n ) -Cn (q).
The peer-to-peer energy trading game is a special case of A n (x -n ) because the objective function Π n depends only on the decision variables of agent n, i.e., it is decomposable per agent. The coupling between the parametrized optimization problems of the agents appears only through the reciprocity constraint (16e), for each pair of neighbors n ∈ N , m ∈ Γ n , n = m. This coupling might give rise to different valuations of the bilateral trade prices, e.g., ζ nm = ζ mn , n ∈ N , m ∈ Γ n , resulting in information asymmetry between agents n and m. Furthermore, the noncooperative game in which each agent solves optimization problem (16) has a specific structure; indeed it is a generalized Nash potential game (GPG) with potential function P (D, G, q) := n∈N Π n D n , G n , q n . Furthermore, the set of VEs solutions of (16) coincides with the set of social welfare optima. Following Facchinei et al., a distributed decomposition method such as regularized Gauss-Seidel best-response (GS BR) algorithm [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF] can be used and is proved to converge to a Nash Equilibrium of the GPG ( [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF], Th. 4.3). Its detailed description can be found in Appendix A.1.

The prosumers' strategy sets are closed and convex, but their utility functions being not strictly monotone, thus there is no guarantee of uniqueness of the VE [START_REF] Yin | Nash Equilibrium Problems with Scaled Congestion Costs and Shared Constraints[END_REF][START_REF] Shilov | Risk-Averse Equilibrium Analysis and Computation[END_REF].

The noncooperative game is solved on a toy network with three nodes indexed by {0, 1, 2}, as illustrated in Figure 5. The root node 0 has only conventional generation (∆G 0 = 0) with cost (a 0 , b 0 , d 0 ) = (2, 5, 5) and (G, G) = (0, 10). Nodes 1 and 2 are renewable sources (RES)based generators (G n = G n = 0 and ∆G n > 0 for n ∈ {1, 2}). Each node is a consumer (with (D, D) = (0, 10)) and generator (RES or conventional), therefore producing energy that can be consumed locally to meet demand D n and exported to the other nodes to meet the unsatisfied demand.

Regarding the preferences (c nm ) nm , we assume that nodes 1 and 2 both prefer to buy local and to RES-based generators. Node 0 is assumed to be indifferent between buying energy from node 1 or node 2 (see Table 2). Capacities are also defined larger from the source node 0 (κ 0n = 10) than between the prosumers nodes (κ nm = 5).

c nm 0 1 2 0 - 1.0 1.0 1 3.0 - 1.0 2 2.0 1.0 - c nm -c mn 0 1 2 0 - -2.0 -1.0 1 2.0 - 0.0 2 1.0 0.0 - Table 2:
Price differentiation parameters and matrix of differences.

GS BR algorithm (see Algorithm 2 in Appendix A.1) is implemented for different sets of initial values, which are given in Table 3. The values of the social welfare evaluated at optimum and at equilibria are stored in Table 4 while the convergence speed in the number of iterations and the equilibria are represented in Figure 6. With the first set of initial values, the equilibria from the GS BR algorithm coincides with the social welfare optimum. In contrast, the equilibria resulting from the second and third set of initial values yield a lower social welfare compared with the optimal solution.

From Problem 2, we observe that depending on the choice of the initial values, the best-response algorithm can generate either a VE or a GNE that is not a VE. However, the explicit link between the choice of the initial value and the type of equilibria (e.g., either a VE or a GNE that is not a VE) that the best-response algorithm generates is unclear. No formal proof is made in [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF]. Furthermore, the best-response algorithm does not enable the automatic spanning of the set of GNE, contrary to the parametrized I-ADMM algorithm that we will introduce later in this paper.

Other Reformulations of GNEP

Last, we introduce GNEP partial dual reformulation to which our decomposition algorithm will be applied, and extended game reformulation.

Partial Dual Reformulations

By the KKT conditions, there is a Lagrange multiplier λ n := λ n (x -n ) such that x n maximizes the Lagrangian function (3) and checks the complementarity constraints (5a)-(5b). We call the game with utilities given by Lagrangians L n as the general relaxed game or Lagrangian game. It coincides with a partial dual reformulation of the GNEP, where the coupling constraint is relaxed by adding a penalty to the players' utility functions. (c) qmn. Definition 5 (General relaxed game).

max xn∈Xn Π n (x n , x -n ) -λ n (x -n )K(x n , x -n ) . (17)
This reformulation has an interesting economic interpretation. In case we translate the coupling constraint (1b) into uniform penalty in a simpler version of the general relaxed game. Definition 6 (Relaxed game).

max xn∈Xn Π n (x n , x -n ) -λK(x n , x -n ) . (18)
We first observe that both formulations, e.g., ( 17) and ( 18), allow us to decouple the actions of the players. In addition, we note that (18) leads to a symmetric game which guarantees the same resource allocation to any player [START_REF] Altman | Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach[END_REF], whereas the general relaxed game [START_REF] Koshal | Distributed Algorithms for Aggregative Games on Graphs[END_REF] does not. Indeed, in the relaxed game, the penalty λ that appears in the utility function of player n (18) is fixed and given, whereas it is player dependent in the general relaxed game utility [START_REF] Koshal | Distributed Algorithms for Aggregative Games on Graphs[END_REF].

It is possible to prove that the relaxed game admits a unique symmetric VE, by extension of [START_REF] Altman | Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach[END_REF]. However, there might exist VE that are non symmetric. In general, the uniqueness of the VE is guaranteed under strong monotonicity of the gradients of the players' utility functions [START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF][START_REF] Paccagnan | Nash and Wardrop Equilibria in Aggregative Games with Coupling Constraints[END_REF][START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF]. Nevertheless, the relaxed game (18) can be interpreted as a penalty-based reformulation of the GNEP where the original utility function is modified by including a penalty term. A few papers consider aggregative games with convex cost functions, convex local constraints, and global (affine [START_REF] Paccagnan | Nash and Wardrop Equilibria in Aggregative Games with Coupling Constraints[END_REF] or convex [START_REF] Yu | Distributed Learning for Stochastic Generalized Nash Equilibrium Problems[END_REF]) and private coupling constraints [START_REF] Koshal | Distributed Algorithms for Aggregative Games on Graphs[END_REF]. The coupling constraints are relaxed either by introducing a penalty function [START_REF] Yu | Distributed Learning for Stochastic Generalized Nash Equilibrium Problems[END_REF] in the objective or by applying an appropriate projection operator [START_REF] Koshal | Distributed Algorithms for Aggregative Games on Graphs[END_REF]. A VE is then computed applying distributed gradient algorithms with constant [START_REF] Paccagnan | Nash and Wardrop Equilibria in Aggregative Games with Coupling Constraints[END_REF][START_REF] Yu | Distributed Learning for Stochastic Generalized Nash Equilibrium Problems[END_REF] or diminishing step sizes [START_REF] Koshal | Distributed Algorithms for Aggregative Games on Graphs[END_REF], under synchronous and asynchronous update rules. The purpose of the penalty term is to assign large penalties to deviations from the constraints. The penalty reformulation helps avoid the high computational complexity of conventional optimization reformulations or the requirement of projection steps. Traditionally, drawbacks is that penalty method convergence might be quite sensitive on selecting penalty parameters, and enable to compute only one VE.

Extended Game Reformulation

The VI(FS, F ) can be equivalently rewritten as a single shot game with N + 1 players, but no coupling constraints. Definition 7 (Extended game reformulation). [START_REF] Facchinei | Distributed Algorithms for the Solution of (Generalized) Nash Equilibrium Problems[END_REF][START_REF] Kelly | The Mathematics of Traffic in Networks[END_REF] We consider the following extended game formulation with N + 1 players

G ext max xn∈Xn Π n (x n , x -n ) -λK(x n , x -n ), ( 19a
) max λ≥0 λK(x n , x -n ). ( 19b
)
The utility function of each player n ∈ N is similar to that of the relaxed game [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF], while the λ is optimized by a (N + 1) th player as in (19b).

The connection between the solutions of the two noncooperative games G ext and G is presented in the next proposition. Proposition 9. Under Assumption 1, (x * , λ * ) is a Nash Equilibrium solution of G ext if and only if x * is a solution of VI(FS, F ) with multiplier λ * .

Proof. The proof is detailed in Appendix A.2. With Proposition 9, solving the GNEP G becomes equivalent to solve a noncooperative game G ext without coupling constraints. Nash equilibrium solution of G ext can be computed by alternating updates in the primal x and dual variables λ. The (N + 1) th player can be assimilated to a coordinator that broadcasts a tentative price λ(t) at every iteration t of the algorithm. Relying on this price and on the aggregate of the strategies at the previous time period, each agent locally computes x n (t + 1). Based on the global constraint violation, the coordinator updates the price to λ(t + 1) [16,[START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF]. This setting gives rise to a two-level decentralized algorithm that converges to a Wardrop equilibrium of the game [START_REF] Paccagnan | Nash and Wardrop Equilibria in Aggregative Games with Coupling Constraints[END_REF]. For a large enough number of players, this latter constitutes an approximation of the VE. If the GNEP G admits a potential function (e.g., can be reformulated as a GPG) and for well calibrated penalty parameter, an asymmetric gradient projection algorithm is proposed and implemented on a real use case in [START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF]. For GPG reformulation and under strong monotonicity assumption, the asymmetric gradient projection algorithm is proved to converge to a VE [START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF]. The algorithm differs from standard gradient projection algorithm since the dual update at iteration t depends not only on x(t -1) but also on x(t).

Algorithmic Formulation: An ADMM Variation

A certain number of decentralized algorithms to compute VI are proposed in the automatic control literature. In all these papers, VE computation relies on communication protocols involving a communication graph, defining how information is exchanged between the agents. A large part of the automatic control literature focuses on aggregative games that are not necessarily GPG with (strictly) convex/concave utility functions [START_REF] Belgioioso | Distributed Generalized Nash Equilibrium Seeking in Aggregative Games on Time-Varying Networks[END_REF][START_REF] Koshal | Distributed Algorithms for Aggregative Games on Graphs[END_REF][START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF][START_REF] Parise | A Distributed Algorithm for Average Aggregative Games with Coupling Constraints[END_REF][START_REF] Yu | Distributed Learning for Stochastic Generalized Nash Equilibrium Problems[END_REF]. Supermodular games are also considered [START_REF] Facchinei | Distributed Algorithms for the Solution of (Generalized) Nash Equilibrium Problems[END_REF]. For GNEP that can be reformulated as GPG, most algorithms rely on similar techniques, e.g., distributed gradient projections (or variants of it) [START_REF] Yin | Nash Equilibrium Problems with Scaled Congestion Costs and Shared Constraints[END_REF][START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF][START_REF] Parise | A Distributed Algorithm for Average Aggregative Games with Coupling Constraints[END_REF][START_REF] Salehisadaghiani | Distributed Nash Equilibrium Seeking: A Gossip-Based Algorithm[END_REF][START_REF] Zhu | Distributed Robust Adaptive Equilibrium Computation for Generalized Convex Games[END_REF][START_REF] Börgens | ADMM-type Methods for Generalized Nash Equilibrium Problems in Hilbert Spaces[END_REF], proximal methods [START_REF] Belgiosio | A Distributed Proximal-Point Algorithm for Nash Equilibrium Seeking in Generalized Potential Games with Linearly Coupled Cost Functions[END_REF][START_REF] Salehisadaghiani | Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers[END_REF][START_REF] Yi | Distributed generalized Nash Equilibria Computation of Monotone Games via Double-Layer Preconditioned Proximal-Point Algorithms[END_REF], and operator splitting [START_REF] Yi | An Operator Splitting Approach for Distributed Generalized Nash Equilibria Computation[END_REF]. Most of the times, the proof of convergence to a global optimum requires strong assumptions on the players' utility functions, like strong monotonicity or cocoercivity of the gradients of the players' utility functions [START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF][START_REF] Parise | A Distributed Algorithm for Average Aggregative Games with Coupling Constraints[END_REF][START_REF] Salehisadaghiani | Distributed Nash Equilibrium Seeking: A Gossip-Based Algorithm[END_REF][START_REF] Salehisadaghiani | Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers[END_REF][START_REF] Zhu | Distributed Robust Adaptive Equilibrium Computation for Generalized Convex Games[END_REF][START_REF] Belgioioso | Distributed Generalized Nash Equilibrium Seeking in Aggregative Games on Time-Varying Networks[END_REF][START_REF] Yi | Distributed generalized Nash Equilibria Computation of Monotone Games via Double-Layer Preconditioned Proximal-Point Algorithms[END_REF][START_REF] Yi | An Operator Splitting Approach for Distributed Generalized Nash Equilibria Computation[END_REF]. Alternatively, distributed payoff-based learning is considered for a GPG with strictly convex potential function [START_REF] Tatarenko | Learning Generalized Nash equilibria in a class of convex games[END_REF]. Unfortunately, the properties required to prove the distributed algorithm convergence are often not checked in engineering applications and heuristic approaches, like gossip algorithms [START_REF] Salehisadaghiani | Distributed Nash Equilibrium Seeking: A Gossip-Based Algorithm[END_REF], can represent an alternative.

In the game theory community, best-response algorithms can be used to compute solutions of GNEP. For GNEP that can be formulated as GPG, the convergence of best-response algorithms is proved in [START_REF] Facchinei | Decomposition Algorithms for Generalized Potential Games[END_REF]. But a large part of GNEPs can not be formulated as GPGs, and following Facchinei [START_REF] Facchinei | Distributed Algorithms for the Solution of (Generalized) Nash Equilibrium Problems[END_REF], much remains to be done regarding centralized and distributed algorithms for GNEP solution computation. For GNEP that can not be reformulated as GPG, results from Section 3.3.1 underline that a solution of the jointly convex GNEP can be obtained by penalty-based [START_REF] Koshal | Distributed Algorithms for Aggregative Games on Graphs[END_REF][START_REF] Yu | Distributed Learning for Stochastic Generalized Nash Equilibrium Problems[END_REF] or partial dual reformulations [START_REF] Salehisadaghiani | Distributed Nash Equilibrium Seeking: A Gossip-Based Algorithm[END_REF]. Alternatively, reformulation as an extended game G ext with decoupled feasibility sets is considered in Section 3.3.2 [START_REF] Facchinei | Distributed Algorithms for the Solution of (Generalized) Nash Equilibrium Problems[END_REF][START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF][START_REF] Paccagnan | Nash and Wardrop Equilibria in Aggregative Games with Coupling Constraints[END_REF]. This formulation is introduced far earlier, by Kelly in the context of a noncooperative game for bandwidth sharing [START_REF] Kelly | The Mathematics of Traffic in Networks[END_REF]. However, as mentioned in Section 3, penalty-based and extended game reformulation do not enable to compute solutions of GNEP that are non VE, as most centralized and decentralized algorithms from the automatic control literature. According to Facchinei [START_REF] Facchinei | Distributed Algorithms for the Solution of (Generalized) Nash Equilibrium Problems[END_REF], the computation of non VE solutions of jointly convex GNEP still remains an unexplored field of research. In this direction, Nabetani et al. propose a parametrized variational inequality approach to compute GNE [START_REF] Nabetani | Parametrized Variational Inequality Approaches to Generalized Nash Equilibrium Problems with Shared Constraints[END_REF]. However, the method is computationally intensive to apply in practice, which limits the automatic exploration of the set of GNEs [START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF]. Furthermore, equilibrium selection is not straightforward.

In the following section, we eliminate the GNEP coupling constraints by an augmented Lagrangian-type approach, leading to a variant of the ADMM (alternating direction method of multipliers) algorithm [START_REF] Le Cadre | Consensus Reaching with Heterogeneous Users' Preferences, Private Input, and Privacy-Preservation Output[END_REF]. In contrast to standard optimization problems, however, the direct extension of ADMM to GNEPs is not necessarily convergent even for N = 2 players [START_REF] Börgens | ADMM-type Methods for Generalized Nash Equilibrium Problems in Hilbert Spaces[END_REF]. We therefore use a regularized version of ADMM, inspired from Inexact-ADMM (I-ADMM) and present a global convergence result under Lipschitz-continuity condition. The algorithm is also updated, being parametrized in the scaling factors r from Definition 3 whose value tuning enables the spanning of the set of GNEs.

In this section, we complexify the GNEP setting by changing its information structure. We consider agents who can withhold some local information from sensitive data [START_REF] Rasouli | An Efficient Market Design for Electricity Networks with Strategic Users Possessing Local Information[END_REF][START_REF] Salehisadaghiani | Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers[END_REF]. This information structure impacts the coupling constraint definition, hence giving rise to a GNEP G 0 with private coupling constraints. Formally, each agent n ∈ N solves the following optimization problem, parametrized in the decision variables of all the other agents in N :

A 0 n (x -n ) max xn∈Xn Π n (x n , x -n ), (20a)
s.t. K n x n , x -n ≤ 0. λ n (20b)

Parametrized Inexact-ADMM

In this section, we adopt the form (b) of GNEP described at the beginning of Section 2. We assume that the coupling constraint in (20b) is private to agent n.

An algorithm alternating primal and dual updates such as the vanilla ADMM could be employed to compute VE solution of the noncooperative game G (see Figure 7 left). It is adapted to our problem since when the agents optimize their actions, they need to form estimates about the actions of the others to compute the coupling constraint (20b). We rely on the Lagrange dual formulation of G 0 introduced in Section 3.3.1, by allowing the shadow prices to be differentiated per agent. We introduce λ n as the shadow price capturing agent n valuation of the coupling constraint K n (x n , x -n ) ≤ 0. Relying on Definition 3, we let r n be the scaling factor connecting the shared coupling constraint dual variable λ and player n local estimate, such that r n λ n = λ.

With this formulation, a solution of G 0 is obtained by assuming that each player n solves:

min λn≥0 max xn∈Xn Π n (x n , x -n ) -λ n K n (x n , x -n ) , (21a)
s.t. r n λ n = λ. ( 21b
)
To define a decentralized approach to solve the noncooperative game G 0 , we define x n := (x n n , x n -n ) as player n estimate of the actions of the other players, x n n ≡ x n as player n own action, and λ n as her local copy of the Lagrange dual variable. We define an undirected communication graph G C := (N , E) with E ⊆ N × N the set of communication links between the players. (n, n ) ∈ E if and only if n and n exchange (are aligned on) their estimates. Based on the previous graph structure, we set Γ n := {n ∈ N , n = n|(n, n ) ∈ E} as the set of neighbors of n in the communication graph G C . Some slack variables (q nn ) n,n and (p nn ) n,n are introduced to guarantee the coincidence of the local copies. Following [START_REF] Salehisadaghiani | Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers[END_REF], we decompose per agent. Each player n solves the local optimization problem:

min λn≥0,(p nn ) n max x n n ∈Xn,(q nn ) n Π n (x n n , x n -n ) -λ n K n (x n n , x n -n ) , (22a)
s.t. x n = q n n , ∀n ∈ N , ∀n ∈ Γ n , (α n n ) (22b) x n = q n n , ∀n ∈ N , ∀n ∈ Γ n , (β n n ) (22c) λ n = p n n r n , ∀n ∈ N , ∀n ∈ Γ n , (γ n n ) (22d) λ n = p n n r n , ∀n ∈ N , ∀n ∈ Γ n . (δ n n ) (22e)
Following [START_REF] Salehisadaghiani | Distributed Nash Equilibrium Seeking: A Gossip-Based Algorithm[END_REF], a solution of ( 22) is a solution of (21), by identifying x n n = x n and λ n = r n λ, ∀n ∈ N .

Vanilla ADMM can then be employed to solve [START_REF] Höschle | An ADMM-Based Method for Computing Risk-Averse Equilibrium in Capacity Markets[END_REF] in a decentralized manner. To that purpose, we explicit the Lagrangian function associated with ( 22):

L n x n n , {q n n , α n n , β n n }, λ n , {p n n , γ n n , δ n n } = Π n (x n n , x n -n ) -λ n K n (x n n , x n -n ) - n ∈N n ∈Γ n (α n n ) T (x n -q n n ) + (β n n ) T (x n -q n n ) + n ∈N n ∈Γ n γ n n (λ n - p n n r n ) + δ n n (λ n - p n n r n ) . (23)
For any player n ∈ N , at equilibrium, (x n , λ n ) n should satisfy the KKT conditions given below:

∇ xn Π n (x n , x -n ) -λ n ∇ xn K n (x n , x -n ) - n ∈Γn [α nn + β n n ] = 0, -K n (x n , x -n ) + n ∈Γn [γ nn + δ n n ] = 0, α nn + β nn = 0, ∀n ∈ Γ n , γ nn + δ nn = 0, ∀n ∈ Γ n , λ n = λ r n .
We aim to apply an algorithm inspired by ADMM to find equilibria of the game G 0 that does not involve a third-party player to coordinate the agents' updates in their primal variables and with limited information exchanges. A schematic description of our algorithm is provided in Figure 7.

To update the actions of the players, we need to compute the augmented Lagrangian associated with [START_REF] Höschle | An ADMM-Based Method for Computing Risk-Averse Equilibrium in Capacity Markets[END_REF]:

L a n x n n , {q n n , α n n , β n n }, λ n , {p n n , γ n n , δ n n } :=L n ... - ρ 2 n ∈N n ∈Γ n ( x n -q n n 2 + x n -q n n 2 ) + ρ 2 n ∈N n ∈Γ n (λ n - p n n r n ) 2 + (λ n - p n n r n ) 2 .
Following vanilla ADMM, we update the duals following the rules:

α nn (t) =α nn (t -1) + ρ 2 x n (t -1) -x n (t -1) , (24a)
β nn (t) =β nn (t -1) + ρ 2 x n (t -1) -x n (t -1) , (24b)
γ nn (t) =γ nn (t -1) + ρ 2 r n λ n (t -1) -r n λ n (t -1) , (24c)
δ nn (t) =δ nn (t -1) + ρ 2 r n λ n (t -1) -r n λ n (t -1) , (24d)
where ρ > 0 is the vanilla ADMM penalty parameter. We update the slacks (q nn ) n,n :

q nn (t) = arg max q nn L a n x n (t -1), {q n n , α n n (t), β n n (t)}, λ n (t -1), {p n n (t -1), γ n n (t), δ n n (t)} , ⇔ q nn (t) = 1 2ρ α nn (t) + β nn (t) + 1 2
x n (t -1) + x n (t -1) .

Assuming that the initialization is chosen such that α nn (0) = β nn (0) = 0 and using the update rules of the duals (24), we infer the following expression for q(t):

q nn (t) = 1 2 x n (t -1) + x n (t -1) . (25)
Similarly, assuming that γ nn (0) = δ nn (0) = 0 and relying on the dual updates [START_REF] Kelly | The Mathematics of Traffic in Networks[END_REF], we obtain the following expression for p(t):

p nn (t) = r n r n r n + r n λ n (t -1) + λ n (t -1) . (26)
To simplify the notations, in the remaining, we set:

Φ n := n ∈Γn [α nn + β n n ] and Ψ n := n ∈Γn (γ nn + δ n n ).
The local estimate update for player n is a max-min optimization problem:

x n n (t) = arg max

x n n ∈Xn min λn≥0 L a n x n n , {q n n (t), α n n (t), β n n (t)}, λ n , {p n n (t), γ n n (t), δ n n (t)} = arg max x n n ∈Xn min λn≥0 Π n (x n n , x n -n (t -1)) -λ n K n (x n n , x n -n (t -1)) -Φ n n (t) T x n n + Ψ n λ n -ρ n ∈Γn x n -q nn (t) 2 - n ∈Γn (λ n - p nn (t) r n ) 2 . ( 27
)
By substitution of ( 25) and ( 26) in [START_REF] Le Cadre | Consensus Reaching with Heterogeneous Users' Preferences, Private Input, and Privacy-Preservation Output[END_REF], we obtain:

x n n (t) = arg max

x n n ∈Xn min λn≥0 Π n (x n n , x n -n (t -1)) -Φ n n (t) T x n n -ρ n ∈Γn x n n - x n n (t -1) + x n n (t -1) 2 2 -λ n K n (x n n , x n -n (t -1)) +Ψ n (t)λ n + ρ n ∈Γn λ n - 1 R nn (λ n (t -1) + λ n (t -1)) 2 , (28)
where to simplify the notations we set R nn := rn+r n rnr n . Derivating [START_REF] Le Cadre | A Pricing Model for a Mobile Network Operator Sharing Limited Resource with a Mobile Virtual Network Operator[END_REF] with respect to λ n , we obtain:

λ n (t) = 1 2ρ|Γ n | K n (x n n , x n -n (t -1)) -Ψ n (t) + 2ρ n ∈Γn λ n (t -1) + λ n (t -1) R nn . (29)
Substituting ( 29) in [START_REF] Le Cadre | A Pricing Model for a Mobile Network Operator Sharing Limited Resource with a Mobile Virtual Network Operator[END_REF] and dropping ρ n ∈Γn

1 R nn (λ n (t -1) + λ n (t -1)) 2
, which is a constant, the local estimate update for player n becomes:

x n n (t) = arg max x n n ∈Xn Π n (x n n , x n -n (t -1)) -Φ n n (t) T x n n -ρ n ∈Γn x n n - x n n (t -1) + x n n (t -1) 2 2 - 1 4ρ|Γ n | 2ρ n ∈Γn λ n (t -1) + λ n (t -1) R nn -Ψ n (t) + K n (x n n , x n -n (t -1)) 2 . (30)
We apply first order proximal approximation around x n (t -1) to Π n (x n n , x n -n (t -1)) and the last term (to the power of 2) in [START_REF] Monderer | Potential Games[END_REF]. Then, (30) becomes:

x n n (t) = arg max x n n ∈Xn ∇ x n n Π n (x n (t -1)) T x n n -x n n (t -1) - ∇ x n n K n (x n (t -1)) 2ρ|Γ n | 2ρ n ∈Γn λ n (t -1) + λ n (t -1) R nn -Ψ n (t) +K n (x n (t -1)) x n n -x n n (t -1) - βn 2 x n n -x n n (t -1) 2 -Φ n n (t) T x n n -ρ n ∈Γn x n n - x n n (t -1) + x n n (t -1) 2 2 , (31)
where βn > 0 is a penalty factor for the proximal first order approximation in player n's utility [START_REF] Salehisadaghiani | Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers[END_REF].

The parametrized I-ADMM steps are described in Algorithm 1. Note that the algorithm is parametrized in r ∈ R m + . A powerful feature of the proposed algorithm is that different values of r n result in different equilibrium points. The parametrized I-ADMM can be adopted to find specific equilibrium points in two ways. Firstly, if the required constraints/properties can specify r n , we then assign the corresponding values in the algorithm and solve the game. The resulting equilibrium points would be the ones we want. Secondly, in a more general case without knowledge of the desired r n , we can enumerate r n to find the ones that satisfy additional constraints/properties. This process will not be time-consuming if high-performance computing resources are available, because we can parallelize the samples and employ a number of CPUs to solve them.

Algorithm 1 Inexact-ADMM for NNE Computations Parametrized in r ∈ R m + (i) Initialization Step
Each player n builds initial estimate of her actions and of that of the other players leading to x n (0) ∈ X and λ n (0) ≥ 0. The players set α nn = β nn = 0, γ nn = δ nn = 0, ∀n ∈ N , ∀n ∈ Γ n , and parameters pri stop , dual stop , t max , ρ > 0, βn > 0. At iteration t, while pri (t)

≥ pri stop ∨ dual (t) ≥ dual stop ∧ t ≤ t max (ii) Communication Step
Each player n ∈ N exchanges her previous estimate of the other players' actions x n (t -1) and her dual Lagrange multiplier λ n (t -1) with her neighbors n ∈ Γ n .

(iii) Action Step Update

Each player n updates her actions, estimates, and Lagrange multiplier via the inexact-ADMM

• Φ n (t) = Φ n (t -1) + ρ n ∈Γn x n (t -1) -x n (t -1) , • Ψ n (t) = Ψ n (t -1) + ρ n ∈Γn r n λ n (t -1) -r n λ n (t -1) , • x n n (t) is updated according to (31), • λ n (t) is updated according to (29), • x n -n (t) = 1 2 x n -n (t -1) + 1 |Γ n | n ∈Γn x n -n (t -1) received information - 1 2ρ|Γ n | Φ n -n (t) penalty term , pri (t) = x(t) -x(t -1) , dual (t) = λ(t) -λ(t -1) , t = t + 1.
Remark 4.1. In the action step update, each player n needs to know her scaling factor r n and the scaling factors of all the other players in her neighborhood, e.g., (r n ) n ∈Γn . The scaling factors are interpreted in Section 2 as the valuation that each agent puts in the coupling constraint (20b).

For parametrized I-ADMM to run, these valuations need to be shared between players belonging to the same neighborhood. In case of a complete communication graph G C , all the scaling factors are known to each agent. In case some coordination wants to be achieved between the agents to reach an equilibrium with specific desirable property, these scaling factors can be interpreted as reflecting the power relationships between the agents. For example, using the two node toy network from Example 1, a large company with large demand will be charged far more -as it is assumed to contribute a lot to the line congestion -than a small company with limited demand. In that example, the scaling factors can be interpreted as being proportional to the company demand (size).

Convergence Proof and Information Structure Impact on Player's Strategies at Equilibrium

Convergence rates of accelerated I-ADMM have been recently analyzed by Hager and Zhang [START_REF] Hager | Convergence Rates for an Inexact-ADMM Applied to Separable Convex Optimization[END_REF]. They prove that for a number of iterations t max , the convergence rate of I-ADMM is a O( 1 tmax ) in a concave setting, and O( 1

t 2 max
) in a strongly concave setting. We prove in this section that strong monotonicity of the mapping F is not required to guarantee parametrized I-ADMM convergence.

Instead, we assume Lipschitz-continuity of the gradients of the players' utility functions and that the coupling constraints are separable and linear in the players' strategies.

Assumption 4. For all n ∈ N , ∇ xn Π n is L n -Lipschitz continuous, i.e., there exists L n > 0 such that ∇ xn Π n (x) -∇ xn Π n ( x) ≤ L n x -x , ∀x, x ∈ X .
Assumption 5. The local coupling constraints are linear in the agents' decision variables, e.g.,

K n (x n , x -n ) = A n x n + A n -n x -n
, where A n , A n -n are private to agent n.

Remark 4.2. Note that A n -n might be different from A -n , since the players might withhold their local information resulting in biased interpretations of the coefficients in front of the other player's decision variables in the coupling constraint, by player n.

Theorem 1. Under Assumptions 1, 4 and 5, for any scaling factor vector r ∈ R m + and any player n ∈ N , if L n < βn -An 2 2ρ|Γn| , then x n (t) n generated by Algorithm 1 converges to x * which is a GNE of the noncooperative game G 0 .

Proof. The proof is detailed in Appendix A.3. Remark 4.3. As a follow up of Theorem 1, we note that under the sufficient condition of Theorem 1, Algorithm 1 is proved to converge to a NNE. While VE will be reached for r = 1, GNEs that are not VEs can be computed for any value of r = 1. Therefore, varying r in a sufficient large space enables to span automatically the full set of GNEs. Assumption 6. There exist C n , Cn such that

∇ xn Π n (x n , x -n ) = diag(C n )x n + Cn .
Assumption 6 means that player n's utility function is quadratic in her decision variables and, can be decomposed in her decision variables and in that of the other players, e.g., there exists Ξ n such that Π n (x n ,

x n ) = 1 2 x T n C n x n + Cn x n + C 0 n + Ξ n (x -n ).
Theorem 2. Under Assumptions 1, 5 and 6, player n's deviation in her strategy at equilibrium obtained as outcome of Algorithm 1, caused by the information structure in which players can withhold some local information, is a O

1 |2ρ|Γn| min n (diag(C n ))-1 -An 2 |
.

Proof. We suppose that there exists

H n -n such that K n (x n , x -n ) = A n x n + A n -n x -n = A n x n + A -n x -n K(xn,x-n) +H n -n x -n
, where H n -n captures the errors made by agent n in the estimation of the other agents' local coupling constraint coefficients. With this formulation, K(x n , x -n ) = A n x n + A -n x -n can be interpreted as the global coupling constraint with no local information, in which all the players are aligned on their estimations of A coefficients in the coupling constraint.

By derivation of (28) with respect to x n n ≡ x n , we obtain:

diag(C n ) -(2ρ|Γ n | - A n 2 2ρ|Γ n | )I xn n + Cn -Φ n n (t) +2ρ n ∈Γn x n n (t -1) + x n n (t -1) 2 - (A n ) T 2ρ|Γ n | 2ρ n ∈Γn λ n (t -1) + λ n (t -1) R nn -Ψ n (t) + A n -n x n -n (t -1) - (A n ) T 2ρ|Γ n | H n -n x n -n (t -1) = 0, (32)
where xn n is the outcome of Algorithm 1 computed with biased estimations of the other agents' local coupling constraint coefficients, e.g., A n -n = A -n + H n -n and H n -n = 0. Substituting [START_REF] Murphy | A Mathematical Programming Approach for Determining Oligopolistic Market Equilibrium[END_REF] in xn n (t) -x * n , we obtain the following upper bound:

xn n (t) -x * n ≤ x n n (t) -x * n + (A n ) T H n -n x n -n (t -1) |2ρ|Γ n |[min n (diag(C n )) -1] -A n 2 ]| . ( 33
)
Theorem 2 statement follows considering [START_REF] Nabetani | Parametrized Variational Inequality Approaches to Generalized Nash Equilibrium Problems with Shared Constraints[END_REF] for t large enough: the left-hand part of the inequality can be interpreted as a measure of the deviation in player n's strategy at equilibrium caused by the information structure, while we have proved in Theorem 1 that x n n (t) -x * n → 0. We consider a noncooperative game for cellular resource allocation between a MNO (n = 1) and a MVNO (n = 2), as pictured in Figure 8. The MNO domain is divided in a finite number of cells C, which are all connected to the Internet. We define D n as the peak total demand on the network for service provider n. The MNO determines how the traffic at peak hour is split over the network cells. This allocation is known only to him. We define D nc > 0 as the demand of service provider n ∈ {1, 2} on cell c ∈ {1, 2, ..., C}, and S nc D nc with S nc ∈ [0, 1] as service provider n served demand on cell c at peak hour. The MNO determines the proportion of his demand that is served over each cell so that it maximizes his utility, taking into account constraints resulting from the finite cell and the peering link capacities while sending his traffic to the Internet:

max S1 Π 1 (S 1 , S 2 ), (34a)
s.t. 0 ≤ S 1c ≤ 1, ∀c ∈ {1, 2, ..., C}, (µ 1 , µ 1 ) (34b)
S 1c D 1c + S 2c D 2c ≤ κ c , ∀c ∈ {1, 2, ..., C}, (ν) (34c)
S T 1 D 1 + S T 2 D 2 ≤ κ 0 , (λ MNO ) (34d)
where κ c > 0, known only to the MNO, is cell c finite capacity, and κ 0 > 0 is the finite capacity of the peering link that connects the MNO network to the Internet. Simultaneously, the MVNO optimizes the proportion of her demand that is served over each cell to maximize her utility, while guaranteeing an average quality of service (QoS) δ QoS -close to that of the MNO (to keep an acceptable market share):

max S2 Π 2 (S 1 , S 2 ), (35a)
s.t. 0 ≤ S 2c ≤ 1, ∀c ∈ {1, 2, ..., C}, (µ 2 , µ 2 ) (35b) 1 C C c=1 (S 1c -S 2c ) ≤ δ QoS , (ξ) (35c)
(34d). (λ MVNO )
The QoS gap δ QoS is defined exogenously through a contract between the MNO and the MVNO. We define p 1 (S 1 ) and p 2 (S 2 ) as the price paid by the consumer to the MNO and MVNO respectively per unit of traffic, and λ M N O , λ M V N O as the peering prices charged by the Internet to the MNO and MVNO respectively. Note that λ M N O might be different from λ M V N O ; therefore, reflecting the use of the peering link by both service providers. We assume an inverse relationship between the providers' traffic price and served demand, such that p

1 (S 1 ) = a 1 -b 1 S T 1 D 1 and p 2 (S 2 ) = a 2 -b 2 S T 2 D 2
, where a 1 , b 1 , a 2 , b 2 are positive parameters. We also define p > 0 as the transit price paid by the MVNO to the MNO per unit of traffic sent on his network.

We explicit the utility function of the MNO:

Π 1 (S 1 , S 2 ) := p 1 (S 1 )S T 1 D 1 + pS T 2 D 2 . ( 36
)
For the MVNO, we get:

Π 2 (S 1 , S 2 ) := p 2 (S 2 ) -p S T 2 D 2 . (37)
The noncooperative game (34)- [START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF] gives rise to the following Hessian matrix elements in each cell c:

∂Π1 ∂S1c = a 1 D 1c -2b 1 (S T 1 D 1 )D 1c and ∂ 2 Π1 ∂S 2 1c = -2b 1 D 2 1c < 0; ∂Π2 ∂S2c = (a 2 -p)D 2c - 2b 2 (S T 2 D 2 )D 2c and ∂ 2 Π2 ∂S 2 2c = -2b 2 D 2 2c < 0; ∂ 2 Π1 ∂S2c∂S1c = ∂ 2 Π2 ∂S1c∂S2c = 0.
As a result, the Hessian matrix in c is diagonal and since all the elements on the diagonal are negative, the Hessian matrix is negative-definite. Therefore, the operator F is strongly monotone, implying that the noncooperative game admits a unique VE [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Game[END_REF].

The Hessian matrix being symmetric, the noncooperative game admits a potential function, P . Following [START_REF] Monderer | Potential Games[END_REF], we compute the potential function:

P (S 1 , S 2 ) := (a 1 -b 1 S T 1 D 1 )S T 1 D 1 + (a 2 -p)S T 2 D 2 -b 2 (S T 2 D 2 ) 2 .
Assumptions 1 and 3 being checked, Proposition 8 holds. This means that to compute the VE solution of the noncooperative game (34)- [START_REF] Paccagnan | Distributed computation of general-ized Nash equilibria in Quadratic Aggregative Games with Affine Coupling Constraints[END_REF], it is equivalent to compute the maximum of the optimization problem with P as objective function and concatenation of the MNO and MVNO's constraints.

The game is implemented based on the data from [START_REF] Le Cadre | A Pricing Model for a Mobile Network Operator Sharing Limited Resource with a Mobile Virtual Network Operator[END_REF] and the parameters are scaled according to the number of cells. In Table 5, we present the parameters adopted in the 10-cell case, which is extensively analyzed. We first analyze the case where r n = 1, i.e., I-ADMM computes a VE. As shown in Figures 9 to 10, we compare the performance of ADMM and I-ADMM in terms of the consensus of primal solution from MNO and MVNO measured by pri (t), I-pri (t), and the dual variables of the Internet link capacity constraint (34d) defining the peering prices λ

M N O , λ M V N O and I-λ M N O , I-λ M V N O .
In addition, we show the peering prices obtained from the GS BR algorithm (Algorithm 2) as BR-λ M N O , BR-λ M V N O .

We have three major observations:

(1) I-ADMM tends to converge faster than standard ADMM and the convergence speed only weakly increases with the number of cells.

(2) In the four cases (e.g., for increasing number of cells C = 1, C = 10, C = 100, C = 500), the solution is of acceptable quality within 50 iterations, which indicates the algorithms applies to the case with very large number of cells. To give an idea on numbers, the total number of cells for the Belgian mobile network is 5.10 3 . Note that we did not tune ρ or β to find the best performance in the simulations.

(3) BR-λ M N O and BR-λ M V N O are not equal, indicating GS BR is not able to align the peering prices of the agents. Consequently, a VE can not be guaranteed by GS BR.

We further show that the parametrized I-ADMM algorithm can span the set of GNEs by tuning the parameter r n , which can be interpreted as a measure of the power relationship between the two service providers. For each cell indexed from 1 to 10 in the 10-cell example, we illustrate in Figure 11 how parametrized I-ADMM performs on the set of GNE spanning with r 1 /r 2 on the interval [10 -3 , 10 3 ]. Each GNE is characterized by the couple of strategy S 1 (Figure 11a), S 2 (Figure 11b) chosen by the MNO and the MVNO at equilibrium. From the figures we can see that the S 1 and S 2 concentrate in a certain range even though the values of r 1 /r 2 differ significantly, which implies that the boundary of the equilibrium set is reached on this sample. This observation can also be confirmed by Figure 11c, which shows the peering prices only change marginally when r 1 /r 2 is close to the extrema. Figure 11d further shows the relative utility of MNO and MVNO, and the social welfare. Note the values are relative to the corresponding values when r 1 /r 2 = 1. We can see that neither the utility of the MNO nor the social welfare is impacted by r 1 /r 2 significantly. The decrease of the utility of the MVNO is more observable, but it is still within 8%.

Finally, we evaluate the impact of errors in the coupling constraint (34d). Following the framework of Proposition 2, we assume that the MVNO does not know the peak traffic allocation rule chosen by the MNO, which can be justified by the fact that the MVNO does not have direct access to the MNO network, e.g., she cannot perform any monitoring of the traffic flows. This asymmety of information leads to errors in the MVNO evaluation of D 1 , D 2 , and impacts in turn her strategy. In Figure 12, the errors in the coupling constraint is captured by a percentage measuring the ratio of the difference between the true allocation rule and the estimation made by the MVNO over the true allocation rule. We observe in Figure 12a that the error percentage increase also increases the number of iterations needed for the parametrized I-ADMM to converge. In Figure 12b, we have plotted the peering price as a function of the error percentage. We observe that in case the percentage error increases with positive values, the peering price logically increases, implying larger peering costs for the MNO and the MVNO. However, in case the error percentage decreases with negative values, the peering price also decreases, implying smaller peering costs for the MNO and the MVNO. As a result, the MVNO might have incentives to act strategically on her evaluation of the MNO peak traffic allocation rule to decrease the peering price. Figure 12c is consistent with Figure 12b, in the sense that when the peering price is lower, the optimal solution of S 2 is higher. From Figure 12d we can see that the utility of the MVNO is impacted by the error remarkably. Note the values are relative to the corresponding values when there is no error. We observe that both MNO and MVNO can increase their profits by choosing an error percentage in the interval (-10%, 0%). This means that both MNO and MVNO can take advantage of the information asymmetry. Furthermore, the MVNO's maximum utility is reached at -5% error.

Relying on Normalized Nash Equilibrium to Design Incentives

One goal of this paper is to use the algorithm developed in Section 4 to coordinate the agents to converge to one equilibrium with specific desirable system-level properties. This goal can be achieved by the appropriate tuning of the scaling factors r, since both update rules [START_REF] Le Cadre | Peer-to-peer Electricity Markets: From Variational to Generalized Nash Equilibrium[END_REF], [START_REF] Murphy | A Tutorial on Building Policy Models as Mixed -Complementarity Problems[END_REF] are parametrized by r. These scaling factors define the degree of price discrimination between the agents, by comparison with the price computed at the VE which assumes equal charging of all the players (e.g., r = 1). Going a step further, tuning these scaling factors r can be equivalently interpreted as determining the relative prices ( λn λ ) n . To define specific desirable system-level properties, we introduce J(x, r), as a secondary systemlevel cost function. Concretely, by tuning r, the coordinator sends signals (relative prices) to the agents, who each reacts by computing selfishly the actions x * n (r) which maximizes her parametrized optimization problem A 0 n (x -n ). For a fixed r, the dual variables λ * n (r) n defines prices that are r ∈ [r, r]

Inexact-ADMM

x (r), λ (r)

The principal computes J x (r), λ (r) .

Pick r such that r = arg min r∈[r,r] J x (r), λ (r) .

when no new GNE can be computed

Algorithm for Incentive Design

In Section 4, we relied on a partial dual reformulation of the GNEP, to which the parametrized I-ADMM algorithm is applied. While the dual variable update rule ( 29) is amenable to a closedform expression, the primal variable update rule [START_REF] Murphy | A Tutorial on Building Policy Models as Mixed -Complementarity Problems[END_REF] is obtained by computing the outcome of a constrained concave optimization problem. Proceeding backwards (see Figure 13), we initialize the scaling factors r and run Inexact-ADMM. As output, we obtain the rational reaction function of the players evaluated in r, i.e., x * (r) and the associated dual variables λ * (r) that we substitute in the cost function of the principal J(.). The process is iterated for a large number of scaling factors r ∈ [r, r]. Convergence is reached when no new equilibrium can be generated. Under that condition, the principal picks the r from the sample used as input of Inexact-ADMM, and chooses the one(s) which parametrizes the equilibrium which minimizes his cost.

The information exchanged between the principal and the agents when solving (38) is represented in Figure 14 for a specific instance of the graph in which the players are split between two neighborhoods such that Γ 1 = Γ 2 = Γ 3 and Γ 4 = Γ 5 .

Remark 5.1. In case the GNE set is discrete and finite, grid-based exploration of the set of scaling factors r gives rise to a finite number of GNEs. Then, the enumeration of all the values of the secondary-level cost function evaluated in each of these GNEs enables to determine r * that minimizes J(.). More sophisticated methods can be used to explore the set of scaling factors r, like genetic or cross-entropy algorithms [START_REF] Kroese | The Cross-Entropy Method for Continuous Multi-Extremal Optimization[END_REF], or hybridization of both. In case the GNE set is infinite, heuristic exploration methods of the r space should already be sufficient to generate multiple equilibrium solutions. More sophisticated intelligent approaches relying on the structure of the GNE set might be developed for a more systematic spanning of the GNE set. This latter research direction is out of the scope of the current paper, but will be the subject of another contribution.

Problem 4. Coordinating the MNO and MVNO on efficient and fair equilibria

We consider the cellular resource allocation setting described in Problem 3. GNE will be selected on the basis of two system-level objective functions:

• social welfare J(S, r) = n=1,2 Π n S(r) , that we will aim to maximize.

• fairness J(S, r) = n=1,2 Πn S(r) 2 N. n=1,2 Πn S(r)

2 measured by the Jain's index [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems[END_REF], that we will try to maximize. Note that J(.) belongs to the interval [ 1 N , 1], with 1 N worst case to 1 best case. The simulation results are shown in Figure 15. Figure 15a shows the evolution of the efficiency (indicated by the relative welfare at different values of r1 r2 compared with the welfare in the case of r1 r2 = 1 ) and fairness (indicated by Jain's index) with respect to r1 r2 . Then the thicker segment of the curve illustrates the efficient frontier 5 . The corresponding prices charged to each agent is described in Figure 15b. In our study, the relative social welfare is the highest at r1 r2 = 0.1 on the efficient frontier and the prices are λ MNO = 5.56e/Mbps and λ MVNO = 0.556e/Mbps. In other words, we can achieve the highest efficiency at a required level of fairness when r1 r2 = 0.1.

Conclusion

Many real-life problems involve a joint capacity constraint that is shared between agents acting strategically. Such problems can be modeled as generalized Nash equilibrium problems (GNEP). However, spanning the set of equilibria solutions of these noncooperative games can be challenging, as it can be quite vast (even infinite in some cases). Furthermore, the algorithm should enable to coordinate the agents on equilibrium with desirable properties such as stability, efficiency, systemfairness, etc. Various reformulations of GNEP exist in the literature. However, most of them rely on strong properties of the game (potential formulation, submodularity property, strong monotonicity, etc.) and focus on a specific generalized Nash equilibrium (GNE). In this paper, we introduce parametrized Inexact-ADMM (I-ADMM) as a relevant algorithm to span many more equilibrium points. We prove that parametrized I-ADMM convergence is guaranteed under mild assumptions and check numerically that it reaches significantly better convergence rates than vanilla ADMM. In addition, we consider an information structure in which the players have local information from sensitive data, that they might not want to share with the other players. The impact of this information structure on the players' strategies at equilibrium generated by parametrized I-ADMM, is quantified analytically. This variant of ADMM is parametrized in scaling factors that capture the players' valuations of the dual variable associated with the coupling constraint. The tuning of these scaling factors can enable to select equilibrium with desirable system-level properties

Figure 2 :

 2 Figure2: Link between the different solution concepts of equilibrium that will be used to parametrize our algorithm. Variational equilibrium set is included into generalized Nash equilibrium (GNE) set. Normalized Nash equilibrium solution concept can be used to characterize through the r scaling factor vector, equilibria in the GNE set. Each r ∈ R m + gives rise to a GNE.

Figure 3 :

 3 Figure 3: A two node toy network illustration.

Figure 4 :

 4 Figure 4: Market clearing in Problem 1.

Figure 5 :

 5 Figure 5: Three node network example for peer-to-peer energy trading.

  Dn and Gn.

Figure 6 :

 6 Figure 6: Comparison of convergence and equilibria of the best-response algorithm with different initial values in Problem 2.

  Each player builds initial estimate of her actions and of that of the other players Initialization All estimates at t -1 are revealed to all players Communication • Each player updates her action following the augmented Lagrangian • A third party player updates the Lagrange multiplier following the augmented Lagrangian Update (a) Vanilla ADMM for games. Assign values to r ∈ R N + Parametrization Each player builds initial estimate of her actions and of that of the other players Initialization Communication of estimates at t -1 with neighbors only Communication • Each player updates her action and Lagrange multiplier estimate following the augmented Lagrangian • Each player updates her estimate of other players' actions Update (b) Inexact ADMM with local information.

Figure 7 :

 7 Figure 7: Illustration of the parametrized Inexact-ADMM.

4. 3 .

 3 Cellular Resource Allocation under Competition as a Coordination Game Problem 3. Cellular resource allocation under competitionCellular resource allocation is essential to the provision of mobile communication services. The cells constitute a finite resource and can accomodate a limited number of simultaneous users at one time. Due to this scarcity, allocating traditional mobile licenses to new mobile operators is unrealizable. Hence, new entrants, known as Mobile Virtual Network Operators (MVNOs), should bargain access to the network of the incumbent Mobile Network Operator (MNO) who establishes contracts specifying access charge (transit prices) and minimum admissible quality of service (QoS) for the MVNOs' clients.

Figure 8 :

 8 Figure 8: MNO-MVNO resource allocation problem.

Figure 9 :

 9 Figure 9: Consensus of MNO and MVNO.

Figure 10 :

 10 Figure 10: Dual variable of the Internet capacity constraint interpreted as the peering price.

  Solution of each cell of MNO in the 10-cell case. Solution of each cell of MVNO in the 10-cell case. Dual variables of the Internet capacity constraint with respect to r1/r2.

  Relative utility of MNO and MVNO, and the social welfare with respect to r1/r2.

Figure 11 :

 11 Figure 11: Solution of MNO and MVNO with different values of rn.

  Solution of each cell of MVNO in the 10-cell case. Relative utility of MNO and MVNO, and the social welfare with respect to the error.

Figure 12 :

 12 Figure 12: Impacts of errors on the coupling constraint.

Figure 13 :

 13 Figure 13: Flowchart incentive design.

5 P r 1 , r 2 , r 3 x 1 , x 2 , x 3 r 4 , r 5 x 4 , x 5 x 1 , λ 1 x 2 , λ 2 x 3 , λ 3 x 4 , λ 4 x 5 , λ 5

 51314545123455

Figure 14 :

 14 Figure 14: Communication graph incentive design.

  Efficient frontier in the MNO and MVNO coordination game.

  Prices charged to each agent at the efficient frontier.

Figure 15 :

 15 Figure 15: Efficient and fair equilibria in the coordination of the MNO and MVNO.

Table 1 :

 1 Values of parameters used in Problem 1.

	Agent	Technology	Q n	Q n	an	bn
	1	Nuclear	0	800	0.005	7
	2	Coal	0	400	0.040	25
	3	Gas	0	400	0.012	50
	4	Demand	-250	0	0.020	40
	5	Demand	-1250	0	0.004	200
			200
		Price [e/MWh]	100
			0
			0 200 400 600 800 1,000 1,200 1,400 1,600
			Quantity [MWh]

Table 3 :

 3 Three sets of initial values in Problem 2 [in MW].

		q 01	q 12	q 20	q 10	q 21	q 02
	First initial values	5.39	5	2.73 -5.39	-5	-2.73
	Second initial values	0	0	0	0	0	0
	Third initial values	5.39	5	0	0	-5	-2.73

Table 4 :

 4 Social Welfare comparison in Problem 2 with different initial values.

	Algorithm	Social Welfare [e]
	GPG Optimization	472.2
	GS BR First Intial Values	472.2
	GS BR Second Initial Values	464.7
	GS BR Third Initial Values	316.7

Table 5 :

 5 Values of parameters used in the 10-cell example of Problem 3.

	Parameter	Value
	κc	{15, 20, 25} [Mbps]
	D 1	70
	D 2	30
	allocation vector	randomly generated and normalized
	κ 0	55
	δ QoS	1
	an	c Dnc/κ 0
	b 1 , b 2	0.8, 0.85
	p	4.41 [e/Mbps]

The network model introduced in Problem 2 is virtual and reflects constraints on the virtual (financial) trades between prosumers. The mapping of the virtual trades to feasible flows checking the power grid power flow equations and operational constraints are out of the scope of Problem 2.

Both inequalities on r are understood element-wise.

The efficient frontier is the set of optimal scaling factors r that offer the highest expected social welfare for a defined level of fairness or the highest fairness for a given level of expected social welfare. In our case, it is the segment where Jain's index exceeds 0.619.

Hélène Le Cadre) The support of FWO Energy Policy Decision Support Toolbox (Eldest) project is acknowledged. The authors would like to thank the two anonymous referees for their constructive comments and suggestions.

charged to each agent n ∈ N . The impact of the designed incentives r on the system can be quantified by computing the system-level cost J x * (r), r .

To minimize the secondary system-level cost function, the principal needs to determine the r which minimizes the system-level cost function J x, r . Framed in an incentive design setting, the problem can be formulated as a principal-agent problem, commonly known as a Stackelberg game in the optimization community [START_REF] Ratliff | A Perspective on Incentive Design: Challenges and Opportunities[END_REF], that we write as a bilevel programming problem (BLPP) [10]:

(BLPP) min

In (38a)-(38b), the principal optimizes the scaling factors r defining signals that he sends to the agents, while anticipating their rational reactions. Each agent n ∈ N reacts rationally to the relative price signal sent by the principal, by determining the action x n which maximizes her utility function under local and private coupling constraints.

Proposition 10. Assuming (38b) satisfies Slater's condition, (BLPP) can be rewritten under the compact form:

where

Proof. This results directly from the strong duality property which is satisfied provided Slater's condition holds. The strong duality property enables us to invert max and min operators in [START_REF] Harker | Generalized Nash Games and Quasi-Variational Inequalities[END_REF], which is an equivalent reformulation of the lower-level problem (38b).

Solving the Principal-Agent Problem

Definition 8 (Agent n's rational reaction function). The set A solution to the Stackelberg game (BLPP), as introduced in Definition 10, does not always exist. Following [START_REF] Simann | On the Stackelberg Strategy in Nonzero-Sum Games[END_REF], Prop. 3.1, if the spaces of definition of x and r are compact and if J(.), Π p n (.), ∀n ∈ N are real-valued continuous functions on X × [r, r], with r > 0 and r < +∞ 4 , then Stackelberg strategies exist. This means that to ensure the existence of a Stackelberg equilibrium, we need to enforce lower and upper bounds on the space of definition of r. This is consistent with the fact that price caps are typically imposed by regulatory authorities on (relative) prices charged to the agents. quantified through a secondary cost function. The resulting coordination game is formulated as a principal-agent problem, and a procedure is detailed to compute GNE that additionally minimizes the secondary cost function. The scope of applicability of our work is illustrated on two power dispatch problems under complete and incomplete competition, and the parametrized I-ADMM is implemented on a cellular resource allocation problem enabling the coordination of the providers on equilibria that achieve both system-level efficiency and maximum fairness.

Future works will assess the scalability of parametrized I-ADMM to large-scale pricing games aiming at coordinating electric vehicle charging so as to avoid congestion in charging stations, or large-scale flexibility activation coordination in the distribution power grid. On the theoretical side, it might be interesting to quantify the impact of more sophisticated information structures, enabling the agents to update dynamically their estimates of the coupling constraint coefficients, on the players' strategies at equilibrium. A side-result would be to determine the amount of information to release in the course of the game to reach a specific equilibrium.

Appendix

A.1 Regularized Gauss-Seidel Best-Response to Solve Problem 2

In the regularized GS BR algorithm, the actions of the players are updated sequentiallyrequiring the players to be ordered from 1 to N . We define the best-response function of player n as follows where, at iteration t, τ (t) > 0 is the regularization (adaptive) parameter:

Practically, at iteration t + 1 each player n optimizes her actions taken as given the last updates at t + 1 of the n -1 players before her and the updates at time t shared by the N -n players after her. The update process is described in Algorithm 2.

In parallel, we note that G ext (19a)-(19b) is equivalent to the system of KKTs

and

By comparing the KKTs [START_REF] Rasouli | An Efficient Market Design for Electricity Networks with Strategic Users Possessing Local Information[END_REF] with the KKTs ( 41)-( 42), we check that x solves (40) with multipliers {λ, (µ n ) n } if, and only if, (x, λ) solves ( 41)-( 42) with multipliers (µ n ) n and K(x n , x -n ) = -κ.

A.3 Proof of Theorem 1

From (31), we have the following expression:

From ( 29), we obtain the relation:

By substitution in [START_REF] Salehisadaghiani | Distributed Nash Equilibrium Seeking: A Gossip-Based Algorithm[END_REF], we obtain:

Substracting the first KKT stationarity condition and multiplying by (x n n (t) -x * n ), we obtain:

Adding the dual update rules (24c), (24d) to (29), we obtain:

Substracting the second KKT stationarity condition to the previous equation, we get:

Then, (44)+2ρ|Γ n |. [START_REF] Scutari | Convex Optimization, Game Theory, and Variational Inequality Theory[END_REF].(λ n (t) -λ * n ) can be rewritten as follows:

Last update rule for agent n gives:

Multiplying it by -2ρ|Γ n |(x n -n (t) -x * -n ) and adding this term to [START_REF] Shilov | Risk-Averse Equilibrium Analysis and Computation[END_REF] gives us:

By (24a), (24b), and initial conditions α nn = β nn = 0, we obtain that α nn (t) + β nn (t) = 0, ∀n ∈ N , ∀n ∈ Γ n . Combining this relation with the KKT n conditions, we obtain the following simplication for (47):

where α = (α n ) n and β = (β n ) n . From (24c) and (24d), we get that Ψ n (t -1) -Ψ * n = 0. By the Mean Value Theorem, we have the following relation: 47) is bounded as follows:

Under Assumption 5, we observe that the sum of the first two terms in [START_REF] Simann | On the Stackelberg Strategy in Nonzero-Sum Games[END_REF] can then be upper bounded, giving as upper-bound:

We then make use of the relationship from [START_REF] Salehisadaghiani | Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers[END_REF], which establishes that for any M semi-definite positive χ(t) -χ(t -1)

M , to upper bound the part on the left of the 0 in (47) by an upper bound which is the sum of norms of vector differences multiplied by negative coefficients.

From this observation, we conclude that if L n < βn -