Differentially-private Distributed Algorithms for Aggregative Games with Guaranteed Convergence

The distributed computation of a Nash equilibrium in aggregative games is gaining increased traction in recent years. Of particular interest is the mediator-free scenario where individual players only access or observe the decisions of their neighbors due to practical constraints. Given the competitive rivalry among participating players, protecting the privacy of individual players becomes imperative when sensitive information is involved. We propose a fully distributed equilibrium-computation approach for aggregative games that can achieve both rigorous differential privacy and guaranteed computation accuracy of the Nash equilibrium. This is in sharp contrast to existing differential-privacy solutions for aggregative games that have to either sacrifice the accuracy of equilibrium computation to gain rigorous privacy guarantees, or allow the cumulative privacy budget to grow unbounded, hence losing privacy guarantees, as iteration proceeds. Our approach uses independent noises across players, thus making it effective even when adversaries have access to all shared messages as well as the underlying algorithm structure. The encryption-free nature of the proposed approach, also ensures efficiency in computation and communication. The approach is also applicable in stochastic aggregative games, able to ensure both rigorous differential privacy and guaranteed computation accuracy of the Nash equilibrium when individual players only have stochastic estimates of their pseudo-gradient mappings. Numerical comparisons with existing counterparts confirm the effectiveness of the proposed approach.


I. INTRODUCTION
The distributed computation of a Nash equilibrium over networks has gained increased attention in recent years. It has found applications in various domains where multiple players (agents) compete to maximize their individual payoff functions, with typical examples including energy management in smart grids [1], congestion control in communication networks [2], market analysis in economics [3], and route coordination in road networks [4]. In many of these application scenarios, a participating player's payoff function depends on the aggregate (e.g., total sum) of all players' decisions, but such an aggregate is inaccessible to individual players. Namely, no central coordinator/mediator exits to collect and distribute the aggregate information, and a player can only access the decisions of its immediate neighbors. Consequently, individual players cannot compute their accurate payoff functions, but instead, they share information among neighboring players to estimate the aggregate decision [5], [6], [7], [8]. The  Despite recent progress in such aggregative games where distributed computation can be conducted under partialdecision information obtained through local information sharing [5], [6], [7], [8], [9], all these distributed algorithms explicitly share estimate/decision variables in every iteration, which can lead to a potential disclosure of players' sensitive information. This problem is significant in that the players are opponents and have every reason to protect their individual private information in competition. Take the Nash-Cournot game as an example, players' cost functions could be market sensitive and every player is well motivated to protect its cost function to gain an edge over its competitors [10]. Moreover, sometimes privacy legislations require the privacy of players' information to be protected during equilibriumbehavior implementation in a game. For example, in routing games [11], California Privacy Rights Act forbids disclosing the spatiotemporal information of drivers because these information can be used as the basis for inferences of a person's activities [12].
To address the urgent need of privacy protection in aggregative games, some efforts have been reported in recent years (see, e.g., [13], [14], [15]). However, these efforts mainly address Nash-equilibrium computation in the presence of a coordinator/mediator which greatly simplifies the privacy design problem. The work [16] proposes a privacy approach for fully distributed Nash-equilibrium computation, but the use of correlated noise restricts its applicability when players can have arbitrary communication patterns. The paper [17] proposes to use an uncertain parameter to obscure the pesudogradient mapping to enable privacy in continuous-time Nashequilibrium computation algorithms. However, the fact that the uncertain parameter is a constant scalar restricts its privacyprotection strength. In fact, the approach can only avoid the payoff function from being uniquely identifiable, while the relations among private parameters are still revealed. Given that differential privacy can provide strong protection against arbitrary post-processing and auxiliary information [18], and is becoming the de facto standard for privacy protection, the recent works [19] and [20] propose differential-privacy mechanisms for equilibrium computation in fully distributed aggregative games. However, to ensure rigorous ǫ-differential privacy (with finite cumulative privacy budget), these approaches have to sacrifice provable convergence to the exact Nash equilibrium.
To avoid the problem of trading convergence accuracy for differential privacy that is plaguing existing differentialprivacy approaches for aggregative games, this paper presents the first distributed Nash-equilibrium computation approach that can simultaneously achieve both rigorous ǫ-differential privacy (with finite cumulative privacy budget) and guaran-teed convergence to the Nash equilibrium. Motivated by the observation that persistent differential-privacy noise has to be repeatedly injected in every iteration of information sharing, which results in significant reduction in algorithmic accuracy, our key idea is to gradually weaken the coupling strength to attenuate the effect of differential-privacy noise added on shared messages. We judiciously design the weakening factor sequence to ensure that convergence to the Nash equilibrium is guaranteed even in the presence of persistent differentialprivacy noise. It is worth noting that compared with our recent result for differentially-private distributed optimization [21], [22], the results here are significantly different: 1) In distributed optimization, agents cooperate to minimize a common objective function, whereas in aggregative games players are competitive and only mind their own payoff functions; 2) Adding differential-privacy noise can easily alter the equilibrium of a game (just as evidenced by the loss of accurate convergence in existing differential-privacy approaches for aggregative games [19]), and hence we have to judiciously design our noise-adding mechanism to avoid perturbing the equilibrium.
Contributions: The main contributions are summarized as follows: 1) By judiciously designing the aggregate estimation mechanism, we propose a fully distributed computation approach for aggregative games that can ensure rigorous ǫ-differential privacy without losing guaranteed convergence to the Nash equilibrium. The algorithm can ensure both a finite cumulative privacy budget and accurate convergence, which is in sharp contrast to existing differential-privacy approaches for aggregative games (see, e.g., [19] and [20]) that have to trade accurate convergence for differential privacy. To the best of our knowledge, this is the first such algorithm in the literature.
2) We propose a new proof technique for the convergence analysis of the fully distributed computation approach for aggregative games in the presence of information-sharing noise (caused by, e.g., differential-privacy design). The new convergence derivation does not impose the restriction that the pseudo-gradient mapping is uniformly bounded, an assumption that is used in existing distributed algorithms (e.g., [19] and [20]) for aggregative games subject to noises. Note that avoiding the uniformly bounded pseudo-gradient assumption is significant since in the presence of differential-privacy noise (e.g., Laplacian or Gaussian noise) which are not uniformly bounded, the aggregative estimation may become unbounded, which makes the pseudo-gradient mapping unbounded in many common games such as the Nash-Cournot game under a price governed by the linear inverse-demand function.
3) Even without taking privacy into consideration, the proposed algorithms and theoretical derivations are of interest themselves. The convergence analysis for the proposed algorithms has fundamental differences from existing proof techniques. More specifically, existing convergence analysis of distributed (generalized) Nash-equilibrium computation algorithms for aggregative games (e.g., [5], [23], [24], [25], [26], [27]) and their stochastic variants (e.g., [20] and [28]) rely on the geometric (exponential) decreasing of the aggregate-estimation error (consensus error) among the players, which is possible only when all nonzero coupling weights are lower bounded by a positive constant. Such geometric (exponential) decreasing of aggregate-estimation error is key to proving exact convergence of all players' iterates to the Nash equilibrium. In our case, since the coupling strength decays to zero, such geometric (exponential) decreasing of players' aggregateestimation error does not exist any more, which makes it impossible to use the proof techniques in existing results. 4) We extend the approach to the case where the pseudogradient mapping is stochastic, and prove that rigorous ǫdifferential privacy and guaranteed convergence can still be achieved simultaneously in this case. Note that different from [20], [28] which consider stochastic pseudo-gradients with decreasing variances (via increasing sample sizes), we allow the variance of the stochastic pseudo-gradient to be constant, or even increasing with time, as specified in Remark 11.
The organization of the paper is as follows. Sec. II gives the problem formulation and some results for a later use. Sec. III presents a differentially-private distributed computation algorithm for aggregative games. This section also proves that the algorithm can ensure all players' convergence to the exact Nash equilibrium while ensuring rigorous ǫ-differential privacy with a finite cumulative privacy budget, even when the number of iterations goes to infinity. Sec. IV extends the approach to the case of stochastic aggregative games and prove that it can ensure both guaranteed computation accuracy of the Nash equilibrium and differential privacy with guaranteed finite cumulative privacy budget when individual players only have stochastic estimates of their pseudo-gradient mappings. Sec. V presents numerical comparisons with existing distributed computation approaches for aggregative games to confirm the obtained results. Finally, Sec. VI concludes the paper.
Notations: We use R d to denote the Euclidean space of dimension d. We write I d for the identity matrix of dimension d, and 1 d for the d-dimensional column vector will all entries equal to 1; in both cases we suppress the dimension when it is clear from the context. A vector is viewed as a column vector, and for a vector x, [x] i denotes its ith element. We write x > 0 (resp. x ≥ 0) if all elements of x are positive (resp. non-negative). We use ·, · to denote the inner product and x for the standard Euclidean norm of a vector x. We use x 1 to represent the L 1 norm of a vector x. We write A for the matrix norm induced by the vector norm · . We let A T denote the transpose of a matrix A. For two vectors u and v with the same dimension, we use u ≤ v to represent the fact that every element of the vector u − v is nonpositive. Often, we abbreviate almost surely by a.s.

