Distributed Algorithms for Aggregative Games on Graphs

Introduction

An aggregative game is a non-cooperative Nash game in which each player’s payoff depends on its action and an aggregate function of the actions taken by all players .Such games have been shown to be closely related with subclasses of potential games where a potential game refers to a Nash game in which the payoff functions admit a potential function . The potential function of an aggregative game is a special case of the function employed in , where distributed algorithms for optimization problems with general separable convex functions are presented. Nash-Cournot games represent an important instance of such games; here, firms make quantity bids that fetch a price based on aggregate quantity sold, implying that the payoff of any player is a function of the aggregate sales . The ubiquity of such games has grown immensely in the last two decades and examples emerge in the form of supply function games , common agency games , and power and rate control in communication networks (see for more examples). Our work is motivated by the development of distributed algorithms on a range of game-theoretic problems in wired and wireline communication networks where such an aggregate function captures the link-specific congestion or the signal-to-noise ratio . In almost all of the algorithmic research on equilibrium computation, it is assumed that the aggregate of player decisions is observable to all players, allowing every player to evaluate its payoff function without any prior communication.

In this paper, we consider aggregative games wherein the players (referred to as agents) compete over a network. Distributed computation of equilibria in such games is complicated by two crucial challenges. First, the connectivity graphs of the underlying network may evolve over time. Second, agents do not have ready access to aggregate decisions, implying that agents cannot compute their payoffs (or their gradients). Consequently, distributed gradient-based or best-response schemes cannot be directly implemented since agents do not have immediate access to the aggregate. Accordingly, we propose two distributed agreement-based algorithms that overcome this difficulty by allowing agents to build estimates of the aggregate by communicating with their local neighbors and consequently compute an equilibrium of aggregative games. Of these, the first is a synchronous algorithm where all agents update simultaneously, while the second, a gossip-based algorithm, allows for asynchronous computation:

Synchronous distributed algorithm: At each epoch, every agent performs a “learning step” to update its estimate of the aggregate using the information obtained through the time-varying states of its neighbors. All agents exchange information and subsequently update their decisions simultaneously via a gradient-based update. This algorithm builds on the ideas of the method developed in for distributed optimization problems.

Asynchronous distributed algorithm: In contrast, the asynchronous algorithm uses a gossip-based protocol for information exchange. In the gossip-based scheme, a single pair of randomly selected neighboring agents exchange their information and update their estimates of both the aggregate and their individual decisions. This algorithm combines our synchronous method in (a) with the gossip technique proposed in for the agreement (consensus) problem.

We investigate the convergence behavior of both algorithms under a diminishing stepsize rule, and provide error bounds under a constant steplength regime. Additionally, the results are supported with numerics derived from application of the proposed schemes on a class of networked Nash-Cournot games. The novelty of this work lies in our examination of distributed (neighbor-based) algorithms for computation of a Nash equilibrium point for aggregative Nash games, while the majority of preceding efforts on such algorithms have been spent towards solving feasibility and optimization problems. Before proceeding, a caveat is in order. While the proposed game-theoretic problem can be easily solved via a range of centralized schemes (see for a comprehensive survey), any such approach relies on the centralized availability of all information, a characteristic that does not hold in the present setting. Instead, our interest is not merely in equilibrium computation but in the development of stylized distributed protocols, implementable on networks, and complicated by informational restrictions, local communication access, and a possibly evolving network structure.

Broadly speaking, the present work can be situated in the larger domain of distributed computation of equilibria in networked Nash games. First proposed by Nash in 1950 , this equilibrium concept has found application in modeling strategic interactions in oligopolistic problem settings drawn from economics, engineering, and the applied sciences . More recently, game-theoretic models have assumed relevance in the control of a large collection of coupled nonlinear systems, instances of which arise in production planning , synchronization of coupled oscillators , amongst others. In particular, agents in such settings have conflicting objectives and the centralized control problem is challenging. By allowing agents to compete, the equilibrium behavior may be analyzed exactly or approximately (in large population regimes), allowing for the derivation of distributed control laws. In fact, game-theoretic approaches have been effectively utilized in obtaining distributed control laws in complex engineered systems . Motivated by the ubiquity of game-theoretic models, arising either naturally or in an engineered form, the distributed computation of equilibria has immense importance.

While equilibrium computation is a well-studied topic , our interest lies in networked regimes where agents can only access or observe the decisions of their neighbors. In such contexts, our interest lies in developing distributed gradient-based schemes. While any such algorithmic development is well motivated by protocol design in networked multi-agent systems, best-response schemes, rather than gradient-based methods, are natural choices when players are viewed as fully rational. However, gradient-response schemes assume relevance for several reasons. First, increasingly game-theoretic approaches are being employed for developing distributed control protocols where the choice of schemes lies with the designer (cf. ). Given the relatively low complexity of gradient updates, such avenues are attractive for control systems design. Second, when players rule out strategies that are characterized by high computational complexity (referred to as a “bounded-rationality” settingThis notion is rooted in the influential work by Simon where it is suggested that, when reasoning and computation are costly, agents may not invest in these resources for marginal benefits.), gradient-based approaches become relevant and have been employed extensively in the context of communication networks .

The present work assumes a strict monotonicity property on the mapping corresponding to the associated variational problem. This assumption is weaker than that imposed by related studies on communication networks where strong monotonicity properties are imposed. From a methodological standpoint, we believe that this work represents but a first step. By combining a regularization technique, this requirement can be weakened while extensions to stochastic regimes can also be incorporated by examining regularized counterparts of stochastic approximation . However, all of these approaches are under the assumption that agents have access to the decisions of all their competitors.

Finally, it should be emphasized that the distributed algorithms presented in this paper draw inspiration from the seminal work in , where a distributed method for optimization has been developed by allowing agents to communicate locally with their neighbors over a time-varying communication network. This idea has attracted a lot of attention recently in an effort to extend the algorithm of to more general and broader range of problems . Much of the aforementioned work focuses on optimizing the sum of local objective function in a multi-agent networks, while a subset of recent work considered the min-max optimization problem , where the objective is to minimize the maximum cost incurred by any agent in the network. Notably, extensions of consensus based algorithms have also been studied in the domain of distributed regression , estimation and inference tasks . While much of the aforementioned work focuses on consensus-based algorithms, an alternative distributed messaging protocol for consensus propagation across a network is presented in . The work in this paper extends the realm of consensus based algorithms (and not consensus propagation) to capture competitive aspect of multi-agent networks.

The remainder of the paper is organized as follows. In section 2, we describe the problem of interest, provide two motivating examples and state our assumptions. A synchronous distributed algorithm is proposed in section 3 and convergence theory is provided. An asynchronous gossip-based variant of this algorithm is described in section 4 and is supported by convergence theory and error analysis. In section 5.2, we present an extension to the problem presented in section 2 and suitably adapt the distributed synchronous and asynchronous algorithm to address this generalization. We present some numerical results in section 6 and, finally, conclude in section 7.

Problem Formulation and Background

In this section we introduce an aggregative game of our interest and provide its sufficient equilibrium conditions. The players in this game are assumed to have local interactions with each other over time, where these interactions are modeled by time-varying connectivity graphs. We also discuss some auxiliary results for the players’ connectivity graphs and present our distributed algorithm for equilibrium computation.

To formalize the game, let $\bar{K}$ denote the Minkowski sum of the sets $K_{i}$, defined as follows:

