Differentially Private Equilibrium Finding in Polymatrix Games
Authors: Mingyang Liu
Gabriele Farina
Asuman E. Ozdaglar
Venue: ICLR 2026 Poster (2026)
Keywords: Polymatrix Game
Differential Privacy
Primary area: learning theory
TL;DR: Simultaneously achieves high accuracy and low differential privacy budget in computing the equilibria of polymatrix games

Abstract: We study equilibrium finding in polymatrix games under differential privacy constraints. Prior work in this area fails to achieve both high-accuracy equilibria and a low privacy budget. To better understand the fundamental limitations of differential privacy in games, we show hardness results establishing that no algorithm can simultaneously obtain high accuracy and a vanishing privacy budget as the number of players tends to infinity. This impossibility holds in two regimes: (i) We seek to establish equilibrium approximation guarantees in terms of Euclidean \emph{distance} to the equilibrium set, and (ii) The adversary has access to all communication channels. We then consider the more realistic setting in which the adversary can access only a bounded number of channels and propose a new distributed algorithm that: recovers strategies with simultaneously vanishing \emph{Nash gap} (in expected utility, also referred to as \emph{exploitability}) and \emph{privacy budget} as the number of players increases. Our approach leverages structural properties of polymatrix games. To our knowledge, this is the first paper that can achieve this in equilibrium computation. Finally, we also provide numerical results to justify our algorithm.

Published as a conference paper at ICLR 2026
DIFFERENTIALLY PRIVATE EQUILIBRIUM FINDING IN POLYMATRIX GAMES
Mingyang Liu, Gabriele Farina & Asuman Ozdaglar LIDS, EECS Massachusetts Institute of Technology Cambridge, MA 02139, USA (1iumy19 9, gfarina, asuman (aammannemmttt.. fmim..m.........e. emit.edu
ABSTRACT
We study equilibrium finding in polymatrix games under differential privacy con- straints. Prior work in this area fails to achieve both high-accuracy equilibria and a low privacy budget. To better understand the fundamental limitations of differential privacy in games, we show hardness results establishing that no algorithm can simultaneously obtain high accuracy and vanishing privacy budget as the number of players tends to infinity. This impossibility holds in two regimes: (i) We seek to establish equilibrium approximation guarantees terms of Euclidean distance the equilibrium set, and (ii) The adversary has access to all communication chan- nels. We then consider the more realistic setting in which the adversary can access only bounded number of channels and propose a new distributed algorithm that: recovers strategies with simultaneously vanishing Nash gap (in expected utility, also referred to as exploitability) and privacy budget the number of players in- creases. Our approach leverages structural properties of polymatrix games. To our knowledge, this is the first paper that achieve this in equilibrium computation. Finally, we also provide numerical results to justify our algorithm.
INTRODUCTION
Many multi-agent settings are challenging because each participant's action can influence all others. However, in many settings of interest, the interaction is more localized and tractable. Polymatrix games provide a tractable and rich model that can capture such settings (Janovskaja) 1968 Cai et al. 2016 Deligkas al. 2017). In polymatrix games, players engage in pairwise interactions defined by an underlying graph in which nodes represent players and edges model the interaction between the two players connected by an edge. Each player chooses the same strategy in each pairwise game she is involved with, and her utility is the sum of her utilities for each of these games.
In several settings, such security games (De Nittis al. 2018) and financial markets (Evangelista et al. 2022 Donmez et al. (202)), the players' utility functions may be sensitive and need to be kept private by the players as they update their behavior toward equilibrium. Consider, for instance, decentralized bilateral trading network. Here, players are traders, actions represent pricing strategies, and graph edges denote trade relationships. While players aim reach market equilibrium to maximize profit, their specific utility matrices, which encode sensitive reservation prices or private valuations, must remain confidential to prevent exploitation in future bargaining.
Typically. there are two approaches for finding equilibrium while keeping the utility functions private: centralized and distributed methods. centralized methods, the players send their utility functions to trusted central server (Kearns et al.) 2014) Rogers& & Roth [004]] Cummings et al.) 2015). When trusted central server is infeasible, the only viable option for computing equilibrium is for the players to use distributed algorithm where they make local computations and exchange information with their neighbors. Throughout the process. a malicious adversary may inspect the communication channel and infer the utility function, which might reveal sensitive information about individual preferences. To keep the computation secure and prevent the leakage of sensitive information, tools from differential privacy (DP) (Dwork et al. 2006) can be employed.

---