A. On Aggregative Games
We consider a set of m players (or agents), i.e., [m] = {1, 2, . . . , m}, which are indexed by 1, 2, · · · , m. Player i is characterized by a strategy set K i ⊆ R d and a payoff function x i denotes the average of all players' decisions. Note that sometimes the payoff function depends on the aggregate decision mx = m i=1 x i rather than the average decisionx. In these cases, all algorithms and analysis in this paper are still valid by replacingx with mx.
Since each decision variable x i is restricted in K i , the averagex is restricted to the set that is the 1/m-scaling of the Minkowski sum 1 of the sets K i , denoted byK, i.e., With this notation, we can formalize f i (x i ,x) as a mapping from K i ×K to R, and further formulate the game that player i faces as the following parameterized optimization problem: The constraint set K i and the function f i (·) are assumed to be known to player i only.
To characterize a Nash equilibrium of the aggregative game (1), following [5], we introduce the following notations and These notions allow us to define two mappings Similar to [5], we make the following assumptions on the constraint sets K i and the functions f i : Remark 1. It is worth noting that the strictly monotone assumption on φ(x) is weaker than the commonly used strongly monotone assumption in [7], [19], [20], [28], [29], [30].
According to [5], Assumption 1 ensures that the aggregative game (1) has a unique Nash equilibrium . Moreover, following [5], we also make the following assumption on the mapping F i (x i , u): Assumption 2. Each mapping F i (x i , u) satisfies the following Lipschitz continuous condition with respect to u: for all x i ∈ K i , all u 1 , u 2 ∈ R d , and all i ∈ [m], we always have A scaling tX of a set X with a scalar t is the set given by tX = {tx | x ∈ X}. A Minkowski sum of two sets X and Y is the set for someL > 0.
We consider distributed algorithms for equilibrium computation of the game in (1). Namely, no player has a direct access to the average decisionx or the aggregate decision mx. Instead, each player has to construct a local estimate of the average/aggregate through local interactions with its neighbors. We describe the local interaction using a weight matrix L = {L ij }, where L ij > 0 if player j and player i can directly communicate with each other, and L ij = 0 otherwise. For a player i ∈ [m], its neighbor set N i is defined as the collection of players j such that L ij > 0. We define L ii − j∈Ni L ij for all i ∈ [m], where N i is the neighbor set of agent i. We represent L 0 as the matrix obtained by replacing matrix L' all diagonal entries with zeros while keeping its all other entries unchanged. Furthermore, We make the following assumption on L: Assumption 3 ensures that the interaction graph induced by L is connected, i.e., there is a path from each player to every other player. It can be verified that In the analysis of our methods, we use the following results: holds almost surely, where {V k } and {H k } are random sequences of nonnegative matrices and E v k+1 |F k denotes the conditional expectation given v ℓ , u ℓ , a ℓ , b ℓ , V ℓ , H ℓ for ℓ = 0, 1, . . . , k. Assume that {a k } and {b k } satisfy ∞ k=0 a k < ∞ and ∞ k=0 b k < ∞ almost surely, and that there exists a (deterministic) vector π > 0 such that π T V k ≤ π T and π T H k ≥ 0 hold almost surely for all k ≥ 0. Then, we have 1) {π T v k } converges to some random variable π T v ≥ 0 almost surely; 2) {v k } is bounded almost surely; and 3) ∞ k=0 π T H k u k < ∞ holds almost surely.