In a generic aggregative game, given $\bar{x}_{-i}$, player $i$ faces the following parametrized optimization problem:

A classical example of an aggregative game is a Nash-Cournot played over a network . Suppose a set of $N$ firms compete over $\mathcal{L}$ locations. In this situation, the communication network of our interest is formed by the players which are viewed as the nodes in the network. One such instance of connectivity graph is as shown in Figure 1. This graph determines how the firms communicate their production decision over $\mathcal{L}$ locations. More specifically, the firm in the center of the graph has access to information from all the other firms, whereas all the other firms have access to the information of the firm in the center only. We consider other instances of connectivity graph in Section 6. To this end, let firm

In effect, firm $i$’s payoff function is parametrized by nodal aggregate sales, thus rendering an aggregative game. Note that, in this example we have two independent networks, the first being used to model the communication of the firms and the second being used to model the physical layout of the firms production unit and locations. We allow the communication network to be dynamic but the layout network is assumed to be static.

2 Equilibrium Conditions and Assumptions

To articulate sufficiency conditions, we make the following assumptions on the constraint sets $K_{i}$ and the functions $f_{i}.$

Under Assumption 1, the (sufficient) equilibrium conditions of the Nash game in (2) can be specified as a variational inequality problem VI$(K,\phi)$ (cf. ). Recall that VI$(K,\phi)$ requires determining a point $x^{*}\in K$ such that

Next, we make an assumption on the mapping $\phi(x)$.

The mapping $\phi(x)$ is strictly monotone over $K$, i.e.,

Assumption 1 allows us to claim the existence of a Nash equilibrium, while Assumption 2 allows us to claim the uniqueness of the equilibrium.

Consider the aggregative Nash game defined in (2). Suppose Assumptions 1 and 2 hold. Then, the game admits a unique Nash equilibrium.

By Assumption 1, the set $K$ is compact and $\phi$ is continuous. It follows from Corollary 2.2.5 that VI$(K,\phi)$ has a solution. By the strict monotonicity of $\phi(x)$, VI$(K,\phi)$ has at most one solution based on Theorem 2.3.3 and uniqueness follows. ∎

Strict monotonicity assumptions on the mapping are seen to hold in a range of practical problem settings, including Nash-Cournot games , rate allocation problems , amongst others. We now state our assumptions on the mappings $F_{i}$, which are related to the coordinate mappings of $\phi$ in (7).

Each mapping $F_{i}(x_{i},u)$ is uniformly Lipschitz continuous in $u$ over $\bar{K}$, for every fixed $x_{i}\in K_{i}$ i.e., for some $\bar{L}_{i}>0$ and for all {{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}z_{1}}},{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}z_{2}}}\in\bar{K},

One would naturally question whether such assumptions are seen to hold in practical instances of aggregative games. We will show in section 6 that the assumptions are satisfied for the Nash-Cournot game described in Example 1.

Before proceeding, it is worthwhile to reiterate the motivation for the present work. In the context of continuous-strategy Nash games, when the mapping $\phi$ satisfies a suitable monotonicity property over $K$, then a range of distributed projection-based schemes and their regularized variants schemes can be constructed. In all of these instances, every agent should be able to observe the aggregate $\bar{x}$ of the agent decisions. In this paper, we assume that this aggregate cannot be observed and no central entity exists that can globally broadcast this quantity at any time. Yet, when agents are connected in some manner, then a given agent may communicate locally with their neighbors and generate estimates of the aggregate decisions. Under this restriction, we are interested in designing algorithms for computing an equilibrium of an aggregative Nash game (2).

Distributed Synchronous Algorithm

In this section we develop a distributed synchronous algorithm for equilibrium computation of the game in (2) that relies on agents constructing an estimate of the aggregate by mixing information drawn from local neighbors and making a subsequent projection step. In Section 3.1, we describe the scheme and provide some preliminary results in Section 3.2. This section concludes in Section 3.3 with an analysis of the convergence of the proposed scheme.

Our algorithm equips each agent in the network with a protocol that mandates that every agent exchange information with its neighbors, and subsequently update its decision and the estimate of the aggregate decisions, simultaneously. We employ a synchronous time model which can contend with a time varying connectivity graph. Consequently, in this section we consider a time varying network to model agent’s communications in time. More specifically, let ${\cal E}_{k}$ be the set of underlying undirected edges between agents and let ${\cal G}_{k}=({\cal N},{\cal E}_{k})$ denote the connectivity graph at time $k.$ Let ${\cal N}_{i}(k)$ denote the set of agents who are immediate neighbors of agent $i$ at time $k$ that can send information to $i$, assuming that $i\in{\cal N}_{i}(k)$ for all $i\in{\cal N}$ and all $k\geq 0$. Mathematically, ${\cal N}_{i}(k)$ can be expressed as:

We make the following assumption on the graph ${\cal G}_{k}=({\cal N},{\cal E}_{k})$.

This assumption ensures that the intercommunication intervals are bounded for agents that communicate directly; i.e., every agent sends information to each of its neighboring agents at least once every $Q$ time intervals. This assumption has been commonly used in distributed algorithms on networks, starting with .

Due to incomplete information at any point, an agent only has an estimate of $\bar{x}$ in contrast to the actual $\bar{x}.$ We describe how an agent may build this estimate. Let $x_{i}^{k}$ be the iterate and $v_{i}^{k}$ be the estimate of the average of the decisions $x_{1}^{k},\ldots,x_{N}^{k}$ for agent $i$ at the end of the $k$th iteration. At the beginning of the $(k+1)$st iteration, agent $i$ receives the estimates $v_{j}^{k}$ from its neighbors $j\in{\cal N}_{i}(k+1)$. Using this information, agent $i$ aligns its intermediate estimate according to the following rule:

where $w_{ij}(k)$ is the nonnegative weight that agent $i$ assigns to agent $j$’s estimate. By specifying $w_{ij}=0$ for $j\not\in{\cal N}_{i}(k)$ we can write:

Using this aligned average estimate $\hat{v}_{i}^{k}$ and its own iterate $x_{i}^{k}$, agent $i$ updates its iterate and average estimate as follows:

where $\alpha_{k}$ is the stepsize, \Pi_{K_{i}}{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(u)}} denotes the Euclidean projection of a vector $u$ onto the set $K_{i}$ and $F_{i}$ is as defined in (8). The quantity $N\hat{v}^{k}_{i}$ in (12) is the aggregate estimate that agent $i$ uses instead of the true estimate $\sum_{i=1}^{N}x_{i}^{k}$ of the agent decisions at time $k$. Under suitable conditions on the agents weights $w_{ij}(k)$ and the stepsize $\alpha_{k}$, the iterate vector $(x_{1}^{k},\ldots,x_{N}^{k})$ can converge to a Nash equilibrium point $(x_{1}^{*},\ldots,x_{N}^{*})$ and the estimates $N\hat{v}^{k}_{i}$ in (12) will converge to the true aggregate value $\sum_{i=1}^{N}x_{i}^{*}$ at the equilibrium. These assumptions are given below.

Let $W(k)$ be the weight matrix with entries $w_{ij}(k)$. For all $i\in{\cal N}$ and all $k\geq 0$, the following hold:

$w_{ij}(k)\geq\delta$ for all $j\in{\cal N}_{i}(k)$ and $w_{ij}(k)=0$ for $j\not\in{\cal N}_{i}(k)$;