Published as a conference paper at ICLR 2026
Several authors have considered the question of differentially private equilibrium computation in games. However, previous work was either unable to achieve high accuracy and low differential privacy budget simultancously (Ye al., 2021; Wang et al. 2022), only achieved weaker form of differential privacy where the adversary is still able to infer part of the private information (Wang & Wang & Nedič 2024). We defer broader discussion on prior work to Appendix
Başar 2024
CONTRIBUTIONS AND TECHNIQUES
In this paper, we study the problem of distributed, differentially private equilibrium computation in polymatrix games. We build on the notion of adjacent distributed optimization problem defined in Huang et al. (2013). In particular, given a polymatrix game G we define adjacent games as those that differ from 9 on the utility function of single player (see Figure (a) and Definition 2.1). Then, once the algorithm for equilibrium finding is differentially private, an adversary cannot distinguish, with high probability from his observations, the original game from any other games that are adjacent to Hence, when differential privacy holds, the adversary is unable to determine the utility function of any player with high confidence, ensuring the equilibrium computation process
Impossibility. Using this concept of adjaceney, we begin by showing that finding an approximate equilibrium with arbitrarily small differential privacy guarantees can be impossible, depending on the desiderata imposed on the process. Specifically, we show that if the adversary can access an arbitrary number of communication channels, the target accuracy metric of interest is the Euclidean distance from the equilibrium set, then distributed computation of high-quality equilibria while providing vanishing privacy guarantees is impossible. In other words, one will inevitably suffer either a low approximation of the equilibrium, or low level of privacy (high privacy budget). While these negative results serve as guardrails to guide algorithm design, it is important to realize that they do not preclude all paths to meaningful results. Indeed, it is important to realize that Euclidean distance the equilibrium set is only one of the set of possible quality metries for measuring equilibrium approximation. Another metric is Nash gap or exploitability, meaning how close a strategy is to equilibrium in terms of expected utility rather than metric distance to the equilibrium set in strategy space. This is particularly relevant in practice, where potential gains from deviation are more important than proximity in strategy space.
Positive Results. Finally, we complement our negative result with a positive result regarding
exploitability guarantees, corroborated by experiments in Appendix [ In particular, we propose a new distributed algorithm for computing a coarse correlated equilibrium (see Figure (b)). As is typical in the differential privacy literature, our algorithm involves each player communicating a noisy version of their strategy to their neighbors and updating their strategy using a regularized proximal gradient step. A key novelty of the algorithm to scale the regularizer proportional the harmonic mean of the degrees divided by the degree of the player. The inverse proportionality with the degree ensures that more regularization is introduced for players with a lower degree (since a low-degree player's is gradient is more sensitive to variations in the utility matrices of its neighbors).
High-Level Intuition. We propose Algorithm I which simultancously achieves low exploitability and low DP budget, with guarantees that improve as the number of players N increases. Moreover, the algorithm achieves that whenever the associated graph with the polymatrix game is sparse or dense, by imposing an adaptive regularizer on players' utility functions. When the graph associated with the polymatrix game is sparse, we leverage the fact that for most nodes that are least of distance / to the edge of the changed utility matrices, changes in the utility matrices between adjacent polymatrix games have minimal impact on them during the first updates. In contrast, when the graph is dense, additional regularization, which is inversely proportional to the players' degrees, stabilizes the updates of players with low degrees so that the adversary's 's observation in two adjacent games will be similar. For players with high degrees, the aggregative nature of the utility function in polymatrix games mitigates the effect of changes in the utility matrices.
2 PRELIMINARIES
We now review several key concepts related to differential privacy and polymatrix games.
2

---

Published as a conference paper at ICLR 2026
P1
Adremer
Achenam
P1
P2
P3
P4
8
D
P1
Access to Partial Comm. Channels & Low Exploitability
Access to Full Comm.
Low Euclidean Distance to the Equilibrium
Channols X
P3
P4
(b)
Figure 1 (a): An illustration of adjacent polymatrix games defined in Definition 2.1 represent the players, and the lines represent the edges of the polymatrix game. The two games differ the bluc/orange edge, and the adversary cannot differentiate these two games with certainty from his observations. 2 on an edge means that the communication channels between those two players can be accessed by the adversary.
The nodes
Figure [ (b): The illustration of results: the impossibility when the adversary can access all commu- nication channels showed in Le the impossibility achieve low Euclidean distance showed in Lemma 3.2 (middle), and the positive results showed in Theorem 7.1 (right).
Basics. For any integer N > 0. let [N] = (1,2,3,.... N.I..,,,.,N For any vector æ, we use
||>||p to denote its p-norm. By default, ||œ||| denotes the Euclidean norm ||l|||- The symbol A {a E [0, 1]":: E H; 1} denotes the (n 1p-11 1) dimensional probability simplex. Moreover, for any discrete set S, we can define A as the probability simplex over S, with each index as the element in S. Hence, [N N For any convex set C, use Projc (æ²) = argmin || x a²| to denote the projection to from a vector x' with respect to Euclidean distance.
Polymatrix Games.
Polymatrix games be written tuple
g = (IN), E, (Adieei
(Us (Ursha
where
[]] is the set of players.
E is the set of edges, where each (i, E indicates that players i, interact with each other.
(As (Aihee)) is the set of players' action set, which means player i E [N] chooses actions in A,.
Let A == max |Ail be the size of the largest action set.
U2i e 1,,,, 1jAxAA is the utility matrix between player (i.j) E E.
For each player í E [N], we denote with the symbol N(ti) = [N]: (i.j) E E} the set of her neighbors. Then, when each player & [N] chooses her strategy T& E A., the utility of player is pV EjeN(o n. UZ5T Moreover, when the strategy profile of all players is (TI, T2, (T)) we can define the gradient of player i's strategy with respect to her loss function (the negative of utility function) as g," == N(0 EjEN()) U.
'Typically the definition of player i's utility is E)eN()) म. Uty However, to ensure that the function and its gradient are bounded by constants regardless of the game size, we divide it by [V)),, which aligns with the DP literature (Huang et al. 2015| Wei et al. 2020 Ye et al. 202T) Note that such modification will not change the equilibrium.
3

---

Published as a conference paper at ICLR 2026
Differential Privacy. We adopt the notion of adjacency in Huang et al. (2015). For any two polymatrix games, they are adjacent to each other if and only if they only differ from the utility matrices on single edge. An intuitive illustration can be found in Figure [ (a). Formally,
Definition 2.1 (Game adjacency), Given two polymatrix games g = (IN), E, {Ai (Ar) {U (UL ) and g' = ([N'), E (AIhENN : (U1s) (s))E:) they are said to be adjacent, indi- cated as g' if
1. N = N', E E' and A, = A for any E [N]; and
2. except for an edge (i.j) E E, Uv U and Uy U3 for any (V.5")
E (1.
Consider generic iterative algorithm for finding equilibrium in polymatrix games, and denote with @ the space of all possible internal states of the algorithm at any time. Then, for a given polymatrix game G. when the algorithm runs & > 0 timesteps, it will generate intermediate variables O which are called executions of the algorithm. Of is the (-fold Cartesian product of @ with itself. Due to the randomness in the algorithm, this will result in distribution Pg over Oc. Moreover, there is adversary with access the communication channels between the players. Therefore, for any execution 0 E O', the adversary can observe (0) = ) ....,," .(") =: o E O', where O is the space of all observations at a single timestep. Hence, we can define the (e, -ddifferenni privacy ((e, 6)-P) as follows.
0 = (o 2(2) ..... ,((t))
Definition 2.2 ((c, Diffferrettia Privacy). For an e 2 and 5 2 0, an iterative distributed algorithm for finding equilibria is (e, 6) d)diifferentially private, if and only if for any two adjacent polymatrix game G' any timestep
and any set of observations S _ 05,
Pg (10: (0) E SS) S P (10: (g) E 5.)
(I)
Intuitively, Definition 2.2 guarantees that the algorithm will generate similar observations while deployed on adjacent games. Therefore, the adversary cannot differentiate G, g' from the observation
so he cannot infer the utility matrices with certainty from observations.
In this paper, we consider generalization of Definition 2.2 Rényi differential privacy (Rényi DP)
(Mironov 2017). The distribution of observations up to timestep t can be written as 14 (o) = Pg (Rg (o)) for o E O' and thus we can define the (a,, c)-Réy DP as follows.
(t)
Definition 2.3 ((a,c) c))-ényi Differential Privacy). For a > and 2 O, an iterative distributed algorithm for finding equilibria is (a, c)-Rén differentially private, if and only if for any two adjacent polymatrix game G, g' and timestep t > 0,
(t) Pg (0)
(0 Da (ng 16
(0)
log E
(1) G'
(1) (1g (o)
SC
where is also called the privacy budget. Definition 2.3 can be extended to = 1 and too by defining D1 (..-) lim 1+ Da (-.-). which is KL-divergence (Mironov 2017). and Doo (., = lima Da (-..). Moreover, Rényi DP can be converted to (c, 5)-P according to the following lemma from Mironov (2017).
Lemma 2.4. If an algorithm satisfies (a, R)-ényi DP for a then for any 8 E (0, the algorithu also satisfies
( log(1/5), )-DPP. Moreover, (oc, R)-Rné DP is equivalent (e, DD-
In light of Lemma 2.4 we focus on Rényi DP throughout the remainder of the paper.
3 NECESSARY CONDITIONS FOR ACHIEVING HIGH ACCURACY AND DIFFERENTIAL PRIVACY SIMULTANEOUSLY
In this section, we discuss the necessary conditions to achieve differential privacy and high accuracy in approximating equilibria in polymatrix games. Specifically, we will show that: (i) the adversary should not have access to all communication channels; and (ii) the accuracy metric cannot be the Fuclidean distance to the equilibrium. If even one of the conditions is violated, one can find constant
4

---

Published as a conference paper at ICLR 2026
cu 0 so that when N is large enough, there exists polymatrix game with N players that the approximation error Ç and differential privacy budget cannot be guaranteed to be smaller than Co simultaneously in that game. The results are summarized in Figure (b).
All hardness results in this section are constructed with zero-sum polymatrix games (Cai et al. 2016), special class of polymatrix games, that is, polymatrix games ([N], E, {A; SEIN (U
( (L,))E) such that, for any strategy profile π, EiE[N] EjeN(o) मH U, = O. Since zero- sum polymatrix game is subclass of general-sum polymatrix game, the hardness result also holds for general-sum polymatrix games automatically.
One can see that when U -,,, for any (i, E F,, the polymatrix game is zero-sum. Since the coarse correlated equilibria (CCE) in zero-sum polymatrix games collapse to NE (Cai et al. 2016)) an algorithm that approximates CCE will approximate NE. Therefore, without loss of generality, in this section, we assume the algorithm will approximate the NE instead of CCE.
3.1 NECESSITY OF LIMITED ADVERSARIAL. CHANNEL ACCESS
Assume that there is distributed algorithm for finding equilibrium with the following guarantees of accuracy and privacy. In any polymatrix game G with players, the algorithm outputs a strategy profile with distribution lág the observations. Here we omit the timestep superscript on l4g to emphasize that it is the distribution over all observations till termination of the algorithm. Then, there exists parameter a 2 such that the algorithm satisfies the following accuracy and privacy guarantees in any N --llayer game G:
Accuracy: Σ
E
max (TT 9..99") sS REAA
(3)
Privacy: Do Hg:) Se VG ~~ G'.
(4)
When C (T, i. 9.7 < Ç for every player i [N]. the strategy profile π is called an <-approximate NE. The accuracy metric maxa, CA (TT - ". also known as exploitability. measures how much player can benefit herself by unilaterally deviating from the current strategy profile π,, which should be when π is the equilibrium. Exploitability provides a weaker notion of accuracy than Euclidean distance the equilibrium: if π is close an equilibrium in Euclidean distance, then its exploitability must be small, but the reverse need not hold.
In the following, we will show that if the adversary has access all communication channels, it is impossible to achieve low exploitability Ç and low privacy budget simultaneously.
Lemma 3.1. For any N > 12, there exists two zero-sum adjacent polymatrix games with N players so that for any algorithm guaranteeing (3) and (4), we have
3 exp (-2c)
2 min
(5)
112
112
Lemma 3.1 implies that even when N goes to infinity, once <
112 we have 6 log To illustrate
the proof of Lemma 3.1 we can first consider relaxation of 33. E max (T, ;. S
Ç holds for any player i E [N], then we can construct two adjacent polymatrix games, such that the approximate equilibrium any player i E [N] converges to differs much in two games, once the accuracy is lower than Ç in both games. Then, the adversary can distinguish those two games by computing the approximate equilibrium from his observations. While back to the original condition (3). we can use the pigeon-hole principle to construct a set of zero-sum polymatrix games, such that there exists two adjacent polymatrix games satisfying E [max; (T, T. R..9.) O()) sinultaneously for some player E [N]. The full proof is postponed to Appendix B. where we also provide a lower bound for (c, DDDP.
3.2 NECESSITY OF ACCURACY METRICS BEYOND EUCLIDEAN DISTANCE
Moreover, even if the adversary only has access to the observation of single player, it is still impossible to find an accurate approximation of the equilibrium, in terms of Euclidean distance to the equilibrium, while guaranteeing privacy.
5

---

Published as a conference paper at ICLR 2026
Let A be the of Nash equilibrium (NE) of player i in zero-sum polymatrix game. Moreover, Hgg;; denotes marginal distribution on the observation of player given the joint distribution μıg on all observations. Then, consider an algorithm with the following guarantee in any N N-player game g. There exists parameter a 2 1 such that the algorithm satisfies that
Accuracy:
E
||: Projea.- (T:)) s
(6)
N
N
Privacy:
Do (o),)) Se Vg ~ G'.
(7)
N
(6) guarantees that the output strategy of the algorithm is close to the set of NE, in terms of Euelidean distance. 7 states that for any two adjacent games G G", the Rényi divergence between the distribution of player i's observations is small. This implies that by accessing the communication channel of player the adversary cannot distinguish G and G', so he cannot speculate the utility matrices.
Lemma 3.2. For any 2 8, there exists two zero-sum adjacent polymatrix games with players so that for any algorithm guaranteeing (6) and (7). then
< 2 min 3 exp 4c).
1
(8)
16
Lemma 3.2 implies that once S
1 the average differential privacy budget > log 6
4 even when
N goes to infinity. The proof of Lemma 3.2 based on the following observation: for a two-player
0
zero-sum game with row player's utility matrix
0 1 when row player's strategy changes from
(0.51, 0.49) (0.49, 0.51), the column player's best-response changes from (0, 1) (1, In this way, for two adjacent polymatrix games with the utility matrices on the edge (i.j) changes, player i, equílibria will also change. Then, by careful construction of the utility matrices in the game, such changes in equilibria will gradually propagate to the rest of the players. Lastly, we can prove that two adjacent games with the equilibrium differs much, is impossible to compute the equilibria accurately while the communications between players (the adversary's ' observations) are similar. The full proof can be found in Appendix B.2
4 METHODS
In this section, we will propose an iterative algorithm for finding coarse correlated equilibrium (CCE)
in general-sum polymatrix games (Moulin & Vial 1978). As we will show in Section this algorithm guarantees differential privacy under the conditions required in Section 3 We start by recalling well-known connection between regret and convergence to CCE.
For an iterative algorithm that produces strategy profile N (1) at timestep E [T]. its average strategy is the <-approximate CCE of a polymatrix game G with players if and only if for any player i [N), maxa,
Proposition 4.1.
g ..; (1)
7. - S.
By picking timestep E [T] uniformly at random and all players will play according to (+), the expected increase of utility when player deviates to मे is T E gf
7
Let g = g. (0) A: as the identity matrix with index A, A,, and N (0, I2IA,) as the isotropic normal distribution over A, with zero mean and o² variance. Then, the algorithm is as follows: for
any player E [N], at each iteration t E 10, T 1, for some T > (iT (0) is initialized
as the uniform distribution over A,), player i will sample random noise n (e) N/ (0,0 (1.)).A.). (t)
Then, she will broadcast her strategy कं plus the noise her neighbors. After receiving the noisy strategies from her neighbors, she will do one step of the projected gradient descent with the gradient (t)
g; learning rate 7/ and weight-decay parameter 7;. The complete algorithm is shown in Algorithm

---

Published as a conference paper at ICLR 2026
Algorithm 1 Differentially Private CCE Computation in Polymatrix Games
Input: Player index i
Initialize TT (()) uniform distribution over A,
) Initialize 73 f- (N) (
Let = No (Ei pooo
be the harmonic mean of players' degrees
for t = 0, 1, .... do
Sample n N 00,
Broadcast π + n, to neighbors j E (N))
for j (i) do
(1) and compute 70 + Projs (T)) + m Receive + j end for Gradient g: (ol EjEN(o) 3
(1+1) < argmin
Tc. (T.. (11) + [//TTTT|
+ 77
1
=1(0)
(9)
REAA;
{ [We remark that (9) is equivalent to (1+1) t Projam
end for
The intuition of TÜ 2 being inversely proportional to [i( is that for players with fewer neigh- bors, her gradient is sensitive the variation of single utility matrix, so more additional regularization (larger decay rate) required to hide the difference of x; between adjacent games.
Moreover, to avoid observations from two adjacent games from increasingly diverging updating
more timesteps, the gradient descent of x; ((+1) starts from Z instead of π (6) However, we need to pay the price of suffering additional approximation error caused by the noise added to 7(".
Remark 4.2. Let (t) = (n1 n ....,,.. ....,n??) In Algorithm | the execution of the algorithm at timestep is (t) nn()). Then, Rg (17(0), ((()),) = (ULEIN) ( + n, +nn+))²
5 CONVERGENCE ANALYSIS
This section will show the convergence of Algorithm iin general-sum polymatrix games. Theorem 5.1. Consider Algorithm ! Let = max |Ag. The update-rule can achieve the following guarantee in any polymatrix game. For any T > O, player i E [N] and strategy मı E A,
N
(g.
1041)
1 - m.)
((+1)
NT
+ A 0²
227
To
A
27/ (NV) 4/9 log N (N) log N
(10)
7/T
2n
The proof sketch and the proof are postponed to Appendix C Theorem 5.1 limplis that the average strategy converges to coarse correlated equilibrium (CCE). Besides, it is noteworthy that when applying noise for better differential privacy guarantees, i.e. larger a, the convergence rate will worsen since the gradients provide less information.
With fixed learning rate 17 and noise the accuracy increases when the number of players N grows, while previous work (Gade et al., 22000) Ye et al. [221]] Wang et al., [022 Shakarami et al. 2022) cannot, enabling achieving high accuracy and low differential budget simultaneously (see Section 7)
7

---

Published as a conference paper at ICLR 2026
6 ANALYSIS OF DIFFERENTIAL PRIVACY
In this section, we show that Algorithm| 1 can simultaneously guarantee differential privacy. Since Lemma 3.1 states that the adversary should not have access to all communication channels, we will bound Rényi DP when the adversary only has access to the communication channel of single player,
(t) Le.. Rényi divergence of Pg the marginal distribution of M4g over (T(()) + + (n..)) t
s=1 According to
the composition rule of Rényi differential privacy (Mironov 2017), when the adversary has access
multiple communication channels, the privacy budget is the product of the number of communication channels he has access to, and the privacy budget when he only has access to a single communication channel. Effectively, this models a scenario where the communication network is largely reliable.
We break the analysis into two cases: dense graphs and sparse graphs. In the following, will show that the privacy budget of Algorithm | is proportional to r/² T but inversely proportional to o². Intuitively. when the learning rate 17 larger or the algorithm runs more timesteps, the observation will diverge more due to the different utility matrices. But when we add more noise, i.e. larger it
will be harder to determine which distribution a sample न. n. (t) is from.
Theorem 6.1. Consider Algorithm ! and any two adjacent polymatrix games g.9' G' that differ at (U1, U2) Let dist(i,j) j) be the length of the shortest path between players i, which is so when i. are not connected. The update-rule guarantees the following for any > 0 and player E [N].
Da Pggi MG's
(T) (T)
min
T
(11)
where
16A3 (log N2
4A
(12)
(N)
4/9
N
2A
N
(T > min {dist(i, u1), dist(i, o2)))
(13)
N
The proof sketch and complete proof can be found in Appendix D Theorem 6. iimpliss that when the graph is dense, i.e. N 2 No for some p E 1), will be sublinear in N. When the graph is sparse, i.e. A Amaax = max [W(i) is constant, will be small since the most players will be distant from 1i, V/ (approximately Ω (log N). Therefore, even with a fixed learning rate r and noise a, the privacy budget will decrease as the number players grows, which is in stark contrast to previous work (Gade et al., 2020 details are deferred to Section|/
Ye et al. 2021 Wang et al. 2022 Shakarami et al. 2022). The
TRADE-OFF BETWEEN ACCURACY AND DIFFERENTIAL PRIVACY
According to Theorem 3.1 and Theorem 6.1 by picking 7, a and T carefully, when the number of players grows to infinity, we may obtain zero privacy budget while converging CCE.
Theorem 7.1. Consider Algorithum 7 with - and any adjacent polymatrix games G, g that differs at v2), The update-rule guarantees the following,
N max (1
Σ
E
(97
(1+1)
(1+1)
++ 1
7A3/2
1
2nv AT
3/2 VT
(14)
T/T
T
(N) 1/9
log N
(N) 1/9
log N
N Σ
Da
(T)
< am² min ( $
(15)
N
8

---

Published as a conference paper at ICLR 2026
The proof is simply substituting the values of into Theorem dense, i.c. N NP for some p > O, take 17 = T$1/3 T
5.1 and Theorem 6.1
When the graph
N
then
(log (log Ny
ΣΣΣB NT 1=
B Kor ((12)
T (((1)) m.) o
(log N)
N4p/27
where the O notation takes A constant. Simultaneously, the differential budget guarantees that
(log.)
2//33
E Dr
(T) (T) Us Ug Po
S
N4p/27
Therefore, when the graph is dense, the accuracy and differential privacy budget of Algorithm | would both be better as the number of players increases.
Consider when the graph is sparse, i.e. .N Nmmax is constant. If Amax 2, let 1j
T
(1 logx log N) logamaz N, then S No 1,
4A since at most Nmax TT I
2(
Nog players satisfy
2N
min [dist(i, v1), dist(i, v2)3 T. If max
2 for any T > Therefore.
T
Σ Σ
E (
(9
((
,,, (((11)
(o+1) - m.> 0o
NT
(log N)
1=
Σ
Da
(T) ( Pgg P
a (log N/3/33
N
Compared to previous work (Gade et al. 2022), the main contribution of Theorem 7.1 is that for any desired accuracy Ço > 0 and differential privacy budget 6o > O. we can ensure our accuracy and differential privacy budget to be lower than So, Eo simultancously when N is large enough. In contrast, to keep accuracy smaller than Co. previous work will suffer a differential privacy budget larger than cg, no matter how large N is, and vice versa.
2020
Ye al. 2021 Wang er al. 2022
Shakarami et
We emphasize that Theorem bounds the differential privacy budget when the adversary access a single communication channel. By the composition rule for Rényi differential privacy (Mironov 2017). see the beginning of Section the overall privacy budget scales linearly with the number of channels the adversary accesses, specifically, equals the number of accessed channels times the bound in Theorem 7.1
In the non- non-private setting, the noise a and the additional regularization 7 can be removed. Conse- quently, the algorithm reduces Online Mirror Descent with Euclidean norm regularizer (Hazan
et al. 2016), achieving a convergence rate of O 1/T + .1). However, in the private setting, the terms
(log N/ represent the error incurred within T iterations, rather than the convergence rate itself. Given that T the algorithm maintains rapid convergence rate.
O
[log NJ 2
and O
(log NyT and T (1 logN log N) log N respectively,
5p99
EXPERIMENTS
-;, of our method and In this section, we evaluate the exploitability ( (mxx; AAA. (x; baseline algorithm obtained by adapting Huang et al. (2055) from an single-objective optimization formulation to the game setting. As shown in Figure 3 and Figure 4 under the same differential- privacy budget, our method consistently attains lower exploitability. Moreover, as the number of players increases, the exploitability of our method decreases, whereas the baseline's 's does not.
Figure 3 shows the results for an Erdös Erdös-Rényi graph, where each pair of players interacts with probability p.
Figure 4 displays the results for graphs with a clustered topology. Specifically, players are randomly divided into [1/p] clusters. All pairs of players within the same cluster interact with one another, while pairs of players belonging to different clusters interact with probability 10p. This setup models scenarios characterized by dense within-cluster interactions. Additional experimental results are provided in Appendix E

---

Published as a conference paper at ICLR 2026
Dense Graph
2.8 x 10
Exploiaability
10
2.7 x 10
2.6 10-!
2.6 x 10
10
2.5 x 10
2.2 10
2.4 x 10
2
Number of players (A=5)
Number players (A=10)
Ours
Baseline
p=0.1
p=0.3
p=0.5
Figure 3: We evaluate the exploitability of our algorithm and a baseline on dense graphs. Each node (player) connects another node independently with probability p. and duplicate edges then removed. All players have action sets size A. Both the baseline and our method are run under the same differential privacy budget.
Dense Graph
2.9 X
2.8 x 10
2.8 X 10
Explotaabiig
2.7 10
2.7 x 10
2.6 x 10-1
2.5
2.4
10
2.5 10
2.3
2.4 x
2.1 x
10
2
27
2
Number of players (A=5)
Number players (A=10)
Ours
Baseline
p=0.1
p=0.3
p=0.5
Figure 4: The exploitability of our algorithm and the baseline for dense graphs with cluster topology. All players have action sets of size A. Both the baseline and our method are run under the same differential privacy budget.
CONCLUSION AND LIMITATIONS
This paper shows necessary conditions find the equilibria of polymatrix games with DP guarantees. Moreover, we propose an algorithm to find the equilibria with DP guarantees under the conditions. Moreover, the number of players the game increases, the algorithm will gradually achieve perfect accuracy and DP guarantees. Lastly, we provide empirical evidence to justify the algorithm in Appendix E Currently, our framework specified for polymatrix games. Therefore, an interesting future direction is to extend it other games, such as normal-form games and extensive-form games.
LCKNOWLEDGEMMET
The authors thank the anonymous reviewers and the area chair for their helpful feedback. M.L. was supported by the MathWorks Fellowship. A.O. and G.F. were supported in part by the ONR grant N060142512296. G.F. was additionally supported by CCF-2443068 and an AI2050 Early Career Fellowship.
10

---

Published as a conference paper at ICLR 2026
10 ETHICS STATEMENT
This paper presents work that aims to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
11
REPRODUCIBILITY STATEMENT
The proofs are presented in Appendices B to
12 USE OF LARGE LANGUAGE MODELS
In this paper, we use large language models (LLMs). For example, by correcting grammatical errors, generating illustrative images (Figure T. and producing code.
REFERENCES
Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Interna- tional Conference on Machine Learning (ICML), 2017.
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap. In Conference on Learning Theory (COLT), 2023.
Digvijay Boob and Cristóbal Guzmán. Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems. Mathematical Programming, 204(1); 255-297, 2024.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum polyma- trix games: generalization of minmax. Mathematics of Operations Research, (1(2)6648-655, 2016.
Rachel Cummings, Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. Privacy and truthful equilibrium selection for aggregative games. Web and Internet Economics: 11th International Conference. WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings 11, pp. 286-299 Springer, 2015.
Edwige Cyffers, Mathieu Even, Aurélien Bellet, and Laurent Massoulié. Muffliato: Peer-to-peer privacy amplification for decentralized optimization and averaging. Neural Information Processing Systems (NeurIPS), 2022.
Giuseppe De Nittis, Alberto Marchesi, and Nicola Gatti. Computing the strategy to commit to in polymatrix games. In AAAI Conference on Artificial Intelligence (AAAI), 2018.
Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul Spirakis. Computing approximate Nash equilibria in polymatrix games. Algorithmica, 77(2)487-514, 2017.
Ahmed Said Donmez, Yuksel Arslantas, and Muhammed O Sayin. Team collaboration vs competition: New fictitious play dynamics for multi-team zero-sum games, In Neural Information Processing Systems (NeurIPS), 2024.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284, Springer, 2006.
David Evangelista, Yuri Saporito, and Yuri Thamsten. Price formation in financial markets: game-theoretic perspective. arXiv preprint arXiv:2202. /416, 2022.
Shripad Gade, Anna Winnicki, and Subhonmesh Bose. On privatizing equilibrium computation in aggregate games networks. IFAC-P,persOmLLine, 53(2):3272-3277, 2020.

---

Published as a conference paper at ICLR 2026
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used univariate continuous distributions. Information Sciences, 149:124-131,200
Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full- cull-information and bandit settings. Neural Information Processing Systems (NeurIPS), 2013.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4)1157-325 2016.
Zhenqi Huang, Sayan Mitra, and Nitin Vaidya. Differentially private distributed optimization. In International Conference Distributed Computing and Networking (ICDCN), 2015.
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Conference Learning Theory (COLT), 2012.
Elena Janovskaja. Equilibrium points in polymatrix games. Lithuanian Mathematical Journal, 8(2):
381-384, 1968.
Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Innovations in Theoretical Computer Science (ITCS), 2014.
Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar. policy-gradient approach solving imperfect-infformtionn games with iterate convergence. In International Conference on Learning Representations (ICLR), 2025.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer (CSF), pp. 263-275 IEEE, 2017.
symposium
H. Moulin and J.-P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. Int. J. Game Theory, 7(3):201-211, September 1978. ISSN 1432-1270. doi: 10. 10.000/00007699900
Abdellah EI Mrini, Edwige Cyffers, and Aurélien Bellet. Privacy attacks in decentralized learning. International Conference on Machine Learning (ICML), 2024.
Erfan Nozari, Pavankumar Tallapragada, and Jorge Cortés. Differentially private distributed convex optimization via functional perturbation. IEEE Transactions on Control of Network Systems, 5(1): 395-408, 2016.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, pirh-ppeffrmance deep learning library. In Neural Information Processing Systems (NeurIPS), 2019.
Ryan M Rogers and Aaron Roth. Asymptotically truthful equilibrium selection in large congestion games. In ACM Conference on Economics and Computation (EC), 2014.
Mchran Shakarami, Claudio De Persis, and Nima Monshizadeh. Distributed dynamics for aggregative games: Robustness and privacy guarantees. International Journal of Robust and Nonlinear Control, 32(9) 5069, 2022.
Jimin Wang, Ji-Feng Zhang, and Xingkang He. Differentially private distributed algorithms for stochastic aggregative games. Automatica, 142:1 10440, 2022.
Yongqiang Wang and Tamer Başar. Ensuring both almost sure convergence and differential privacy in Nash equilibrium seeking directed graphs. IEEE Transactions on Automatic Control, 2024.
Yongqiang Wang and Angelia Nedié. Differentially-privaa distributed algorithms for aggregative games with guaranteed convergence. IEEE Transactions on Automatic Control, 2024.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security, 143454-34699 2020.
12

---

Published as a conference paper at ICLR 2026
Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush R Vashney, Siwei Lyu, and Yiming Ying. Differentially private SGDA for minimax problems. In Conference on Uncertainty in Artificial Intelligence (UAI), 2022.
Maojiao Ye, Guoqiang Hu, Lihua Xie, and Shengyuan Xu. Differentially private distributed Nash equilibrium seeking for aggregative games. IEEE Transactions on Automatic Control, 67(5): 2451 -458, 2021.
Liang Zhang, Kiran K Thekumparampil, Sewoong Oh, and Niao He. Bring your own algorithm for optimal differentially private stochastic minimax optimization. Neural Information Processing Systems (NeurIPS), 2022.
13

---

Published as a conference paper at ICLR 2026
A RELATED WORK
In this section, we discuss prior work specifically targeted at distributed equilibrium computation. We omit a discussion of prior work distributed (single-agent) optimization as it is hardly applicable to our purposes, for several important reasons. For one, distributed optimization with differential privacy guarantee (Huang et al. 2015] Nozari al., 2016 Wei al., 2020 Cyffers et al. [022] Mrini et al., 2024) aims to find the minimum of the weighted sum of players' utility functions. Specifically, the adversary cannot distinguish between two sets of functions that differ only in one player's function based on his observations, as discussed in (Cyffers et al. 2022, Mrini et al., (024). However, distributed equilibrium finding more complex since it aims find the equilibrium point of those utility functions. Furthermore, the target output of the distributed optimization is of constant dimensionality with respect to the number of agents involved in the optimization process, such as the best parameters for neural network (Wei et al., 2020). However, the output's dimension of equilibrium finding scales linearly with respect to the number of agents, since we need to specify the strategy of each individual player.
Online Learning with Differential Privacy. Prior work, IncludingJainn et al. (2012); Guha Thakurta & Smith/ { Agarwal & Singh has studied no-regret learning with DP guarantee, focusing on ensuring that an adversary cannot determine the utility (loss) vector at any single timestep. However, that condition does not imply differential privacy with respect the payoff function itself. For instance, in a two-player Normal-form game, the utility vector at timestep t for player is Um!") where U is the utility matrix and Th is the strategy of player algorithm that reveals Um! (1) + rt("), where n2()) is sampled from a multivariate Gaussian, ensures differential privacy with respect to each individual utility vector. However, consider the case when (+) is sampled uniformly on each axis for any timestep t. By taking the average over all utility vectors, the Gaussian noise cancels out, and will get the average of U's columns. Therefore, U is not differentially private, while each utility vector is still private.
timestep t. In this case, an
Differential Privacy in Minimax Optimization. Yang al. 2022 Zhang et al. (2022) Bassily et al. 2023): Boob & Guzmán (2024) analyze differential privacy in minimax optimization, but their setting differs from ours in several aspects. First, they study two-player zero-sum games, whereas consider multi-player general-sum polymatrix games (a class that subsumes two-player zero-sum). Second, they assume each player's 's utility decomposes as an average of multiple component utilities and aim to prevent an adversary from inferring any single component. This, however, does not protect the average itself, the true game utility, which is precisely what we seek to keep private.
Differential Privacy in Games. Other prior work, including Gade et al. (2020); Ye et al. (201));
Wang al. (2022): Shakarami et al. al. (2022). 2. has focused on finding equilibrium in aggregative games with differential privacy guarantees. However, they cannot achieve accuracy and differential privacy simultaneously (e.g. privacy budget O (c) and accuracy O (t)). In other words, to achieve fixed accuracy, the privacy budget will not continue to decrease while the number of players increases. The reason is that they did not exploit the game's s structure to cancel out the noise imposed during the update. Therefore, accuracy will be harmed when achieving low differential privacy budget by adding a large amount of noise. Furthermore, the privacy guarantee of Wang & Nedič (2024); Waang & Bayar 2024) is weak because the adversary may determine the value of the utility function in small region around the equilibrium point. Therefore, when the utility function is multilinear, such as polymatrix games, normal-form games, and extensive-form games, the adversary can fully determine the utility functions with certainty. Instead, in this paper, we exploit the structure of polymatrix games, whether the associated graph is dense or sparse, to mitigate the impact of the imposed noise, thereby achieving accuracy and differential privacy simultaneously. Specifically, we can achieve privacy budget O to the number of players N and goes to infinity N - co. Details can be found in Theorem 7.1
F[N] and accuracy O <g(N)) where ((N),((N) are monotone functions with respect
14

---

Published as a conference paper at ICLR 2026
B PROOF OF SECTION 3
The section is arranged as follows. For both Lemma 3.1 and Lemma 3.2 we will show that there exists polymatrix game, so that achieving accuracy and (e, 6D- simultaneously is impossible. Then, we further show that achieving accuracy and Rényi DP is impossible by showing that for (é.e)- DP. Because the a-Rényi divergence grows monotonically with respect a (Mironov 2017
B.1 PROOF OF LEMMA 3.1
Lemma 3.1. For any N 2 12, there exists two zero-sum adjacent polymatrix games with N players so that for any algorithm guaranteeing (3) and (4). we have
eep (-2e)
2 min
(5)
112
112
Table I: is the row player and j is the column player, the utility in the table is Ua,(a,,a)) = U3 (za(ay,a)).
d1
a1
a1
a2
Q1
01
01
0.5
0
Q2
Q2
02
0
0.5
Proof. Consider zero-sun polymatrix game with 3N players, where its corresponding graph is For E [N), 13-1133-2 Table [ (left) a chain, iee. the edge set E {(i, ( + 1)1
and -3 is Table [ (right). All other utility matrices are zero matrices. Therefore, the only cquilibrium is all players playing 01. Let denote the game as GO.
In this case, for any [N], when changing 13 to Table (middle), the equilibrium of both 3i - and 3i will be choosing a2 deterministically, and the equilibrium of other players keep unchanged. Let denote this new game as g(+).
B.1.1 LOWERBOUNDS ON (e, 6DP
This section will show that if the algorithm satisfies (c, -DP then
C 2 28 (1)
(16)
Suppose the distributed algorithm satisfies the following guarantee accuracy and privacy. Let g," (9) be the gradient of player in G and π (i) be the output of the algorithm in G(i), Then,
3N
ViE [N).
Σ
E
max
- (g S SNC
(Accuracy)
REEA
J=1
ViE(N, set C. Pr(xT EC) S ee Pr(T EC) +
(Privacy)
Moreover, it is easy to verify that for any strategy profile क E x A and E (let (()) 9 for simplicity), have
T3311 - 1. (9(k))) -
3i Io. (g(h)) 2
(.5TT:((a2) (,3
i i
max
max Aa:
Ra. 18s-1EAA0 Agi
i= k.
Since the algorithm is distributed, the findr for each player can written as f:: OT x RAIXAL-1 x AA x A; - R (let Ao AN+1 () for notational simplicity). which is conditional distribution over all possible strategies in A,, conditioned on all past observations and player's utility matrices.
15

---

Published as a conference paper at ICLR 2026
Let adv(o, Ts:) (oi 331,3i-1: Tas) for O and T3s E A where 331,31-1 is the utility matrix between player 3i, 3i in go Note that since the adversary cannot access utility matrices, adv(o, Tai) is fixed even though the observation now comes from games ((k) for some & E [M]
Then, the adversary may sample .dvvkk according adv(o Tzi), where of E O is the observation "3i
in game Gik), Because the utility matrices of player 34 in G and G are identical, have
0.5E
adv.k 33
(a2)
=0.5E
3
{k)
(a2)
(x) 31-1
(R)
T: 951 91 (g(h)))
(-) 33
(M) T30 g5:
(Qthh))
<B
max
max 7a:EA-3i
Rai-1EA
As
Similar bounds also holds for E (TS) (a1)] when
Then, by Markov inequality and the definition of (c, 6D-P,, we have
4E
max
1_0 #33-1
ã3.- -35-1. 135-1-93--16 11)
max
73. I3i
(9O)
R. Ra.EA-9.
21
0 9 (az)
Pr
advv T3i
(a2) 2 0.5
Pr
T3i
advv0
(a1) $ 0.5
(17)
26 - Pr
33i
(+)
(01) S 0.5)
- se
00
21
Tsi
adv
(a1)
- -
26 _
4E
max
T3:--1 33--
(1)
1,99:11
+
max EAA
{i) (11)) T33
r 3i
(4)
(GL))
de
R3: EA A3c-1
Moreover, for each i [N] and g(1), we can further define ((.))) for $ [N] as the adjacent game to g(&t that differs from ( only at Uaj-1,39-2. by changing it from Table (left) to Table (middle). Also note that ((,)) also adjacent to G(J), Such a process can recursively applied to (b.d) and finally we will get N games (9*)sE[N]
SC[NN]
constructed above. There must exist adjacent games g and JSJ( with i [N] \ S, that
Lemma B.I. Consider the 2 games {gS ISS[ {
(
( TTi-1 T33- (99) +
g% (09))
max R A8s
-
max Ra.
STC
(18)
Sufi) T3i-1
Su()) (GSU()))
Sufi)
GU(E)
(GSU(3))
max
93
max 7a/EA-4:
T
5 7Ç
AG-IEAL Age-1
(19)
The proof is postponed Appendix B.3 Since 17) also holds for the g and gSu(1) in Lemma B.1 we have
28 (e c + 1) 2 5c
Therefore, 2
-66 28(e ++1) 28(1+ee)*
1-5
16

---

Published as a conference paper at ICLR 2026
B.1.2 LOWERBOUNDS ON (a, c)-RÉNYI DP
This section will show that if the algorithm satisfies (e, 0)-D,, then
1 N
Σ
G
1 [ d:
2 N
(20)
+EN N Ei=1
+ exp
By monotonicity of Rényi Divergence (Mioonov 2017
we only need show the lowerbound of
KL-diivegeence By further post-processinn on "gg
SdvvS
for [M] and [ [N]. the adversary can
output whether "3i
aadv,5 (az) 2 0.5. Let the distribution of the output be n Then, for the adjacent
games g g(),, where i E [M], we have
Pr
adv,0 33s
(a2)
2 0.5
KL (U Ugi (1) -Pr Pr
adv (a2) 2 0.5) T3i
log
Pr
T33
(dv
(az) 2 0.5
1- Pr
T3
adv.0
(a2) 2 0.5
+ 1 Pr
adv. A3i
(a2) 2 0.5) log
adv.(i)
1 Pr
33.
(az) 2 0.5
1 1- expl
expl!
11 - expl,) log
+ expl log
expl.
1 - expl (1)
where
expl,
4E
max Asi
/ 33i-1 T3--11 1. e
-
max
"3: T3l 9 (09))
Rx Asi
(i) because Pr adv.0 33i
(a2) 2 0.5) S explÇ and Pr
(a2) 2 0.5) 2 -xxpp!!
By Lemma B.1 there exists S [N] and E [M] \
so that expl, explsuti).
28c. Therefore,
1 - 28C
28C
1 1-28(
e 2 (1 28() log
+ 28c log
1-28C (1 - 56C) log
28c
28c
It implies that when 5 TT2. 2 log
3 so that Ç 2 112 exp(2))
1126
B.2 PROOF OF LEMMA 3.2
Lemma 3.2. For any N 2 8, there exists two zero-sum adjacent polymatrix games with N players so that for any algorithm guaranteeing (6) and (7), then
2 min {3 exp (-4)) 16
Proof. Consider a zero-sum polymatrix game, where its corresponding graph a chain. Specifically, there is edge (i, j) E E, if and only if 1. Moreover, each player has two actions and U1.41 is shown in Table (left).
Table 2: i is the row player and j is the column player, the utility in the table is U:(a; az) and U, (a),a:) = (a,,,,a)))
Q1
02
Q1
02
Q1
0.5
0.5
01
0.5
24;
0.5
36g
02
0.5
36;
0.5
2
02
0.5
4
0..5
Moreover, 0.1 = 41 10rs > 102 _...= 10N-1 AN > 0. Then, the Nash equilibrium (NE) is 01, a2 01
a,, 02 ... a 1-
However, when the utility matrix between player (1, 2) changes to
17

---

Published as a conference paper at ICLR 2026
Table 2 (right), the NE becomes (02, a1, a2 01, , 1 as G and the new game as G¹.
Let the original game be denoted
With the observation O; O of any player i > the adversary may sample strategy Tद".. from the distribution adv(o;, (T) = fo, U1 1; to obtain the equilibrium of player i, where U, U1.+1 are both utility matrices in go.
B.2.1 LOWERBOUNDS ON (e, 6DDP
For each player [N] \ (1,2), assume the distributed algorithm may achieve the following guarantee.
Vk (0,1), E -11+-=+*1' *11 Sc
(Accuracy)
4C Pr(mţ E C.) S Pr(a, C.) + 6,,
(Privacy)
where nf. .t. is the output of the algorithm when deploying player for gl.
adv.k be the random variable sampled from adv(o :) where of the observation in G with Let n,
k E (0, 1}. Since post-processing will not decrease the strength of DP, observing π; of will leak less information. Moreover, since the utility matrices of players >> 2 do not change, for any player > 2 and & (0, 1), we have
adv,k instead of
27 =
ud.
E
Let the equilibrium of Go be +00
((1,0), (0, 10,1). .)....) and the equilibrium of G be x-
((0, (1,0),,, Then, by Markov inequality, for any k E {0, 13 and i > 2, we have
E
m
Adv.
m
E
T
n.
Pr
adv. R
n..
21
2
S
S Gr.
Therefore, according to the privacy guarantee, for any i i> 2, we have
(1 n. 0000
(2)
ワ. - 21
4i s Pr
s1
(1 Pr
a S
(1
1|
21 + 0, S e 8,
n7.11 1/:111? 2. (ii) is because post-processing will not decrease the strength of
(i) is because
+.0 TT
DP.
Therefore, have Si Ite
1-8, for i > 2. For i {1,2), we have 1 2
1-8, Itc
since 1 5, S 1.
Moreover, we have
1
1 N 1 max d (8)
maxiE(N 6
2
N
+
N
1 + cs
+ exp ( +N
1=1
(i) uses Jensen's 's inequality.
B.2.2 LOWERBOUNDS ON (a, (),E)-RÉNYI DP
By further post-processing on प. .dv. distribution over (0, 1} indicating whether
we can get random variable sampled from u², which the
n
adv,k
n
Then, for any i 2, we have
(9) Da (1g33, ()).)) = KL(U (1))
(10
1- Ge Ci log
1 Ci = (1 - (1-(()) log
2
(1
GGGG)ogg log
Ci
1-
C
18

---

Published as a conference paper at ICLR 2026
(i) is because post-processing will not weaken Rényi DP MMironov 2017 (it) is because (4) = Pr
adv.0 adv,1
0.0 m,:0
;;
S 2i
(1) = Pr
- S Pr
m
adv,1 x, 2 1 S SCa.
Therefore, the -l.-divergence is lowerbounded by (1 (i) log 1-G + Si log
G
C
T-
When S: S 3. we have e; 2 1 log 3. Therefore, Ç: 2 3 Moreover, if N Ei= Si S 18 by
pigeon-hole principle, there exists a set of players I C [N] (1 with [Z] 2 so that for any E I. Ci S 1- This further implies that
N Σ
4
1 N
Σ
4
Σ 4 iET
2
2
JET
since Se, 2 0 for any E [N]. Therefore, finally,
1 N
Σ 2 27
1 Σ4
3
Σ
26
2
3
exp
2
Σ
2
3
exp
4
8|
8
[
N
iET
1ET
i=1
uses Jensen's inequality.
B.3 OMITTED PROOF OF LEMMAS
Lemma B.1. Consider the 2N games {gs) (9))sMM JENN constructed above. There must exist two adjacent
games g and gSJ(i with i (N) so that
E
max
1 T3--1
T31 - 198) +
max AAA
( T32
The (09))
S7C
(18)
Fis 1EA
Sufr) 13--1 A1-1-1
Su(+) (QSU(E))
suf0 T3
Su(e)
(asu(i))
max
31 93i-1
max 7a:EAAa
35 P3i
S
Rai-JEAASE
(19)
Proof. By the accuracy condition and non-negativity of max max EA (Tg- - - " (
we have
Σ
E
max A
T3:
max A3. 1
( ( - t3 god (04)
I 3NNC.
RE[M]
Therefore,
by the pigeon-hole with Z
principle,
there must
exist
a
sub-
set
I
C
[N]
1. SO that for any
E I. (G9)
E
max
Ra--1E4
A35-1
@ T
-
9
(g
max TTg Fai I3i
6
< 7C.
The same guarantee holds for any gli with E [N].
Then, we will form meta graph, with each node as subset of [N] so that there are 2 nodes in total. For each two nodes S², S with |Sa| S |Sa), they are connected in the meta graph if and only if gs* and gs are adjacent. In other words, S S u {i} and i E [N] S,S The edge between (8), .82) is labeled as E [N] if S2 S {i}. Therefore, each node has N edges and their labels are different from each other. Then, there are 2 nodes in the meta graph and N2N-1 edges.
For each node S [NT, the set I constructed above can be viewed selecting edges with labels in I. Then, for each node S and its selected edge with label i, it is guaranteed that
Tsi. 95 (G9)) STÇ. (21)
E
- 1, 1 + max 131-1 1
max
Rar-1EA EA
1
19

---

Published as a conference paper at ICLR 2026
and there are N2 edges in total, by pigeon-hole principle, there must exist edge being selected twice. In other words, there exist two adjacent nodes , S that both select edge with label i. By definition, assume |S I |Sa) without loss of generality, then 5 - U {i]. Therefore, (1 is satisfied for both 8 , on i.
Because [ 2
C PROOF OF THEOREM 5.1
Theorem 5.1. Consider Algorithm 1 Let A = [ [A,. The update-rule can achieve the following guarantee in any polymatrix game. For any T > 0, player i E [N] and strategy E A,,
N ΣΣΣ
NT
E
g
1(11))
:
((+1)
-m))
i=1 t=1
$ nT
1
+ A x²
+
2n)²
+
To
A
1
24/ log a (N) 4/9 log N
+
(10)
2m
2 (N) 4/9
We will give a proof sketch of Theorem 5.1 first.
C.I PROOF SKETCII
To show the convergence of Algorithm| 1 by Lemma D.4. in Liu et al. 2025), we have
Ti
T
(1+1)
Ti
||T
g:
((+1)
mi)
2
2
1
(t)
2
1 1/7
(1+1)
1
(t+1)
T3
217
2n
2n
Moreover,
((+1)
Ti
|T/
< 2
Then, by adding
g. (g,((
9 " (1+1)
T; on both
2
sides, have
111)) (++1)
T
9
2
1
(0) |
1 +
(1+1)
T n
21
2n
1
(++1)
(t) |2
(1 1)
(t)
(1+1)
TT.
+ 9,
π
n
27
Moreover, E ( (( (1-1)
9
g.
(1) (1+1)
;
+ To A
Will Σjev() Tj where the
2
complete proof is postponed to Lemma telescoping, we have
C.I
Therefore, by taking expectation on both sides and
Σ
(
g
(11) (t-1)
-Ti) mi)
E
|Tا - # |1]]]
+ 722
To
A +
T +
Σ 1=2
T E
-
(0)
n
(1)
21
2
2
A
Σ Tz.
O a
JEN(6)
20

---

Published as a conference paper at ICLR 2026
Ri 7((13
7 m; [01]]]
Further,
is bounded by,
(1)
(8)
E
T1 ProjaMi
( + ni
ST
T1 " n
(0)
(1){ || - Tj. x;
1011
( 11
(1)
+ n (1
-E
Th 7
(1)
(2) (1)
= -o
(i) is because E n, (2) = 0 and n;
(2) is independent of क. - =_ By aggregating the results above and substitute TÜ by its value in Algorithm the proof is concluded.
C.2 FORMAL PROOF OF THEEREM 5.1
By Lemma D.4.
in Liu et al.
2025
since Algorithm
is equivalent to x; (++1)
argming;ess Ti.
(0)
+
T 2
||
2n
1
T
for any E AA, we have
1)+1)
1//
||
Il
+
g ;, Ts.
(e+1)
2
2
1
(0)
2
1
1/7
((+1)
2
1
((+1)
=
2
T
R;
2
T
2
Then, by adding v (g. (1+1)
Di
(1) ((+1)
;
on both sides, we have
m77
11+1)
174
||
2
+ 17 gg
(++1)
(++1)
- TT
(22)
2
2
2 Th 201
1
1T:
(1+1)
2
1
(1+1)
- (,11/²
+ 17 (g (e+1)
(0) ((+1) TT
π
a
gi
2
2
Moreover,
(1-1) (t+1)
(112)
((+1)
((+1)
(112) (++1)
+ g
9."
. - mi
((+1)
1 (1+1)
96
g
(1+1)
U1S (z)(t()) - (f(+11
TT 2 [N(ii]
jEA(())
(
x (11) (e+1)
-m)
Σ
(1-1) [((+1)||
g
m
[iiil
jj
3
JEN(3)
(i) is because U1, E 1]:iA; Recall that A = ma LAs/. we have
13 (++1) - =//11/
S VV
((+1)
(++1)
= -VA
(t+1)
Projas, (1+1) + +ng ||
/ A
n
(c+1)
21

---

Published as a conference paper at ICLR 2026
By taking the expectation on both sides of 22
have,
E
774
(1+1)
175
2
2
+
[N(i)
E
U
(1+1) (1+1)
ni
(23)
jEV(1))
1
(1)
1 +
T7 2
1++1)
1
(++1)
न.
T
xi
2VA
+ n/
9i
(1+1)
Di 5 n
(1) (1+1)
IN(ii]
Σ
JEN(()
By Jensen's Inequality,
n
(++))
-
n
27
VlA a. Therefore,
2
Σ
E
m
(+1l
S 2Ao
W(1i
JEN(()
Moreover, since ||
1 1], we have
E
17
[ii
Σ
(1+1)
(1+1)
Ti
jEN(i)
1
(1) 2
+ 1774
(++1)
((+1)
=,(0|1²
(g.
(1t1))
(1+1)
m3))
<E
13
m m/
2
+ 2AAo +
2 T5.
To bound IP
(9, (1+1) (1) (t+1)
9; -m:)]
we have the following lemma.
Lemma C.1. Consider Algorithm For any player i E [N], we have
9: g. .
(t+1)
(++1)
Tz)
2n
30 2
A
2n A
Σ Tg.
(24)
[iii) JEN(S)
σ
The proof is postponed to the end of this section.
(1)
We can further bound E
π. by
E
(8) m:
Projam:
(T
nz (10)
m n.:
(0) 2
<TE
m
(1)
n
(8)
T 7. 10
E
2 n
(t) (8)
m
n (8)
12
(0) 27
E
n2
Ao
is because [2]"] = and n is independent of n;
m3
22

---

Published as a conference paper at ICLR 2026
Finally, by telescoping,
T
E
[1)1]
Σ
U
(++1) (++1)
"
mi
tm
JEN(()
11
7
02
T
21)
30
A 2AoT +22 T:I
24VA
E T,T
27
21
IN(i)lo
JEN(1)
- - + A 1 +
211²
To
A
2
T:T
2nVA [i jEN(()
Σ T,T.
(25)
21
2
Further, by taking summation over all player E [N] and averaging, we have
N
T
E
[iii
Σ
U
(f+1)
"i
((+1)
Mi
1=1
t=1
JEN(()
S + A 0²
20)²
T
N
N
2 A
T +
+
1
+
Σ THT.
2n
2
2N
N
N(i)l
1=1
JEN()
Then, can further bound the summation over тÜ by Lemma C.2
Lemma C.2. When (o(o) for any i [N], where 0 game dependent constant, we have
1
Σ Tg T N JEN(()
T
(26)
N
W(i)
( 3/9
The proof is postponed to the end of this section. Therefore, since have
log in Algorithm
we
N
T
E
Σ
Unj (1+1) 1
(1+1) Ttç
N
T
Wiii
i=1
1=1
jEN(()
1
2ny
7o
20/A A
+
A
+
A
+
T/
211
2
4/9 (N)
log (N) 4/9
log N
C.3 OMITTED PROOF OF APPENDIX
C
Lemma C.1. Consider Algorithm
For any player [N], we have
E
9: Di m
(t+1)
(t+1)
mi)1
2n1 +
30 2
A
2nvA A
Σ Tj.
(24)
W
JEN(()
Proof. By Hölder's Inequality, we have
E (9)
(t+1) 1)
g!!) m
(t+1)
mi)
E
g
(++1)
906)
m
(t+1)
mT
23

---

Published as a conference paper at ICLR 2026
Moreover,
(++1)
0
1
Σ Uni (Proja ( (z)ettl) + +nl me(ttl)) - m7(1)
9:
[x((1)
JEN(1)
VIA
Σ
Projams (T) (T(((t)) + nz (2(1))) - - ||
JEN(()
VIA
Σ
VIAii Projam (3g + nz ( -
((++1)
INOI)
JEN(()
VIA
Σ
/
nn ((+1) -
WiI JEN(()
Therefore,
(++1)
(++1)
Ti m
EE
9i
[N(11]
A
Σ
E
π
1)
+ n2
1++1)
( . (e+1) T
JEN(()
E
(e+1)
+ n
(++1)
- TT 11311(9]
o A
(e+1)
me
=11"]
W(
oVA
A
4
(EN(()
Furthermore, since E
[++1] n2
(++1) is independent of n and n
(1+1)
we have
E (++1) + nj
(e+1) - 1
=E
((+1)
=(0) 2
+ E
n
(t)
(0)
SE
Proja
119
#(()
+ Ao
1 + 177j
(8) n9
<E
(1)
+ Ao²
1 + m/3
T/T
x (c)
71
(
Ao²
+ T7T
1 nTJ
(6)
221TT E ||
+ +22
110 (1)
+ Ao²
(1)
21TT + 2n, A + 2o
(i) because (a + 6) < 20² + 212 for any a, b E R and + mT 2 max {1, 17,3. (1i) is because
U.y E (]1,1] Also, _V-TE
- ((+1)
33 19
S σv
Therefore,
2
Di Dt n
(t+1)
(t) (1+1)
Ti }1
s
211²
30 +
A
2n A
Σ T
σ
2
W
JEN())
Lemma C.2. When T3
[ for any i [N]. where c >> is a game-dependens constant, we have
1
Σ
T N
(26)
N
T
N
JEN(()
24

---

Published as a conference paper at ICLR 2026
Proof. By definition,
N
N
C
1
= c
N
N
[N(1]
N
1=1
1=1
Moreover,
N
N
Σ
N
[N(i)
Tj
N
I((1 INGI
1=1
(EN(s)
i=
jEV(
N
N
2( 2|N
JEN()
N
(((())
N
2|)
(i) because each player contributes [|]? to the summation 2 times on each edge, iee. (
times in total.
D PROOF OF SECTION
Theorem 6.1. Consider Algorithum I and any two adjacent polymatrix games G, that differ at (U1, U2). Let dist(i,j) be the length of the shortest path between players i, which co when i. are not connected. The update-rule guarantees the following for any T > 0 and player E [N].
1
N
Da
(1g
(T) (T)
anp²
min
T,
(11)
N
σ²
1=1
where
16A3
(log N)²
44
(12)
(N)
4/9
N
2A
(T > min {dist(i, v1), dist(i, v2)))
(13)
N
We will give a proof sketch of Theorem 6.1 first.
D. PROOF SKETCH: THE CASE OF DENSE GRAPHS
Firstly, we will introduce the chain rule of Rényi divergence.
Lemma D.1 (Chain Rule of Rényi divergence). For any distribution p.q over random variables X1, X2, for any a 2 1, we have
Da (p(X2, xx), g(x2, X²)
<Da q((X)))) sup Da (p(X² x =
2²))
(27)
A proof of the above lemma is provided in Appendix D.5 for completeness. By Lemma D.I the divergence between the distribution over observations can decomposed into the divergence between the distribution over the observation at single timestep. Formally, for any 2 1, adjacent games G'. and player E [N].
Do (G P
(T) (T)
Da (110)
(1) (100))))) (0t1,,,)01.11111 ((-11))).
sup (a0),... (000)...,,(-111)
25

---

Published as a conference paper at ICLR 2026
m When the graph is dense, i.e. N NP for some p > the degree [i(i)) of most players will close to N.
Note that the observation here ō(*) "; +
(+)
Then, since post-processing will not increase the privacy budget, we can augment the set of obser-
(T) ) ) Specifically, for two adjacent games g ~ G' that differs at the
vations to bound Da (10.3 (0:3)
utility matrices on edge (V1, U2), the augmented observation will include { {TH + +
(t)
(t) S JES'
where
(1) s [N] \ (2) and v1, will be included in S if their degrees are no less than N2/99, Let Mo.s
{ 3 + +n² (1)
denotes the marginal distribution of pi on
We can see that for any i S,
jES
(T) Da (0.ii1g11)
(T)
S Dr
(1
(T) (T)
For i & S, we can show that Do ( M is bounded by some constant. Therefore, since
(T)
(T) (T) |S| N 2, Em S Da (M ( is bounded when Da. (M pgy is sublinear in N.
(T) (T)
Note that 1g (-1 (-) (0)0 )(-11) is multivariate Gaussian distribution with mean
(8) TT:
and
variance 0² XiesA, Therefore, by the Rényi divergence of multivariate Gaussian (Gil et al. 2013 the divergence is bounded by 20 Eies | n. (0)
If S = [N] then for any player i E [N]] \ (2),02) given all past observations (1 (1)))) n
(+) (-1
are identical in G,9', x,
(6) = For i E fui, U2). given =((-1)
jES
(t-1) and only U0 + U U
| - O (wvi)) = (0((1)))
(ar)ar)) by definition of S.
O hides constants invariant to the number of players N, e.g. A, the size of the largest action set.
If UI, U2 S, then for any i E S (V((1) (V2)) मं = ا((")) For N((i)) UN(2), (-) : m2g
will further augment the space of observations so that the adversary can observe ((mi))
(x)
==1"
Assume i E ((e)) (V(22) for ease of exposition. For any E Nii)
v2), we have 3
- Therefore, | x S s (1=-1-)) - (t-ft-1 1) s 0 Thg
(t-1) - - >"--"/ More-
over, due to the additional regularization imposed on each player, we have the following lemma.
Lemma D.2. Consider the Algorithm 7
For any player E [N] and timestep L > O, by updat-
ing the strategy {I, (1) J
. {m( {1))
(*) but different gradients with the same noise { (T) J s=0
{g. S J.-o {olon Samo
(')
individually, we have
(t) π
2VA T
S
(28)
The proof is postponed to Appendix D.5
Therefore, finally, |1 - -(()
S 0
1
O
log N 173
because [W(w1)] S (N) 2/9 Moreover, since (W(1)) S (VV) 2/9
Σ
m
(t)
n
((0)
Σ
(6)
x 10
5 (log
(log N72
(A/) 4/9
For cases of Un E S, U2 S and o1 & S, U2 S, the proof is similar.
26

---

Published as a conference paper at ICLR 2026
D.2 PROOF SKETCH: THE CASE OF SPARSE GRAPHS
For the sparse graph, the degree of all players is bounded by constant A For simplicity, let's consider two adjacent games G' which differs at the utility matrices on edge (mi, v2) E E, and 0 in Algorithm ie. the noise-free case.
(t) in 9 and its counterpart ( in G' are identical if S min {dist(i, v1), dist(i, U2)} At timestep n, This can be proved by mathematical induction.
(t) Therefore, Rényi divergence between Hg. (- , and N (-10(1)) ,- 1))-1) is 0,
(e)
since they are both normal distribution with mean n. (1) and variance O.
Recall that the graph is sparse and the degree of each player is bounded by constant Ammax, such cases, most players are at least of distance O (logyamax N) to the edge 02), Therefore, if T in Algorithm is no larger than O (log.max N), the Rényi divergence of most players at timestep & is O. Therefore, by averaging across all players, the privacy budget will be 0 as the number of players goes to infinity.
The general proof for the cases when σ > 0 shown in Appendix D.4
In the following, we will introduce the proof for dense graphs (4) first and that for the sparse graphs later.
D.3 PROOF FOR DENSE GRAPHS
Let = (1 wol) be the harmonic mean of players' degrees. When the graph is dense,
N will be relatively large. Now, we will bound Rényi DP. Let (V1, U2) be the edge on which the utility matrix differs in and gr. Then, we define the set
[N]
((1)).. ((22)l 2 2//
[N] \ [w1
[W(1)) < (V) 2/9
[N(v2) 2 (N) 2/9
S =
[N] \ [w2}
[W(22) < (N) 2/9 [W(1))
2 (N) 2/9
[N] \ (2i,02}
(((2)) < (N)
2/9
Consider the marginal distribution
Pg.s of Pg over ((TZ(
(8) (
n (s)
Then,
iES a=1
Da (1g.s: ( 2 D. (16.0018 199)) for any E [N] (2),02) and t 0 since and enlarging the set of observations will not decrease the Rényi divergence. This is because post- processing (delete observations) will not increase Rényi divergence (Mironov 2017).
D.3.1
U1, E
By Lemma
D.1
let n (1)
be the counterpart of क. (t) for any i E [N], we have
Da
(0.5:
sup
Do (Ne.s(- (200) ,0,) ,r3).... ... ot o(- 1. (,1101)),60)) 5 5(t
(oe4) 0000
1))
| - -00
sup .0
20
1=1 ME[M] (ot)) (00,
(i) is by the Rényi divergence of multi-variate Gaussian distribution (Gil et al. 2013). since the distribution of n. + n is multivariate gaussian with mean T/
(t) and variance o T²TA, (TA, the identity matrix indexed by A; A.). The inequality above implies that the Rényi divergence can be
(t)
bounded by the squared 2-norm of n; (t) (f) given all past observations (6(1)0(2 ................................ ((-1)) identical in g,
27

---

(f) Published as a conference paper at ICLR 2026
(t-1) of all players except v v2 Given the observations are identical in G, the gradient 9:
identical in G, G" since the gradient only depends on me (t-11 + n; (t-1) and the utility matrices, which
are identical for E [M] \ (2), Therefore, ni ( for any i [N] for, 02). For
i E {11, v2), we have
(t-1)
(1-1)
+ *(t-1)
79 (1-1)
(1)
(1)
Proja4
n1
119.
- Proja*
1 1 1771
1 777
(1-1)
π (1-1) "ggg.
(t-1))
π
ng.
+ 1/Ts
1 1971
Σ JEN(()
(Uts U(,) (1111)
51
(i)
2m
VIA.l
(i) is because Utg E 1-1, x and U2 + Uh, only if (i.5) (U1, U2) or (i, (e2, 01).
Therefore, since the distribution of +( + n is actually multivariate gaussian with mean π, (t) and variance o² LA, so that the Rényi divergence is bounded by
(1)
[<]\(=)]|> AA + (M)())) (uzz)) T.
20n²
20n²
By the definition of S, it is further bounded by
4nn² AT.
o2 (
D.3.2 01, 1/ E S
(=(() T
(e) +
( 2=1
When the adversary may only observe
for some & E (U1,22), by Lemma D.I we when all past observations
n
only need to bound
(t)
x(1))
2
(=(() + ((()) 1-1 are the same in
g, g.. Then,
(1-1)
12-1)
(1-1) - -ngg (t-1) K
(t)
π
(0)
Proja4
119
Projaa
k
1 1 1/Tk
+ 17Tk
[t (t-l) 1)
(t-1)
(t-1)
119" (1-
119
1
1 17Th
+ 17Th
((-1)
g (
(t-1)
9k
/
For k [N] \ (11, v2), similar the proof in the previous section, we will augment the ob- servations of the adversary first. The adversary may observe (!m) + (+))) (e s-1
and (fmll)) non 1) a=1 at timestep t. Note that the actual observation of the adversary is still (m(()) (a) + +mk (()))) s=1
We augment the observations to simplify the proof, since the Rényi divergence of the the augmented observation's distribution upperbounds that of the actual observation.
Still, by the chain rule of Rényi divergence, we need to bound ΣxEN))( |T(
n -(0) for any
t E [T]. For any & (vx) (N2)22) similar to the discussion in previous section, the gradients y."
and n (t-1) are identical in G, g', that the क. m(()
28

---

Published as a conference paper at ICLR 2026
F ((z) (UN( \ fei, 02), we have
c ( 5n 9i (--1) - 06 1
7
Σ
Uis (
- -
[V(01
JEN(()
( "
Σ
Uis (T - 
IW(1)
je
MA4
Σ
- ( - x1((-111
[V(1]]
nA
Σ
1((-1) 1 --11
[V(
je (
(i) uses the fact that /
((-1)
= =((1-1 for i @ {o,, U2). Since, ny (t-1)
= nn ((-1)) for any j E {v1, 02).
we have
7 (1 1)
1/ (1-1))
Projad;
T (t-1) + n 1) - Projati (T/) + nn m
[) (1-1) (1-1) - x (1-1) n 1/
m
(1-1) 11-1)
Moreover, due to the additional regularization, for E (11,02) as follows according to Lemma D.2
mj - x// ((--1)
(t-1)
will be bounded
(N) 2/9
2 Ay (
log N 2 log
| (--))) 1)
2 A/
(N) 3/9
(N) 1/3
(i) is because when U1 & S. ((n)) < (V) 2/9
(T)
so that To,
(x) (/ log N by definition. The same
((0)
4n 3/2 log N where A = max |A,]-
argument also holds for 82. Therefore,
S
Furthermore, for E [N] \ (21
16n/ A3 (log N)²
Da (9.. (3) < Do Do (1TT) (T) (T)
(g
_ a
(())))(()2))
(A/)2/8 2/8
T
202
(in [N(1)
16n2 A3 (log N)²
(TV)) 2/9
$ 202
T
(N) 2/3
minieM(en)uN((s)) [(())²²
16am/ A (log N)²
a² (N) 4/9 minieN((.) ((O))
Finally, since min (ea) (Wii 2 1, we can conclude the proof. Moreover, (wn (i) can be much larger than a constant in practice, egg., Erdōs-Rénys graphs. The proofs for the rest possibilities (#1 S, U2 & S and & S.02 S) are similar.
D.4 PROOF FOR SPARSE GRAPHS
In this section, we show the DP guarantee when the associated graph of the polymatrix game sparse. Formally, there exists constant Nmmax > 0 so that [W(i)) A/max for any i [N].
We will augment the observations from (m!")) + (.())
1-1
==1 (( + m,,')
SES((") ==1
where
8(0) = {j: min (dist(j, 2n ), dist(j; {2)} 2 s} (2)
min (dist(i, vn), dist(i, 02)} 2 8
Otherwise.
29

---

Published as a conference paper at ICLR 2026
When min {dist(i, 01), dist(i, (2)), we will show in the following that with all past observations identical in g g", then " and its counterpart π in G' are identical for any j E S! When s 0, 5 = [N] and (0) = -/(0) for any j [N] since they are both initialized to uniform distribution over Ay. When > 0, for any j s(*), we must have N() S s otherwise min [dist(j, v1), dist(j, #2)) < Therefore, since all past observations identical, have = are identical in G.G' for any E N(i) so that the gradient 9j (a-1) g ((a=1), Moreover, given are identical in G.
(s-1)
=((=1) are identical, x (5)
When min [dist(i, v1), dist(i, 22)}, |m x!100
2n/ |Ai ///. given the past observation
(s-1) + n
(s-1) is identical.
By Lemma D.1 for any T O.
2008
(T) Da (1ga Mgr.))
S max (0, min {dist(i, u1), dist(t, o2)1}
|Ai
o²
2007"
1 (T's min (dist(i, v1), dist(i, b2){)
σ² LAiTT
L
D.5 OMITTED PROOF OF LEMMAS
Lemma D.2. Consider the Algorithm
1
For any player E [N] and timestep / > O, by updat-
{ (+) J==0" (
(a) but different gradients
ing the strategy
with the same noise n
J s=
{9, (1)
S {glln
individually. we have
(2)
((0)
2VA
(28)
Ti
Proof.
Projadi
(1) (8)
[T: + nz
(1)
-19
(t)
Proja
x + +m! kn.))
ng
(1+1) (++1)
x
Projat
Projo4:
1 T7Ts 19T
177 1756
Proja4:
ti + +n (1) - ng!
(1)
Projas:
(T((1) m2:
1 1/T
1 17=
Projaa (T,(1) (t)
+ +n! (1) - Projam.
(-((+++
+ + (1)
(8)
+
9
+ T)7
1 + TyT
1
(1)
</10 1+ 17.
(0) g(((1)
1+ TyT;
By recursively applying the inequality above, we have
| (++1) 1-( ((+1)
1
(0)
(0)
8-8+1
(5)
(+)
9
1+ 1T:
1
==0
t-++1
(6)
(5)
1 1+777
9
(i) because मं n are both initialized as uniform distribution over A,. Therefore, since each element of the gradient is bounded by [-1,1] by definition, we have
(0)
(0)
n T
(1+1)
2m
VA. 2nV A
1
A
I 1774
(1+177;
(1-
Ti
30

---

Published as a conference paper at ICLR 2026
Lemma D.1 (Chain Rule of Rényi divergence). For any distribution p. p.q over random variables X1, xx,, for any a 2 1, we have
Da (c(xx g(x xx))
DD (x(x)),((xx))
+ sup Da (p(x² x)). x x,, =z'))
(27)
z²
Proof. By definition, when > 1, we have
Da (p(x), ,(x)
log I (pla), x²))) (g(x' ,0,),,,)))) 1-a dx de?
x1 .122
(
log [ (Le 1x!)) (9(0) |x!)) 1-a do²) (p(x")) (e(x!)) 1-a dx
(6))
( (p(a 12)) (g(ي"1 1-a do2) (1 (p(at)) (a(xt))² La dx!
log sup a²
(p(0) 13)) (a(x² x2) dx a log J (p(at)) (g(x!)) dr
suplog
21
Dr (p(x*), (x()) sup Dr (p(x² 3* q (X2 x = E²1)
(i) is by Tonelli's 's theorem. (it) is by Hölder's Inequality.
When a the corresponding Rényi divergence KL-divergence. Therefore.
D1 x3),
x²²) f 3 p(x), xx) log g(x0) x2)
do do?
S 121,2 pl )p(p))((p log p(a² x² p(x*) q(22 x² )xx1)
de dx²
= [ Jun p(x² 10 (pp(a))lo
p(xt) do' do? + 1 Jet pl2² | )((=)) log pl1² |xt)
dx do?
((x!)
g(x² x²)
= =D (p(X'), (() + B2Ix((X)) [Dr (p(X² = =z)), x== =x'x
<DI (x(X'), )(x + sup Di (p(X² X 3a), 2() | =3))).
E EXPERIMENTS
The experimental results are shown in Figures 5 and The baseline algorithm is adapted from Huang ct al. (2015). Our implementation uses Py PyTorch Paszke et al. 2019) to enable efficient, fully parallel updates of all players' strategies, and all runs were executed on 2x NVIDIA H200 GPUs. The error bars denote la.
On dense graphs, as the number of players increases, our algorithm's 's exploitability and the privacy budget both decrease, whereas the baseline's 's exploitability increases. On sparse graphs, by contrast, only the privacy budget decreases. A plausible explanation is that the convergence rate sparse graphs is O
[log N)77) which is too mild to overcome constant factors and stochastic noise for
N < 216, Hyperparameters were chosen according to Theorem 7.1
E. RESULTS IN GRAPHS WITH DIFFERENT TOPOLOGIES
In this section, we provide further results in dense and sparse graphs with different topologies.
31

---

Published as a conference paper at ICLR 2026
Dense Graph A=5
24 10:
2.2 10
2.8 x 10
Exploitahlity
Privacy Budget:
18 10
2.6
1.6 10
2.4 10
1.4 10
1.2 10
2.2 x 10
10
A=10
2.8 x 10"1
3x
Exploitailiity
2.7 x 1071
Privacy Budget,
2.6 x 10
24 10-1
2
20
Number players
Number of players
-
Ours
Baseline
p=0.1
p=0.3
p=0.5
Figure 5: Experiment results of dense graphs. Each node (player) in the graph will connected to another node with probability p, the connection is sampled i.idd for each node. Then, the duplicate edges will removed. The action set sizes of all players are set to A. We can see from the result that the exploitability and the privacy budget both decrease the number of players increases.
Dense graph: players are randomly divided into [1/p] clusters. All pairs of players within the same cluster interact with one another, while pairs of players belonging to different clusters interact with probability X
Sparse graph: players are randomly sampled 2-D plane. Each player only interacts with the c-nearest neighbors.
32

---

Published as a conference paper at ICLR 2026
Sparse Graph A=5
Exploitabiliy
Privacy Budget:
10'
10-1
6 10
110
27
29
A=10
2 10'
3 x 10
Exploitability
2 10
Privacy Budget:
10
6 x 10"
6.-1
4 x 10"
2
2
Number players
Number players
Ours
Baseline
c=1
Figure 6: Experiment results of sparse graphs. We will randomly generate eN edges in total, with each node appearing times. Then, duplicate edges and self-loops will be removed. The action set sizes of all players are set to A. The result shows that while the exploitability remains unchanged, the exploitability decreases the number of players increases.
Dense Graph
A=5
2.9 x
241 10
2.8 X 10
2.2 10
2.7
Privacy Budget:
2.6 10
1,8 10a
2
1.6 10
1.4 10
10
1.2 10
10
10
A=10
2.8 x 10
3
2.7 10
Privacy Budget:
2.6 x 10
10
2.5 x 10
2.x x
2
29
27
2
Number players
Number of players
Ours
Baseline
p=0.1
p=0.3
p=0.5
Figure 7: Players are randomly divided into [1/p] clusters. All pairs of players within the same cluster interact with another, while pairs of players belonging different clusters interact with probability N. The action set of each player is of size A. We can see from the result that the exploitability and the privacy budget both decrease as the number of players increases.
33

---

Published as a conference paper at ICLR 2026
Sparse Graph A=5
Exploitability
Privacy Budget:
104
10
6 10"
x 109
3
27
211
23
255
29
2
233
215
A=10
Privacy Budget:
Explostablitt
10
10-1
6 10"
4
27
2
21
2
25
27
2
211
2
2
Number of players
Numher of players
Ours
Baseline
c=l
CM3
c
Figure 8: Players are randomly sampled on 2-D plane. Each player only interacts with the c-nearest neighbors. The action set of each player is of size A. The result shows that while the exploitability remains unchanged, the exploitability decreases as the number of players increases.
34


Reviews:
[{"review_id": "mJMinYgjU9", "reviewer": "Reviewer_8A83", "summary": "This paper studies the problem of zero-sum polymatrix games under differential privacy (DP). The notion of DP is defined over adjacent games that differ by a single utility matrix.\n\nBuilding on this definition, the authors establish two lower-bound results, showing that to achieve meaningful privacy and convergence guarantees, (i) the adversary must not have access to all communication channels, and (ii) the accuracy metric cannot be based on the Euclidean distance. The paper further provides upper-bound results demonstrating that low privacy parameters and small exploitability can be achieved when the adversary has access to only a single user’s communication channel.", "questions": "All questions are included in \"Weaknesses\" section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The lower-bound results are solid contributions, as they establish the necessary conditions for ensuring valid privacy and utility guarantees. I also appreciate that the authors provide detailed explanations and intuitions behind most of the theoretical results, which greatly help readers better understand these concepts.", "weaknesses": "1. In Theorem 6.1, the privacy of a single user’s observation is defined as the average privacy loss across all users. However, the corresponding privacy notion in Equation (7) is defined as a maximum over all users, i.e., it bounds the worst-case privacy loss. Therefore, the comparison between the lower- and upper-bound results may not be entirely fair, since Equation (7) imposes a stronger constraint on privacy loss (maximum vs. average). It would be helpful to clarify whether Theorem 6.1 still holds if we instead upper bound the maximum privacy loss rather than the average.\n2. Following Lemma 3.2 (Lines 279–281), the authors present an example illustrating the instability of the best response with respect to other players’ strategies. I am curious how this instability is circumvented when exploitability is used as the performance metric instead of Euclidean distance.\n3. The dependence on $N$ for both the accuracy and privacy loss in the upper-bound results appears quite weak, scaling with $O((\\log N)^{-1/3})$. The authors note that this is the first result showing diminishing accuracy with sufficiently large $N$, which is an interesting finding. It would strengthen the discussion to also include a comparison with the non-private convergence rate, to better illustrate the performance gap between private and non-private settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jVUPg0jp9X", "reviewer": "Reviewer_ssdW", "summary": "In this work, the authors establish both impossibility results and positive results in the problem of computing equilibria in polymatrix games. \nPaper demonstrates that achieving both high accuracy and low privacy budget is impossible if the adversary has access to all communication channels or if Euclidean distance is used as the accuracy metric. Conversely, the authors propose an algorithm that achieves differential privacy while converging to coarse correlated equilibrium (CCE) with guarantees on exploitability. A key contribution is demonstrating that both privacy and accuracy can improve as the number of players increases, particularly for dense or sparse graph structures, through careful regularization and noise injection.", "questions": "**CCE vs Nash.** \nThe algorithm is analyzed in terms of coarse correlated equilibrium (CCE) regret. Do the authors have comments on whether a Nash equilibrium (or approximate NE) can be learned with DP under similar conditions? Could the algorithm be modified to target NE?\n\n**Graph assumptions.** Are there any assumptions on the polymatrix game’s graph? Since the privacy bound involves shortest path distances: could highly irregular graphs (e.g., diameter ~ log N vs diameter ~ N) affect the results then?\n\n**Parameter choice.** Th. 7.1 requires setting $\\eta,T,\\sigma$ as functions of $N$. How sensitive are the results to these choices? In practice, how would one tune these parameters?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Novel problem domain.** The work pioneers DP equilibrium computation in polymatrix games, a richer class than previously studied DP games such as \"Two-Player Zero-Sum\" games and \"Aggregative\" games. The notion of adjacent games that is used --- reasonable and simplifies the formal statements.\n\n**Impossibility results (Lemmas 3.1 and 3.2).** Prior DP game-theory work mostly considered aggregative games or centralized settings, but showing a lower bound on the Nash-gap for DP algorithms under full eavesdropping is a strong negative result, highlighting a fundamental privacy–accuracy trade-off.\n\n**Positive results (Th. 5.1–7.1).** Give us that both exploitability and privacy cost vanish as $N\\to\\infty$, this results is stated formally in Th. 7.1. The authors highlight differences with prior works, which suffer a differential privacy budget, no matter how large $N$ is, and vice versa.\n\n**Method.** The proposed algorithm (_Find CCE in polymatrix games with DP guarantee_) achieve both perfect accuracy and DP guarantees as the number of players in the game increases. Also, the efficient implementation on PyTorch is provided.", "weaknesses": "**One limitation regarding the adversary model.** The positive results assume the adversary can only see a constant number of communication channels. In practice, an adversary might intercept many edges. If it sees $k$ channels, then the privacy cost scales by $k$. It would be helpful to discuss how realistic your “bounded channels” assumption is, and how performance degrades as $k$ grows.\n\n**You can extend the limitations a bit.** As mentioned in limitations, you only discuss polymatrix games. But I would clarify that your impossibility results focus on zero-sum polymatrix games; it is not clear if similar impossibility holds for general-sum cases.\n\n**Extended experiments.** I think you can add more problems to your codebase, e.g., different topologies of the polymatrix game’s graph.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XWagvR0g0Y", "reviewer": "Reviewer_UsT1", "summary": "This paper studies equilibrium computation in polymatrix games under edge-DP (everything else is fixed in the neighboring \"games\" execpt the value of a single edge). The authors observe that existing works cannot simultaneously achieve high accuracy meaning good approximation to equilibrium) and low privacy budget in fully distributed setting.\n\nThe paper gives impossibility results which show that achieving vanishing privacy loss and vanishing error simultaneously is impossible under two regimes: when the accuracy metric is Euclidean, or when the adversary can access all communication channels.\n\nUnder more restricted conditions where an adversary can access only a limited number of channels, and accuracy measured by a certain exploitability metric, they design a distributed, DP algorithm where each player sends a noisy version of their message to neighbors and updates using a regularized proximal gradient step with an adaptive regularizer scaled by the player’s degree.\n\nIt is then shown that for this algorithm, both the expected exploitability and the privacy budget vanish as the number of players $N$ grows, in both sparse and dense graphs.", "questions": "- Why to only consider the edge-DP definition? Why not e.g. player-wise DP or DP for the values of the nodes?\n\n- Could you think of practical scenarios where the results of this paper would be useful?\n\n- Or: could you think of extending the results of this paper to a practical scenario where they would be useful?\n\n- In Thm. 6.1, what is the improvement over LDP scenario, i.e., when everything is observed? It seems as if the guarantees of Thm. 6.1 get weaker as $N$ grows, or am I reading it wrong? So the vanishing error of Thm. 7.1 comes somehow from the averaging effect?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-rigorous formalization of distributed equilibrium computation with DP using the adjacency notion from [Huang et al. (2015)](https://arxiv.org/pdf/1401.2596) (edge-DP).\n\n- The impossibility theorems are conceptual but insightful: they clarify why prior work could not achieve both accuracy and privacy simultaneously. These negative results provide valuable theoretical boundaries.\n\n- Novel distributed algorithm with the adaptive regularization which balances privacy noise and update stability, allowing performance to improve with scale.\n\n- Asymptotic trade-off analysis: Theorem 7.1 shows how both exploitability and privacy budget can converge to zero as number of players $N \\rightarrow \\infty$ a clear improvement over prior results in aggregative and network games.", "weaknesses": "- Although the introduction cites “security games” and “financial markets” as motivating examples, the setting of the paper is quite abstract and conceptual. It is hard to imagine that actual scenarios in security or finance would actually fit into this framework, though I understand that the results give the theoretical limits in private fuly distributed games.\n\n- Limited privacy scope: The paper only considers the edge-DP definition considered by [Huang et al. (2015)](https://arxiv.org/pdf/1401.2596) (edge-DP). \n\n- Some central references seem to be missing: e.g. [Cyffers et al., 2022](https://proceedings.neurips.cc/paper_files/paper/2022/file/65d32185f73cbf4535449a792c63926f-Paper-Conference.pdf) is missing, as well as at other works by Cyffers and Bellet on decentralized ML. A recent paper by [El Mrini et al., 2024](https://proceedings.mlr.press/v235/mrini24a.html) also considers a local view of decentralized ML algorithms. [Cyffers et al., 2022](https://proceedings.neurips.cc/paper_files/paper/2022/file/65d32185f73cbf4535449a792c63926f-Paper-Conference.pdf) also considers a scenario where the adversary has only a local view and improve upon LDP guarantees. While the DP definitions are different: node-value level DP, meaning that the graph and edges stay constant instead of edge-DP like in this paper, I think thery are relevant.\n\n- The fact that Algorithm 1 requires the harmonic mean of players degrees, $\\bar{\\mathcal{N}}$ and total number of players, i.e., global information, makes it less practical since I think some central entity would be required to communicate that information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5GjqDYXxlY", "reviewer": "Reviewer_eMY6", "summary": "This work proves that for polymatrix games, if either adversary can access an arbitrary number of communication channels or the learning objective is to minimize the Euclidean distance to the equilibrium set, no algorithm can simultaneously find an accurate enough approximate equilibrium strategy profile and guarantee a low level of privacy. The authors further relax the restrictions to consider that the adversary can only access a bounded number of channels. Under this condition, the authors propose an algorithm that can simultaneously find an approximate coarse correlated equilibrium (CCE) strategy profile and guarantee a low level of privacy. Experiments with a varying number of players are conducted to validate the effectiveness of the proposed algorithm.", "questions": "Please see my questions in the weakness part.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The presentation of most parts of the paper is clear.", "weaknesses": "I’m concerned with the problem formulation, the motivation, and the design of the proposed algorithm. \n\nFirst, it is unclear to me whether the utility matrix $U\\_{i,j}$ for each $ (i, j) \\in E $ is known or unknown in Section 2. I guess the authors assume known $U\\_{i,j}$’s as the proposed algorithm explicitly uses $U\\_{i,j}$’s to compute the gradient $\\overline{\\boldsymbol{g}}\\_i^{(t)}$. However, if each $U\\_{i,j}$ is known, I think this problem is just an optimization problem and the equilibrium can be **computed** simply using an optimization method in an offline manner. In this sense, there is no need to use online learning to **learn** an approximate equilibrium strategy profile in an online manner. Consequently, I think no communications between agents and privacy-preserving are needed.\n\nFurther, even if each $U\\_{i,j}$ is known, there are many works in the literature studying how to learn the approximate equilibrium strategy profile under the bandit feedback (i.e., only the rewards of the chosen actions are revealed) in an uncoupled manner (say, [1,2]). These algorithms do not require any communication or coordination between the agents. As such, there is also no need to preserve privacy in these scenarios. \n\nTherefore, I think the motivation for studying privacy-preserving algorithms using the communication of the policy information between agents seems not very reasonable. This also casts doubt on the value of the proposed algorithm.\n\n[1] Cai et al. Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback. NeurIPS, 23.\n\n[2] Ito et al. Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback. COLT, 25.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)