B. On Differential Privacy
We adopt the notion of ǫ-differential privacy for continuous bit streams [31], which has recently been applied to distributed optimization algorithms (see [32] as well as our work [21]). A commonly used approach to enable differential privacy is injecting Laplace noise to shared messages. For a constant ν > 0, we use Lap(ν) to denote a Laplace distribution of a scalar random variable with the probability density function x → 1 2ν e − |x| ν . It can be verified that Lap(ν) has zero mean and variance 2ν 2 . Following the formulation of distributed optimization in [32], for the convenience of differential-privacy analysis, we represent the distributed game P in (1) by three parameters (K, F, L), where K defined in (3) is the domain of decision variables, F {f 1 , · · · , f m }, and L is the interplayer interaction weight matrix L. Then we define adjacency between two games as follows: Definition 1. Two distributed Nash-equilibrium computation problems P = (K, F, L) and P ′ = (K ′ , F ′ , L ′ ) are adjacent if the following conditions hold: • K = K ′ and L = L ′ , i.e., the domains of decision variables and the interaction weight matrices are identical; According to Definition 1, it can be seen that two distributed aggregative games are adjacent if and only if one player changes its payoff function (can be in an arbitrary way) while all other game characteristics are identical.
Given a distributed Nash-equilibrium computation algorithm, we represent an execution of such an algorithm as A, which is an infinite sequence of the iteration variable ϑ, i.e., A = {ϑ 0 , ϑ 1 , · · · }. We consider adversaries that can observe all communicated messages in the network. Therefore, the observation part of an execution is the infinite sequence of shared messages, which is represented by O. We define the observation mapping as R(A) O. Given a distributed Nashequilibrium computation problem P, observation sequence O, and an initial state ϑ 0 , R −1 (P, O, ϑ 0 ) is the set of executions A that can generate the observation O.
Definition 2. (ǫ-differential privacy, adapted from [32]). For a given ǫ > 0, an iterative distributed algorithm solving problem (1) is ǫ-differentially private if for any two adjacent P and P ′ , any set of observation sequences O s ⊆ O (with O denoting the set of all possible observation sequences), and any initial state ϑ 0 , we always have where the probability P is taken over the randomness over iteration processes.
The above definition of ǫ-differential privacy ensures that an adversary having access to all shared messages in the network cannot gain information with a significant probability of any participating player's payoff function. It can also be seen that a smaller ǫ means a higher level of privacy protection. It is also worth noting that the considered notion of ǫ-differential privacy is more stringent than other relaxed (approximate) differential privacy notions such as (ǫ, δ)-differential privacy [33], zero-concentrated differential privacy [34], or Rényi differential privacy [35].

III. A DIFFERENTIALLY-PRIVATE DISTRIBUTED COMPUTATION ALGORITHM FOR AGGREGATIVE GAMES
To achieve strong differential privacy, independent noise should be injected repeatedly in every round of message sharing and, hence, constantly affecting the algorithm through inter-player interactions and leading to significant reduction in algorithmic accuracy. Motivated by this observation, we propose to gradually weaken inter-player interactions to reduce the influence of differential-privacy noise on computation accuracy. Interestingly, we prove that by judiciously designing the interaction weakening mechanism, we can ensure convergence of all players to the Nash equilibrium even in the presence of persistent differential-privacy noise.
Every player i maintains one decision variable x k i , which is initialized with a random vector in K i ⊆ R d , and an estimate of the aggregate decision v k i , which is initialized Every player j adds persistent differential-privacy noise ζ k j to its estimate v k j , and then sends the obscured estimate v k j + ζ k j to player i ∈ N j . b) After receiving v k j + ζ k j from all j ∈ N i , player i updates its decision variable and estimate as follows: where Π Ki [·] denotes the Euclidean projection of a vector onto the set K i . c) end Remark 2. Note that different from [16] where players use correlated noise which restricts the strength of privacy protection, here the noises ζ k i (i = 1, 2, · · · , m) of all players are completely independent of each other, and hence can enable strong differential privacy.
The sequence {γ k }, which diminishes with time, is used to suppress the influence of persistent differential-privacy noise ζ k j on the convergence point of the iterates. The stepsize sequences {λ k } and {α k } and attenuation sequence {γ k } have to be designed appropriately to guarantee the accurate convergence of the iterate vector x k have zero-mean and γ k -bounded (conditional) variances, which are specified in Assumption 4: where {γ k } is the attenuation sequence from Algorithm 1. The initial random vectors satisfy Remark 3. Given that γ k decreases with time, (8) can be satisfied even when {σ k i } increases with time. For example, under γ k = O( 1 k 0.9 ), an increasing {σ k i } with increasing rate no faster than O(k 0.3 ) still satisfies the summable condition in (8). Allowing {σ k i } to increase with time is key to enabling the strong ǫ-differential privacy in Theorem 2.