Assumption 5 essentially requires every player to assign a positive weight to the information received from its neighbor. Following Assumption 5 (ii)-(iii), the matrix $W(k)$ is doubly stochastic. We point the reader to for the examples and a detailed discussion of the weights satisfying the preceding assumption.

The stepsize $\alpha_{k}$ is chosen such that the following hold:

The sequence $\{\alpha_{k}\}$ is monotonically non-increasing i.e., $\alpha_{k+1}\leq\alpha_{k}$ for all $k$;

$\sum_{{k=0}}^{\infty}\alpha_{k}=\infty$;

$\sum_{{k=0}}^{\infty}\alpha_{k}^{2}<\infty.$

Such an assumption is satisfied for a stepsize of the form $\alpha_{k}=(k+1)^{-b}$ where $0.5<b\leq 1$.

2 Preliminary Results

We next provide some auxiliary results for the weight matrices and the estimates generated by the method. We introduce the transition matrices $\Phi(k,s)$ from time $s$ to $k>s$, as follows:

Let Assumptions 4 and 5 hold. Then the following hold:

$\lim_{k\to\infty}\Phi(k,s)=\frac{1}{N}\mathbf{1}\mathbf{1}^{T}$ for all $s\geq 0.$

The convergence rate of $\Phi(k,s)$ is geometric; specifically, we have $\left|[\Phi(k,s)]_{ij}-\frac{1}{N}\right|\leq\theta\beta^{k-s}$ for all $k\geq s\geq 0$ and for all $i$ and $j$, where $\theta=(1-\frac{\delta}{4N^{2}})^{-2}$ and $\beta=(1-\frac{\delta}{4N^{2}})^{\frac{1}{Q}}.$

Next, we state some results which will allow us to claim the convergence of the algorithm. These results involve the average of the estimates $v^{k}_{i},i\in{\cal N}$, defined by $y^{k}$:

As we proceed to show, $y^{k}$ will play a key role in establishing the convergence of the iterates produced by the algorithm in (12)–(13). One important property of $y^{k}$ is that we have $y^{k}=\frac{1}{N}\sum_{j=1}^{N}x^{k}_{j}$ for all $k\geq 0.$ Thus, $y^{k}$ not only captures the average belief of the agents in the network but it also represents the true average information. This property of the true average $y^{k}$ has been shown in within the proof of Lemma 5.2 for a different setting, and it is given in the following lemma for sake of clarity.

Let $W(k)$ be such that $\sum_{j=1}^{N}[W(k)]_{ji}=1$ for every $i$ and $k$. Then, $y^{k}=\frac{1}{N}\sum_{i=1}^{N}x^{k}_{i}$ for all $k\geq 0$, where $y^{k}$ is defined by (14).

It suffices to show that for all $k\geq 0$,

We show this by induction on $k$. For $k=0$ relation (15) holds trivially, as we have initialized the beliefs with $v_{j}^{0}=x_{j}^{0}$ for all $j$. Assuming relation (15) holds for $k-1,$ as the induction step, we have

where the first equality follows from (13), the second inequality is a consequence of the mixing relationship articulated by (11), and the last equality follows from $\sum_{j=1}^{N}[W(k)]_{ji}=1$ for every $i$ and $k$. Furthermore, using the induction hypothesis, we have $\sum_{j=1}^{N}(x_{j}^{k}-x_{j}^{k-1})=\sum_{j=1}^{N}x_{j}^{k}-\sum_{j=1}^{N}v^{k-1}_{j},$ thus implying that $\sum_{j=1}^{N}v^{k}_{j}=\sum_{j=1}^{N}x_{j}^{k}.$ ∎

As a consequence of Lemma 2, Assumptions 1 and 3, we have the following result which will be often used in the sequel.

Let $W(k)$ be such that $\sum_{j=1}^{N}[W(k)]_{ji}=1$ for every $i$ and $k$. Also, let Assumptions 1 and 3 hold. Then, there exists a constant $C$ such that

By Lemma 2, we have $Ny^{k}=\sum_{i=1}^{N}x_{i}^{k}=\bar{x}_{k}\in\bar{K}$, where $\bar{K}$ is compact since each $K_{i}$ is compact (Assumption 1). Since each $F_{i}$ is continuous over $K_{i}\times\bar{K}$, the first inequality follows. To show that $\{F_{i}(x_{i}^{k},N\hat{v}_{i}^{k})\}$ is bounded, we write

Using the Lipschitz property of $F_{i}$ of Assumption 3, we obtain

Let $\hat{K}$ be the convex hull of the union set $\cup_{i}K_{i}$. Note that $\hat{v}^{k}_{i},y^{k}\in\hat{K}$ for all $k$ and that $\hat{K}$ is compact (since each $K_{i}$ is compact).Though $y^{k}\in\bar{K},$ we cannot claim the same for $\hat{v}^{k}_{i}$. Thus, $\{\|\hat{v}_{i}^{k}-y^{k}\|\}$ is bounded. As already established, $\{F_{i}(x_{i}^{k},Ny^{k})\}$ is also bounded, implying that $\{F_{i}(x_{i}^{k},N\hat{v}_{i}^{k})\}$ is bounded as well. ∎

In the following lemma, we establish an error bound on the norm $\|y^{k}-\hat{v}^{k}_{i}\|$ which plays an important role in our analysis.

Let Assumptions 1–5 hold, and let $y^{k}$ be defined by (14). Then, we have

where $\hat{v}^{k}_{i}$ is defined in (11), $\theta=(1-\frac{\delta}{4N^{2}})^{-2}$, $\beta=(1-\frac{\delta}{4N^{2}})^{\frac{1}{Q}}$, $M=\sum_{j=1}^{N}\max_{x_{j}\in K_{j}}\|x_{j}\|$ and $C$ denotes the bound in Lemma 3.

Using the definitions of $v^{k+1}_{i}$ and $\hat{v}_{i}^{k}$ given in Eqs. (13) and (11), respectively, we have

which through an iterative recursion leads to

The preceding relation can be rewritten as:

By the definition of $v^{k+1}_{i}$ in Eq. (13), we have $\hat{v}^{k}_{i}=v_{i}^{k+1}-x_{i}^{k+1}+x_{i}^{k}$, through which we get

Now, consider $y^{k}$ which may be written as follows:

By Lemma 2 we have $y^{s}=\frac{1}{N}\sum_{j=1}^{N}x^{s}_{j}$ for all $s\geq 0$, which implies

where the last equality follows by the definition of $y^{0}$ (see (14)).

where the last inequality follows from $\left|\frac{1}{N}-[\Phi(k,s)]_{ij}\right|\leq\theta\beta^{k-s}$ for all $0\leq s\leq k$ (cf. Lemma 1).

Now, we estimate $\|x_{i}^{s}-x_{i}^{s-1}\|.$ From relation (12) we see that for any $s\geq 1$,

where the first inequality follows by the non-expansive property of projection map, and the second inequality follows by Lemma 3. Combining (3.2) and (3.2), we have

From the right hand side of the expression in Lemma 4, it is apparent that the parameter for network connectivity, $Q$ (cf. Assumption 4) determines the rate of convergence of player’s estimate of the aggregate to the actual aggregate. If the network connectivity is poor, $Q$ is large implying $\beta$ is close to 1 resulting in a slower convergence rate.

3 Convergence theory

