Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions
Authors: Wenjing Yan
Xuanyu Cao
Venue: NeurIPS 2024 poster (2024)
Keywords: Performative Prediction
Decision-Dependent Distribution
Decentralized Noncooperative Games. Cournot Competition
Primary area: algorithmic_game_theory

Abstract: Distribution variations in machine learning, driven by the dynamic nature of deployment environments, significantly impact the performance of learning models. This paper explores endogenous distribution shifts in learning systems, where deployed models influence environments and subsequently alter data distributions. This phenomenon is formulated by a decision-dependent distribution mapping within the recently proposed framework of performative prediction (PP) Perdomo et al. (2020). We investigate the performative effect in a decentralized noncooperative game, where players aim to minimize private cost functions while simultaneously managing coupled inequality constraints. Under performativity, we examine two equilibrium concepts for the studied game: performative stable equilibrium (PSE) and Nash equilibrium (NE), and establish sufficient conditions for their existence and uniqueness. Notably, we provide the first upper bound on the distance between the PSE and NE in the literature, which is challenging to evaluate due to the absence of strong convexity on the joint cost function. Furthermore, we develop a decentralized stochastic primal-dual algorithm for efficiently computing the PSE point. By carefully bounding the performative effect in theoretical analysis, we prove that the proposed algorithm achieves sublinear convergence rates for both performative regrets and constraint violation and maintains the same order of convergence rate as the case without performativity. Numerical experiments validate the effectiveness of our algorithm and theoretical results.

Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions
Wenjing Yan Xuanyu Cao
Department of Electronic and Computer Engineering The Hong Kong University of Science and Technology yan@connect. ust hk, eexcao@ust.ha hk
Abstract
Distribution variations in machine learning, driven by the dynamic nature of deploy- ment environments, significantly impact the performance of learning models. This paper explores endogenous distribution shifts in learning systems, where deployed models influence environments, which in turn alters the data distributions that the learning models rely on. This phenomenon is formulated by peecisionddepentee distribution mapping within the recently introduced framework of performative prediction (PP) (Perdomo et al. 2020p. Our study investigates the performative effect in decentralized noncooperative game, where players aim to minimize private cost functions while simultaneously managing coupled inequality con- straints. In this context, we examine two equilibrium concepts for the studied game: performative stable equilibrium (PSE) and Nash equilibrium (NE), and establish sufficient conditions for their existence and uniqueness. Notably, we provide the first upper bound on the distance between the PSE and NE in the literature, which is challenging to evaluate due the absence of strong convexity the joint cost function. Furthermore, we develop a decentralized stochastic primal-dus algorithm for efficiently computing the PSE point. By rigorously bounding the performative effect, we prove that the proposed algorithm achieves sublinear convergence rates for both performative regret and constraint violations and maintains the same order convergence rate as the case without performativity. Numerical experiments further confirm the effectiveness of our algorithm and theoretical results.
Introduction
Machine learning aims to generalize models trained on given datasets to make accurate predic- tions or decisions on new, unseen data (Hl Naqa and Murphy) (015). The effectiveness of those models depends on the alignment between the training datasets and deployment environments Mamoonero-Candell al. 2008). However, real-world environments are seldom static and often exhibit fluctuations that can severely degrade model performance (Zhou) 2022). In particular, shifts in data-generating distributions, driven by the dynamic nature of real-world conditions, present significant challenges for model deployment.
Distribution shifts in machine learning can occur exogenously or endogenously. Exogenous distri- bution shifts are driven by external factors beyond the control of the learning platforms, such as environmental changes (Chan et al.) 2020) or policy amendments (Wu al.) (00T). In contrast, endogenous shifts arise from the system's 's inherent dynamics and interactions, where the deployed models affect environments, which in turn alters the data distributions that the learning models rely on (Dong et al.) 2018). For instance, an increase in commodity prices may decrease user interest, thereby impacting sales. The key distinction lies in the controllability of endogenous shifts, providing
"Corresponding Author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

an opportunity for designers to either exploit these shifts for improved performance or mitigate unintended consequences (Dean et al. 2023).
While substantial efforts have been made to address exogenous distribution changes, such as covariate shift (Chan et al.] 2020), label shift (Wu et al. 2021), and concept drift (Lu et al. 2018), relatively little attention has been paid to the challenges posed by endogenous distribution shifts. Tackling these endogenous shifts is partieularly challenging as data distributions are intrinsically linked to
the decisions made by the learning model itself (Perdomo et al. 2020). As a result, addressing endogenous shifts may require the explicit modeling of feedback loops, consideration of causal relationships, and the adaptation of models to dynamic environments.
A notable advancement in this area is the recently proposed framework of "performative prediction (PP) (Perdomo et al.) 2020), also referred to as "decision-ddependnn learning" (Drusvyatskiy and Xiao 2023). This framework elegantly captures the dynamic interplay between decisions and data distributions through a decision-dependee aaaeeraaaareeeeeee
mapping, denoted by D(Ø) where I represents the decision variable. By linking 0 to the data distribution, this formulation bridges the gap between model deployment and parameter optimization. Following the seminal work of (Perdomo et al. 22020), growing body of research has emerged, focusing on stability and optimality analysis (Piliouras and Yu 2023 Miller et al., (02T), as well as algorithmic design for various settings, including reinforcement learning (Mandal et al. 2023). online learning (Wood et al., 202I), bandit problems (Jagadeesan et al. 20222, and bilevel optimization (Lu) 2023).
This paper investigates endogenous distribution shifts in a decentralized noncooperative game, where players aim to minimize private cost functions while simultaneously managing coupled inequality constraints. To contextualize this setting, consider scenarios where strategic responses exhibit in learning environments and competitive interactions occur among players. For example, in autonomous vehicular networks, multiple vehicles compete to select their routes under constraints such as road capacities, traffic congestion, and travel costs. The route choices of each vehicle influence traffic patterns and consequently affect the travel times experienced by other vehicles (Mori et al.) (015)). Similarly, in finance, traders compete to maximize profits under constraints like market capacities and inventory levels. The trading strategies of these participants impact market volatility and the distribution of asset prices, creating dynamic pricing landscape (Fattouh and Mabadeva 2014). These dynamics extend to other domains, such as electricity market competition (Moshari al. 2010), ride-sharing platforms (Narang et al., 2023), natural resource extraction (Cust and Poelhekke 2015). and online advertising auctions (Varian 2009).
Despite its pervasiveness, this performative phenomenon has largely been overlooked in the studies of decentralized noncooperative games. This paper addresses the problem by formulating performativity using coupled picision-dependenn distributions, following the PP framework of (Perdomo et al. 2020 However, the intricate interplay between decentralized players and endogenous distribution shifts presents challenging theoretical and algorithmic questions: How do strategic responses in learning environments influence the game's 's equilibrium? How can players adapt their strategies effectively when confronted with coupled decision-dependen distributions? How can we design algorithms to exploit these dynamics for optimal decision 2crisionnmaking? These questions form the core of our investigation, guiding us toward more resilient, adaptive, and efficient learning outcomes in decentralized games, especially in environments characterized by continuously evolving data and decision-making processes. Our main contributions are summarized below:
We initially formulate the problem of decentralized noncooperative games with data perfor- mativity, where selfish players seek to minimize individual costs while managing coupled inequality constraints. Under this setting, we examine two equilibrium concepts: performa- tive stable equilibrium (PSE) and Nash equilibrium (NE), and establish sufficient conditions for their existence and uniqueness. Compared to conventional games, this examination is more complicated due to the interplay between decision decision-making and distribution changes. Notably, we make a significant contribution by providing the first upper bound on the distance between the PSE and NE in the literature. Computing this distance in PP games is challenging due to the absence of strong convexity on the joint cost function, an essential property for determining the optimality gap of performative stable points in previous work. Instead, we characterize the distance by leveraging relations from strong duality and derive result comparable to the findings of the prior work (Perdomo et al. 2020 Lu 2023).

---

To compute the PSE point of the PP-game, we propose a decentralized stochastic primal algorithm based on repeated risk minimization (RRM). The development and convergence analysis of this algorithm face two primary challenges. First, there is complex interaction between decentralized competition and endogenous distribution shifts. Second, players only have partial observation, as they communicate solely with neighbors, despite their private cost functions being influenced by the strategies of all players. We evaluate the performance of our algorithm by two commonly used metrics: performative regret, which measures the suboptimality of the strategy sequence generated by RRM relative to the PSE point, and constraint violation. By rigorously bounding the performative effect, we prove that the proposed algorithm achieves sublinear convergence rates for both metrics. Furthermore, results show that while the performative effect slows down convergence, it does not degrade the order of performative regret compared to the case without performativity (Lu et al. 2020).
Finally, we conduct numerical experiments on a networked Cournot game and a ride-share market. The simulation results confirm the sublinear convergence of our algorithm. Furthermore, the results demonstrate that while greater performative strength leads to a wider gap between the PSE and NE, the discrepancy between these two equilibria remains marginal. This verifies both the effectiveness of the PSE solutions and the accuracy of our distance analysis between the PSE and NE.
Related Work: Among the numerous existing studies, two closely related works (Narang et al. 2023) and [Wang et al., 2023) have considered performative behaviors games. key distinction in our work is that our model requires all players' collective strategies to adhere to the constraints of the learning system, whereas both (Narang et al., 2023) and (Wang et al. 2023) address unconstrained settings. This difference results in fundamentally distinct algorithmic designs and convergence analyses. Our approach employs a primal- dual technique and requires consensus, whereas their methods only rely on local stochastic gradient descent. Additionally, we consider a mathematically richer model compared to /Wang et al., 2023), whose framework is structured in a specific form involving local costs dependent solely individual strategies and regularizer quantifying similarity among neighboring strategies. Furthermore, our algorithm design accounts for practical constraints where players can only communicate with their immediate neighbors, while (Narang et al.) (023) assumes full accessibility to all players' strategies across the entire network. Importantly, our work makes significant contribution by providing the first upper bound on the distance between the performative stable equilibrium (PSE) and Nash equilibrium (NE) gap not previously addressed. Other related works such as (Li et al. 2022] and (Piliouras and Yu 2023). have studied performative prediction in decentralized multi-agent optimization. The former focuses on consensus-seeking agents, while the latter is restricted to location-scale families. Finally, (Yan and Cao (024b) considers the constrained performative prediction problem in a single-agent setting, whereas our paper addresses decentralized noncooperative games. A more comprehensive literature review is provided in Appendix A
Problem Formulation
Consider a decentralized noncooperative game with n players. Each player i selects a strategy (or, interchangeably, decision, action), denoted as 0,, from its feasible set Z2 C Rd. Let the collective decisions of all players be denoted as 0 = col (0)
On), and the collective decisions of all players 0,-1, 1 0
an). for any E [m]] where [n]] denotes the set of integers {1, (1,2....,m)) n... Each player i has a private cost function (E:: O2, O).. which depends on the random variable & E =. the player's 's private decision O,, and the decisions of all other players 0 0... This paper considers scenario where the underlying populations strategically respond to the players' decisions, causing shifts in data distributions. This interplay is modeled by a decision- dependent distribution mapping &, ~ DD (0,, 0_)) for all i E [n]. The objective of each player i is selfishly minimize its performative risk Ee, J., ,,, o-:) (abbreviated as (R, 0 fx)),, subject to a coupled constriant Dnd g 5 0, i.e.
except player be represented as f_, = col (0) 1.
min
DD 00.00.. (E,; 0,, 0.:)
e.en,
subject to (0) + E,
3 0.
Both J.(.) and g.(-) are only locally accessible to player i for all E [m]] the game ① each player solves its private optimization problem to determine the best strategy, given the current strategies
3

---