A. Convergence Analysis
To prove the convergence of the decision vector x k to the Nash equilibrium x * , we have to present some properties of the iterates. The first property pertains to the average of the More specifically, we will prove thatv k converges almost surely to the average of decisionsx k

Lemma 3. Under Assumptions 3 and 4, if the stepsize se
Proof. Using the definitions ofx k andv k , we have the following relationship based on (7): whereζ k m i=1 |Lii|ζ k i m and we have used the symmetric property of L and the fact L ii − j∈Ni L ij .
The preceding relationship implies Using the assumption that the DP-noise ζ k i has zero mean and variance (σ k i ) 2 conditional on x k i (see Assumption 4), taking the conditional expectation, given we obtain the following inequality for all k ≥ 0: . Under the conditions in the lemma statement, it can be seen that v k+1 −x k+1 2 satisfies the conditions for v k in Lemma 1, with o k = (α k ) 2 , q k = 2α k , and Using Lemma 3, we have the following results under Assumption 1: Lemma 4. Under Assumption 1, and v k i governed by Algorithm 1, the following inequalities hold a.s. for some C > 0 and all k ≥ 0: is continuous over the compact set K i ×K and hence is bounded. Using the relation- according to Assumption 2, we have the first inequality (note that v k −x k converge a.s. to zero and hence is bounded according to Lemma 3).
To show the second inequality, we use the following relationship . Then using the Lipschitz continuous condition in Assumption 2 and the proven fact that s. bounded, we can arrive at the second inequality in (10).