In this subsection, under our assumptions, we prove that the sequence produced by the proposed algorithm does indeed converge to the unique Nash equilibrium, which exists by Proposition 1. Our next proposition provides the main convergence result for the algorithm. Prior to providing this result, we state two lemmas that will be employed in proving the required result, the first being a supermartingale convergence result (see for example [44, Lemma 11, Pg. 50]) and the second being [47, Lemma 3.1(b)].

Let $V_{k},u_{k},\beta_{k}$ and $\gamma_{k}$ be non-negative random variables adapted to some $\sigma$-algebra $\mathcal{F}_{k}$. If almost surely $\sum_{k=0}^{\infty}u_{k}<\infty$, $\sum_{k=0}^{\infty}\beta_{k}<\infty$, and

then almost surely $V_{k}$ converges and $\sum_{k=0}^{\infty}\gamma_{k}<\infty$.

[47, Lemma 3.1(b)] Let $\{\zeta_{k}\}$ be a non-negative scalar sequence. If $\sum_{k=0}^{\infty}\zeta_{k}<\infty$ and $0<\beta<1,$ then $\sum_{k=0}^{\infty}\left(\sum_{s=0}^{k}\beta^{k-s}\zeta_{s}\right)<\infty.$

In what follows, we use $x^{k}$ to denote the vector with components $x_{i}^{k}$, $i=1,\ldots,N$, i.e., $x^{k}=(x_{1}^{k},\ldots,x_{N}^{k})$ and, similarly, we write $x^{*}$ for the vector $(x_{1}^{*},\ldots,x^{*}_{N})$.

Let Assumptions 1–6 hold. Then, the sequence $\{x^{k}\}$ generated by the method (12)–(13) converges to the (unique) solution $x^{*}$ of VI($K,\phi)$.

By Proposition 1, VI$(K,\phi)$ has a unique solution $x^{*}\in K$. When $x^{*}$ solves the variational inequality problem VI$(K,\phi)$, the following relation holds $x^{*}=\Pi_{K_{i}}[x^{*}_{i}-\alpha_{k}F_{i}(x^{*}_{i},\bar{x}^{*})]$ (see [11, Proposition 1.5.8, p. 83]). From this relation and the non-expansive property of projection operator, we see that

By expanding the last term, we obtain the following expression:

To estimate Term 1, we use the triangle inequality and the identity $(a+b)^{2}\leq 2(a^{2}+b^{2})$, which yields

where $C$ is such that $\|F_{i}(x_{i}^{k},N\hat{v}_{i}^{k})\|\leq C$ for all $i$ and $k$ (cf. Lemma 3) and $\max_{(x_{i},\bar{x})\in K_{i}\times\bar{K}}\|F_{i}(x_{i},\bar{x})\|$ is finite by Assumption 1. Next, we consider Term 2. By adding and subtracting $F_{i}(x_{i}^{k},Ny^{k})$ in Term 2, where $y^{k}$ is defined by (14), we have

By applying the Cauchy-Schwarz inequality, i.e. $a^{T}b\geq-\|a\|\|b\|$, to the first term on the right hand side of the preceding relation and the Lipschitz continuity of $F_{i}(x_{i},u)$ in $u$ (cf. Assumption 3), we see that

where in the last inequality we use $x_{i}^{k},x_{i}^{*}\in K_{i}$ and the compactness of $K_{i}$ (cf. Assumption 1) and $M\geq\max_{x_{i}\in K_{i}}\|x_{i}\|$ for all $i$. Therefore, we have

By substituting the preceding estimates of Term 1 and Term 2 in (22), we obtain

Summing over all agents from $i=1$ to $i=N$, yields

Using $Ny^{k}=\sum_{i=1}^{N}x^{k}_{i}$ (see Lemma 2) and letting $\bar{x}^{k}=\sum_{i=1}^{N}x^{k}_{i}$, we have for all $k\geq 0$,

where we also use the fact that $F_{i}(x_{i},\bar{x})$ is a coordinate map for the mapping $\phi(x)=F(x,\bar{x})$ (see (9) and (10)). To claim that the sequence $\{x^{k}\}$ converges to $x^{*}$, we apply Lemma 5 (for the deterministic sequences) to relation (24). To apply this lemma, since $\sum_{k=0}^{\infty}\alpha_{k}^{2}<\infty$ by Assumption 6, we only need to prove

Using $\alpha_{k}\leq\alpha_{s}$ for all $k\geq s$ (Assumption 6), for the series $\sum_{k=1}^{\infty}\alpha_{k}\left(\sum_{s=1}^{k}\beta^{k-s}\alpha_{s-1}\right)$ we have

We now use Lemma 6, from which by letting $\zeta_{s}=\alpha_{s}^{2}$ we can see that $\sum_{k=1}^{\infty}\alpha_{k}\left(\sum_{s=1}^{k}\beta^{k-s}\alpha_{s-1}\right)<\infty.$ To establish the convergence of $\sum_{k=0}^{\infty}\alpha_{k}\beta^{k}$, we note that $\alpha_{k}\leq\alpha_{0}$ (Assumption 6), implying that $\sum_{k=0}^{\infty}\alpha_{k}\beta^{k}\leq\alpha_{0}\sum_{k=0}^{\infty}\beta^{k}<\infty$ since $0<\beta<1$. Thus, relation (26) is valid.

As relation (24) satisfies the conditions of (the deterministic case of) Lemma 5, it follows that

Though it is difficult to make a statement on the rate of convergence for the result of Proposition 2, the network connectivity plays an important role in determining the rate as already discussed for the results of Lemma 4. Indeed, if $\beta$ is close to 1, which is the case for a network with poor connectivity, players take longer to converge on their estimate of the true aggregate, thereby taking it longer to converge on their optimal decision.

Distributed Asynchronous Algorithm

In this section, we propose a distributed gossip-based algorithm for computing an equilibrium of aggregative Nash game, as defined by (2). In a gossip protocol, the information is propagated by running a round of information exchange between a randomly chosen player who communicates with another player chosen at random. A more detailed description of the algorithm and some preliminary results are provided in section 4.1. The global convergence of the algorithm is examined in section 4.2, while constant steplength error bounds are provided in section 4.3.

In the proposed algorithm, agents perform their estimate and iterate updates the same as in the synchronous algorithm (12)–(13), but the updates occur asynchronously. As a mechanism for generating asynchronous updates we employ the gossip model for agent communications . Together with the asynchronous updates, we allow the agents to use uncoordinated stepsize values by letting each agent choose a stepsize based on its own information-update frequency. To accommodate these updates and stepsize selections, we model the agent connectivity structure by an undirected static graph ${\cal G}({\cal N},{\cal E})$, with node $i\in{\cal N}$ being agent $i$ and ${\cal E}$ being the set of undirected edges among the agents. When $\{i,j\}\in{\cal E}$, the agents $i$ and $j$ may talk to each other. We let ${\cal N}_{i}$ denote the set of neighbors of agent $i,$ i.e., ${\cal N}_{i}=\{j\mid\{i,j\}\in{\cal E}\}.$ We use the following assumption for the graph ${\cal G}({\cal N},{\cal E})$.

The undirected graph ${\cal G}({\cal N},{\cal E})$ is connected.