of all the other players. An equilibrium of the game ① corresponds to a set of strategies where no player can improve its performance by deviating unilaterally from its strategy.
Denote by & == col ( ,...),)))) {n) the concatenation of the variables E, and by J (E: 0)
=
col (Ji (51; 0) ,.... Jn (E.: 0)) the concatenation of the cost functions Jz(+) for all
[n]. A stochastic pseudogradient mapping of J (E:0) is defined as VJ (E:0)
==
col (Va, (E: 0), Ve., In (E,; 0)). We have the following assumption on VJ VJ (E:
Assumption 2.1. There exists a constant 1a > 0 such that the stochastic gradient mapping V. (E: 0) is justrongly monotone, i... (VJ (c: 0) - VJ (E: (5:00) 0') 2 ul| 0 0'12. Yg E, 0, 0' e 2
where = = 5 x...... E and Q == U2
Assumption 2.1 commonly made in the literature of game theory. It suffices to guarantee the existence of Nash equilibrium for a stochastic game with fixed data distributions (Facchinei and Pang 2003, Theorem (b). However, in our paper, since the data distributions are peciison-ddeennenn Assumption 1 does not imply the monotonicity of the gradient mapping of the joint performative risk, denoted by PR(-) : col (PR1()) (.).... .............................. (R),()). Therefore, the existence and uniqueness (E&U) conditions for the Nash equilibrium of the game ① need further investigation.
We define a graph (PP) represent the impact of players' decisions the data distributions of different players In G(P), the weight Ptj > 0 if player j's decision affects player i's data distribution, and Ptş = 0 otherwise. Particularly, Pa represents the weight of self-influence. These weights are normalized as ビ== Pij I, for all i E [m]. Clearly, the larger the weight Pij. the stronger the effect of player j's decision on the data distribution of player i.
Let Wi (D, D') represent the Wasserstein-1 distance between two probability measures D and D'. Following (Wang et al. 2023). we impose the following assumption on the distributions (Dihelm)
Assumption 2.2. For any E [n], there exists a constant E, 2 0 such that, V0, 0' E Ω. the
distribution mapping DD is constrained by Wi (D: (0), D. (0') S e: Pj=1Pt Pij 00 0'
For any i E [n]. the parameter e, bounds the sensitivity of player i's distribution with respect to (w.r.t)) the decision variations of all players. This E-sensitivity property of distributions is conceptually akin to the Lipschitz continuity of functions that quantifies the variation of function values w.r.t argument changes. We also require the following assumptions.
Assumption 2.3. For any i [n], the non-empty feasible set Zt is closed, convex, and bounded, i.e., there exists a constant C. 2 0 such that, V0, E S2 ||0:1|2 I C.
Assumption 2.4. For any E [n] and 0, St the cost function (E;; 0,, 0-.) is convex w.r.t. 0:. Moreover, there exists a constant L; > 0 such that J, (E 0) is L,-smooth, i.c. [. (E,; 0) - VJ, (E': 0') l12 S L, (I|E; e/ll2 + 0 - 0'12) .E. 4 E E,, 0, 0' E Ω.
Assumption 2.5. For any i E [n] and 0; SG the constraint function g, (0.) is convex w.r.t. O,- Moreover, there exist a constant Gg 2 0 such that (-) is Gy-Lipschitz, i.e., [g (0,) 9, (,00) S 1/112, vO,, 0- E S2..
Assumptions 2.3 and 2.5 are widely used in constrained optimization (Bertsekas 2014 Yan and Cao
2024a), and Assumption 2.4lis standard in the PP literature. From Yan and Cao (2024a| Proposition I),
under Assumptions 2.3 and 2.4 the cost function (5 0), Vi E n is Lipschitz continuous, i.c., there
exist a constant G; 2 0 such that [J:(E,; 0) - J
0 < G; (|EE. & ll + 010 0'(l2) V&, & e
E, 0,0 o' St Moreover, Assumptions 2.3 and 2.5 imply the boundedness of (0.) i.c. there
exists a constant B 2 0 such that (0, S B, v0 E Q, i E [n].
3 Equilibrium of the PP-Game
This section examines two fundamental equilibrium concepts of the performative game 1 Nash equilibrium (NE) and performative stable equilibrium (PSE), as defined below. Definition 3.1 (Nash Equilibrium). A vector f := col (0 )Th)) achieves an NE of the game ① if it holds for any E [n] that
H E arg min
Eg (c,.D.(0..00)) (5:3 0 0T.)
0.en,
subject to (0,) + Ent; 9, (0 = 0.
4

---

Definition 3.2 (Performative Stable Equilibrium), A vector 0 = col (0
0 achieves
PSE of the game ① if it holds for any i [n] that
0000 E arg min 0,E0;
LL ( (E:1 02 !.)
subject to (0:) ビzzz 9, (0 0.
NE is fundamental concept in game theory. At NE, each player's a strategy optimally aligns with its own interest, given the strategies of other players. Hence, player has incentive to deviate from its strategy unilaterally. In the case performative games, the computation of NE needs to take into account the data distributions (.).) for all i [n)], as they parameterized by the optimization variable 0. However, this information is often unavailable in practice. Instead, at PSE, the data distribution of each player i [n] is fixed at D; (0 and the PSE point achieves an NE of the game ①T) under the fixed data distribution of its own deployment. This formulation draws benign properties akin problems with fixed data distributions, facilitating the adaptation of existing algorithms. Therefore, PSE is more frequently chosen as performance metric in the literature of PP.
3.1 Existence and Uniqueness PSE
We first establish the condition for the E&U of the PSE of the game D. Our approach relies repeated risk minimization (RRM) for closed-loop retraining. First, we define a mapping T(Ø) := {TT(0)) kie[]] that, for any E [n].
0 T(()) arg min 00 00. (E,s U6, 0':)) w:Eh,
subject to gu(,,) + Ej 9j (0)) 30
The mapping T(0) outputs the NE of the game ① under the fixed data distributions (,, for all i [n). With Assumption! 2.1 the E&UU of this NE is guaranteed, thereby ensuring the validity of the mapping T(0). Based on T(0), the RRM updates 0 at each iteration by
g = Ti(0"), Vi E [n].
(2)
Clearly, r-+1 is an NE of the game 1 under the deployment of 0", Additionally, we have that any fixed point of (2) achieves PSE for the game (I). i.e., O T())m)). By investigating the convergence the iterative equation (2. we have the following sufficient condition for the E&U of the PSE of the game ①T.
Theorem 3.3. Suppose that Assumptions 2.1 2.5 hold. Then. any 0, 8 E Ω the mapping T(0) satisfies
[IT(0) -(()) < v E L7e3 maxxe[m] Pij |00 -0112-
Thus, if is satisfied that
1 Σm 1 Lβ maxje(n) Pij < 1,
(3)
the sequence generated by the RRM converges to a unique PSE point 0 at a linear rate that
1
gas 12
TL De maxye]s] Pij)
||o' 0
The proof of Theorem 3.3 is provided in Appendix According to Theorem 3.3 under Assumptions
2.1 2.5 when condition holds, we have that: the game (1) admits unique PSE, and (ii) the RRM method (2) converges linearly to the PSE.
Since the influence weights (Po))yE(a) are normalized, with Ej=1 1 for all i [n],
generally have that Pi, = (()). Therefore, the contraction condition (3) exhibits good scalability w.r.t. the number of players. Moreover, according to the proof in Appendix B if for any player i [m], its distribution (+) depends only on its own decision 0.. i.c., Pij = for all j * i, then we have
[T(()) - T(8)1l2 S max4e(m) T46, ||5 0 012--
5

---

The contraction of the above iterative equation only requires that maxie(1) Lie; < 1. Furthermore, if all players exhibit equivalent model parameters that I1 = ... I, I. and 61 = ... En and P.j = 1 for all j.j E [n]. condition 3 reduces LE 1, recovering the contraction requirement in of (Perdomo al. 2020 for a single-agent PP case.
3.2 Existence and Uniqueness of NE
First, we define a gradient mapping ( 6-) = (.) Vs, (E,; (,, for any i E [n].
(ō;;
and (ō) = col ( (6). G _ (6) Moreover, for any i E [n]. define
(1))
0..0. (6) = Vu, Bu (. [Jr (E;; 6)] u;=0;
and H6) :- col 0 (6),... H.o... (8)) Then, for any i E [n]] the gradient of the performative risk PR, (0,, 0 i)) w.r.t 0 is given by
Ve, PR, ,0,, 0-)) = G(
0, (0 03,0-,) (-,,0-i)++0 H6. 0:00 ,
(0,, 0-1).
Define VPR(0) == col (V, PR,
VR,,
PR,, (0)). we further have
VP)(0) ( + (0).
From Facchinei and Pang (2003 Theorem 2.3.3(b)), prove the E&U of the NE of the (T). we require the strongly monotonivity of the gradient mapping (P)( Therefore, we have the following sufficient condition for the E&U of the NE of the game (1.
Theorem 3.4. Suppose that Assumptions
2.7 2.5
hold. If is satisfied that
p - Rh
LiE maxje[al vPj
EE Litp >> O,
then, the PP- game ① is strongly monotone and admits a unique NE.
The proof of Theorem 3.4 is presented in Appendix C
Since Pij characterizes the influence of player j's decision the data distribution of player we typically have Pij S Pts for j # i and thus maXje[m) Pij = Pa for all é E [n]. Then, the condition (4) reduces to μ Σ L, VE Le > O. Similarly, when L all ú E [n), we require that μ 2L >> 0, i.c., E S 27. which recovers the condition to guarantee the convexity of the performative risk PR(-), and thereby the E&UU of the performative optimal point of (Miller et al. 202T) for single-agent PP.
Ln 11
en = E, and Pt; = for
P
3.3 Distance Between PSE and NE
- E. LE, max jeln) PPf and α E.=1 G. (1+ E, max y Pig Suppose that Assumptions 2.1 for every PSE point and NE point, we have the following relations:
Theorem 3.5. Define j
hold and j 0. Then,
10pse_ - -0
< 1 V
Gleppa
and [PR(O (P((O) 2 x- Geoppn.
The proof of Theorem 3.5 presented in Appendix D According Theorem 3.5 the distance between the PSE and NE of the game ( depends on the cost functions' parameters μc, {G J. { as well as the sensitivity of the data distributions {Ev}. Larger sensitivity parameters widen the gap between the PSE and NE, while a bigger monotonicity parameter μ reduces it. Notably, when the sensitivity parameter e; = 0 for all i [m]. the game (1) reduces to a conventional stochastic game with fixed data distributions, and as result, the PSE and NE converge to the same point.
To the best of our knowledge, this is the first result the distance between PSE and NE of PP-games. Characterizing this distance is challenging in games due to the lack of strong convexity on the joint cost function J(-). which is an essential property for determining the optimality gap of performative stable points in previous work (Perdomo et al. 2020; Lu 2023). In this paper, we characterize this gap by leveraging relations from strong duality (Boyd and Vandenberghe 2004; Facchinei and Pang 2010). Our result is comparable to the findings in (Perdomo et al. (0200) for single-agent PP problems wherein this optimality gap is bounded by 2LE In our case, when G₁
G, G.
" El En E and Ptg for all i, E [rz]. we have | - 00e Gs
p-Le

---

Algorithm 1 Decentralized Stochastic Primal-Dual Algorithm: The Procedures at Player i, Vi E [n]:
1: Initialize 0: E; arbitrarily, Set X 0 and 0z 0 for all h +
2: for = 1 to d'
3: Exchange 0r 0 and X with all neighbors: 2++
4: Update the estimate 8i for all h + by: 0hh = Enzt aukknn + a..
5: Deploy the model 0 and sample E D, D, ,);
6: Update the primal variable by: 0 Ps. 0 - (Vo.Ji (E: 0 0.) + 7 TV }
7: Update the dual variable by: X ++ = (1 - 72) Ejeni azd23 + mg: (0:)
8: end for
4 Computation of the PSE
Although RRM theoretically has the capability find a PSE point, how to perform risk minimization at its each update remains unknown. Moreover, RRM requires the computation of an NE for each deployment, which computationally intensive. In this section, we present a decentralized stochastic primal-dual algorithm for efficiently computing the PSE of the game (I. Theoretical analysis is also provided on the convergence of the proposed algorithm.
4.1 Algorithm Development
For each player i E [n). define a regularized Lagrangian as
( (0;, 0-, A) = Eg,-D, 0; 0-1) 0())) g.. + +E (0z)
where À E RT is the dual variable. Denote by (.) the Jacobian matrix of g. From the primal-dual theory (Boyd and Vandenberghe 2004 Facchinei and Pang, 2010),, for any y 0, there exists a bounded Lagrangian multiplier X yrar such that the tollowing condition holds:
pse
=Pa
10000 - (Gli). (APse
pee)
+ (0 T {
Vi [n].
pse
Apse + (g,00 + EZji 9j (0)m))
where 7 is control parameter. Thus, given 0 and under & D.(0 (Opee D60) is saddle
point of the Lagrangian C (0,, Ouer A) for any i E [n). The joint saddle point (O A A achieve
the PSE of the game I under strong duality (Boyd and Vandenberghe 2004).
In the decentralized noncooperative game (I]. each player can only communicate with its neighbors. We use (AA) to denote the communication graph of the network, where A (azj)axx represents weight matrix. In ((A), aij aji if there is a communication link between player and play and a.j- = aji- = 0 otherwise. Let AG be the set containing player i and all its neighbors such that j E N₁, if aij O. We assume that the communication graph G(A) is connected and the weight matrix A is doubly stochastic.
To find the saddle point (0 A we develop decentralized stochastic primal-dual algorithm, as presented in Algorithm [ The basic idea of Algorithm [ is to perform gradient update on the primal variables 0 for all [m] and the dual variable X. In the decentralized noncooperative game, each player i E [n] only observes information from its neighbors. However, its private cost funtion (, f 0 ._,) involves all players' strategies. To solve this problem, we let each player i store an estimate for the strategies of all the other players, denoted by 0m.. for all + i. Define a vector O that concatenates all the estimates 0..- In each iteration f, neighbors exchange strategy 0% estimate 00, and dual varible X with each other. Then, each player i updates the estimates O.n. for all h of i by weighted average in Step 4. The primal variable 0 is updated by gradient descent by Step 6, and the dual variable X; is updated by gradient ascent by Step The coefficient 7t is the stepsize the tth iteration for all e [T].
7

---

4.2 Performance Analysis
Before analyzing the performance of Algorithm| | paper. The first metric is performative regret. For any player i [n], its performative regret over T iterations is defined as
we define the performance metries adopted in this
RT(T:==; (o (E,; 0º 0 -PR, (@
The regret (T) measures the suboptimality of the sequence of decisions ......... 0 taken by play relative to 0: Besides, since the decisions of all players are subject to constraints, another performance metric of constraint violation, denoted by Rg (T), is required, defined as
(T) = - E (0))
Any online or learning algorithm is regarded as "good" if both the time-average regret and the time-average constraint violation are sublinear, i.e., limm RT) S o(1) for any E [n] and lim (T)/TT S o(1).
For analysis, make the following assumption on the variance of the stochastic gradient Je (5;; vi E [n].
Assumption 4.1. The stochastic gradient Vo, J (E 8, 8_.) is unbiased that
Vo, (E 8_,) = G d_;) and there exist constants do, σ > 0 such
(D)(
that Di= ())(())) Vo. (E
5-5) ---)-= -G (6,.ō_i) S oB + of lle gosel vO, E SS
Theorem 4.2. Define
? =
P EE= LiE; maxje[m] Pij and
V
3 (oî + +3 L3 (1 Ef maxje(n] Pt)).. Suppose that Assumptions
2.1 2.5 and
4.1 hold
and μ > 0. By Algorithm
if the stepsize satisfies supre(ry " S 1.
w then, the performative regret of
the game ① bounded by
(v ("x Et +t=aaa))
R₂(T) S
vi [m].
Further, the constraint violation is bounded by
(T) S 7r +V(+
+ m1) (++++
(1+E1117)) )²))
For sequence of diminishing stepsize = 7 (m2 + +T) where 72 > 0 and 0 < 17 < we have that: 1) ET= - 0 ( Σi= (t) < O (2). Plugging the above results into
1=1
Theorem 4.2 yields
(T( SO (T b + + i E [n] and R2( S (T3'+T =
+ +
Based on the above two inequalities, the best choice of r such that R.(T) S OTT e [n] and (T) S O(T.). This convergence speed matches that of the decentralized noncooperative game without performativity (Lu al. 2020).
The proof of Theorem 4.2 is provided in Appendix E According to Theorem 4.2 the performative
effect reduces the convergence rate by amplifying the coefficient in the regret bounds. Specifically, as the sensitivity parameters e; increase, the coefficient ğí decreases, leading to a slower convergence rate of (T)) for all i E [n). This occurs because larger e; indicates a stronger performative influence, which more significantly impacts the algorithm's 's convergence. Nevertheless, the perfor- mative effect does not degrade the convergence order of Algorithm comttareeeccmped to the case without
performativity (Lu et al. 2020
Numerical Experiments
In this section, we evaluate the effectiveness of our algorithm and theoretical results by conducting
numerical experiments on networked Cournot game (Abolhassani et al., 2014), which is founda-
tional model in economic theory (Allaz and Vila 1993) for analyzing oligopolistic competitions. We

---

25-
-W
Figure 1: Convergence of time-average regrets and time-average constraint violations.
X-02 LMgA
F-06
120
110 1b1be
PR.8F)
100
10-4
80
10-2
2m03
2w0.2
(wo
C+0
itorations
Itorationn
Figure 2: (a). Normalized distance between 0' and 0"c (b). Total revenue at PSE and NE.
consider a networked Cournot game with five firms selling a single commodity across three markets. Each firm aims to maximize its profit by determining the quantities serves in all markets. The total accommodated quantity in each market is limited by its market capacity. The simulation details and additional numerical results are presented in Appendix F. We also provide additional experiment on a ride-share market in Appendix [F2]]
Fig. illustrates the convergence of the avme-average regrets of five firms, denoted by (t)///t, vi [5]. and the convergence of the time-average constraint violations of three markets. de- noted by 1 E Ei 95g Eis (6')), Vj E [3]. The results demonstrate that both Rt(t)/t and Ei= Σ Giy (0)(0)) approach zero as the iterations increase. This verifies the sublinear con-
vergence of the regrets and constraint violations in Theorem 4.2
Fig. (a) compares the normalized distance between 0', generated by Algorithm and the NE | 0'12-- The NE point is computed based on perfect knowledge of (Di). We consider three different performative strengths: E 0.2, 0.4, and 0.6. It is observed that |00- - 00" ||2/ /1/////|')/ ||2 stabilizes at values approximately equal to or smaller than 10-1 with iterations, varifying the effectiveness of Algorithm | Additionally, larger performative strength leads to a wider normalized distance between the convergent point of 0º and 0Te In Fig. (b), we compare the total revenues, denoted by Σ PR, under the same three settings. We consider two scenarios: 1). "pse", where 0f is generated by Algorithm 1 2). "ne", where 0' is generated by performing the same procedures as Algorithm [ but with perfect information on the distributions (ee))n)) The result demonstrates the close performance of the "pse" approach and the "ne" approach. More numerical results can be found in Appendix F
point 0 nh denoted as lØe - 102
Conclusions: We have studied the performative phenomenon in decentralized noncooperative game where selfish players seek to maximize their individual profits while adhering coupled inequality constraints. We have derived sufficient conditions for the E&?U of both PSE and NE and provided the first upper bound on the distance between these two equilibria. Furthermore, we have developed decentralized stochastic primal-dual algorithm for efficiently computing of the PSE point. Theoretical analysis has demonstrated the same order of convergence speed of our algorithm as the case without performativity. Finally, numerical simulations have been provided to verify the effectiveness of our algorithm and theoretical results.

---

References
Melika Abolhassani, Mohammad Hossein Bateni, MohammadTaghhi Hajiaghayi. Hamid Mahini, and Anshul Sawant. 2014. Network cournot competition. International Conference Web and Internet Economics. Springer, 15-29.
Blaise Allaz and Lea Vila. 1993. Cournot competition, forward markets and efficiency. Journal of Economic theory 59, (1993), 1-16.
Dimitri Bertsekas. 2014, Constrained optimization and Lagrange multiplier methods. Academic press.
Stephen P Boyd and Lieven Vandenherghe. 2004. Convex optimization. Cambridge university press.
Alex Chan, Ahmed Alaa, Zhaozhi Qian, and Mihacla Van Der Schaar. 2020. Unlabelled data improves bayesian uncertainty calibration under covariate shift. In International conference machine learning. PMLR. 1392-1402.
James Cust and Steven Poelhekke. 2015. The local economic impacts of natural resource extraction. Annu. Rev. Resour. Econ. (2015), 251-268.
Sarah Dean, Mihaela Curmei, Lillian J. Ratliff, Jamie Morgenstern, and Maryam Fazel. 2023. Emergent segmentation from participation dynamics and multi-learner retraining. arXiv preprint arXiv:2206.02667 (2023).
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. 2018. Strategic classification from revealed preferences. Proceedings of the 2018 ACM Conference on Economics and Computation. 55-70.
Dmitrit Drusvyatskiy and Lin Xiao. 2023. Stochastic optimization with decision-deependent distributions. Mathematics of Operations Research 48, 2 (2023), 954-998.
Issam EI Naqa and Martin Murphy. 2015. What machine learning? Springer.
Francisco Facchinei and Jong-Shi Pang. 2003. Finite-dimensional variational inequalities and complementarity problems. Springer.
Francisco Facchinei and Jong- Shi Pang. 2010. Nash equilibria: the variational approach. Convex optimization in xignal processing and communications (2010), 443.
Bassam Fattouh and Lavan Mahadeva. 2014. Causes and implications of shifts in financial participation in commodity markets. Journal of Futures Markets 34, 8 (2014), 757-787.
Yiguang Hong, Jiangping Hu, and Linxin Gao. 2006. Tracking control for multi-agent consensus with active leader and variable topology. Automatica 42, (2006), 1177-1182.
Roger A Horn and Charles R Johnson. 2012. Matrix analysis. Cambridge university press.
Zachary Izzo, Lexing Ying, and James Zou. 2021. How to learn when data reacts to your model: performative gradient descent. In International Conference Machine Learning. PMLR, 4641-4650.
Meena Jagadeesan, Tijana Zraic, and Celestine Mendler Dinnner. 2022. Regret minimization with performative feedback. In International Conference on Machine Learning. PMLR, 9760-9785.
Qiang Li, Chung Yiu Yau, and Hoi-To Wai. 2022. Multi-agent performative prediction with greedy deployment and consensus seeking agents. Advances in Neural Information Processing Systems 35 (2022), 38449 38460.
Jie Lu, Anjin Liu, Fan Dong, Feng Gu, Joao Gama, and Guangquan Zhang. 2018. Learning under concept drift: A review. IEEE transactions on knowledge and data engineering 31, 12 (2018), 2346-2366
Kaihong Lu, Guangqi Li, and Long Wang. 2020. Online distributed algorithms for seeking generalized Nash equilibria in dynamic environments. IEEE Trans. Automat. Control 66. (2020). 2289-2296.
Songtao Lu. 2023. Bilevel optimization with coupled decision deeeneen-eependent distributions. In International Confer- ence Machine Learning. PMLR, 22758 22789.
Debmalya Mandal. Stelios Triantafyllou, and Goran Radanovic. 2023. Performative reinforcement learning. In International Conference on Machine Learning. PMLR,
John P Miller, Juan C Perdomo, and Tijana Zmie 2021. Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning PMLR, 7710-7720
10

---

Usue Mori, Alexander Mendiburu, Maite Álvarez, and Jose A Lozano. 2015. A review of travel time estimation and forecasting for advanced traveller information systems. Transporimetrica A: Transport Science 11, (2015), 119-157.
Amir Moshari, GR Yousefi, Akbar Ebrahimi, and Saeid Haghbin. 2010. Demand-side behavior in the smart grid environment. 2010 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT Europe). IEEE, 1-7.
Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian Ratliff. 2023. Multiplayer performative prediction: Learning in decision decision-dependem games. Journal of Machine Learning Research 24, 202 (2023), 1 56.
Juan Perdomo, Tijana Zrnic, Celestine Mendler- Proceedings of the 37th International Conference on Machine Learning (ICML 2020). PMLR, 7599-7609.
Mendler-Dünner, Dünner, and Moritz Hardt. 2020. Performative prediction. In
Georgios Piliouras and Fang-Y Yi Yu. 2023. Multi-agent performative prediction: From global stability and optimality to chaos. In Proceedings of the 24th ACM Conference on Economics and Computation. 1047- 1074.
Joaquin Cuinonero-Candlla, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. 2008. Dataset shift machine learning. Mit Press.
Jia-Wei Shan, Peng Zhao, and Zhi-Hua Zhou. 2023. Beyond Performative Prediction: Open-environment Learning with Presence of Corruptions. In International Conference on Artificial Intelligence and Statistics.
PMLR, 7981-7998.
Hal R Varian. 2009. Online ad auctions. American Economic Review 99, (2009). 430-444-4 434.
Xiaolu Wang, Chung- Yiu Yau, and Hoi To Wai. 2023, Network effects in performative prediction games. In International Conference on Machine Learning. PMLR, 66514-36540.
Killian Wood, Gianluca Bianchin, and Emiliano Dall' Anese. 2021. Online projected gradient descent for stochastic optimization with decision-dependent distributions. IEEE Control Systems Letters (2021), 1646-1651.
Ruihan Wu, Chuan Guo, Yi Su, and Kilian Q Weinberger. 2021. Online adaptation to label distribution shift. Advances Neural Information Processing Systems (2021), 11340-1 11351.
Wenjing Yan and Xuanyu Cao. 2024a. Decentralized Multi-Task Online Convex Optimization Under Random Link Failures. IEEE Transactions on Signal Processing (2024).
Wenjing Yan and Xuanyu Cao. 2024b. Zero-regret performative prediction under inequality constraints, Advances in Neural Information Processing Systems 36 (2024).
Zhi-HHu Hua-Hua Zhou. 2022. Open-environment machine learning. National Science Review 9, (2022), n3ac123.

---

A Related Work
In recent years, the exploration of distribution shifts in machine learning systems has been extended beyond traditional exogenous shifts (Quinonero-Camee Candell et al. 2008), such as covariate (Chan jet al. 2020), label (Wu et al., 202T). and concept (Lu et al., 2018) drifts, to include endogenous shifts resulting from strategic behaviors within the learning platforms themselves. |Peddomo (2020) introduced the framework of performative prediction, which captures the platform's 's strategic responses using decision-dependent distribution mappings. Following this seminal work, significant research effort has been dedicated to investigating the phenomenon of performativity in various scenarios. In particular, (Shan et al., (023) studied the endogenous distribution change in open environments, where data are obtained from a corrupted recision-dependee
(Perooo et al.)
distribution. They proposed effective algorithm with theoretical guarantees by dccoupling the two sources of effects. Lu (2023) investigated the presence of performativity in bilevel optimization. They first established sufficient conditions for the existence of performatively stable solutions and then developed stochastic algorithm to find the PS point. In (Mandal et al.) (023), the authors examined the
performative effect in regularized reinforcement learning problem and showed that repeatedly optimizing this objective converges to a performatively stable policy under reasonable assumptions on the transition dynamics. It is demonstrated in (Drusvyatskiy and Xiao 2023) that typical gradient- based stochastic algorithms can be applied to find performative stable equilibria with a biased gradient oracle.
While most existing work focused on finding performative stable points, there are studies aimed at
identifying the optimal solutions for performative prediction problems (Miller et al. |021 Izzo et al.
2021| Jagadeesan et al. (002). The optimality gap of performative stable points was first presented
in (Perdomo et al. |l.[20200 where their bound is proportional to the strong convexity parameter and inversely proportional to the smoothness parameter of cost functions and the sensitivity parameter of the decision-dependent distributions. The primary challenges in computing optimal points in performative prediction problems lie in the unknown decision-dependent data distributions. To address this challenge, a commonly used method is to make parametric assumptions on the data distributions and then design algorithms to estimate them. For instance, (Miller et al., (022I) proposed a two-stage algorithm find the performative optima for distribution maps in the location family, Lzzo et al. (202T) proposed a PerfGD algorithm by exploiting the exponential structure of the underlying distribution maps.
Among the numerous existing studies, (Narang et al. 2023) and (Wang et al. 2023) are, at a conceptual level, the closest papers
own since they have considered performative behaviors in games. On a technical level, however, these two works are quite distinct from ours since we study completely different problem settings. One defining distinction is that, in our model, the collective strategies of all players must adhere to the learning system's 's constraints, whereas both (Narang ct al. 2023) and (Wang al., [023) are unconstrained. Constraints are unavoidable in certain game scenarios, such as safety and cost constraints in transportation, relevance and diversity constraints in advertising, and risk tolerance and portfolio constraints in financial trading. The constrained problem in our work results in fundamentally different algorithm design and convergence analysis from these two papers. Our work utilizes the primal-dus -uall technique and necessitates consensus, whereas their approach only requires local stochastic gradient descent. Additionally, there are distinctions in the problem settings. In (Wang et al., 2023), the private cost function of each player is structured in a specific form, involving a local cost depending solely on its own strategy and regularizer quantifying the similarity of strategies among neighbors. In contrast, we consider a mathematically richer setting where each player's private cost function depends on the strategies of all players in the game, thus encompassing the model in (Wang et al. 2023). Moreover, our algorithm design takes into account the practical implementation where players can only communicate with their neighbors, while (Narang et al. 2023) assumes that the strategies of all players are publicly accessible across the entire network. This more practical setting poses challenges for each player in observing the entire network. More importantly, although (Narang et al., (023) and (Wang et al. 2023) demonstrated the existence and uniqueness of the PSE and NE for their respective game settings, neither of them offers insights into the distance between these two equilibria. This paper makes a significant contribution by presenting the first upper bound on this distance.
Furthermore, there are works on decentralized optimization of multiagent performative prediction (Li et al. 2022 Piliouras and Yu 2023). Specifically, (Li et al. 2022) focused on decentralized
12

---

optimization with consensus-seeking agents, where the data distribution of each agent depends only on its own decision. Although (Piliouras and Yu 2023) considers multiagent, their study is centralized fashion and their data distributions are restricted to location-scale families. Lastly, it is worth mentioning that one paper Yan and Cao 2024b) has considered constrained optimization in the context of performative prediction. However, (aan and Cao 2024b) studied the single-agent case, while this work considers a more complex model with decentralized noncooperative players and partially observed information about competitors' strategies. Additionally, this paper contributes to the evaluation of equilibria, whereas such analysis has not been involved in Yan and Cao 2024b).
B Existence and Uniqueness of Performative Stable Equilibrium
From the definition of the mapping T(0), we have that
0: Ti(0) = arg min u, EZ
Eg (e) (E,; u. 0'-.) s.t. gu;); + E9 (0,) S 0,
Vi E [r]]
jtt
8. T(()) arg min E.E
E (.) (E, ui, u;; 8',)) s.t. (u(4)) +
Σ 9, (8) S 0,
Vi [n]
jt1
Define ()) Vo (E:: 0':) == Gl (0', O".). From the optimality condition of constrained optimization, we have
G (0'), 0: 5:) S 0, Wi [n].
Define vector Go(O") col (c!²) (0') ... ( (0') that concatenates all the (0'(0) i [m]. Then, have
(Go (0') 0' 8¹) < 0.
(A1)
Similarly, we have
(Gs (8') 0' 8¹) 0.
(A2)
Further, from the monotoniticy of the gradient mapping V.J 0) in Assumption 2.1 have
(Go(O') Go(d'), 0' 8') EE
V (E: 0*) VJ (E: 0' 8¹) 2 m 8111. (A3)
where D(0) (0) (0). Plugging Al and A2
into A3 gives
0| 5/1 < (-Go (8') 0' 8')
$ (Gs (8') Go (8') 0' 5*)
< Go (8') - Go (8') 112 11 -8'1l2
(A4)
From Assumption 2.2 Wi (D, (O), (0') S si Σラ Pij 10, - 0,,13 Along with Assumption
we have that
|Gss (8') Go (8') <
L.E ||,, - 0,
i=1
Σ
Lee max Pij 18 - jE(m)
Plugging the above result into A4) yields
110' - 8'112 <
L7e? max Pıj ||6 011 jE
4
13

---

From the RRM procedure, we know that 0 = T(0") and the PSE satisfies 0 = T( Then, we have
10
0
2 S
of max Pij jE(m)
11
01se| 1
18
1=
Σ
L7 max Psj jEin]
110
0000
Further, if for any player i, its distribution Dj depends only on its own decision 0., i.e. Pij 0 and Psi = 1 for all i,j E [r]] and j * i, then, we have
(I(Gs (8') - Go 6
S
LE |8: 0.112 max L 0
(A5)
sE(m]
Plugging
A5
into
A4
yields
1
00' - 81112 -
max Lis; 118 01l2- /e iE(m)
Correspondingly, we have
(1 max LyEs iE|m)
@ +1
g
110
g
C Existence and Uniqueness of Nash Equilibrium
Based on the results in Facchinei and Pang (2003 Theorem 2.3.3(b)), to show the existence and uniqueness of NE, we need to prove that the gradient mapping VPR(O) of the performative game
(I) is strongly monotone, i.e., there exists a a > 0 such that (VPR(0) ()) VPR(0). 0 8) 2 10 2122 where denotes the strongly-monotone parameter. Since VPR ()) Ge(O) + Ho we have
(VPR(0) VPR(6), 0 -0 6) - (Go - 8) + (Ho(() ( 8).
From Assumption 2.2 we have
(Go(0) - G,()) 5) 2
La max /Pij 0 0-51.. jEin]
Moreover, from the monotonicity of the gradient mapping VJ 0) in Assumption 2.1 we have
(Ga(0) Go (6), 5) = Eg-D(S) (VJ(E:0) - VJJ 8), 6) 2 1 |10 8
Combining the above two inequalities yields
(Go(O) Go - 8) = (Go(O) - Gb( 0 - 8) + (G)(0) G) 5)
n
Li max Pij JEIn]
||0 6112
(A6)
Further, let 76)) 0' + s (0- - 0') for E (0, 1). Then, we have
Jj (E:; 0) J, (5:;0') = 1'' (V., (E:; (())-)). 0 0¹) ds
= 1.' (V., (s)) - 0*) ds.
(A7)
14

---

From the definition of H (6) that (8)== = Vu, 0... [1 (5,; 6)] u,=0,
we have that
(0) (0)) = Vu, Ee Be, 1/'0 (V.I(E;;)))) -- 0²) ds
1,
Vu, Be (V::
0¹)
ds.
(A8)
u.=0.
From Assumption 2.4 we have
Eg E JJ: (E;; BE VJJ (5): LD,,
Along with Assumption 2.2 we know that the function Be (0,00 0 .) VJ. (E:: Lipschitz continuous w.r.t ,. and thus its gradient satisfies
is L,EPP
V u. D. [V (E:: (E:: (s)) $ L,E,pr
(A9)
Combing
A8 and
A9
gives
( HQ
(0)
H
(
(0)| - [ De V.J, [VJ
(, 0'|12 ds
S LEEPpi 11 0'112
where the first inequality holds due the Cauchy-Schwand inequality. This further implies that
Ho( Ho(0')
H (0) -1600 (0)
LE Pss
0
0
Following prior work (Narang et al. 2023) and (Wang et al. that the mapping (0) is monotone w.r.t 6, i.c., (H) Hs(
2023) on performative games, assume
8) 2 0. Then, we have that (VPR(O) VPR(0), 0 - 8) = (0) - 0)
- Hs( 0 8)
(G) Gs(0), + Hs((), 0 5)
+ (Gs(O) - GG()), 0 8) + (H) Ho( 5)
L max VPi jEin
|10 51/2
Based the classical result that strongly monotone game non-empty, closed, and convex set admits a unique NE Facchinei and Pang (2033 Theorem 2.3.3(b)), we have the E&U condition for the NE of the game 1 as given in theorem 3.4
D Distance Between PSE and NE
The computation on the distance between the PSE and NE of the game 1 is based on the strong duality (Boyd and Vandenberghe 2004 Facchinei and Pang 2010). Recall the definitions in Section that
00, A) = (6) (E.: + (. gg,(0)) j
Moreover, define a gradient mapping oi (E,; 0, = O) (0,) X and concatenation
vector Φ = 10,, Φn] For any i E (n]. since (0 > poe is saddle point of the Lagrangian
c(i) (0, paee A) under &, DOPS,), we have that
(0pse 0 A) < c(ii (opse, 0 p
pasc <
((t)
(0,, 0 A pPee) VO, E S2 A E R..
guee
gine
15

---

Similarly, for any i E [n]. ( > the saddle point of the regularized Lagrangian f fe (0,, t =i 2) with Decision-dependen distribution E, D, 0")). Setting in the first part of the proceeding inequality, we obtain
ne
L (0 0 Aue) pse > g (0 ) Vi E [m]. where (A A Ana) g (0) Ez=1 (Afer
0 S Open
(0 O
A Apee)
T
T
A50 (Ei=1 95s (0) )). By the convexity of gra(+)
for all j [m]] E [n], we have that
Σ
93s (0 0
(gss (0 + (Vgji (0 p 07²))
Vggee (0) , 0 Vj E [m].
where the last inequality follows from that gj(0 (0")
2i=1 93 (0.)) S 0. Multiplying the preceding
inequality with X and adding over all j E [m]. we obtain
poe
Iji (0)-0) (ARso) T (0
pse
9js (0
0.ee
0,00
(0, T X pse 0:000 0:T))
(A10)
By the definition of the mapping (,),), for any &; E E,, we have that,
Vg, )
A = (5(E,; 0use , p Vo Ji (E;; 00000 vi E [m].
(A11)
Plugging All into ATO gives
(A A g (Ongo)
(Ei 0pee A A - Vo,Ji (5,; ),0c - -70)) Vi E [m].
(A12)
Likewise, we have the following inequality based on the convexity of the functions (9)(-)):
Ijs (0 2 93s (0TT) + (Vgji (0"t), 0.00 0,7)) Vj E [m], E [m].
Multiplying the preceding inequality with - Aye and summing over j E [m]. we obtain
m
ne
9j
psee
pC
9J (0
nc Ojz (0th)
pse 0
1=1
j=1
i=1
Vg: (0:0) x ne 00h g
where the equality follows from that ΣØt 1 by the complementary slackness condition of the Lagrangian _ oue (0, - A) for all i E [m]] Similar to A12). we have
Dm 9j. (0.²)
(2
g (0"0) = 0, which holds
(A g (OPse)
(E: 0"e, Aao) Ve. 05, -00 0
(A13)
Combining A12 and A yields
(Aeee ) g (o0)))
(d p0e (bse -E,EE, U >0)) 0.00 0
Vo, Ji (E:; 0pse) Vo, 0 000e 0
16

---

Taking expectation on both sides of the above inequality over the distribution (, for all i E [n]] gives
(AD60 ) 9 )
B D. (E,( 0pse , Aoo)
2i(E, 0ne >="),, 0. 0!²)
Σ ( (0ese)
G ppen (fue). 0pme 0-e
(A14)
Since (0) ) is saddle point of the Lagrangian (i) (O pose) have that
given E DO
Eg EE (Eii Opne
A p
0:000 0 S
(A15)
Furthermore, for any E [n]) have
Be, (e (E,; 0ue Ane)
G
(8)
(0 + (O.))
T 2 ne
gase
Vo.
0 (
Vo, (0. 0
(A16)
Since (0.e, A " is saddle point of the Lagrangian L 0ue distribution (0, "))) we have that
(0 0
A A with decision-dependent
Vo. PR, TO OT) + Vg, (0
me 0:00
0 S 0, Vi E [n].
(A17)
Plugging A15
A and A17 into A14 yields
S pse
g ngns
O 0
G( gine
(0"²), 0.50
0.00!
Glf
Open (02se)
(8) (Que). 0.00 0ue
H (Q + gen
(fue)
G(())
(0Dse). 000e Q
- gren
Then, we have
Gene (0"²), Onse 0nc) < (Hae (0""), gus 0nc) From the result in (6)) and the Cauchy-Schware inequality, we have
(goue (Q
Tye max VPg JEIm]
|
gue 1|2 < Ho mr (0 l12 Uue 1|2-
Since the cost function J+(+) is G, Lipschitz for any e [n]. along with Assumption 2.2 we have
Hg ( ll2
(8) r.h om
(0 00 <
Greipa.
Combining the above results yields
2i GiapP
pse
0
1/2 5
-i=1 T,e; max piij
Further, from Assumption 2.2 we have
IR,
(R,(
< 0
8u0l|2 + GrE
Piş
|10
0
1=1
< Gi
1 max vPts) jE(n)
|
- 1|2-
17

---

Then, we have
PR PR(O
PR, (0 - (6"))
i= Giopps
Gi
+ & max vPG))
5e(ml
Di=1 Lie; max Pij
E
Convergence of the Decentralized Stochastic Primal-Dual Algorithm
The proof of this section utilizes the following supporting lemmas.
Lemma E.1. Based on the update rule of the dual variable À in Algorithm for any n 2 0,
X E PT. i [n], and E [T', we have that Ei= 11 S nB².
Lemma E.2. Define X" == n E X; the average of the dual variable over all players at the tth iteration. Then, for any 7tt 2 and t [TT, we have the following relationship:
T1
mx))) 9.(0)) S
Σ
T T2
7
9i (0))
+
1
T
Pt
11
+
9
n
x
2
2
1=1
T
T Σ
+ +1(11 + v VT))
B
Σ
A
x²11
X²)
+
4n
72
tm1
1m1
Am
Moreover, we require the following Lemma on the weight matrix A.
Lemma E.3. Let (A) denote the recond-larges eigenvalue of the weight matrix A. Since A is assumed to be doubly stochastic, it holds that (2(A) < 1 (Hor and Johnson 2012). Furthermore, for any i E [ni,, we construct weight matrix A by removing the ith row and column of A. Let B represent the maximum eigenvalue of A for all i [n]. It has been established in Hong et al. 2006 Lemma 3) that 3 < 1.
With Lemma E.3 we have the following results.
Lemma E.4. Define e'n, == 0th 0% the estimation error of player on the decision of player at the tth iteration, for all i, h E [n] and t E (T). Let ej, denote the concatenation of ein that
ef, := col (ein. in 1)h E (1+1)0 ... ".,,", .ehh) Then, the sum of [le/ over h E [n]] and t e [T] satisfies
nC nyn T(G + VBBC Blelll2 <
T O
g)
Σ
===0
Σ 7t
1-3
1 B-B
Moreover, the sum of | 112 over E [n] and t [T] satisfies
2nC² 1 1- 3 T
2n(n - 1)(G fTBG,) )
T
T
+
Σn = O
7t
(1 3)
Lemma E.5. With the definition X' = 1 Ei X we have the following relationship the
consensus error of the dual variable Xr given by Xi X for all i E [n] and t E [T]:
T
2(n + /T) B
Σ 2t 0
Σ 71
o2(AA (A)
t=1
ΣΣ x  
4(n + vT 2 B
Σ
2 = 0
Σ 7t
(1- 02 A))²
18

---

Next, we start the proof of Theorem
4.2
For ease of proposition, we define the following gra-
dient mappings: for any E
[T)
OE 0.,0- 0_. := (E;; o... 0) + 74h Vg, X
Φ'(-) = ())().... .... (.] D (0, = G (0) + 7 Vg X, and $/ =
8 20, >), ... $ (0, 2)
Then, we have
E 10 g
2
Pa.
0
no
(E': 0 00, x:)] - Ps. @0ee
Bree (@ A pso)
2
I 100
O
2 2
+ Vi Σ E o3 [::00 0 0 23)
n
$b Di (Opse Aprce)
2
2
2%
E 0 p
of ( 0 0z 21)
give (Orse ( >
(A18)
The second term on the right side of (A18) is handled as follows.
n
72
c/ 0g 07, N:)
(O Baee)
2
2
E
c 0 01,00 81,,1))
2 (0', 0 2t)
at
+ x (0), 02 21)
-D
gine
(g
)
|
|
2
1=1
< 3//
>
EE ||0 (5): 0 0/, 21)
2 (0% 0 x1 11 + +3
E
((
0:)
G (OP2e) 1
g"
1=1
1=1
(n)
(8)
Vg: (0)) T X Vg, (0 T A pse 2
+ +,
(A19)
We have the following results on these three terms in the last inequality of (A19).
(5): 0% 0:) c (0% 0.) 1
|
(a) 3- Σ R
Jo
i=1
S 37 (o) 2
0ose (3)
(b) 3 Σ
n
E ( (0% 0.)
ب (0¹) + _ (0') G(( (@pa)) + +G6 (@PSe) -G(() gre (@Pac)
2
2
< <99?' Σ
E
(1)
(0% 0.)
c (0") ||3
2 + 1 (0') c (@nse)
! + ||c.50 (arme)
2
(2) grue (0rme))
2)
1=1
< 3
Σ 1=1
E
L?
0 0²,
1" + L 10 0 || + L.
12
max Púj 110 - - 122 /E(n]
where the last inequality is based on Assumptions 2.2 and 2.4 g,(:) is Gg Lipschitz for all i E [n]. we have that
Further, since the constriant function
Vg. (0:) T x1|
(c) S 6%
E
+
6
E Vg. (Opoe) T A A
s 0 g
Σ
El 1 113 + 6% n 9
1 1|
1=1
< G + 6% 4 G 1
1
19

---

where the last inequality is based on Lemma E.1 Plugging the results of (a), (b), and (c) into (A19 gives
n
R
5/ 0 0; x:) 0
f. guse
(Q A p
2 2
i=1
1 e max pis) )) E 10' - g |
S 33
of + Σ + 377
L
jE(n]
im1
n + 9% 2
2
0 B
0
+
6
n B² G2 + 6% 6r 1 1
(A20)
2
Next, we deal with the last term on the right side of (A18). First, we have the following inequality:
E Φ c 0r 0¹ 2;) T (0nan, )
= E
G (0' 0.)
Gpmn (0vee) + MB
Vg. (0!) T A - Vg. (0)Pe0) T A A
Moreover, we have
-2t
0
p ( Dr
(0% (0%,0.) 0:) - -G/0 (Quee)
2
E
0
0.000 G (0' 01) (i) (00) -27xBB (0' -0 GGg (0') Gg (0Pm))
2
(0'
0
Go (Qns0) - Geaen (Qnso)
< 40
L
0 0-
-2p 1|00 @Dse
1 +
2
Lee: max jE(n]
V 0
1|2
(A21)
where the last inequality is from Assumptions 2.2 2.3 2.4
and the Cauchy-Schwarz inequality.
Further, we have
27
E
0
0.00
Vg. (0.) X; - -VV ( T A
E 00000 0 Vg. (0') T x1) + +47, APS0 2
< 2
1=1
< 2
Σ 1=1
IE (g. (0Pmm)) - g. (0)) T x + GG | 11
S 22 E
9, (0 T (2i - 2²) + g (ORRe) T X² Σ
9. (0') T {
+ GG, |
1=1
i=1
12
< 2n
IE [19, (0 || 2 - 9, (0') X
11, 1
(A22)
where the last inequality uses the fact that g (Øose)
T 0
Define Ā == Ei= Le; maxje(nl Pij. V == 3 (of + +3 L3 (1 + of maxje(m) Ptj ), and
== 30 + Gn GnG | 1 1 + 4CG | pse
|| Plugging the results in A20 A2 and
20

---

A22
into A18
yields
E 0
g
2
$ (1 27000 + vn:) E B110' O 1/2 + Σ L; 0, 0-
+
0
0-
2
2
2
+ 2
E
B x
x111 9: (0.) {t] + nt.. 2
(A23)
i=1
Let sup:21 Yt S E. then
2 + v 1 Tin. Thus, we have
E 1
Opee|
2 2
1
E
0
0
2 2
E
||0rt1
g
4C
n L&E
0
0
2)
2
i=1
97
Σ 0
L3
1
2% B
E
A
x
9,
(0))
X
+
xy
i
1=1
Summing the above inequality over E [T] and plugging into the result of Lemma
E.2
yields
T
E 0'
0
2
2
S
00
Øpse
2 - E 10
0
2
+
40
T
n
LE
0
112
P
+
T
71
LB
0
0"
1
+
23+
B
T
Σ
E
-
11
2
/
1=1
1=1
1=1
9
T
8nB²
x x
2
7t.
P 1=1
[=1
2
Σ
n
T
(
+
1+
Σ
T
it
2
||>112 1
(A24)
1=1
Since
110¹
@
|
2
4C2, have that
T
E
|²
0
g
E
g
gase
112)
(=1
T
1 E
e@@
g
2
1
E
rr
g
+
Σ
1
1
E|
E
0
2
71
TT
71
7c-1
1=2
< 71
1 2
Σ t=2
T
11-11 7--
20
402
(A25)
7/
YT
where in the last inequality is based on the fact that sequence. Further, we have the following relations:
1
0 because "/ is non-increasing
T
ύ--1
2 0¹ 0- 1
Σ EE
max L,
0% max L,
l 11:
(A26)
2
lift
Σ
n
L,E
00
0-
< max Li
01h
0% 1|2
2
2
n
0% |
< max Li
i=1 hppi
< max Livn n
|eill
(A27)
hml
21

---

where the last inequality is based on the fact that va+b-c5 v vb+ + vc for any a, b. c 2 0.
Plugging (A25). have that
A26
and
A277
into
(224)
and utilizing the results in Lemmas E. and E.5 we
r
2 T
T 1
E
0²
O
7x
(0))
n
r
P
t=1
1=1
1=1
0
71
(A28)
PTT
1
Eisn y1 Ei= (())
Since any À E RT satisfies the above inequality, by setting x
we have that
a11+211177 7?)
ET "e Ei=1 91 (89)
2 T
Σ Y
9: (01)
1 Σ
YE
A
(A29)
jin 1 ΣT- 1+= 7p)
As the terms in A29) is non-negative, omitting it in A28
gives
1
E
0
gosel
00
Σ 7t
pAT
1 1=1
Furthermore, since D( [J((E 0g 0DSe) we have that
JE @nsc)| S G₁ 0
0
2l for any i E [m].
R2(T)
[Eg D( [J (E:: 0% m) J (E,; )D
T
< G;
|0 0 ||
1=1
<G
T
0
0.:0
2
/m]
T
1
0
+
7t
Vi
E
[m].
YT
On the other hand, plugging Σl
A29
into
A28
and omitting the non-negtive term
IE 110t g 1 we have
12
E To EL 9: (0:)
T
+
1
<0
76
jun
(1+ (1+
2 7/)
t=1
T
so
Σ -
T
T
Σ T
(0*)
1
Σ
1=1
t=1
t=1
Then, we prove that
T
T
(T)
+
Σ 7t
1
?
7T
22

---

E.1 Proof of Lemma E.1
From the update rule of the dual variables, for any X E RR,, i e [n]], and t E [T]. we have that
Σ
aij [(1- - X3 + (00)
(1- カ + +ウ² (00)
4
7/
||33112 (1- 7))
+ -19.
ag
12
5(1 71) Σ
|A:11 Σ 119.10))12
1=1
<(1 70
|3:1 nB²
We next bound Ei=1 | Vt [T] by deduction. First, since A/ = 0, 71 S 1, and (0) <
B², Vi E [m], we have that Σ AB1 S Σ (0, S nB² S nB²
Assume that
E | I nB²
Since (Te) is a non-incerasing sequence, Σ 112 <
nB 22-1
< nB² 7f
and thus Σ - | 12
+ nB² nB² < (1 - 7:)) 7p
Therefore, for any L E [T], we have
%
E
| 1 S
BB²
nB² i.e., Ei= |1 S nB² which completes the proof.
7. 741
E.2 Proof of Lemma E.2
From the update rule of the dual variables A, for any X E RT, we have that
|
112 =
Σ
(1
7) Σ 2 + +ng. (0))
A
1=1
JEN;
(1 7)
aij (2)- - 23) + (2:- - >) 2a (0:) - -7)
JEN.
Σ aij | x|||2 + || - ~112 + + |19. (0!) -n.2,112
1=1 JEN.
+ 2 Σ
aij (A} - - - 2) + (2 - g: (0)) - A1)
JEN
+2% Σ aij |
X1l1 199 (0.) 232illaa)
(A30)
JEV.
where we use the fact - 7 - in AA3 Next, we simplify the terms in (A3)) First, based on the
inequality (a 6)2 < 2 (a² + b²) for any a, b N O. we have that
111 2 = ΣΣ<2 ai (1(>)-
(A!-x)]13
x
\/-
atj
1=
23

---

In addition, with the result in Lemma
E.
we know that
m
9g (0!) 7 >x 1 s
9. (0)) 12 +2 2 > 11 S 2nB² + 2nB² 4nB²,
i=1
[g: (0)) - >o>i 2 - 9 (0 ll2 + || 112 S B + /nB = (1 Vn)
Moreover, based on the fact that Ei=1 شラ= at (2) - x) = 0 for any & E R,", we have that
n ΣΣ (2
A)
aij (x} - - x²)
j=
i= j=1
||
2ا1د + | -
4ij
x - x
ΣΣ
Furthermore, notice that
(2: (0)) - m2)) = (V g. (01) - 7111A113 + > > Tx - (A X, 9: (0)) + "I
2 (INII - 11:11)
where the last inequality follows that X X =/11113 + +
We also have
n
Bzy
|
11 S Σ
1=1
Plugging all the above results into A30 we obtain
41
11^ x
| - 2112 1 -x" x² x
|
2
1=1
+ 2% (A - -x, (01) +7² (I^11² - |
+4%(11 + vn) B ||| X - X | + 4n
Rearranging the terms in the above inequality and summing over t E [T] gives
T
T
m
(A: - X. (0)))
| 2 2
2
1=1
n
(| - ~11²
|
111)
1=1
| - xx1 113
Σ
4nB²
Σ 7t
T
T ΣΣΣ
2
2(1 + B
x
x
+
||:112-
2
1=1
==1
The last term on the right side of the above inequality is non neg-tvee and can be omitted. Besides, - ~X1
since X = 0 for all i E [n], then Σn=
(IA
|
2 -1 || for any X e
24

---

R.. Thus, we have
(
g.
X (09)
Yt
T
T
n
1+
Σ
|
x
x
?
2
1=1
T
2(1 + vn
B
X
4nB²
Σ '
t=1
1=1
Rearranging the terms in the above inequality yields
T
T
T Σ
T
m())) (0) <
XX
(O(
+
11 2
1
7
1
12
+
ΣΣ
2
1=1
T
2 +
vn)
B
Σ
>111
+ 4nB2
Σ 78
1=1
i=1
1=1
which completes the proof.
E.3 Proof of Lemma
Based on the update rule of Di that 0ih
r+1
= E Eksph Ok + O. vh * and i, h E [n], we have
that
[+1 (+1
= 0%h
0%
g++
Oik kn + +an00 0%+ +0, 0%
anhhh (0)+1 0%)
Recall that A T is the weight matrix formed by removing the hth row and hth column of the weight
matrix A for any h E [n], and eq = col (cin..... e Cia .eh)))))))))))))))) Then,
e = (A, @ La)e + 1- @ (0) 0% Since 8 is the maximium eigenvalue of , for all h E [n], we have that
B Blle, 1l2
(A, @ La)e ll2 E 1 1- @ (0 0%) ll2
0h (4h:0 0" 2h. |1
$ 3E ll + vn - 1
BE|e la vn IB
Vo, Jn (sh: 0% 0/)
+ /n - V (x,l2
s sE|e la vn (G
G (11Ail1))))))
s 8'E e + Vn Σ km
8 n ( + vnBG,).
(A31)
Further, since 0, 0 for any h Summing the above incquality over E
[n). then, from Assumption [T]
2.3
E Ele
110/12 s C.
and E [n]. we obtain
T
T
T 1-2
Elle 1 S nO
gt-
+n 1(G + vnBG,)
34 カー
nC
n2 n - [ vnB
I-
CC
nyn I + VBBG
<
1- 3
1- 3
25

---

On the other hand, taking square on both sides of A311. we have
1-2
Elle 2 || + 2(n 1)(G+ vzBG,)²
8 1t- k-
(A32)
Using the Cauchy-Schwarz inequality yields
2
2
Σ1- 3h
Σ
g n
Σ
ge
k-1
S
k==
k-1
(A33)
k==0
Plugging A33
into A32
and summing over t E (7]. we have that
t
T
gr 2n(n L) + vrBG,)²
T 1-2
ΣΣ
B
Ele
< 2n
Σ
3
p-
1- B 2n(n 1)(G + vnBG,,
t=1
2n 3
7k-
31-
E,4 Proof of Lemma E.5
Let w! = (1 72) EjEN, 0iz2} + ,g (0:) - -EJEN, asd Then, for any i [n]], we have
that
||00
(1 - 72) Σ
and + +ng (0!)
Σ
asd
iEN
JEN
<
Σ
aij Y + M9: (0:)
JEN.
Σ
aij 1
11l + 1 11))
7/
JEN;
S 7: l)B.
(A34)
The first inequality in A34) results from the nonexpansive property of projection, and the third inequality holds by using Lemma
E.1 By the update rule of X, for any i [m]) we have that
X X
aij w/. JEN,
Σ
Define concatenation vectors X col (Ai,.... 2hh and w/ col (wf, ,.))). Then, for any t [2], we have
X X+1= = (A ② Im) X :.
(A35)
Since X' = 1 Ei A,. we have that
(In 1m) X'= ((..
1
Im
X 14 [T).
(A36)
n
Combining A35 and A36 yields
H+1 (A A + ((1
11
3 Im
w Vt E [T).
26

---

Firmo
Firm
Firm
Firu
Market 3
Market
Figure 3: A networked Cournot game with five firms and three markets.
Since 2 = 0 for all i E [n]. then A 1 0. Based on the fact that || - 11
S
2, we have that
|
-(11-) 11"
\ ++
= -11 ++1 112 = (A 2 Im) A
2
I
w
$ ||
((
(1-
11
2
D
w
2
n
2
$ (2
11
+ 2 2||Wo112
2
(A)* 1 #12
k=0
$ 2nn + VT) (2(A))
where the last inequality based on the result in A34). yields
Summing the above inequality over [2]
T ΣΣ
T 2-2
2 + Vn
B
(2(A) 7-
(A)
==
t=1 1
2(n
Vn)B
(A)
7kk
Similarly to the calculation of Σ >5
| in Section
E.3
we have that
X
x 1 S
4(n + 22
(1 o=o2
k=1
Simulation Details
F.1 Networked Cournot Game
The Cournot game is a foundational model in economic theory (Allaz and Vila 1993) for analyzing oligopolistic competition, where a limited number of firms dominate a specific market. Cournot games, all firms sell a homogeneous commodity and aim to maximize their individual profits by independently and simultaneously determining optimal production quantities. The total quantity produced by all firms is constrained by factors such as market capacity, raw material availability, and environmental considerations. The profit of each firm depends not only on own production quantity but also on the quantities chosen by its competitors, they influence the demand price determined
27

---

0.4
0.6
Price
2-
D50
M1
M2
M3
M1
M2
M3
M1
M2
M3
Figure 4: The demand prices of three markets.
E = 0.2
& 0,4
0.6
6-
6
Quantity
4-
4
2
pse 2
2
0
F5
F5
E = 0.2
E = 0.4
E = 0.6
4
4
Quantity
2
2
pGe
0
F1
F5
F5
F1
F3
F5
E 0.2
0.4
0.6
Quantity
1-
F4
Figure 5: The serving quantities of five firms to three markets.
by the market's demand curve and the total production quantity. There are strategic interactions between firms and markets in the Cournot game. According the law of supply and demand, an increased production quantity drives down the demand price, and vice versa. The Cournot game model has diverse applications in various fields, including supply chain management, electricity market competition, natural resource extraction, online advertising auctions, and the telecommunications industry.
In this experiment, we consider a networked Cournot game comprising n firms selling a single commodity across markets, illustrated in Fig. [] Each firm i [n] determines its output quantity 0, = col (fa..... ...).)))))))))............ subject to the constraint of its production capacity Q; that Σ 6₁ S Qi Here, f, denotes the quantity of player sold to the jth market. The total quantity allocated to market j is limited by its market capacity B,, satisfying the condition that Σn= 05 S B, Vj E [m)) Thus, the local constraint of player associated with market, j is
(..) = O2g- B,/n, Vi E [n], [m].
Let (0.) col (0.), m6m (.)), Vi E [m).
28

---

The cost function of firm i is defined as
J- d. 0; Σ Pr j=1
where d, = col (d.1," ... dam) and dz represents the cost that firm sells a unit of its product to the jth market, Vi E [n], E [m]. d, includes the cost of raw material, transportation, maintenance, etc. In J4, the term Pj denotes the unit demand price of market j determined by its market demand curve and the total production quantity, given by
Pj -
G
015
Vj
[m].
(A37)
d
where cj. dj Aj. and rj > 0 are constants, Ej is random variable. Due to the interaction between firms and markets, the demand price can fluctuate with production quantities, represented by Ey ~ D0) Note that the quantiy--ependent distributions (0) for all [m]] are unknown by players. For any j E [m]. the variable Ej is defined as
E EJ + 6 -jr=1 ajj
Σ 0ig
where EJ is the random base component, E 2 0 represents the performative strength of markets, and 0j is the relative strength market j for any j E [m]] According to the law of supply and demand, an increased production quantity generally decreases market's 's demand price, which corresponds to the setup that a, S for all j E [m]. Thus, the objective of each play i [n] in the network Cournot game is formulated by
min o.En.
E (0,, d, 0,
Σ 1=1
p5Oij
subject
Bi Σ Bvg S Bj. [m]. p'i
In the simulation, set n and m 3. The network structure is as depicted in Fig. Each element of the communication weight matrix A = (azj) is set to be ai [N:11 and [ is the cardinality of Mg. The production capacity Q2 is randomly and uniformly drawn from [10, 12] for all i E [5]. and the market's 's capacity By is randomly and uniformly drawn from [10, 15) for all j [m]] All entries in d, Vi [ni] are randomly and uniformly drawn from [1, 1.5]. The distribution of Eg is set to (aa 1), 2.5). 7.5). The performative power a, is randomly and uniformly drawn from (-1, 0], for all j [3]. Other settings are: A, = 10, C = 10, d, = 5 and T, = 2, Vj [3].
Fig. compares the demand prices of three markets PSE and NE with performative strength 8 = 0.2, 0.4, and 0.6 and Fig. ccompares the corresponding serving quantities five firms to these three markets. The results suggest that, although larger performative strength leads to wider gap, the difference in these two indicators between the PSE and NE remains insignificant. This confirms the effectiveness of PSE solutions and our distance analysis between the PSE and NE as stated in Theorem 3.5
F.2 Ride-Share Market
We further examine example of ride-share market, where multiple platforms compete to maximize their individual revenue by offering shared rides in competitive areas, taking into account opera- tional constraints and market demands. This experiment builds upon the semi-synthetic simulation conducted in (Narang et al. 2023), adapting it to our constrained noncooperative game setting.
Consider ride-share market with platforms competing in areas. Each platform i [n:] aims to maximize its revenue by determining the quantities offers at the jth area, denoted as 0,y, for all j E [m). Let 0; 0...... 0am] IT. The total number of rides provided by each platform cannot exceed a predefined limit Q. given by Σ Osj Qi. Vi E [n). Let pj denote the demand price
29

---

t=03
100
100
360
120
140
100
220
300
00
the
We
40
30
Iaeations
Figure 6: Convergence of the time-average revenues of three platforms.
-50
-40
-03
-80
-AA
Iterations
heeraiors
Figure 7: Convergence of the time-average constraint violations at eight areas.
the jth location, which fluctuates with the total offered quantity at the area following the law of supply and demand. We adopt the same model for {py} as in the network Cournot game, given by Additionally, the maintenance costs associated with platform operations may vary across locations due to factors such as distance or labor costs. Let d; E R" represent the cost vector of platform at all areas. Then, the inverse of the revenue function for each platform can be expressed as
(37
J4 -- 25-2Pe
p,O d. Vie [n].
Assume that each platform only offers one type of ride. Considering the diverse ride characteristics, such as shape and speed, we use h; to denote the spatial occupancy of each ride offered by platform i. The accommodated ride quantity at each location is constrained by By due to parking availability and road conditions, such that Σi=1 h,0rs < By. Then, the objective of each platform i E [n] in the ride-share market is formulated as
m
(igg Er,0 d. 0: o.cn.
min
i=1
(A38)
subject
h,0g
Σ Cho0ss S B3, Vj E [m]. i'
The simulation setup is based on dataset from prior Kaggle competition Our study focuses three ride-share platforms (Uber, Lyft, and Via) and eight competing areas within New York. We randomly and uniformly assign the total number of rides, Qi from the range [200, 400] for each platform E [3]. Similarly, the accommodated capacity, B,, is randomly and uniformly drawn from [50, 150) for all сÿ is set as min (iaxmaa(X((()) 1), 5). Additionally, we set the following values
[8]. All entries in d, Vi [n] randomly and uniformly drawn from [0.2, 2.2].
The distribution for all areas j E [8]: A₁ = 5, = 5, d, = 5, and Tj = 2.
Fig. compares the convergence of the time-average revenues of these three platforms: Uber, Lyft, and Via, denoted by - B (J 0²) }}. We consider three performative strengths:
The data is publicly available https//wwww.aaggl..coo///bbbbbee -ot--y---daaatee-boooomm
30

---

10*
0-0.1
==0.3
Ijo -m-
109
10a
10-
10a
10a
10a
Iterations
Figure 8: The normalized distance between 0 and 0
& 0.1. and 0.3. Similarly to Fig. 2 (b), we compare the performance of Algorithm represented by "pse", and the performance of Algorithm with perfect knowledge of data distributions D, (0) for j [m]. It is observed that, with mild performative strength E, the revenues achieved by the "pse" are close to those of the "ne" for all three platforms. However, as increases, the gap between the two approaches widens, although it remains relatively small. This observation confirms the analytical result presented in Theorem 3.5
Fig. shows the convergence of the time-average constraint violations at eight areas by Algorithm [ denoted by = Σi=
9s5 (0. ).j = 1,..., 8, with performative strengths of ı = 0.1, 0.2, and 0.3. The constraints hold for all three performative strengths. However, increases, the platform tends to allocate fewer rides. This may be attributed to larger market fluctuations associated with higher leading more conservative allocation.
Fig. compares the normalized distance between 6 and the NE point 6tC. denoted as ||0' gue 2 1000 2. with performative strengths: E = 0.1, 0.2, and 0.3. The result is quantitatively analogous to the findings presented in Fig. g Firstly, 0* gradually approaches g with iterations. Secondly, a higher performative strength leads to wider normalized distance between the convergent
point of 0f and 0"c
Fig. compares the demand prices of eight areas and the ride quantities offered to them by three platforms at PSE and NE. We consider performative strengths 0.1 and 0.3. It observed that the values of these indicators at the PSE and NE are close to each other when 0.1. However, a noticeable discrepancy arises when 0.3.
Additionally, we display the demand prices of eight areas in New York in Fig. 10 with different performative strengths: & 0.1, 0.2, and 0.3. It can be observed that, while prices vary by location, smaller values of Æ generally correspond to higher prices. The offered quantities of these three platforms the eight locations are illustrated in Fig. TT The results indicate a conservative allocation as the performative strength increases. Furthermore, with the cost of these three platforms at different locations in Fig. 12 obtain the revenues of the platforms Uber, Lyft, and Via in different areas, as illustrated in Fig. 13 Clearly, performativity has an inverse effect on revenues, and the stronger the performative strength, the lower the revenues.
31

---

t=1
0
2.0
2.0
1.5
0.5
0.5
0.0
0.0
Loc1 Loc4 Locs Loc7
Loc3
Loc6 Lac8
Uber:g = 0.1
Uber:g 0.3
Quantay
10
Loc1 Loc2 Loc3 Loc4 LocS Locs Loc7 Loca
Loc1 Loc2 Loc3 Lac4 LocS Loc6 Loc7 Laca
Lyft:g=0
Lyft:8=00
Quartay
30
20-
Loc1 Loc4 Loc6 Loc7
Loc1 Loc2 Loc3 Loc4 Loc5 Loc6 Locs
Via:6= 0.1
Via:E= 0.3
H
quantay
20
10
Loc1 Loc2
Loc3
Loc4 Loc5
Loc5 Loc7 Loc8
Loc1 Loc2 Loc3 Loc4
Loc5
LocB
Loc7 Loca
Figure The demand prices of eight areas and the ride quantities offered to them by three platforms.
Price: 0.1
Price: 0=0.2
0=0.3
Scant
15
15
Way Word Sinkea
Eaco
6.
Figure 10: The demand prices of different areas.
32

---

Uber: c=0.1
Lyft: E-0.1
g=0.1
Pore
Val Selaw
Book
Uber: E-0.2
Lyft: 6=0.2
E=0.2
Cue
Uber: 8=0.3
Lyft: 0-0.3
Via: c=0.3
Park
28
20
20
Figure 11: The quantities of platforms offered to different areas.
Cost: Uber
Cost: Lyft
Cost: Via
Figure 12: The cost of platforms in different areas.
33

---

Uber: 6=0.1
Lyft: E-0.1
Via: ==0.1
Uber: E-0.2
Lyft: c=0.2
Via: 2=0.2
Leyrens
Hetee Seweley
Uber: 6=0.3
Lyft: 0-0.3
Via: c=0.3
Levon
Figure 13: The revenues of platforms in different areas.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
2. Limitations:
Does the paper discuss the limitations of the work performed by the authors? [No]
Answer: [No]
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: Yes)
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Ys]]
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: (Ys]]
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics httppp////.eeese.cc/////////ccca
Answer: [Yes]
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
35

---

Answer: [NA]
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
13. New Assets
Question:
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
36


Reviews:
[{"review_id": "L35yq0ouCa", "reviewer": "Reviewer_QNeF", "summary": "The paper studies the effect of endogenous distribution shifts stemming from the underlying interaction of the learning system, as formalized in the recent framework of performative prediction. In particular, the paper focuses on the performative effect in a non-cooperative game in which players endeavor to minimize individual cost functions while satisfying coupled constraints. They consider two natural equilibrium concepts, and provide sufficient conditions for their existence and uniqueness. Further, they provide a bound relating the distance between those two, and they develop a decentralized stochastic primal-dual algorithm for efficiently computing one equilibrium that achieves sublinear rate under various assumptions. Numerical experiments support the theoretical results.", "questions": "- The citation style is not used correctly; for example, \"unseen data El Naqa and Murphy (2015)\" should instead be \"unseen data (El Naqa and Murphy, 2015)\". That is, use parenthesis when the citation is not syntactically part of the sentence. This is done consistently thoughout the paper.\n- I would like to see more discussion concerning the papers by Li et al. (2022) and Piliouras and Yu (2023). It is not quite clear how those results relate to those in the paper.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I believe that the paper makes a concrete contribution that fills a natural gap left in the literature. One can view most of the results derived in this paper as the natural counterparts of the results obtained by Perdomo et al. but in a more general non-cooperative game setting, which can be motivated in a number of applications. The results obtained in the paper take an important step toward characterizing the performative effect in multi-player non-cooperative settings. The theoretical results are technically non-trivial, and all claims appear to be sound; I did not find any notable issue. The related work section is also quite thorough, and the most relevant papers have been discussed adequately to the most part. Finally, the presentation and the writing are of high quality, and the main body goes a great job at giving high-level sketches of the main ideas behind the proofs.", "weaknesses": "In terms of weaknesses, I believe that some of the assumptions necessary for the theoretical results (Assumptions 2.1-2.5) require further justification. In most cases, the authors simply claim that the assumption is quite standard in some other settings, but that itself is not sufficient justification. The authors need to argue that the assumptions are also aligned with the applications considered in their paper, otherwise they appear to be artificial. Perhaps an example could serve to make that point.\n\nBesides the point above, an important caveat of the paper is that most of the results appear to follow from relatively standard techniques in the literature, and so the technical novelty is limited. Although the setting considered in the paper is, to my knowledge, novel, it seems that it can be readily reduced to well-understood problems in game theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.**\n\n**Reply to Weakness 1:** Thank you for the useful comment. We have provided justifications for the conditions outlined in Assumptions 2.1-2.5 through both simulation examples, specifically the networked Cournot game and the ride-share market. Below is an excerpt of the justification for the networked Cournot game:\n\n> Given the formulation of the networked Cournot game, it is evident that the stochastic gradient mapping of $J(\\cdot)$ adheres to Assumption 2.1, as expressed by:\n>\n> $$\\left\\langle \\nabla J\\left(\\xi;\\theta\\right) -\\nabla J\\left(\\xi;\\theta^{\\prime}\\right), \\theta - \\theta^{\\prime} \\right\\rangle \n  \\geq \\mu ||\\theta - \\theta^{\\prime}||_2^2$$\n>\n> with $\\mu =2\\varepsilon \\min_j \\frac{\\alpha_j}{\\sum_{j^{\\prime}=1}^m\\alpha_{j^{\\prime}}} $, where $\\varepsilon\\geq 0$ denotes the performative strength of markets, and $\\alpha_j$ represents the relative strength of market $j$ for any $j\\in[m]$. \n>\n> Moreover, for any $i$, the quantity-dependent distribution $D_i(\\theta)$ satisfies \n>\n> $$\\mathcal{W}_1(D_i(\\theta), D_i(\\theta^{\\prime})) \\leq\\varepsilon\\sqrt{\\sum_j\\frac{\\alpha_j}{\\sum_j^\\prime\\alpha_j^\\prime}||\\theta_j-\\theta_j^{\\prime}||_2^2}$$\n>\n> in accordance with the condition in Assumption 2. \n>\n> Furthermore, each local cost function $J_i(\\cdot)$ demonstrates smoothness with a parameter $L \\geq \\varepsilon \\max_j\\frac{\\alpha_j}{\\sum_{j^{\\prime}=1}^m\\alpha_{j^{\\prime}}}$ and thus satisfies the condition in Assumption 4.\n> \n> Given that the output quantity of each firm is constrained by an upper bound $Q_i$, Assumption 3 is inherently fulfilled with $C>\\max_iQ_i$. \n> \n> Lastly, the Lipschitz condition of constraints in Assumption 5 holds true for any $G_g\\geq 1$, under the accommodating quantity constraints of markets. \n>\n> Overall, the formulation of the networked Cournot game satisfies all assumptions required in our study.\n\n**Reply to Weakness 2:** We would like to highlight the following technical contributions of this paper:\n\n1. We evaluate the conditions for the existence and uniqueness of both NE and PSE. The NE evaluation needs to quantify the performative effect that the studied performative game requires the condition $\\mu - \\sum_{i=1}^n L_i \\varepsilon_i \\max_{j\\in[n]} \\sqrt{p_{ij}} -  \\sqrt{\\sum_{i=1}^n L_i^2 \\varepsilon_i^2p_{ii}}>0$ to guarantee monotonicity while the non-performative counterpart (Lu et al., 2020) only requires $\\mu>0$, which is an assumption of the paper. The PSE is a unique concept in performative games and has not been considered in conventional games without data performativity.\n\n2. This paper makes a significant technical contribution by presenting the first upper bound on the distance between PSE and NE, which is significant to understand the impact of data performativity in games. Such bounds have been a major focus in prior research on performative optimization but are challenging to quantify in games due to the competitive nature of players. We leverage relations provided by strong duality and derive a result comparable to the findings in performative optimization settings. \n\n3. The convergence analysis of our decentralized algorithm needs to carefully control the deviation caused by data performativity. The decentralized nature and the presence of constraints further complicate our analysis. Nevertheless, we derived a result that preserves the order of convergence as the case without data performativity (Lu et al., 2020). Our results demonstrate how performativity influences convergence, slowing it down by a coefficient $\\tilde\\mu := \\mu - \\sum_{i=1}^n L_i \\varepsilon_i \\max_{j\\in[n]} \\sqrt{p_{ij}}$, which offers a theoretical foundation for designing decentralized performative game systems.\n\n**Reply to Question 1:** Thank you for pointing this out. We have carefully revised the citation style throughout our paper.\n\n**Reply to Question 2:**  Thank you for the advice. We have added more discussions on the works Li et al. (2022) and Piliouras and Yu (2023) in our paper. Similarly to our work, Li et al. (2022) and Piliouras and Yu (2023) also studied multiagent systems with performativity but in constraint-free scenarios.  Specifically, Li et al. (2022)  focused on decentralized optimization with consensus-seeking agents, where the data distribution of each agent depends solely on its own decision. They investigated conditions for the existence and uniqueness of performative stable solutions and provided theoretical analysis on the convergence of gradient descent algorithms in multiagent performative prediction systems. In contrast, Piliouras and Yu (2023) studied multiagent systems in a centralized fashion with data distributions restricted to location-scale families. Under this setting, they explored the existence conditions of performative stable points and demonstrated the equivalence of performative stability and performative optimality.\n\n**We sincerely appreciate the reviewer's positive assessment. The strengths you have identified are crucial for evaluating this paper and align with observations from other reviewers.** \n\n**Given our contributions to the field of performative prediction and noncooperative games, we respectfully request that you consider improving the rating scores to enhance the likelihood of acceptance for this work. We thank you for your time and thoughtful consideration.**", "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": "jzYo4fKNLo", "reviewer": "Reviewer_ReB3", "summary": "In this paper, the authors introduce the framework of decentralized noncooperative games incorporating the performativity factor and investigate the existence and uniqueness of two equilibrium concepts: Nash equilibrium and performative stable equilibrium. The distance upper bound between NE and PSE is firstly provided. To compute the PSE point under the given problem settings, a decentralized stochastic primal-dual algorithm is proposed, and corresponding convergence analyses are conducted.", "questions": "**Typo List**: \n\n- Line 176, \"there exists a constant **$C\\leq 0$** such that ...\", it should be $C\\geq 0.$\n\n- After Line 208, second line of optimization problem, $g_i(u_i)$ should be $g_i(\\theta_i)$.\n\n- In the problem after Line 727, symbol $\\theta$ does not use same font. Same typo in equation (A37).", "limitations": "Please answer the questions in weakness part. I will reconsider the rating based on the author's response.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow, clearly presenting the authors’ logic. The proof of the theorem is solid.", "weaknesses": "- Since the authors proposed the primal-dual algorithm to find the PSE solution, how can the NE be found under the performativity framework? In the Simulation part, how do the authors find $\\theta^{ne}$?\n\n- The analytical techniques of the Decentralized Stochastic Primal-Dual algorithm appear to be a special case of the approach in Wood and Dall’Anese (2023), as the primal-dual algorithm can be transformed into a min-max problem. Are there any unique analytical techniques used in this paper? Could the authors provide a comparison between this work and Wood and Dall’Anese (2023)?\n\n[a] Wood, Killian, and Emiliano Dall’Anese. ``Stochastic saddle point problems with decision-dependent distributions.\" SIAM Journal on Optimization 33.3 (2023): 1943-1967.\n\n- In decentralized noncooperative games, each player is assumed to be selfish. Why would they want to communicate with their neighbors and share their information via a graph? In Line 4 of Algorithm 1, the estimator is constructed by a weighted average of the local parameter and neighbors' information. Is this reasonable in a competitive problem setting? I am confused by the logic of these game settings. \n    \n- In Line 6 of Algorithm 1, the gradient is given as $\\nabla_{\\theta_i} J_i(\\xi_i^t; \\theta_i^t, \\hat{\\theta}_i^t) + \\underline{\\gamma_t} \\nabla g_i(\\theta_i^t)^\\top \\lambda_i^t$. Is this $\\gamma_t$ a typo? The same concern arises in the equation after line 278.\n    \n- Is Assumption 4.1 used in the proof of Theorem 4.2? Also, in Assumption 4.1, where is the $\\delta$ in the right-hand side of the assumption inequality?\n\n- In Line 347, the performative strengths are set as $\\rho=0.2, 0.4, 0.6$. I suggest using $\\varepsilon$ to denote performative strength to maintain contextual consistency. Additionally, does this setting imply that all ${\\cal D}_i(\\theta_i)$ admit the same shifting strength?\n    \n- How does the spectral gap of graph ${\\cal G}(A)$, i.e., graph topology, affect the convergence results in Theorem 4.2?\n\n- Since Theorem 3.5, the upper boudn of PSE and NE is one of the major contribution of this paper, is there any corresponding simualtion which can support the theoretical results?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for recognizing our contributions and for the constructive comments. Our point-to-point responses are given below.**\n\n**Reply to Weakness 1:** Given the explicit expressions of the decision-dependent distributions $D_i(\\theta)$ for all $i$, we can compute the exact gradient of the performative risk PR($\\theta$). Consequently, the Nash Equilibrium (NE) can be asymptotically determined through best response dynamics. This approach is structurally similar to repeated risk minimization but crucially accounts for the decision-dependent nature of the distributions, rather than fixing them at the current deployment for each update. In our simulations, we employ this method to calculate the NE, which serves as our baseline for comparison purpose. We appreciate the reviewer's observation and have incorporated detailed explanations of the NE computation process in the simulation section of our manuscript. \n \n**Reply to Weakness 2:** We appreciate the reviewer for bringing this reference to our attention. We have incorporated a comprehensive comparison of our work with [a] in our paper, as summarized below:\n- [a] investigates centralized minimax optimization, whereas our work addresses a more complex model involving decentralized noncooperative players with partial information observation. Our analysis needs to account for consensus and competition among players. The NE of a game generally does not correspond to the optimal solution of its corresponding optimization problem.\n- [a] requires a more stringent assumption of strong-convexity-strong-concavity on the minimax problem. In contrast, our paper only necessitates the stochastic gradient mapping $\\nabla J(\\xi; \\theta)$ to be monotone, which is a weaker condition than strong convexity.\n- We characterize the existence and uniqueness of the NE and PSE, which are concepts unique to game theory.\n\n**Reply to Weakness 3:** In noncooperative games, players are assumed to be both selfish and rational. Despite their self-interest, players have incentives to share information as it enables more effective optimization of their individual strategies, potentially leading to improved personal outcomes and enhanced overall game stability. The vast majority of existing research on decentralized games is predicated on this assumption of rational players. Without this premise, player behavior could become unpredictable, rendering meaningful analysis challenging, if not impossible.\n\n**Reply to Weakness 4:** The symbol $\\gamma_t$ is not a typo; rather, it serves as a crucial coefficient for regulating the step size of the optimization process in Algorithm 1.\n\n**Reply to Weakness 5:** We appreciate the reviewer's observation. Assumption 4.1 pertains to the stochastic gradient variance of $\\nabla_{\\delta_i} J_i(\\xi_i;\\delta_i, \\delta_{-i})$, which forms the foundation for Theorem 4.2. To enhance clarity, we have revised Assumption 4.1 and added it into Theorem 4.2 as a necessary condition.\n\n**Reply to Weakness 6:** Thank you for the valuable advice. We have substituted $\\rho$ with $\\varepsilon$ to denote the performative strength. You are right that this setting implies that all markets exhibit an equivalent shifting strength.\n\n**Reply to Weakness 7:** Let $\\sigma_2(A)$ denote the spectral gap of the weight matrix $A$. The spectral gap affects the convergence results in Theorem 4.2 by a coefficient $\\mathcal{O}\\left(\\frac{1}{1-\\sigma_2(A)}\\right)$, which is shown in Lemma E.5 of the Appendix. We omit this coefficient in Theorem 4.2 since this paper primarily concentrates on the impact of data performativity, which slows down convergence by a coefficient $\\tilde\\mu := \\mu - \\sum_{i=1}^n L_i \\varepsilon_i \\max_{j\\in[n]} \\sqrt{p_{ij}}$.\n\n**Reply to Weakness 8:** Thank you for the question.  In the simulation of the networked Cournot game, Fig. 2(b) compares the total revenue of all firms at the PSE and NE. Figure 4 contrasts the demand prices across five markets, while Fig. 5 illustrates the quantities served by five firms in different markets at both PSE and NE. For the simulation of the ride-share market, Fig. 6 compares the time-averaged revenues of three platforms at PSE and NE, whereas Fig. 9 depicts the demand prices in distinct areas and the corresponding ride quantities offered by various markets at both PSE and NE.\n\n**Reply to Questions:** Thank you for your careful review.\n\n1. We have rectified this typo in our manuscript.\n2. In Line 208, the optimization variable is $u_i$ instead of $\\theta_i$, thereby the expression of $g_i(u_i)$.\n3. In Line 727 and equation (A37), the bold font $\\boldsymbol{\\theta}$ represents a vector that $\\boldsymbol\\theta_i = [\\theta_{i1},\\cdots,\\theta_{im} ]^{\\top}$ for all $i$, where $\\theta_{ij}$ denotes the product quantity that firm $i$ sells to the $j$th market and is represented in non-bold font as a scalar.\n\n**We sincerely appreciate the reviewer's meticulous review and useful comments**. We would like to reiterate our key contributions, which have been positively acknowledged by other reviewers. For instance, Reviewer QNeF remarked that:\n> I believe that the paper makes a concrete contribution that fills a natural gap left in the literature. One can view most of the results derived in this paper as the natural counterparts of the results obtained by Perdomo et al. but in a more general non-cooperative game setting, which can be motivated in a number of applications. The results obtained in the paper take an important step toward characterizing the performative effect in multi-player non-cooperative settings. The theoretical results are technically non-trivial, and all claims appear to be sound.\n\nSimilar commendations can be found in the remarks of the remaining two reviewers. \n\n**Given our contributions to the field of performative prediction and noncooperative games, we respectfully request that you consider improving the rating scores. We thank you for your time and thoughtful consideration.**", "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": "wlo5lpWeF4", "reviewer": "Reviewer_dWNU", "summary": "This paper studies decentralized non-cooperative games with endogenous distribution shifts. In the model, each player aims to minimize its expected risk over a distribution that changes with their own and other players’ decisions, subject to a coupled constraint. The paper establishes conditions for the existence and uniqueness of Nash equilibria (NE) and and performative stable equilibria (PSE), and further bounds the distance between NE and PSE. The paper then proposes a primal-dual algorithm that computationally-efficiently solves the problem.", "questions": "Why is the condition for $\\mu$ different in E&U of PSE and NE?\n\nIn assumption 4.1, what does $\\nabla_\\theta J(\\xi,\\delta)$ mean? why is the right hand side independent on $\\delta$?\n\nSome minor issues:\nSome citations should be changed to \\citep instead of \\citet\n\nLine 224: $p_{ij} \\propto $ should be $p_{ij} \\leq$", "limitations": "The weakness section lists some limitations of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper makes solid contributions on formulating and solving decentralized non-cooperative games with endogenous distribution shifts. The model is richer than existing works.\n2. The paper first bounds the distance between PSE and NE. This is an important result in the setting of endogenous distribution shift because it characterize how the distribution shift coefficients influence the connection between different equilibrium notions.\n3. The paper proposes a primal-dual algorithm for finding the PSE that is both computationally efficient and decentralized. The regret rate of matches the decentralized noncooperative game.\n4. The paper carries numerical experiments that validates the theoretical results.", "weaknesses": "1. Several existing works have studied noncooperative games under performativity. This work extend the existing formulation by considering coupled constraints and decentralized setting. However, the constraint condition is not the fundamental difficulty in optimizing non-cooperative games as is known in variational inequalities literatures. Furthermore, the proposed algorithm relies on the assumption that players can communicate through a graph A with irreducible and doubly-stochastic weight matrix. The assumption basically ensures that the decentralized information can be disseminated effectively and makes decentralized optimization trivial. In conclusion, the problem studied in this work seems incremental.\n2. The proposed algorithm looks very similar to that in Lu et al., 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.**\n\n**Reply to Weakness 1:** \n1. First, we would like to clarify that only two existing works, namely, Narang et al. (2023) and Wang et al. (2023), have explored performative games to the best of our knowledge, with Narang et al. (2023) considering a centralized case and Wang et al. (2023) focusing on a relatively restrictive model, both of which are constraint-free. In contrast, our work delves into a more practical setting with a mathematically richer model. Considering constraints is crucial since many performative games have inherent restrictions, such as safety and cost constraints in transportation, relevance and diversity constraints in advertising, and risk tolerance and portfolio constraints in financial trading.  This leads to a completely different algorithm design and convergence analysis. Our work is based on the primal-dual technique, while theirs focuses on gradient descent.\n\n2. Second, although there are works on non-cooperative games with constraints, the presence of data performativity poses significant challenges: \n- The NE evaluation needs to quantify the performative effect that the studied performative game requires the condition $\\mu - \\sum_{i=1}^n L_i \\varepsilon_i \\max_{j\\in[n]} \\sqrt{p_{ij}} -  \\sqrt{\\sum_{i=1}^n L_i^2 \\varepsilon_i^2p_{ii}}>0$ to guarantee monotonicity while the non-performative counterpart (Lu et al., 2020) only requires $\\mu>0$, which is an assumption of the paper.  \n- The PSE is a unique concept in performative games and has not been considered in (Lu et al., 2020). \n- The convergence analysis of our algorithm necessitates meticulous control of the performative effect to maintain the convergence order. Our results demonstrate how performativity influences convergence, slowing it down by a coefficient $\\tilde\\mu := \\mu - \\sum_{i=1}^n L_i \\varepsilon_i \\max_{j\\in[n]} \\sqrt{p_{ij}}$, which offers a theoretical foundation for designing decentralized performative game systems.\n\n3. Furthermore, the vast majority of existing research on decentralized learning is based on the assumption of a doubly-stochastic weight matrix. Without this premise, consensus on decentralized systems cannot be guaranteed, rendering meaningful analysis challenging, if not impossible.\n\n4. Last but most important, this paper presents the first upper bound on this distance between PSE and NE, which is significant to understand the impact of data performativity in games. Such bounds have been a major focus in prior research on performative optimization but are challenging to quantify in games due to the competitive nature of players.  \n \n**Reply to Weakness 2:**  Some comparisons of our work with (Lu et al., 2020) have been provided in the Reply to Weakness 1. We would like to supplement that the date performativity does not cause significant difference in the algorithm development when calculating stable points. The primary challenge lies in the performance analysis that requires bounding the deviation induced by the performative effect. This is common in the performative prediction literature where predominate works focus on finding performative stable points. Our algorithm can be extended to calculate the NE by incorporating the gradient of $D_i(\\theta_i;\\theta_{-i})$ with respect to $\\theta_i$ in Step 7. However, estimating $D_i$ for all $i$ is computationally prohibitive as $D_i$ is related to the decisions of all players. Our algorithm results in a PSE that is not far from the NE, as demonstrated in Theorem 3.5.\n\n**Reply to Question 1:** The E&U of NE requires a more stringent condition since the computation of NE needs to take into account the gradient of $D_i(\\theta_i;\\theta_{-i})$ with respect to $\\theta_i$ for all $i$. More specifically, NE computes the gradient of performative risk, given by $\\nabla{\\rm PR}(\\theta) = G_{\\theta}(\\theta) + H_{\\theta}(\\theta)$, while PSE only considers the first component $G_{\\theta}(\\theta)$.\n\n**Reply to Question 2:**  We appreciate the reviewer's observation. Assumption 4.1 pertains to the stochastic gradient variance of $\\nabla_{\\delta_i} J_i(\\xi_i;\\delta_i, \\delta_{-i})$ and $G_{\\theta}^{(i)}(\\delta_i, \\delta_{-i}) := E_{\\xi_i\\sim D_i(\\theta)} \\nabla_{\\delta_i} J_i(\\xi_i;\\delta_i, \\delta_{-i})$. To enhance clarity, we have revised Assumption 4.1 in our manuscript. \n\n**Reply to Question 3:** Thank you for pointing this out. We have carefully revised the citation style throughout our paper.\n\n**Reply to Question 4:** Thank you for the advise.  Since $p_{ij}$ is the normalized influence parameter of $D_i$ with respective to $\\theta_j$, to make sure that $\\sum_{j=1}^n p_{ij}=1$,  we take $p_{ij}\\propto \\mathcal{O}(1/n)$.\n\n**Thank you again for your review and for recognizing our contributions.** We appreciate the strengths you have identified, as they are crucial for the evaluation of this paper and align with the observations of other reviewers. For instance, reviewer QNeF provided the following positive remark:\n> I believe that the paper makes a concrete contribution that fills a natural gap left in the literature. One can view most of the results derived in this paper as the natural counterparts of the results obtained by Perdomo et al. but in a more general non-cooperative game setting, which can be motivated in a number of applications. The results obtained in the paper take an important step toward characterizing the performative effect in multi-player non-cooperative settings. The theoretical results are technically non-trivial, and all claims appear to be sound.\n\n**Given our contributions to the field of performative prediction and noncooperative games, we respectfully request that you consider improving the rating scores to enhance the likelihood of acceptance for this work. We thank you for your time and thoughtful consideration.**", "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": "HHLzCRUxOk", "reviewer": "Reviewer_pBFf", "summary": "This paper examines endogenous distribution shifts in learning systems, where deployed models influence their environments, altering data distributions. The authors first prove a set of sufficient conditions for the existence and uniqueness of performative stable equilibrium (PSE) and Nash equilibrium (NE). The main contribution of the paper is to show that the distance between PSE and NE scales with the distributional shift parameter. They also provide a primal-dual algorithm for computing PSE, which achieves sublinear convergence rates for both performative regrets and constraint violations.", "questions": "1. Is Theorem 3.4 just a simple corollary of Theorem 3.3?\n\n2. The paper provides a sufficient condition for the existence and uniqueness of NE and PSE, but it is not necessary. Can you comment on the potential necessity for the existence and uniqueness of NE and PSE as well?", "limitations": "The authors did discuss the limitation", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Although I did not check the proof, the results of the paper appear to be correct. I appreciate that the authors provide intuition for the underlying mechanism. I am not an expert in this particular field, so I cannot comment much on the contribution. My impression is that the theoretical contribution is fairly significant and the convergence rate shown in this paper is strong.", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Questions are given below.**\n\n**Reply to Question 1:** Theorem 3.3 pertains to the existence and uniqueness of the performative stable equilibrium (PSE). Its characterization is based on the contraction condition of the dynamics of repeated risk minimization (RRM), as defined in Line 208. Theorem 3.4 pertains to the existence and uniqueness of the Nash equilibrium (NE), with the proof established on the strong monotonicity of the performative game (1). These two theorems follow distinct analytical processes, and Theorem 3.4 should not be considered a corollary of Theorem 3.3.\n\n**Reply to Question 2:** The study of equilibrium is fundamental in game theory because it ensures predictability and stability in strategic interactions among rational players. The existence of an equilibrium guarantees that there is at least one outcome where all players' strategies are mutually optimal responses, providing a foundation for predicting behavior in competitive scenarios. Uniqueness further enhances this predictability by ensuring a single, definitive outcome, eliminating ambiguity, and facilitating more straightforward strategic decision-making. This evaluation is essential for practical applications in economics, political science, and beyond, where reliable and stable outcomes are necessary for effective planning and analysis.\n\nWe thank the reviewer for pointing this out, and we have included a discussion on this point in our manuscript. Moreover, we would like to highlight one of our contributions on the equilibrium analysis. \n\n This paper makes a significant technical contribution by presenting the first upper bound on the distance between PSE and NE, which is significant to understand the impact of data performativity in games. Such bounds have been a major focus in prior research on performative optimization but are challenging to quantify in games due to the competitive nature of players. We leverage relations provided by strong duality and derive a result comparable to the findings in performative optimization settings. \n\n\n**Thank you again for your review and for recognizing our contributions.** We appreciate the strengths you have identified and we would like to reiterate our key contributions, which have been positively acknowledged by other reviewers. For instance, Reviewer QNeF remarked that:\n> I believe that the paper makes a concrete contribution that fills a natural gap left in the literature. One can view most of the results derived in this paper as the natural counterparts of the results obtained by Perdomo et al. but in a more general non-cooperative game setting, which can be motivated in a number of applications. The results obtained in the paper take an important step toward characterizing the performative effect in multi-player non-cooperative settings. The theoretical results are technically non-trivial, and all claims appear to be sound.\n\n**Given our contributions to the field of performative prediction and noncooperative games, we respectfully request that you consider improving the rating scores to enhance the likelihood of acceptance for this work. We thank you for your time and thoughtful consideration.**", "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:

Meta-review: This paper studies decentralized non-cooperative games where each player aims to minimize its expected risk over a distribution that changes with their own and other players’ decisions, subject to a coupled constraint. It establishes conditions for the existence and uniqueness of Nash equilibria (NE) and performative stable equilibria (PSE), and further bounds the distance between NE and PSE. The paper then proposes a primal-dual algorithm that solves the problem with provable convergence rates.


There are several highlighted weaknesses. For instance, one reviewer questioned the assumptions; for example, the work requires the stochastic gradient mapping to be strongly monotone, which is a stringent condition. Also, some reviewers questioned the difficulty of the analysis technique since they appear to follow relatively standard techniques in the literature extended to decentralized settings.
Despite these weaknesses, most reviewers find the paper well-written, with non-trivial and novel results. The results obtained in the paper take an important step toward characterizing the performative effect in multi-player non-cooperative settings. Given these strengths, and with most reviewers leaning toward acceptance, I recommend accepting this work.

In the final version, I highly encourage the authors to highlight the technical novelty of this work and to discuss the assumptions on $\varepsilon_i$ in equations (3) and (4), which seem a bit strong.
Decision: Accept (poster)