Remark 4.
Note that different from [19], [20] whose convergence analysis requires F i (x i , v k i ) to be uniformly bounded in the presence of noise, we will provide a new proof technique that removes the uniformly bounded constraint in convergence analysis. This relaxation is significant in that under differential-privacy design, v k i will be subject to unbounded noise, such as Laplace noise or Gaussian noise, and becomes unbounded. Therefore, restricting F i (x i , v k i ) to be uniformly bounded with respect to v k i will significantly limit the applicability of the algorithm. For example, in the Nash-Cournot market game considered in the numerical simulations in Sec. V, the sale price function (the inverse demand function) is usually modeled as a function decreasing linearly with the aggregative production, which will result in a mapping F i (x i , v k i ) that is not uniformly bounded under differentialprivacy noise.
We now apply Lemma 2 to arrive at a general convergence theory for distributed algorithms for the problem in (1): γ k = ∞, and the scalars κ 1 and κ 2 satisfy κ 1 > 0 and 0 < κ 2 γ k < 1, respectively, for all (11) it follows that almost surely for all k ≥ 0, (12) Consider the vector π = [1, κ1 κ2 ] T and note Thus, relation (12) satisfies all conditions of Lemma 2. By Lemma 2, it follows that lim k→∞ π T v k exists almost surely, and that the sequences (12), we have the following relation almost surely for the second element of v k : For this, we use Lemma 2. Under the assumption that {a k } and {b k } are summable, we have that the inequality in (11) satisfies the relationship in Lemma 2 , and π T = [1, κ1 κ2 ] T . Therefore, according to Lemma 2, we know that π T v k converges almost surely, i.e., Now using (14) and the proven fact that x k − x * 2 converges almost surely, we proceed to prove that x k converges to x * almost surely. Because the augmented state decision vector x k belongs to the compact set K defined in (3), we know that the sequence {x k } must have accumulation points in K. So the condition ∞ k=0 c k = ∞ and (14) mean that there exists a subsequence of Recalling that φ(·) is strictly monotone (see Assumption 1), one has that the subsequence {x k ℓ } must converge to x * almost surely. This and the fact that x k − x * 2 converges almost surely imply that x k converges to x * almost surely.
We also need the following Lemma about matrix L: Under Assumption 3 and two positive se- Proof. Because L is symmetric according to Assumption 3, all of its eigenvalues are real numbers. Since L' off-diagonal entries are non-negative and its diagonal entries L ii are given by L ii = − j∈Ni L ij , the Gershgorin circle theorem implies that all eigenvalues of L are non-positive, with one of them being equal to 0. In fact, the 0 eigenvalue is simple (i.e., all the other eigenvalues are strictly negative) from Assumption 3. Arrange the eigenvalues of L as Hence, the norm of (1 − α k )(I − 11 T m ) + γ k L is no larger than max{|1 − α k + γ k ρ m |, |1 − α k + γ k ρ 2 |}. Further taking into account the fact that α k and γ k decay to zero because they are square summable, we conclude that there always exists a T > 0 such that Given |ρ m | ≥ |ρ 2 |, we have the stated result.
Using Proposition 1, we are in position to establish convergence of Algorithm 1.
then Algorithm 1 converges to the Nash equilibrium of the game in (1) almost surely.
Proof. The basic idea is to apply Proposition 1 to the quantities Since the results of Proposition 1 are asymptotic, they remain valid when the starting index is shifted from k = 0 to k = T , for an arbitrary T ≥ 0. We divide the proof into two parts to analyze For the convenience of analysis, we write the iterates of v k i on percoordinate expressions. Define for all ℓ = 1, . . . , d, and In this per-coordinate view, (7) has the following form for all ℓ = 1, . . . , d, and k ≥ 0: where L 0 is obtained by replacing all diagonal entries of L with zero. Note that the diagonal entries of L are defined as The dynamics of the average v k i , i.e.,v k , is given by Under Assumption 3, we have 1 T L = 0, which simplifies the preceding equation (16) to: where [x k+1 ] ℓ represents the ℓ-th element of the vectorx k+1 .
Combining (15), (16), and (17) yields For the sake of notational simplicity, we define It can be verified that W k 1 = 0 holds, and hence W k 1[v k ] ℓ = 0 always holds for any 1 ≤ ℓ ≤ m under Assumption 3. Therefore, (18) can be rewritten as Taking the conditional expectation, given F k = {v 0 , . . . , v k }, and using the assumption that the noise ζ k i is with zero mean and variance (σ k i ) 2 conditional on v k i (see Assumption 4), from the preceding relation we obtain for all k ≥ 0: (22) where we used the fact that Π = 1. Now we analyze the first term on the right hand side of the preceding inequality. Combined with the facts that Π = 1 and there exists a T ≥ 0 such that 0 < W k ≤ 1 − γ k |ρ 2 | holds for k ≥ T (see Lemma 5), equation (22) implies that there always exists a T ≥ 0 such that the following inequality always holds for k ≥ T : (23) Using the inequality (a + b) 2 ≤ (1 + ǫ)a 2 + (1 + ǫ −1 )b 2 valid for any scalars a, b, and ǫ > 0, we further have Setting ǫ = γ k |ρ2| 1−γ k |ρ2| (which leads to (1 + ǫ) = 1 1−γ k |ρ2| and Summing these relations over ℓ = 1, . . . , d, and noting According to (7), we have where in the last inequality we used Lemma 4. The preceding inequality further implies where C x represent the bound on x k i , which is always finite based on (7) and the assumption that K i is compact.

Plugging (28) into (26) yields
Part II: Next, we analyze At the Nash equilibrium x * = [(x * 1 ) T , (x * 2 ) T , . . . , (x * m ) T ] T , we always have Therefore, using (7), we have By adding and subtracting F i (x k i ,v k ) to the inner-product term, we arrive at Next, we characterize the three terms on the right hand side of (31), i.e., Term 1, Term 2, and Term 3, respectively. Using Lemma 4, we can bound Term 1 as follows: (32) Applying Cauchy-Schwarz inequality to Term 2 yields where in the last inequality we used Assumption 2, and in the second inequality we used the inequality 2ab ≤ a 2 ǫ + ǫb 2 valid for any a ∈ R, b ∈ R, and ǫ > 0.
We use Lemma 3 to treat Term 3.
Using Assumption 2 and the relationship a, b ≤ a c yields where C x represents the bound of x k i , which is always finite under (7) and the assumption that K i is compact.

Remark 6. In the derivation, it can be seen that the aggregateestimation error
does not decrease geometrically with k, which makes it impossible to use existing proof techniques for distributed Nash-equilibrium computation algorithms. In fact, in existing distributed Nash-equilibrium computation algorithms (e.g., [5], [23], [24], [25], [26], [27]) and their stochastic variants (e.g., [28] and [20]), because the inter-player interaction is persistent, the aggregativeestimation error m i=1 v k i −v k always decreases geometrically, which makes it possible to separate the evolution analysis of the aggregate-estimation error and the decision distance from the Nash equilibrium. However, in the proposed algorithm, the diminishing γ k leads to a non-geometric decreasing of the aggregative estimation error, which makes it impossible to analyze the evolution of the aggregate estimate v k i and the decision x k i separately, and hence makes the proposed proof technique fundamentally different from existing analysis.
Remark 7. Communication imperfections can be modeled as channel noises, which can be regarded as the differentialprivacy noise here. Therefore, Algorithm 1 can also counteract such communication imperfections in distributed equilibrium computation of aggregative games.
Remark 8. Because the evolution of x k i to the Nash equilibrium satisfies the conditions in Proposition 1, we can leverage Proposition 1 to examine the convergence speed. The relation (11) implies that the following inequality holds almost surely for all k ≥ 0: (39) The first relationship in (13) where we used the fact that {a k } is summable and hence decreases faster than {γ k } (which is not summable). Therefore, we have the following relationship for the error Further using the fact that a k is also a summable non-negative sequence, and all non-negative summable sequences decrease to zero with a rate no slower than O( 1 k ),

B. Privacy Analysis for Algorithm 1
Following the idea of differential-privacy design for distributed optimization in [32], we define the sensitivity of a distributed Nash-equilibrium computation algorithm to problem (1) as follows: Definition 3. At each iteration k, for any initial state ϑ 0 and any adjacent distributed games P and P ′ , the sensitivity of a Nash-equilibrium computation algorithm is Then, we have the following lemma: Lemma 6. In Algorithm 1, at each iteration k, if each player adds a noise vector ζ k i ∈ R d consisting of d independent Laplace noises with parameter ν k to shared messages v k i such that T0 k=1 ∆ k ν k ≤ǭ, then the iterative distributed Algorithm 1 is ǫ-differentially private with the cumulative privacy budget for iterations from k = 0 to k = T 0 less thanǭ.
Proof. The lemma can be obtained following the same line of reasoning of Lemma 2 in [32] (also see Theorem 3 in [19]).
As indicated in [32], since the change in the payoff function f i can be arbitrarily large in the adjacency definition in Definition 1, we have to make the following assumption to ensure bounded sensitivity: Proof. Because the Laplace noise satisfies Assumption 4, it follows from Theorem 1 that the iterate x k i of every player i will converge to the Nash equilibrum x * i almost surely. To prove the three statements on the strength of differential privacy, we first prove that the sensitivity of the algorithm satisfies ∆ k ≤ 2Cλ k . Given two adjacent distributed games P and P ′ , for any given fixed observation O and initial state ϑ 0 = (x 0 ) T , (v 0 ) T T , the sensitivity is determined by R −1 (P, O, ϑ 0 ) − R −1 (P ′ , O, ϑ 0 ) 1 according to Definition 3. Since in P and P ′ , there is only one payoff function that is different, we represent this different payoff function as the ith one, i.e., f i (·), without loss of generality. Because the observations under P and P ′ are identical, we have (7), and further

Remark 9. Note that this uniformly bounded condition on
because of the identical initial condition x 0 = x ′ 0 . Therefore, we have the following relationship for the sensitivity of Algorithm 1: where we used the fact that the observations v k+1 and v ′ k+1 are the same in the second last equality. Using the update rule in (7), and the fact that there is just one player that has different payoff functions in adjacent games (represented as the ith one), we can further write the above relationship as where we have used the relationship x k = x ′ k that holds for all k ≥ 0 in the last equality. According to Assumption 5, we have Combining the two preceding relations leads to Using Lemma 6, we can obtain that the cumulative privacy budget is always less than T0 k=1 2Cλ k ν k . Hence, the cumulative privacy budget ǫ will always be finite even when the number of iterations T 0 tends to infinity if the sequence According to the obtained result that the cumulative privacy budget is inversely proportional to ν k , we can obtain the second statement from the first statement by scaling ν k proportionally. The result in the third statement can be obtained by specializing the selection of λ k , α, γ k , and ν k sequences.
Note that to ensure that the cumulative differential-privacy budget is finite (an unbounded privacy budget means complete loss of privacy protection), [19] and [32] have to use a summable stepsize (geometrically-decreasing stepsize, more specifically), which, however, also makes it impossible to ensure convergence to the exact desired equilibrium. In our approach, by allowing the stepsize sequence to be nonsummable, we achieve both accurate convergence and finite cumulative privacy budget, even when the number of iterations goes to infinity. In fact, to our knowledge, this is the first time that almost-sure convergence to a Nash equilibrium is achieved under rigorous ǫ-differential privacy even with the number of iterations going to infinity.

Remark 10.
It is worth noting that to ensure the boundedness of the cumulative privacy budget ǫ = ∞ k=1 2Cλ k ν k when k → ∞, our algorithm uses Laplace noise with parameter ν k increasing with time (since we require λ k ν k to be summable while {λ k } is non-summable). Because the strength of shared signal is always v k i , an increasing ν k makes the relative level between noise ζ k i and signal v k i increase with time. However, since what actually feeds into the algorithm is γ k Lap(ν k ), and the increase in the noise level ν k is outweighed by the decrease of γ k (see Assumption 4), the actual noise fed into the algorithm still decays with time, which makes it possible for Algorithm 1 to ensure every player's almost sure convergence to the Nash equilibrium. Moreover, according to Theorem 1, such almost sure convergence is not affected by scaling ν k by any constant coefficient 1 ǫ > 0 so as to achieve any desired level of ǫ-differential privacy, as long as the Laplace noise parameter ν k (with associated variance (σ k i ) 2 = 2(ν k ) 2 ) satisfies Assumption 4.

IV. EXTENSION TO STOCHASTIC AGGREGATIVE GAMES
In this section, we prove that the proposed distributed algorithm can ensure the almost sure convergence of all agents to the Nash equilibrium even when individual agents only have access to a stochastic estimate of their payoff functions. Such stochastic Nash-equilibrium computing problems arise frequently in practical applications like electricity markets [8], [29] and transportation systems [36] where the payoff functions are subject to stochastic uncertainties.
Representing the stochastic version of the payoff functions as f i (x i ,x, ξ i ) for player i, wherex m i=1 xi m , and ξ i ∈ R d is a random vector, we can formulate the stochastic game that player i faces as the following parameterized optimization problem: where the expected value is taken with respect to ξ i . The constraint set K i and the function f i (·) are assumed to be known to player i only.
When the payoff functions are given through the expectation, the pseudo-gradients that individual players can access become stochastic, i.e., the gradient mapping F (x,x) has components In this case, in Algorithm 1, the mapping Accordingly, our privacy-preserving distributed algorithm reduces to: Algorithm 2: Differentially-private distributed algorithm for stochastic aggregative games with guaranteed convergence Parameters: Stepsizes λ k > 0 and α k , and weakening factor γ k > 0. Every player i maintains one decision variable x k i , which is initialized with a random vector in K i ⊆ R d , and an estimate of the aggregate decision v k i , which is initialized as v 0 i = x 0 i . for k = 1, 2, . . . do a) Every player j adds persistent differential-privacy noise ζ k j to its estimate v k j , and then sends the obscured estimate v k j + ζ k j to agent i ∈ N j . b) After receiving v k j + ζ k j from all j ∈ N i , player i updates its decision variable and estimate as follows: c) end