We use a gossip protocol to model agent communication and exchange of the estimates of the aggregate $\bar{x}$. In this model, each agent is assumed to have a local clock which ticks according to a Poisson process with rate 1. At a tick of its clock, an agent $i$ wakes up and contacts its neighbor $j\in{\cal N}_{i}$ with probability $p_{ij}$. The agents’ clocks processes can be equivalently modeled as a single (virtual) clock which ticks according to a Poisson process with rate $N$. We assume that only one agent wakes up at each tick of the global clock, and we let $Z^{k}$ denote $k$th tick time of the global Poisson process. We discretize time so that instant $k$ corresponds to the time-slot $[Z^{k-1},Z^{k})$. At each time $k$, every agent $i$ has its iterate $x_{i}^{k}$ and estimate $v^{k}_{i}$ of the average of the current aggregate. We let $I^{k}$ denote the agent whose clock ticked at time $k$ and we let $J^{k}$ be the agent contacted by the agent $I^{k}$, where $J^{k}$ is a neighbor of agent $I^{k},$ i.e., $J^{k}\in\mathcal{N}_{I^{k}}$.

At time $k$, agents $I^{k}$ and $J^{k}$ exchange their estimates $v^{k}_{I^{k}}$ and $v^{k}_{J^{k}}$ and compute intermediate estimates:

and update their iterates and estimates of the aggregate average, as follows:

where $\alpha_{k,i}$ is the stepsize for agent $i$ and $F_{i}(x_{i},y)=\nabla_{x_{i}}f_{i}(x_{i},y).$ The other agents do nothing, i.e.,

As seen from the preceding update relations, the agents perform the same updates as in the synchronous algorithm (12)–(13), but instead of all agents updating, only two randomly selected agents update their estimates and iterates, while the other agents do not update.

We now rewrite the update steps more compactly. To capture the step in (29), we define the weight matrix $W(k)$:

We allow agents to use uncoordinated stepsizes that are based on the frequency of the agent updates. Specifically, agent $i$ uses the stepsize $\alpha_{k,i}=\frac{1}{\Gamma_{k}(i)},$ where $\Gamma_{k}(i)$ denotes the number of updates that agent $i$ has executed up to and including at time $k$. These stepsizes are of the order of $\frac{1}{k}$ in a long run . To formalize this result, we need to introduce the probabilities of agents updates. We let $p_{i}$ denote the probability of the event that agent $i$ updates, i.e. $\{i\in\{I^{k},J^{k}\}\},$ for which we have

where $p_{ji}>0$ is the probability that agent $i$ is contacted by its neighbor $j$. The long term estimates for $\alpha_{k,i}$ that we use in our analysis are given in the following lemma (cf. , Lemma 3), the proof of which is provided in the appendix for completeness.

Based on Lemma 7, we provide the next corollary without a proof.

Let Assumption 7 hold, and let $\hat{p}=1+\min_{\{i,j\}\in{\cal E}}p_{ij}$ and $\alpha_{k,i}=1/\Gamma_{k}(i)$ for all $k$ and $i$. Then for all $i\in{\cal N}$, the following hold with probability one:

Another useful result is provided in [45, Lemma 1], and stated below in a suitable form.

The value of second largest eigenvalue $\lambda$ controls the rate at which information is dispensed over the network. A network with large $\lambda$ will have players agreeing faster on their estimate of the aggregate than a network with a smaller $\lambda$. In Section 6 we consider a variety of networks to demonstrate the impact of network topology through $\lambda$ on the rate of convergence.

2 Convergence Theory

In this section we establish the convergence of the asynchronous algorithm (35)–(37) with the agent specific diminishing stepsize of the form $\alpha_{k,i}=\frac{1}{\Gamma_{k}(i)}$. To take account of the history, we introduce $\mathcal{F}_{k}$ to denote the $\sigma-$algebra generated by the entire history up to $k$. More precisely

with $\mathcal{F}_{1}=\mathcal{F}_{0}\{x^{0}_{i},i\in\mathcal{N}\}.$ Thus, given $\mathcal{F}_{k}$, the vectors $v_{i}^{k}$ and $x_{i}^{k}$ are fully determined. First we state several result which we will use to claim the convergence of the algorithm, as well as to analyze the error bounds.

where $D(k)=W(k)-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}$ and $C$ is a constant as in Lemma 3.

By combining the preceding two relations, using $\frac{1}{N}\mathbf{1}\mathbf{1}^{T}W(k)=\frac{1}{N}\mathbf{1}\mathbf{1}^{T}$, and letting $D(k)=W(k)-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}$, we obtain

Using the non-expansive property of the projection operator and

which when combined with (41) and (42) yields

Our result involves the average $y^{k}$ of the estimates $v^{k}_{i},i\in{\cal N}$, which will be important in establishing the convergence of the algorithm.

Let Assumptions 1–3 and Assumption 7 hold. Let $v^{k}_{i}$ be given by (35) and (37), respectively, and let $y^{k}=\frac{1}{N}\sum_{i=1}^{N}v^{k}_{i}$. Then, we have

From Lemma 9, we obtain that the following holds for $k\geq 0$ almost surely,

By taking conditional expectations with respect to $\mathcal{F}_{k}$, we obtain that the following holds almost surely for all $k$:

Note that the expectation in the term on the right hand side is taken with respect to the randomness in the matrix $W(k)$ only. By relation (39), we have

which combined with (43) yields that the following holds for all $k$ in an almost sure sense:

By multiplying both sides of (44) with $\frac{1}{k}$ and by using $\frac{1}{k+1}<\frac{1}{k}$ we find that almost surely for all $k$:

For the rest of the paper, we use $x^{k}$ to denote the vector with components $x_{i}^{k}$, $i=1,\ldots,N$, i.e., $x^{k}=(x_{1}^{k},\ldots,x_{N}^{k})$ and we write $x^{*}$ for the vector $(x_{1}^{*},\ldots,x^{*}_{N})$. We now show the convergence of the algorithm. We have the following result, where $x^{*}$ denotes the unique Nash equilibrium of the aggregative game in (2).

Let Assumptions 1–3 and Assumption 7 hold. Then, the sequence $\{x^{k}\}$ generated by the method (35)–(37) with the stepsize $\alpha_{k,i}=\frac{1}{\Gamma_{k}(i)}$ converges to the (unique) $x^{*}$ of the game almost surely.

Under strict monotonicity of the mapping and the compactness of $K$, uniqueness of the equilibrium follows from Proposition 1. Then, by the definition of $x^{k+1}_{i}$ we have

Using $x^{*}_{i}=\Pi_{K_{i}}[x_{i}^{*}-\alpha_{k,i}F_{i}(x^{*}_{i},\bar{x}^{*})]$ and the non-expansive property of the projection operator, we have for $i\in\{I^{k},J^{k}\},$

By expressing $\alpha_{k,i}$ as $\alpha_{k,i}=\left(\alpha_{k,i}-\frac{1}{kp_{i}}\right)+\frac{1}{kp_{i}}$, we have the following for all $k$:

By Lemma 3 and Assumption 1 we can see that $\|F_{i}(x_{i}^{k},N\hat{v}^{k}_{i})-F_{i}(x^{*}_{i},\bar{x}^{*})\|^{2}\leq C_{1}$ for some scalar $C_{1}$, and for all $i$ and $k$. Similarly, for the term in (4.2) involving the absolute value, we can see that $|(F_{i}(x_{i}^{k},N\hat{v}^{k}_{i})-F_{i}(x^{*}_{i},\bar{x}^{*}))^{T}(x_{i}^{k}-x_{i}^{*})|\leq C_{2}$ for some scalar $C_{2}$, and for all $i$ and $k$. Substituting these estimates in (4.2), we obtain