A. Convergence Analysis
Next, we prove that Algorithm 2 can ensure the convergence of the decision vector x k [(x k 1 ) T , · · · , (x k m ) T ] T to the exact Nash equilibrium point x * [(x * 1 ) T , · · · , (x * m ) T ] T , even in the presence of differential-privacy noise ζ k i and stochastic pseudo-gradientF i (x i , v k i , ξ k i ). To this end, similar to [29], we first formalize the noise in pseudo-gradients: Assumption 6. Let F k {ξ 0 , · · · , ξ k } be the family of sigma algebra with ξ k = [(ξ k 1 ) T , · · · , (ξ k m ) T ] T , we have the following relationship almost surely: where µ k is some positive scalar.
Proof. Similar to the proof of Theorem 1, the basic idea is still to apply Proposition 1 to the quantities −v k+1 2 in Algorithm 1 still holds under Algorithm 2, i.e., we still have Therefore, we only characterize (43), we can arrive at For the second term on the right hand side of the above inequality, we can bound it by adding and subtracting (48) Plugging (48) into (47) yields (49) Taking the conditional expectation, given F k = {v 0 , x 0 , . . . , v k , x k }, from the preceding relation we obtain for all k ≥ 0: where we used the assumption thatF By adding and subtracting F i (x k i ,v k ) to the inner-product term, we arrive at The three terms on the right hand side of (51) can be bounded in a similar way to Theorem 1: Plugging (52), (53), and (54) into (51) yields Summing (36) (56) Similar to the derivation in Theorem 1, we have the following relations from (46) and (56) for where Using an argument similar to Theorem 1, we have that all elements of the matrices of A k and B k are summable. Therefore, we have Remark 11. Note that different from [20], [28] which deal with stochastic pseudo-gradients with decreasing variances (by increasing sample sizes), our Algorithm 2 allows the variance (µ k ) 2 to be constant and even increasing with time. For example, when λ k is set as c1 1+c2k , the condition ∞ k=0 (λ k µ k ) 2 < ∞ in Theorem 3 can be satisfied for µ k = c 3 + c 4 k ν with any 0 < ν < 0.5 and positive constants c 1 , c 2 , c 3 , and c 4 .
Remark 12. Using a reasoning similar to Remark 8, we can obtain that the convergence of where all parameters are from Proposition 1 andb k = only increases the value of b k but does not affect its order (still summable), we have that the convergence of all players to the Nash equilibrium is still no slower than the order of O( 1 k ). Moreover, since the evolution of v k i is not affected by the stochasticity inF i (x k i , v k i , ξ k i ) and still follows (29), we have that the decreasing speed of m i=1 v k i −v k 2 still increases with an increase in |ρ 2 |, which corresponds to the second largest eigenvalue of L. Therefore, the decreasing speed of m i=1 v k i −v k 2 to zero increases with an increase in the absolute value of the second largest eigenvalue of L in Assumption 3.