For the last term in the preceding relation, by adding and subtracting $F_{i}(x^{k}_{i},Ny^{k})$ and using $Ny^{k}=\sum_{i=1}^{N}x^{k}_{i}=\bar{x}^{k}$ (cf. Lemma 2), we write

where we use the Lipschitz property of the mapping $F_{i}$ (Assumption 3), while $M$ is a constant such that $\max_{x_{i},z_{i}\in K_{i}}\|x_{i}-z_{i}\|\leq M$ for all $i$. The vector $\hat{v}_{i}^{k}$ is a convex combination of $v_{j}^{k}$ over $j=1,\ldots,N$(cf. (35)). Therefore, by the convexity of the norm, we have $\|\hat{v}^{k}_{i}-y^{k}\|\leq\sum_{j=1}^{N}[W(k)]_{ij}\|v_{j}^{k}-y^{k}\|$, which yields

Finally, by combining relations (4.2) and (48) we obtain for $i\in\{I^{k},J^{k}\}$ and for all $k\geq 0$,

Since $x^{k+1}_{i}=x^{k}_{i}$ when $i\not\in\{I^{k},J^{k}\}$, it follows that $\|x^{k+1}_{i}-x^{*}_{i}\|^{2}=\|x_{i}^{k}-x^{*}_{i}\|^{2}$ for $i\not\in\{I^{k},J^{k}\}$. We combine these two cases with the fact that agent $i$ updates with probability $p_{i}$ and, thus obtain almost surely for all $i\in\mathcal{N}$ and for all $k$

Summing relations (50) over $i=1,\ldots,N$, using the fact that $W(k)$ is doubly stochastic and recalling that $F_{i}$ are coordinate maps for $F$ and $F(x,\bar{x})$ defines $\phi$ (cf. (9) and (10)), we further obtain for all $k$:

where $p_{\min}=\min_{i}p_{i}$ and $p_{\max}=\max_{i}p_{i}$. We now verify that we can apply the supermartingale convergence result (cf. Lemma 5) to relation (51). From Corollary 1 it follows that

Further from Lemma 10 it follows that $\sum_{k=1}^{\infty}\sum_{i=1}^{N}\frac{1}{k}\|v^{k}_{i}-y^{k}\|<\infty$ almost surely. Thus, all conditions of Lemma 5 are satisfied and we conclude that

3 Error Bounds for Constant Stepsize

In this section, we investigate the properties of the algorithm when agents employ a deterministic constant, albeit uncoordinated, stepsize. More specifically, our interest lies in establishing error bounds contingent on the deviation of stepsize across agents. Under this setting, the stepsize is $\alpha_{k,i}=\alpha_{i}$ in the update rule for agents’ decisions in (36), which reduces to

where $\alpha_{i}$ is a positive constant stepsize for agent $i$. It is worth mentioning that the rules for mixing estimates (29) and updating estimates (37) are invariant under this modification. Also, we allow agents to independently choose $\alpha_{i},$ thereby maintaining the complete decentralization feature of the gossip algorithm. We begin by providing an updated estimate for the disagreement among the agents. Our result is analogous to that of Lemma 10.

Let Assumptions 1–3 and 7 hold. Consider $\{v^{k}_{i}\}$, $i=1,\ldots,N,$ that are generated by algorithm in (35)–(37) with $\alpha_{k,i}=\alpha_{i}$. Then, for $y^{k}=\frac{1}{N}\sum_{i=1}^{N}v_{i}^{k}$ we have

where $\alpha_{\max}=\max_{i}\{\alpha_{i}\}$, $C$ is the constant as in Lemma 3, and $\lambda$ is as given in (38).

where $D(k)=W(k)-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}$ and $\alpha_{\max}=\max_{i}\alpha_{i}$. Note that by relation (39) we have

Thus, by taking the expectation of both sides in (55), we obtain

Thus, by letting $k\to\infty$, we obtain the following limiting result

By taking the squares of both sides in relation (55), we find

Taking the expectation on both sides in the preceding relation and using estimate (56), we obtain

which upon solving for $S$ and recalling the notation yields

and by the linearity of the expectation, it follows

which is the first relation stated in the lemma. In particular, the preceding relation implies that

On the other hand, by Holders’ inequality we have

from which by taking the limit as $k\to\infty$ and using (59), we obtain

We now estimate the limiting error of the algorithm under the additional assumption of strong monotonicity of the mapping $\phi$. For this result, we also assume an additional Lipschitz property for the maps $F_{i}$, as given below.

Each mapping $F_{i}(x_{i},u)$ is uniformly Lipschitz continuous in $x_{i}$ over $K_{i}$, for every fixed $u\in\bar{K}$ i.e., for some $L_{i}>0$ and for all $x_{i},y_{i}\in K_{i}$,

Let Assumptions 1–3, 7, and 8 hold, and let the mapping $\phi$ be strongly monotone over the set $K$ with a constant $\mu>0$, in the following sense:

Consider the sequence $\{x^{k}\}$ generated by the method (35)–(37) with $\alpha_{k,i}=\alpha_{i}$. Suppose that the stepsizes $\alpha_{i}$ are such that

where for $i=1,\ldots,N$, $L_{i}$ are Lipshitz constants from Assumption 8, $\displaystyle\alpha_{\max}=\max_{i}\alpha_{i},$ $\displaystyle\alpha_{\min}=\min_{i}\alpha_{i},$ $\displaystyle p_{\max}=\max_{i}p_{i}$, and $\displaystyle p_{\min}=\min_{i}p_{i}$. Then, the following result holds

where $x^{*}$ is the unique solution of VI$(K,\phi)$, $C$ is as in Lemma 3, $\lambda$ is as in (38), and $B=(\max_{i}\bar{L}_{i})NM$ with $\bar{L}_{i}$, $i=1,\ldots,N$, being the Lipschitz constants from Assumption 3, and $M\geq\max_{x_{i},z_{i}\in K_{i}}\|x_{i}-z_{i}\|$ for all $i$.

Since the map is strongly monotone, there is a unique solution $x^{*}\in K$ to VI$(K,\phi)$ (see Theorem 2.3.3. in ). Then, by the definition of $x^{k+1}_{i}$ we have

Using $x^{*}_{i}=\Pi_{K_{i}}[x_{i}^{*}-\alpha_{i}F_{i}(x^{*}_{i},\bar{x}^{*})]$ and the non-expansive property of the projection operator, we have for $i\in\{I^{k},J^{k}\},$

By using $(a+b)^{2}\leq 2a^{2}+2b^{2}$ and Lemma 3 we can see that

We now approximate the inner product term by adding and subtracting $F_{i}(x^{k}_{i},Ny^{k})$ and using $y^{k}=\sum_{i=1}^{N}x^{k}_{i}=\bar{x}^{k}$ (see Lemma 2), to obtain

By the Lipshitz property of the mapping $F_{i}$ in Assumption 3, we have

where $M\geq\max_{x_{i},z_{i}}\|x_{i}-z_{i}\|$ for all $i$, which exists by compactness of each $K_{i}$. Upon combining the preceding estimates with (61), we obtain

Now, we work with the last term in (64), by letting $\alpha_{\min}=\min_{i}\alpha_{i}$, and by adding and subtracting $2\alpha_{\min}(F_{i}(x_{i}^{k},\bar{x}^{k})-F_{i}(x^{*}_{i},\bar{x}^{*}))^{T}(x^{k}_{i}-x^{*}_{i})$, we can see that

By using the Cauchy-Schwarz inequality and the Lipschitz property of $F_{i}$ given in Assumption 8, we obtain

Further, by letting $\alpha_{\max}=\max_{i}\alpha_{i}$, from (66) and (69) by collecting the common terms we have for $i\in\{I^{k},J^{k}\}$,

The fact that $x^{k+1}_{i}=x^{k}_{i}$ when $i\not\in\{I^{k},J^{k}\}$ implies that $\|x^{k+1}_{i}-x^{*}_{i}\|^{2}=\|x_{i}^{k}-x^{*}_{i}\|^{2}$ for $i\not\in\{I^{k},J^{k}\}$. Next, we take the expectation in (70), whereby we combine the preceding two cases and take into account that agent $i$ updates with probability $p_{i}$, and obtain for all $i\in\mathcal{N}$,

Summing the relations in (70) over all $i=1,\ldots,N$, recalling that $F_{i}$, $i=1,\ldots,N$ are coordinate maps for the map $F$ (see (9)), which in turn defines the mapping $\phi$ through (10), we further obtain

Using this relation and the strong monotonicity of the mapping $\phi$ with a constant $\mu,$ gathering the common terms, and taking the total expectation, we obtain for all $k\geq 0$,

where $q=1-2\mu p_{\min}\alpha_{\min}+2p_{\max}\max_{i}L_{i}(\alpha_{\max}-\alpha_{\min})$. Note that by the condition

We have few comments on the result of Proposition 4, as follows. The error bound depends on the dimension $n$ of the decision variables, the number $N$ of players, the frequency with which players update their decisions (captioned by $p_{\min}$ and $p_{\max}$), and the network properties including the connectivity time bound $B$ and the ability to propagate the information (captured by the value $1-\sqrt{\lambda}$). When the network parameters $B$ and $\lambda$, and the players’ update probabilities ($p_{\min}$ and $p_{\max}$) do not depend on $N$, the error bound grows linearly with the number $N$ of players.

As a special case, consider the case when the agents employ an equal stepsize, i.e., $\alpha_{\min}=\alpha_{\max}=\alpha$ and $\alpha$ satisfies the following condition $0<\alpha<\frac{1}{2\mu p_{\min}}$. Then, the result of Proposition 4 reduces to

As another special case, consider the case when all players have equal probabilities of updating, i.e., $p_{\min}=p_{\max}=p.$ Then, we have the following result:

When all players have equal probabilities of updating and all use equal stepsizes, i.e., $p_{\min}=p_{\max}=p$ and $\alpha_{\min}=\alpha_{\max}=\alpha,$ then the condition of Proposition 4 reduces to $0<\alpha<\frac{1}{2\mu p},$ and the bound further simplifies to:

Generalizations and Extensions

In prior sections, we have developed two algorithms for addressing a class of Nash games. To recap, our prescribed class of equilibrium computation schemes may accommodate a specific sublcass of noncooperative $N-$person Nash games, qualified as aggregative. Specifically, in such games, given $\bar{x}_{-i}$, the $i$th player solves the deterministic convex program given by (2). Unlike in much of prior work, players cannot observe $\bar{x}_{-i}$ but may learn it through the exchange of information with their local neighbors based on an underlying graph. This underlying graph may either be time-varying with a connectivity requirement or be fixed. In the case of the former, we present a synchronous scheme that mandates that every agent synchronizes its updates and information exchanges while in the latter case, we develop a an asynchronous gossip protocol for communication. Under a strict monotonicity and suitably defined Lipschitzian requirements on the map $F$ and compactness of the set $K$, we show that both algorithms produce sequences that are guaranteed to converge to the unique equilibrium in an almost sure sense. More succinctly, under appropriate communication requirements, any deterministic convex aggregative Nash game may be addressed through such synchronous/asynchronous techniques as long as the requirements on the map and strategy sets hold.

Naturally, one may rightly question whether the presented schemes (and their variants) can accommodate weakening some of the assumptions, both on the map and more generally on the model. Motivated by this concern, in Section 5.1, we begin by discussing how extensions of the algorithm can allow for accommodating weaker assumptions on the problem setting. Subsequently, in Section 5.2, we discuss how the very nature of the coupling across agents can also be generalized.

We consider three extensions to our prescribed class of games:

Strict monotonicity: The a.s. convergence theory for both the synchronous and asynchronous schemes rely on the strict monotonicity of the map as asserted by Assumption 2. There are several avenues for weakening such a requirement. For instance, one approach relies on using a regularized variant of (12), given by

where $\{\epsilon_{k,i}\}$ denotes a sequence that diminishes to zero at a prescribed rate. Such an approach has been employed in prior work and allow for the solution of both deterministic and stochastic monotone variational inequality problems. An alternative approach may lie in the usage of an extragradient framework that requires taking two, rather than one, gradient step. Via such approaches, it has been shown that the gap function associated with a monotone stochastic variational inequality problem tends to zero in mean. We believe distributed counterparts of extragradient schemes hold significant and represent a generalization of the schemes presented in this paper.

Lipschitz continuity: A second assumption employed in deriving convergence and rate statements is the (uniform) Lipschitzian assumption as articulated in Assumption 3. We believe that there are at least two avenues that can be adopted in weakening this requirement. First, there has been significant recent work that integrates the use of local or randomized smoothing (also called Steklov-Sobolev smoothing) to address stochastic variational inequalities in which the maps are not necessarily Lipschitz continuous (cf. ). It may well be possible to extend such techniques to address settings where the uniformly Lipschitzian assumption does not hold. An alternate approach may lie in developing convergence in mean of the gap function, as adopted in where the either Lipschitz continuity or boundedness of the map is necessary.

Stochastic payoff functions: Presently, the main source of uncertainty arises either from the evolution of the connectivity graph (synchronous scheme) or the randomness in the choice of players that communicate as per the gossip protocol (asynchronous) scheme. Yet, the player objectives could also be expectation-valued. Consequently, the equilibrium conditions are given by a stochastic variational inequality. In such instances, one may articulate suitably defined distributed stochastic approximation counterparts of (12) to cope with such a challenge (cf. ). We believe convergence analysis of such schemes, while more complicated, is likely to carry through under suitable assumptions.

2 Extensions to model

It may have been observed that the proposed developments in the earlier two sections required that the agent decisions be of the same dimension. In this subsection, we extend the realm of (2) and generalize the algorithms presented in section 3 and section 4. To this end, consider the following aggregative game

Synchronous Algorithm: To make the synchronous algorithm suitable for the generalized problem in (75), the mixing step in (11) remains the same, but with a different initial condition. Namely, the mixing in (11) is initiated with

where $x_{i}^{0}\in K_{i}$ are initial players’ decisions. The iterate update of (12) and update of the average estimate (74) are modified, leading to the following:

where $\alpha_{k}$ is the stepsize, the mapping $F_{i}$ is given by

and $N\hat{v}^{k}_{i}$ in (78) is an estimate of the true value $\sum_{i=1}^{N}h_{i}(x_{i})$. In the context of the extended synchronous algorithm in the preceding discussion, we have the following result.

Let Assumptions 1–6 hold for the mapping $\phi(x)=(\phi_{1}(x),\ldots,\phi_{N}(x))^{T}$ with coordinates $\phi_{i}(x)=\nabla_{x_{i}}f_{i}\left(x_{i},\sum_{i=1}^{N}h_{i}(x_{i})\right)$ and $x=(x_{1}^{T},\ldots,x_{N}^{T})^{T}$. Then, the sequence $\{x^{k}\}$ generated by the method (78)–(79) converges to the (unique) solution $x^{*}$ of the game in (75).