B. Privacy Analysis for Algorithm 2
Similar to the privacy analysis in Sec. III-B, we can also analyze the strength of differential privacy for Algorithm 2: 2Cλ k ν k for iterations from k = 0 to k = T 0 whereC is from Assumption 5. And the cumulative privacy budget is always finite for T 0 → ∞ when the sequence { λ k ν k } is summable; 2) Suppose that two non-negative sequences {ν ′k } and {λ k } have a finite sequence-ratio sum Φ λ,ν ′ ∞ k=1 λ k ν ′k . Then setting the Laplace noise parameter ν k as ν k = 2CΦ λ,ν ′ ǫ ν ′k ensures that Algorithm 2 is ǫ-differentially private with any cumulative privacy budget ǫ > 0 even when the number of iterations goes to infinity; 3) In the special case where λ k = 1 k , α k = 1 k 0.96 , and γ k = .93 (which can be verified to satisfy Assumption 4) ensures that Algorithm 2 is always ǫ-differentially private for any cumulative privacy budget ǫ > 0 even when the number of iterations goes to infinity.
Proof. The derivation follows the proof of Theorem 2, and hence is omitted here.

V. NUMERICAL SIMULATIONS
In this section, we evaluate the performance of the proposed differentially-private distributed Nash-equilibrium computing algorithms using a networked Nash-Cournot game. More specifically, we consider m firms producing a homogeneous commodity competing over N markets, which has been considered recently in [5], [7], [9]. Fig. 1 presents a schematic of the problem involving N = 7 markets (represented by M 1 , · · · , M 7 ) and m = 20 firms (represented by circles). In the figure, an edge from circle i to M j means that firm i participates in market M j .
We consider the setting where a firm can only see partial decision information of the network. Namely, every firm can only communicate with its immediate neighbors and no central mediator exists which can communicate with all firms. As in [5], [7], we allow firms to communicate with their immediate neighbors to share their production decisions. In the considered scenario, we use x i ∈ R N to represent the amount of firm i' products. Note that a firm i is allowed to participate in 1 ≤ n i ≤ N markets, and if firm i does not participate in market j, then the jth entry of x i will be forced to be 0 all the time. So a firm participating in 1 ≤ n i ≤ N markets will have n i nonzero entries in the production vector x i . For the convenience of bookkeeping, we use an adjacency matrix B i ∈ R N ×N to describe the association relationship between firm i and all the markets. More specifically, B i has zero off-diagonal elements and its (j, j)th entry is 1 when firm i participates in market j, otherwise, its (j, j)th entry is zero. Every firm i has a maximal capacity for each market j it participates in, which is represented by C ij . Denoting C i [C i1 , · · · , C iN ] T , we always have x i ≤ C i . Represent B as B [B 1 , · · · , B N ]. It can be seen that Bx ∈ R N = N i=1 B i x i represents the total product supply to all markets, given firm i's production amount x i . As in [7], the commodity's price in every market M i follows a linear inverse demand function, i.e., it is a linear function of the total amount of commodity supplied to the market: whereP i and χ i > 0 are constants and [Bx] i denotes the ith element of the vector Bx. It can be seen that the price decreases with an increase in the amount of supplied commodity. We let p [p 1 , · · · , p N ] T represent the price vector of all markets, which can be verified to satisfy