The proof mimics the proof of Proposition 2. ∎

Asynchronous Algorithm: We now discuss how the gossip algorithm in section 4 may be modified. While the estimate mixing in (29) remains unchanged, the initial condition is replaced by one given in (77). The iterate update of (36) and average estimate update of (37) are modified, as follows:

where $\alpha_{k,i}$ is the stepsize for user $i$ and the mapping $F_{i}$ is as defined in (80). The following result establishes the convergence of the extended asynchronous algorithm.

Let Assumptions 1–3 and Assumption 7 hold. Then, the sequence $\{x^{k}\}$ generated by the method (81)–(82) with stepsize $\alpha_{k,i}=\frac{1}{\Gamma_{k}(i)}$ converges to the (unique) $x^{*}$ of the game almost surely.

With the initial condition specified by (77), the proof follows in a fashion similar to that of Proposition 3. ∎

Numerics

In this section, we examine the performance of the proposed algorithms on a class of Nash-Cournot games. Such games represent an instance of aggregative Nash games and in section 6.1, we describe the player payoffs and strategy sets as well as verify that they satisfy the necessary assumptions. In section 6.2, we discuss the synchronous setting and present the results arising from applying our algorithms. In section 6.3, we turn our attention to asynchronous regime where we present our numerical experience of applying the gossip algorithm.

We consider a networked Nash-Cournot games which is possibly amongst the best known examples of an aggregative game. Specifically, the aggregate in such games is the total sales which is the sum of production over all the players. The market price is set in accord with an inverse demand function which depends on the aggregate of the network. A formal description of such a game over a network is provided in Example 1. Before proceeding to describe our experimental setup, we show that Nash-Cournot games do indeed satisfy Assumptions 3 and 8, respectively, under some mild conditions on the cost and price functions. It is worth pointing that we have used Assumption 8 only for the error bound results for the asynchronous algorithm with a constant stepsize.

In the sequel, within the context of Example 1, we let $x_{il}=(g_{il},s_{il})$ for all $l=1,\ldots,\mathcal{L}$, $x_{i}=(x_{i1},\ldots,x_{i\mathcal{L}})$ and $x=(x_{1},\ldots,x_{N})^{T}.$ Further, we define coordinate maps $F_{i}(x_{i},u)$, as follows:

where the prime denotes the first derivative. We let $F(x,u)=(F_{1}(x_{1},u)^{T},\ldots,F_{N}(x_{N},u)^{T})^{T}$, and $K_{i}$ denote the constraint set on player $i$ decision, $x_{i}$, as given in Example 1.

We note that the Nash-Cournot game under the consideration satisfies Assumption 1 as long as the cost functions $c_{il}$ are convex and the price functions $p_{l}(u_{l})$ are concave for all $i$ and $l$. Furthermore, the strict convexity condition of Assumption 2 is satisfied when, for example, all price functions $p_{l}$ are strictly concave. This can be seen by observing that

Next, we show that the Lipschitzian requirements on the maps $F_{i}$ of Assumption 3 holds under some mild assumptions on the cost and price functions in Nash-Cournot games, as shown next.

Consider the Nash-Cournot game described in Example 1. Suppose that each $p_{l}(u_{l})$ is concave and has Lipschitz continuous derivatives with a constant $M_{l}$ (over a coordinate projection of $\bar{K}$ on the $l$th coordinate axis). Then, the following relation holds:

where the inequality follows from $(a+b)^{2}\leq 2(a^{2}+b^{2})$. Since $\bar{K}$ is compact and each $p_{l}$ has continuous derivatives, it follows that there exists a constant $C_{l}$ for every $l$ such that

Then, by using concavity of $p_{l}$, we can see that $|p_{l}(u_{l})-p_{l}(z_{l})|\leq C_{l}|u_{l}-z_{l}|$ implying that

where the last inequality is obtained by using the Lipschitz property of the derivative $p^{\prime}_{l}(u_{l})$. From the structure of constraints we have $s_{il}\leq{\rm cap}_{il}$ yielding

Further, by using Hölder’s inequality, and recalling that $x_{i}=(x_{i1},\ldots,x_{i\mathcal{L}})$ and $u=(u_{1},\ldots,u_{\mathcal{L}})$, from the preceding relation we obtain

We now show that $F_{i}(x,u)$ is Lipschitz continuous in $x$ for every $u$.

Consider the Nash-Cournot game described in Example 1. Suppose that each $c_{il}^{\prime}$ is Lipschitz continuous with a constant $L_{il}$ and $|p^{\prime}_{l}(u)|\leq\bar{p}_{l}$ for some scalar $\bar{p}_{l}$ and for all $u\in\bar{K}$. Then, the following relation holds for all $i$,

In our numerical study, we consider a Nash-Cournot game played over ten locations, i.e. $\mathcal{L}=10$, in which all players have cost functions of a similar structure and the $i$th player’s optimization problem may be expressed as

where $g_{il}$ and $s_{il}$ denote player $i$’s production and sales at location $l,$ respectively, and $\bar{s}_{l}$ denotes the aggregate of all the players’ decisions ($\bar{s}_{l}=\sum_{i=1}^{N}s_{il}$) at location $l$. The function $c_{il}(g_{il})$ denotes the cost of production for $i$th player at location $l$ and has the following form:

where $a_{il}$ and $b_{il}$ are scaling parameters for agent $i$. In our experiments, we draw $a_{il}$ and $b_{il}$ from a uniform distribution and fix them over the course of the entire simulation. More precisely, for $i=1,\ldots,N,$ and $l=1,\ldots,10,$ we have $a_{il}\sim U(2,12)$ and $b_{il}\sim U(2,3),$ where $U(t,\tau)$ denotes the uniform distribution over an interval $[t,\tau]$ with $t<\tau.$ The term $p_{l}(\bar{s}_{l})$ captures the inverse demand function and takes the following form:

where $d_{l}$ is a parameter for location $l$. The parameters $d_{l}$ are also drawn randomly with a uniform distribution, $d_{l}\sim U(90,100)$ for all $l=1,\ldots,10.$ Furthermore, we use $cap_{il}=500$ for all $i=1,\ldots,N$ and for all $l=1,\ldots,10.$ The affine price function gives rise to a strongly monotone map $\phi=F(x,\bar{x})$, which together with the compactness of the sets $K_{i}$, implies that this game has a unique Nash equilibrium. Note that in our setup, we have $cap_{il}>d_{l}$ indicating that at a particular location, a player may produce more than the overall demand at that particular location. Such a scenario can arise when it might be more efficient to produce at a location to meet the demand(s) of another location(s) assuming the transportation costs are zero.

2 Synchronous Algorithm

In this section, we investigate the performance of synchronous algorithm of section 3 for the computation of the equilibrium of aggregative game (84). We begin by describing our setting for the connectivity graph of the network of players, where each player is seen as a node in a graph. At each iteration $k,$ we generate a symmetric $N\times N$ adjacency matrix $A$ such that the underlying graph is connected. The entries of $A$ are generated by performing the following steps:

Let $I$ denote the set of nodes that have already been generated;

For each newly generated node $j$, select a node randomly $i\in I$ to establish an edge $\{i,j\}$ and set $[A]_{ij}=[A]_{ji}=1$;