whereP
[P 1 , · · · ,P N ] T and Ξ diag(χ 1 , · · · , χ N ). The total payoff of firm i can then be expressed as p T B i x i . Firm i's production cost is assumed to be a strongly convex, quadratic function  Therefore, firm i's local objective function, which is determined by its production cost c i and payoff, is given by And it can be verified that the gradient the objective function is . It is clear that both firm i's local objective function and gradient are dependent on other firms' actions.
In the implementation, we consider N = 7 markets and 20 firms. Since no firm can communicate with all the other firms, we generate local communication patterns randomly, with the interaction graph given in Fig. 2. The maximal capacities for firm i (elements in C i ) are randomly selected from the interval [8,10]. Q i in the production cost function is set as νI with ν randomly selected from [1,10]. q i in c i (x i ) is randomly selected from a uniform distribution in [1,2]. In the price function,P i and χ i are randomly chosen from uniform distributions in [10,20] and [1,3], respectively.
To evaluate the performance of the proposed Algorithm 1, for every firm i, we inject differential-privacy noise ζ k i in every message it shares in all iterations. Each element of the noise vector follows Laplace distribution with parameter ν k = 1 + 0.1k 0.2 . We set the stepsize λ k and diminishing sequence γ k as λ k = 0.1 1+0.1k , α k = 0.1 1+0.1k 0.95 , and γ k = 1 1+0.1k 0.8 , respectively, which satisfy the conditions in Theorem 1 and Theorem 2. In the evaluation, we run our algorithm for 100 times and calculate the average as well as the variance of the  Fig. 3. Comparison of Algorithm 1 with the existing distributed Nashequilibrium computation algorithm by Koshal et al. in [5] (under the same noise) and the existing differential-privacy approach for distributed aggregative games by Ye et al. in [19] (under the same privacy budget ǫ).
gap x k − x * between generated iterate x k and the Nash equilibrium x * as a function of the iteration index k. The result is given by the red curve and error bars in Fig. 3.
For comparison, we also run the existing distributed Nashequilibrium computation algorithm proposed by Koshal et al. in [5] under the same noise, and the existing differentialprivacy approach for networked aggregative games proposed by Ye et al. in [19] under the same cumulative privacy budget ǫ. Note that the differential-privacy approach in [19] uses geometrically decreasing stepsizes (to be summable) to ensure a finite privacy budget, but the fast decreasing stepsize also leads to the loss of guaranteed convergence to the exact Nash equilibrium. The evolution of the average error/variance of the approaches in [5] and [19] are given by the blue and black curves/error bars in Fig. 3, respectively. It is clear that the proposed algorithm has a comparable convergence speed but much better accuracy. Based a similar setup, we also test the proposed Algorithm 2 when individual players only have access to a stochastic version of the payoff functions and pseudo-gradients. More specifically, we add Gaussian noise of zero mean and unit variance in every dimension of the pseudo-gradient vector F i (x k i , v k i ). The differential-privacy noise still follows Laplace distribution with parameter ν k = 1 + 0.1k 0.2 . The stepsize λ k and diminishing sequence γ k are still set as λ k = 0.1 1+0.1k , α k = 0.1 1+0.1k 0.95 , and γ k = 1 1+0.1k 0.8 , respectively, which satisfy the conditions in Theorem 3 and Theorem 4. The result is given by the red curve and error bars in Fig. 4. For comparison, we also run the existing distributed Nashequilibrium computation algorithm proposed by Koshal et al. in [5] under the same noise, and the existing differentialprivacy approach for networked aggregative games proposed by Ye et al. in [19] under the same cumulative privacy budget ǫ. The evolution of the average error/variance of the approaches in [5] and [19] are given by the blue and black curves/error bars in Fig. 4, respectively. It is clear that the  Fig. 4. Comparison of Algorithm 2 with the existing stochastic distributed Nash-equilibrium computation algorithm by Koshal et al. in [5] (under the same noise) and the existing differential-privacy approach for distributed aggregative games by Ye et al. in [19] (under the same privacy budget ǫ).
proposed algorithm has a comparable convergence speed but much better accuracy.

VI. CONCLUSIONS
Although differential privacy is becoming the de facto standard for publicly sharing information, its direct incorporation into mediator-free fully distributed aggregative games leads to errors in equilibrium computation due to the need to iteratively and repeatedly inject independent noises. This paper proposes a fully distributed Nash-equilibrium computation approach for networked aggregative games that ensures both accurate convergence to the exact Nash equilibrium and rigorous ǫdifferential privacy with bounded cumulative privacy budget, even when the number of iterations goes to infinity. The simultaneous achievement of both goals is a sharp contrast to existing differential-privacy solutions for aggregative games that have to trade convergence accuracy for privacy, and to our knowledge, has not been achieved before. The approach can also be extended to stochastic aggregative games and is proven able to ensure both accurate convergence to the Nash equilibrium and rigorous differential privacy, even when every player's stochastic estimate of the pseudo-gradient is subject to a constant or even increasing variance. Numerical simulation results confirm that the proposed algorithms have a better accuracy compared with existing approaches, while maintaining a comparable convergence speed.