Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions

Authors: wenjing  yan
xuanyu  cao
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-05 05:09:30

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.

Main paper: 
 introduction: 
 Machine learning aims to generalize models trained on given datasets to make accurate predictions or decisions on new, unseen data (El Naqa and Murphy, 2015) . The effectiveness of those models depends on the alignment between the training datasets and deployment environments (Quinonero-Candela et 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 distribution 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 et al., 2021) . In contrast, endogenous shifts arise from the system'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 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 particularly 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-dependent learning" (Drusvyatskiy and Xiao, 2023) . This framework elegantly captures the dynamic interplay between decisions and data distributions through a decision-dependent mapping, denoted by D(θ) where θ represents the decision variable. By linking θ to the data distribution, this formulation bridges the gap between model deployment and parameter optimization. Following the seminal work of (Perdomo et al., 2020) , a growing body of research has emerged, focusing on stability and optimality analysis (Piliouras and Yu, 2023; Miller et al., 2021) , as well as algorithmic design for various settings, including reinforcement learning (Mandal et al., 2023) , online learning (Wood et al., 2021) , bandit problems (Jagadeesan et al., 2022) , 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., 2015) . 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 a dynamic pricing landscape (Fattouh and Mahadeva, 2014) . These dynamics extend to other domains, such as electricity market competition (Moshari et 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 decision-dependent 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 equilibrium? How can players adapt their strategies effectively when confronted with coupled decision-dependent distributions? How can we design algorithms to exploit these dynamics for optimal decision-making? 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 performativity, where selfish players seek to minimize individual costs while managing coupled inequality constraints. Under this setting, we examine two equilibrium concepts: performative 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-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 a 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-dual algorithm based on repeated risk minimization (RRM). The development and convergence analysis of this algorithm face two primary challenges. First, there is a 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, our 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 in games. A 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 on individual strategies and a 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., 2023) assumes full accessibility to all players' strategies across the entire network. Importantly, our work makes a significant contribution by providing the first upper bound on the distance between the performative stable equilibrium (PSE) and Nash equilibrium (NE)-a 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, 2024b) 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 θ i , from its feasible set Ω i ⊆ R d . Let the collective decisions of all players be denoted asθ := col (θ 1 , • • • , θ n ),and the collective decisions of all players except player i be represented asθ -i := col (θ 1 , • • • , θ i-1 , θ i+1 , • • • , θ n ), for any i ∈ [n], where[n] denotes the set of integers {1, 2, . . . , n}. Each player i has a private cost function J i (ξ i ; θ i , θ -i ), which depends on the random variable ξ i ∈ Ξ i , the player's private decision θ i , and the decisions of all other players θ -i . This paper considers a 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ξ i ∼ D i (θ i , θ -i ) for all i ∈ [n]. The objective of each player i is to selfishly minimize its performative riskE ξ i ∼Di(θi,θ-i) J i (ξ i ; θ i , θ -i ) (abbreviated as PR i (θ i , θ -i )), subject to a coupled constriant n i=1 g i (θ i ) 0, i.e., min θi∈Ωi E ξ i ∼Di(θi,θ-i) J i (ξ i ; θ i , θ -i ) subject to g i (θ i ) + j =i g j (θ j ) 0.(1) Both J i (•) and g i (•) are only locally accessible to player i for all i ∈ [n]. In the game (1), each player solves its private optimization problem to determine the best strategy, given the current strategies of all the other players. An equilibrium of the game (1) corresponds to a set of strategies where no player can improve its performance by deviating unilaterally from its strategy.ξ := col (ξ 1 , • • • , ξ n ) the concatenation of the variables ξ i and by J (ξ; θ) := col (J 1 (ξ 1 ; θ) , • • • , J n (ξ n ; θ)) the concatenation of the cost functions J i (•) for all i ∈ [n].A stochastic pseudogradient mapping of J (ξ; θ) is defined as∇J (ξ; θ) := col (∇ θ1 J 1 (ξ 1 ; θ) , • • • , ∇ θn J n (ξ n ; θ)).We have the following assumption on ∇J (ξ; θ). Assumption 2.1. There exists a constant µ > 0 such that the stochastic gradient mapping ∇J (ξ; θ) is µ-strongly monotone, i.e., ∇J (ξ; θ)-∇J ξ; θ , θ -θ ≥ µ θ -θ 2 2 , ∀ξ ∈ Ξ, θ, θ ∈ Ω, where Ξ := Ξ 1 × • • • × Ξ n and Ω := Ω 1 × • • • × Ω n .Assumption 2.1 is 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 2.3.3(b) ). However, in our paper, since the data distributions are decision-dependent, Assumption 2.1 does not imply the monotonicity of the gradient mapping of the joint performative risk, denoted by PR(•) := col (PR 1 (•), • • • , PR n (•)). Therefore, the existence and uniqueness (E&U) conditions for the Nash equilibrium of the game (1) need further investigation.We define a graph G(P) to represent the impact of players' decisions on the data distributions of different players. In G(P), the weight p ij > 0 if player j's decision affects player i's data distribution, and p ij = 0 otherwise. Particularly, p ii represents the weight of self-influence. These weights are normalized asn j=1 p ij = 1, for all i ∈ [n].Clearly, the larger the weight p ij , the stronger the effect of player j's decision on the data distribution of player i.Let W 1 (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{D i } i∈[n] . Assumption 2.2. For any i ∈ [n], there exists a constant ε i ≥ 0 such that, ∀θ, θ ∈ Ω, the distribution mapping D i is constrained by W 1 D i (θ) , D i θ ≤ ε i n j=1 p ij θ j -θ j 2 2 .For any i ∈ [n], the parameter ε i bounds the sensitivity of player i's distribution with respect to (w.r.t.) the decision variations of all players. This ε-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. L i ≥ 0 such that J i (ξ i ; θ) is L i -smooth, i.e, ∇J i (ξ i ; θ) -∇J i ξ i ; θ 2 ≤ L i ξ i -ξ i 2 + θ -θ 2 , ∀ξ i , ξ i ∈ Ξ i , θ, θ ∈ Ω.Assumption 2.5. For any i ∈ [n] and θ i ∈ Ω i , the constraint functiong i (θ i ) is convex w.r.t. θ i . Moreover, there exist a constant G g ≥ 0 such that g i (•) is G g -Lipschitz, i.e., g i (θ i ) -g i (θ i ) 2 ≤ G g θ i -θ i 2 , ∀θ i , θ i ∈ Ω i .Assumptions 2.3 and 2.5 are widely used in constrained optimization (Bertsekas, 2014; Yan and Cao, 2024a) , and Assumption 2.4 is standard in the PP literature. From Yan and Cao (2024a, Proposition 1), under Assumptions 2.3 and 2.4, the cost functionJ i (ξ i ; θ), ∀i ∈ [n] is Lipschitz continuous, i.e., there exist a constant G i ≥ 0 such that |J i (ξ i ; θ)-J i (ξ i ; θ )| ≤ G i ξ i -ξ i 2 + θ -θ 2 , ∀ξ i , ξ i ∈ Ξ i , θ, θ ∈ Ω.Moreover, Assumptions 2.3 and 2.5 imply the boundedness of g i (θ i ) 2 , i.e., there exists a constant B ≥ 0 such that gi (θ i ) 2 ≤ B, ∀θ i ∈ Ω i , i ∈ [n].3 Equilibrium of the PP-GameThis 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 θ ne := col (θ ne 1 , . . . , θ ne n ) achieves an NE of the game (1) if it holds for any i ∈ [n] thatθ ne i ∈ arg min θi∈Ωi E ξ i ∼Di(θi,θ ne -i ) J i ξ i ; θ i , θ ne -isubject to g i (θ i ) + j =i g j (θ ne j ) 0. θ pse i ∈ arg min θi∈Ωi E ξ i ∼Di(θ pse ) J i ξ i ; θ i , θ pse -i subject to g i (θ i ) + j =i g j (θ pse j ) 0.NE is a fundamental concept in game theory. At NE, each player's strategy optimally aligns with its own interest, given the strategies of other players. Hence, no player has an incentive to deviate from its strategy unilaterally. In the case of performative games, the computation of NE needs to take into account the data distributions D i (•) for all i ∈ [n], as they are parameterized by the optimization variable θ. However, this information is often unavailable in practice. Instead, at PSE, the data distribution of each player i ∈ [n] is fixed at D i (θ pse ) and the PSE point achieves an NE of the game (1) under the fixed data distribution of its own deployment. This formulation draws benign properties akin to problems with fixed data distributions, facilitating the adaptation of existing algorithms. Therefore, PSE is more frequently chosen as a performance metric in the literature of PP. 
existence and uniqueness of pse: 
 We first establish the condition for the E&U of the PSE of the game (1). Our approach relies on repeated risk minimization (RRM) for closed-loop retraining. First, we define a mapping T (θ) := {T i (θ)} i∈[n] that, for any i ∈ [n],θ i = T i (θ) := arg min ui∈Ωi E ξ i ∼Di(θi,θ-i) J i ξ i ; u i , θ -i subject to g i (u i ) + j =i g j θ j 0.The mapping T (θ) outputs the NE of the game (1) under the fixed data distributionsD i (θ i , θ -i ) for all i ∈ [n]. With Assumption 2.1, the E&U of this NE is guaranteed, thereby ensuring the validity of the mapping T (θ). Based on T (θ), the RRM updates θ t i at each iteration t byθ t+1 i = T i (θ t ), ∀i ∈ [n].(2)Clearly, θ t+1 is an NE of the game (1) under the deployment of θ t . Additionally, we have that any fixed point of (2) achieves an PSE for the game (1), i.e., θ pse = T (θ pse ). By investigating the convergence the iterative equation (2), we have the following sufficient condition for the E&U of the PSE of the game (1). Theorem 3.3. Suppose that Assumptions 2.1-2.5 hold. Then, for any θ, δ ∈ Ω, the mapping T (θ) satisfiesEQUATIONthe sequence generated by the RRM (2) converges to a unique PSE point θ pse at a linear rate thatθ t+1 -θ pse 2 ≤ 1 µ n i=1 L 2 i ε 2 i max j∈[n] p ij t θ 1 -θ pse 2 .The proof of Theorem 3.3 is provided in Appendix B. According to Theorem 3.3, under Assumptions 2.1-2.5, when condition (3) holds, we have that: (i) the game (1) admits a unique PSE, and (ii) the RRM method (2) converges linearly to the PSE.Since the influence weights {p ij } j∈[n] are normalized, withn j=1 p ij = 1 for all i ∈ [n], we generally have that p ij = O( 1 n ).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 ∈ [n], its distribution D i (•) depends only on its own decision θ i , i.e., p ij = 0 for all j = i, then we haveT (θ) -T (δ) 2 ≤ 1 µ max i∈[n] L i ε i δ -θ 2 .The contraction of the above iterative equation only requires that1 µ max i∈[n] L i ε i < 1. Furthermore, if all players exhibit equivalent model parameters that L 1 = • • • = L n = L and ε 1 = • • • = ε n = ε and p ij = 1n for all i, j ∈ [n], condition (3) reduces to Lε µ < 1, recovering the contraction requirement of (Perdomo et al., 2020) for a single-agent PP case.First, we define a gradient mappingG (i) θ (δ i , δ -i ) := E ξ i ∼Di(θ) ∇ δi J i (ξ i ; δ i , δ -i ) for any i ∈ [n], and G θ (δ) := col G (1) θ (δ), • • • , G (n) θ (δ) . Moreover, for any i ∈ [n], define H (i) θi,θ-i (δ) := ∇ ui E ξ i ∼Di(ui,θ-i) [J i (ξ i ; δ)] ui=θi and H θ (δ) := col H (1) θ1,θ-1 (δ), • • • , H (n)θn,θ-n (δ) . Then, for any i ∈ [n], the gradient of the performative risk PR i (θ i , θ -i ) w.r.t. θ i is given by∇ θi PR i (θ i , θ -i ) = G (i) θi,θ-i (θ i , θ -i ) + H (i) θi,θ-i (θ i , θ -i ). Define ∇PR(θ) := col (∇ θ1 PR i (θ), • • • , ∇ θn PR n (θ)), we further have ∇PR(θ) = G θ (θ) + H θ (θ).From Facchinei and Pang (2003, Theorem 2.3.3(b) ), to prove the E&U of the NE of the (1), we require the strongly monotonivity of the gradient mapping ∇PR(θ). 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.1-2.5 hold. If it is satisfied thatEQUATIONthen, the PP-game (1) is strongly monotone and admits a unique NE.The proof of Theorem 3.4 is presented in Appendix C. Since p ij characterizes the influence of player j's decision on the data distribution of player i, we typically have p ij ≤ p ii for j = i and thus max j∈[n] p ij = p ii for all i ∈ [n]. Then, the condition ( 4) reduces to µ -n i=1 L i ε i p ii - n i=1 L 2 i ε 2 i p ii > 0. Similarly, when L 1 = • • • = L n = L, ε 1 = • • • = ε n = ε, and p ij = 1 n for all i, j ∈ [n],we require that µ -2Lε > 0, i.e., ε ≤ µ 2L , which recovers the condition to guarantee the convexity of the performative risk PR(•), and thereby the E&U of the performative optimal point of (Miller et al., 2021) for single-agent PP.Theorem 3.5. Define µ := µ - n i=1 L i ε i max j∈[n] √ p ij and α := n i=1 G i 1 + ε i max j∈[n] √ p ij .Suppose that Assumptions 2.1-2.5 hold and µ > 0. Then, for every PSE point and NE point, we have the following relations:θ pse -θ ne 2 ≤ 1 µ n i=1 G 2 i ε 2 i p ii and |PR(θ pse ) -PR(θ ne )| ≤ α µ n i=1 G 2 i ε 2 i p ii .The proof of Theorem 3.5 is presented in Appendix D. According to Theorem 3.5, the distance between the PSE and NE of the game (1) depends on the cost functions' parameters µ, {G i }, {L i }, as well as the sensitivity of the data distributions {ε i }. Larger sensitivity parameters widen the gap between the PSE and NE, while a bigger monotonicity parameter µ reduces it. Notably, when the sensitivity parameter ε i = 0 for all i ∈ [n], the game (1) reduces to a conventional stochastic game with fixed data distributions, and as a result, the PSE and NE converge to the same point.To the best of our knowledge, this is the first result on 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., 2020) for single-agent PP problems wherein this optimality gap is bounded by 2Lε µ . In our case, whenG 1 = • • • = G n = G, ε 1 = • • • = ε n = ε and p ij = 1 n for all i, j ∈ [n], we have θ pse -θ ne 2 ≤ Gε µ-Lε .Algorithm 1 Decentralized Stochastic Primal-Dual Algorithm: The Procedures at Player i, ∀i ∈ [n]:1: Initialize θ 1 i ∈ Ξ i arbitrarily. Set λ 1 i = 0 and θ 1 ih = 0 for all h = i. 2: for t = 1 to T do 3: Exchange θ t i , θ t i, and λ t i with all neighbors;4:Update the estimate θ t ih for all h = i by: θt+1 ih = k =h a ik θ t kh + a ih θ t h ; 5:Deploy the model θ t i and sampleξ t i ∼ D i (θ t i , θ t -i ); 6:Update the primal variable by:θ t+1 i = P Ωi θ t i -γ t ∇ θi J i ξ t i ; θ t i , θ t i + γ t ∇g i (θ t i ) λ t i ; 7:Update the dual variable by:λ t+1 i = 1 -γ 2 t j∈Ni a ij λ t j + γ t g i θ t i + . 8: end for 4 Computation of the PSEAlthough RRM theoretically has the capability to 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 is computationally intensive. In this section, we present a decentralized stochastic primal-dual algorithm for efficiently computing the PSE of the game (1). Theoretical analysis is also provided on the convergence of the proposed algorithm. 
algorithm development: 
 For each player i ∈ [n], define a regularized Lagrangian asL (i) δ (θ i , θ -i , λ) = E ξ i ∼Di(δ) J i (ξ i ; θ i , θ -i ) + λ, g i (θ i ) + j =i g j (θ j ) ,where λ ∈ R m + is the dual variable. Denote by ∇g i (•) the Jacobian matrix of g i (•). From the primal-dual theory (Boyd and Vandenberghe, 2004; Facchinei and Pang, 2010) , for any γ > 0, there exists a bounded Lagrangian multiplier λ pse such that the following condition holds:θ pse i =P Ωi θ pse i -γ G (i) θ pse (θ pse , λ pse ) + γ∇g i (θ pse i ) λ pse , ∀i ∈ [n], λ pse = λ pse + γ g i (θ pse i ) + j =i g j θ pse j + ,where γ is a control parameter. Thus, given θ pse -i and underξ i ∼ D i (θ pse ), (θ pse i , λ pse ) is a saddle point of the Lagrangian L (i) θ pse (θ i , θ pse -i , λ) for any i ∈ [n].The joint saddle point (θ pse , λ pse ) achieve the PSE of the game (1) under strong duality (Boyd and Vandenberghe, 2004 ).In the decentralized noncooperative game (1), each player can only communicate with its neighbors. We use G(A) to denote the communication graph of the network, where A = (a ij ) n×n represents a weight matrix. In G(A), a ij = a ji > 0 if there is a communication link between player i and play j, and a ij = a ji = 0 otherwise. Let N i be the set containing player i and all its neighbors such that j ∈ N i if a ij > 0. We assume that the communication graph G(A) is connected and the weight matrix A is doubly stochastic.To find the saddle point (θ pse , λ pse ), we develop a decentralized stochastic primal-dual algorithm, as presented in Algorithm 1. The basic idea of Algorithm 1 is to perform gradient update on the primal variables θ i for all i ∈ [n] and the dual variable λ. In the decentralized noncooperative game, each player i ∈ [n] only observes information from its neighbors. However, its private cost funtion J i (ξ i ; θ i , θ -i ) 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 θ ih , for all h = i. Define a vector θ i that concatenates all the estimates θ ih . In each iteration t, neighbors exchange strategy θ t i , estimate θ t i , and dual varible λ t i with each other. Then, each player i updates the estimates θ ih , for all h = i by weighted average in Step 4. The primal variable θ t i is updated by gradient descent by Step 6, and the dual variable λ t i is updated by gradient ascent by Step 7. The coefficient γ t is the stepsize at the tth iteration for all t ∈ [T ].Before analyzing the performance of Algorithm 1, we define the performance metrics adopted in this paper. The first metric is performative regret. For any player i ∈ [n], its performative regret over T iterations is defined asR i (T ) := T t=1 E ξ i ∼Di(θ pse ) J i ξ i ; θ t i , θ pse -i -PR i (θ pse ) . The regret R i (T ) measures the suboptimality of the sequence of decisions {θ 1 i , • • • , θ T i }taken by play i relative to θ pse i . Besides, since the decisions of all players are subject to constraints, another performance metric of constraint violation, denoted by R g (T ), is required, defined asR g (T ) = T t=1 n i=1 g i θ t i + 2 .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., limT →∞ R i (T )/T ≤ o(1) for any i ∈ [n] and lim T →∞ R g (T )/T ≤ o(1).For analysis, we make the following assumption on the variance of the stochastic gradient∇ θi J i (ξ i ; δ), ∀i ∈ [n]. Assumption 4.1. The stochastic gradient ∇ δi J i (ξ i ; δ i , δ -i ) is unbiased that E ξ i ∼Di(θ) ∇ δi J i (ξ i ; δ i , δ -i ) = G (i) θ (δ i , δ -i ) and there exist constants σ 0 , σ 1 ≥ 0 such that n i=1 E ξ i ∼Di(θ) ∇ δi J i (ξ i ; δ i , δ -i ) -G (i) θ (δ i , δ -i ) 2 2 ≤ σ 2 0 + σ 2 1 θ -θ pse 2 2 , ∀θ, δ ∈ Ω. Theorem 4.2. Define µ := µ - n i=1 L i ε i max j∈[n] √ p ij and ν := 3 σ 2 1 + 3 n i=1 L 2 i 1 + ε 2 i max j∈[n] p ij .Suppose that Assumptions 2.1-2.5 and 4.1 hold and µ > 0. By Algorithm 1, if the stepsize satisfies sup t∈[T ] γ t ≤ µ ν , then, the performative regret of the game (1) is bounded byR i (T ) ≤ O T µ 1 γ T + T t=1 γ t , ∀i ∈ [n].Further, the constraint violation is bounded byR g (T ) ≤ O 1 γ T 1 γ T + T t=1 γ t 1 + T t=1 γ 2 t .For a sequence of diminishing stepsize γ t = τ η 1 (τ 2 t + τ 1 ) -η , where τ 1 , τ 2 > 0 and 0 < η < 1, we have that: 1)T t=1 γ t ≤ O T 1-η ; 2) T t=1 γ 2 (t) ≤ O T 1-2η . Plugging the above results into Theorem 4.2 yields R i (T ) ≤ O T 1+η 2 + T 1-η 2 , i ∈ [n] and R g (T ) ≤ O T 3 2 η + T 1+η 2 + T 1-η 2 .Based on the above two inequalities, the best choice of η is 4 ). This convergence speed matches that of the decentralized noncooperative game without performativity (Lu et al., 2020) .EQUATIONThe 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 1 µ in the regret bounds. Specifically, as the sensitivity parameters ε i increase, the coefficient µ decreases, leading to a slower convergence rate of R i (T ) for all i ∈ [n]. This occurs because a larger ε i indicates a stronger performative influence, which more significantly impacts the algorithm's convergence. Nevertheless, the performative effect does not degrade the convergence order of Algorithm 1 compared 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 a networked Cournot game (Abolhassani et al., 2014) , which is a foundational model in economic theory (Allaz and Vila, 1993) for analyzing oligopolistic competitions. We 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 it 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.1. We also provide an additional experiment on a ride-share market in Appendix F.2. Fig. 1 illustrates the convergence of the time-average regrets of five firms, denoted by R i (t)/t, ∀i ∈ [5] , and the convergence of the time-average constraint violations of three markets, denoted by1 t t t =1 n i=1 g ij (θ t i ), ∀j ∈ [3].The results demonstrate that both R i (t)/t and1 t t t =1 n i=1 g ij (θ t i) approach zero as the iterations increase. This verifies the sublinear convergence of the regrets and constraint violations in Theorem 4.2. Fig. 2 (a) compares the normalized distance between θ t , generated by Algorithm 1, and the NE point θ ne , denoted as θ tθ ne 2 / θ t 2 . The NE point is computed based on perfect knowledge of {D i } i∈ [n] . We consider three different performative strengths: ε = 0.2, 0.4, and 0.6. It is observed that θ tθ ne 2 / θ t 2 stabilizes at values approximately equal to or smaller than 10 -1 with iterations, varifying the effectiveness of Algorithm 1. Additionally, a larger performative strength leads to a wider normalized distance between the convergent point of θ t and θ ne . In Fig. 2 (b) , we compare the total revenues, denoted by -5 i=1 PR i (θ t ) under the same three ε settings. We consider two scenarios: 1). "pse", where θ t is generated by Algorithm 1; 2). "ne", where θ t is generated by performing the same procedures as Algorithm 1 but with perfect information on the distributions {D i (θ)} i∈ [n] . The result demonstrates the close performance of the "pse" approach and the "ne" approach. More numerical results can be found in Appendix F.We have studied the performative phenomenon in a decentralized noncooperative game where selfish players seek to maximize their individual profits while adhering to 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 a 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.In recent years, the exploration of distribution shifts in machine learning systems has been extended beyond traditional exogenous shifts (Quinonero-Candela et al., 2008) , such as covariate (Chan et al., 2020) , label (Wu et al., 2021) , and concept (Lu et al., 2018) drifts, to include endogenous shifts resulting from strategic behaviors within the learning platforms themselves. Perdomo et al. (2020) introduced the framework of performative prediction, which captures the platform'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., 2023) studied the endogenous distribution change in open environments, where data are obtained from a corrupted decision-dependent distribution. They proposed an effective algorithm with theoretical guarantees by decoupling 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 a stochastic algorithm to find the PS point. In (Mandal et al., 2023) , the authors examined the performative effect in a 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 gradientbased 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., 2021; Izzo et al., 2021; Jagadeesan et al., 2022) . The optimality gap of performative stable points was first presented in (Perdomo et al., 2020) , 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., 2021) proposed a two-stage algorithm to find the performative optima for distribution maps in the location family. Izzo et al. (2021) 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 to our 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 constraints, whereas both (Narang et al., 2023) and (Wang et al., 2023) 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 a fundamentally different algorithm design and convergence analysis from these two papers. Our work utilizes the primal-dual 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 a 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., 2023) 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 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 in a 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, (Yan 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) .From the definition of the mapping T (θ), we have thatθ i = T i (θ) = arg min ui∈Ωi E ξ i ∼Di(θ) J i ξ i ; u i , θ -i s.t. g i (u i ) + j =i g j θ j ≤ 0, ∀i ∈ [n], δ i = T i (δ) = arg min ui∈Ωi E ξ i ∼Di(δ) J i ξ i ; u i , δ -i s.t. g i (u i ) + j =i g j δ j ≤ 0, ∀i ∈ [n].Define E ξ i ∼Di(θ) ∇ θi J i ξ i ; θ i , θ -i := G (i) θ (θ i , θ -i ).From the optimality condition of constrained optimization, we haveG (i) θ θ , θ i -δ i ≤ 0, ∀i ∈ [n]. Define a vector G θ (θ ) := col G (1) θ (θ ), • • • , G (n) θ (θ ) that concatenates all the G (i) θ (θ ), i ∈ [n].Then, we haveG θ θ , θ -δ ≤ 0. (A1)Similarly, we haveG δ δ , θ -δ ≥ 0. (A2)Further, from the monotoniticy of the gradient mapping ∇J (ξ; θ) in Assumption 2.1, we haveEQUATION)whereD(θ) := D 1 (θ) × • • • × D n (θ). Plugging (A1) and (A2) into (A3) gives µ θ -δ 2 2 ≤ -G θ δ , θ -δ ≤ G δ δ -G θ δ , θ -δ ≤ G δ δ -G θ δ 2 θ -δ 2 . (A4) From Assumption 2.2, W 1 D i (θ) , D i θ ≤ ε i n j=1 p ij θ j -θ j 2 2 .Along with Assumption 2.4, we have thatG δ δ -G θ δ 2 2 ≤ n i=1 n j=1 L 2 i ε 2 i p ij δ j -θ j 2 2 ≤ n i=1 L 2 i ε 2 i max j∈[n] p ij δ -θ 2 2 .Plugging the above result into (A4) yieldsθ -δ 2 ≤ 1 µ n i=1 L 2 i ε 2 i max j∈[n] p ij δ -θ 2 .From the RRM procedure, we know that θ t+1 = T (θ t ) and the PSE satisfies θ pse = T (θ pse ). Then, we haveθ t+1 -θ pse 2 ≤ 1 µ n i=1 L 2 i ε 2 i max j∈[n] p ij θ t -θ pse 2 ≤   1 µ n i=1 L 2 i ε 2 i max j∈[n] p ij   t θ 1 -θ pse 2 .Further, if for any player i, its distribution D i depends only on its own decision θ i , i.e., p ij = 0 and p ii = 1 for all i, j ∈ [n] and j = i, then, we haveG δ δ -G θ δ 2 ≤ n i=1 L 2 i ε 2 i δ i -θ i 2 2 ≤ max i∈[n] L i ε i δ -θ 2 . (A5) Plugging (A5) into (A4) yields θ -δ 2 ≤ 1 µ max i∈[n] L i ε i δ -θ 2 .Correspondingly, we haveθ t+1 -θ pse 2 ≤ 1 µ max i∈[n] L i ε i t θ 1 -θ pse 2 .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 ∇PR(θ) of the performative game (1) is strongly monotone, i.e., there exists a α > 0 such that ∇PR(θ) -∇PR(θ), θδ ≥ α θδ 2 2 , where α denotes the strongly-monotone parameter. Since ∇PR(θ) = G θ (θ) + H θ (θ), we have∇PR(θ) -∇PR(δ), θ -δ = G θ (θ) -G δ (δ), θ -δ + H θ (θ) -H δ (δ), θ -δ .From Assumption 2.2, we haveG θ (θ) -G δ (θ), θ -δ ≥ - n i=1 L i ε i max j∈[n] √ p ij θ -δ 2 2 .Moreover, from the monotonicity of the gradient mapping ∇J (ξ; θ) in Assumption 2.1, we haveG δ (θ) -G δ (δ), θ -δ = E ξ∼D(δ) ∇J(ξ; θ) -∇J(ξ; δ), θ -δ ≥ µ θ -δ 2 2 .Combining the above two inequalities yieldsG θ (θ) -G δ (δ), θ -δ = G θ (θ) -G δ (θ), θ -δ + G δ (θ) -G δ (δ), θ -δ ≥ µ - n i=1 L i ε i max j∈[n] √ p ij θ -δ 2 2 . (A6)Further, let γ(s) = θ + s θθ for s ∈ (0, 1). Then, we haveJ i (ξ i ; θ) -J i ξ i ; θ = 1 0 ∇J i ξ i ; θ + s θ -θ , θ -θ ds = 1 0 ∇J i (ξ i ; γ(s)) , θ -θ ds. (A7)From the definition ofH (i) θ (δ) that H (i) θ (δ) := ∇ ui E ξ i ∼Di(ui,θ-i) [J i (ξ i ; δ)] ui=θi , we have that H (i) θ (θ) -H (i) θ (θ ) = ∇ ui E ξ i ∼Di(ui,θ-i) 1 0 ∇J i (ξ i ; γ(s)) , θ -θ ds ui=θi = 1 0 ∇ ui E ξ i ∼Di(ui,θ-i) ∇J i (ξ i ; γ(s)) , θ -θ ui=θi ds. (A8)From Assumption 2.4, we haveE ξ i ∼Di ∇J i (ξ i ; θ) -E ξ i ∼D i ∇J i ξ i ; θ 2 ≤ L i W 1 (D i , D i ).Along with Assumption 2.2, we know that the function E ξ i ∼Di(θi,θ-i) ∇J i ξ i ; θ is L i ε i p ii -Lipschitz continuous w.r.t θ i , and thus its gradient satisfies∇ ui E ξ i ∼Di(ui,θ-i) [∇J i (ξ i ; γ(s))] ui=θi 2 ≤ L i ε i p ii . (A9)Combing ( A8) and (A9) givesH (i) θ (θ) -H (i) θ (θ ) 2 ≤ 1 0 ∇ ui E ξ i ∼Di(ui,θ-i) [∇J i (ξ i ; γ(s))] ui=θi 2 θ -θ 2 ds ≤ L i ε i p ii θ -θ 2 ,where the first inequality holds due to the Cauchy-Schwartz inequality. This further implies thatH θ (θ) -H θ (θ ) 2 = n i=1 H (i) θ (θ) -H (i) θ (θ ) 2 2 ≤ n i=1 L 2 i ε 2 i p ii θ -θ 2 .Following prior work (Narang et al., 2023) and (Wang et al., 2023) on performative games, we assume that the mapping H δ (θ) is monotone w.r.t δ, i.e., H θ (θ) -H δ (θ), θδ ≥ 0. Then, we have that∇PR(θ) -∇PR(δ), θ -δ = G θ (θ) -G δ (δ), θ -δ + H θ (θ) -H δ (δ), θ -δ = G θ (θ) -G δ (θ), θ -δ + H θ (θ) -H δ (θ), θ -δ + G δ (θ) -G δ (δ), θ -δ + H δ (θ) -H δ (δ), θ -δ ≥   µ - n i=1 L i ε i max j∈[n] √ p ij - n i=1 L 2 i ε 2 i p ii   θ -δ 2 2 .Based on the classical result that a strongly monotone game over a non-empty, closed, and convex set admits a unique NE Facchinei and Pang (2003, Theorem 2.3.3(b) ), we have the E&U condition for the NE of the game (1) as given in theorem 3.4.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 4.1 thatL (i) δ (θ i , θ -i , λ) := E ξ i ∼Di(δ) J i (ξ i ; θ i , θ -i ) + λ, g i (θ i ) + j =i g j (θ j ) .Moreover, define a gradient mapping φ i (ξ i ; θ, λ) := ∇ θi J i (ξ i ; θ)+∇g i (θ i ) λ and a concatenation vectorφ := [φ 1 , • • • , φ n ] . For any i ∈ [n], since (θ pse i , λ pse ) is a saddle point of the Lagrangian L (i) θ pse (θ i , θ pse -i , λ) under ξ i ∼ D i (θ pse ), we have that L (i) θ pse θ pse i , θ pse -i , λ ≤ L (i) θ pse θ pse i , θ pse -i , λ pse ≤ L (i) θ pse θ i , θ pse -i , λ pse ∀θ i ∈ Ω i , λ ∈ R m + .Similarly, for any i ∈ [n], (θ ne i , λ ne ) the saddle point of the regularized Lagrangian L(i) θi,θ ne -i (θ i , θ ne -i , λ) with decision-dependent distribution ξ i ∼ D i (θ i , θ ne -i ).Setting λ = λ ne in the first part of the proceeding inequality, we obtain0 ≤ L (i) θ pse θ pse i , θ pse -i , λ pse -L (i) θ pse θ pse i , θ pse -i , λ ne = (λ pse -λ ne ) g (θ pse ) , ∀i ∈ [n],where(λ pse -λ ne ) g (θ pse ) = m j=1 λ pse j -λ ne j ( n i=1 g ji (θ pse i )). By the convexity of g ji (•) for all j ∈ [m], i ∈ [n], we have that n i=1 g ji (θ pse i ) ≤ n i=1 (g ji (θ ne i ) + ∇g ji (θ pse i ) , θ pse i -θ ne i ) ≤ n i=1 ∇g ji (θ pse i ) , θ pse i -θ ne i , ∀j ∈ [m],where the last inequality follows from that g j (θ ne ) = n i=1 g ji (θ ne i ) ≤ 0. Multiplying the preceding inequality with λ pse j and adding over all j ∈ [m], we obtainm j=1 n i=1 λ pse j g ji (θ pse i ) = (λ pse ) g (θ pse ) ≤ n i=1 m j=1 λ pse j ∇g ji (θ pse i ) , θ pse i -θ ne i = n i=1 ∇g i (θ pse i ) λ pse , θ pse i -θ ne i . (A10)By the definition of the mapping φ i (•), for any ξ i ∈ Ξ i , we have that,EQUATIONPlugging (A11) into (A10) gives(λ pse ) g (θ pse ) ≤ n i=1 φ i (ξ i ; θ pse , λ pse ) -∇ θi J i (ξ i ; θ pse ) , θ pse i -θ ne i , ∀i ∈ [n]. (A12)Likewise, we have the following inequality based on the convexity of the functions {g ji (•)}:g ji (θ pse i ) ≥ g ji (θ ne i ) + ∇g ji (θ ne i ) , θ pse i -θ ne i , ∀j ∈ [m], i ∈ [n].Multiplying the preceding inequality with -λ ne j and summing over j ∈ [m], we obtain- m j=1 λ ne i n i=1 g ji (θ pse i ) ≤ - m j=1 λ ne j n i=1 g ji (θ ne i ) - n i=1 m j=1 λ ne j ∇g ji (θ ne i ) , θ pse i -θ ne i = n i=1 ∇g i (θ ne i ) λ ne , θ ne i -θ pse i ,where the equality follows from that m j=1 λ ne j n i=1 g ji (θ ne i ) = (λ ne ) g (θ ne ) = 0, which holds by the complementary slackness condition of the Lagrangian L(i) θi,θ ne -i (θ i , θ ne -i , λ) for all i ∈ [n]. Similar to (A12), we have -(λ ne ) g (θ pse ) ≤ n i=1 φ i (ξ i ; θ ne , λ ne ) -∇ θi J i (ξ i ; θ ne ) , θ ne i -θ pse i . (A13)Combining (A12) and (A13) yields(λ pse -λ ne ) g (θ pse ) ≤ n i=1 φ i (ξ i ; θ pse , λ pse ) -φ i (ξ i ; θ ne , λ ne ), θ pse i -θ ne i - n i=1 ∇ θi J i (ξ i ; θ pse ) -∇ θi J i (ξ i ; θ ne ) , θ pse i -θ ne i .Taking expectation on both sides of the above inequality over the distribution D i (θ pse ) for all i ∈ [n] gives(λ pse -λ ne ) g (θ pse ) ≤ n i=1 E ξ i ∼Di(θ pse ) φ i (ξ i ; θ pse , λ pse ) -φ i (ξ i ; θ ne , λ ne ), θ pse i -θ ne i - n i=1 G (i) θ pse (θ pse ) -G (i) θ pse (θ ne ) , θ pse i -θ ne i . (A14) Since (θ pse i , λ pse ) is a saddle point of the Lagrangian L (i)θ pse (θ pse , λ pse ) given ξ i ∼ D i (θ pse ), we have thatE ξ i ∼Di(θ pse ) φ i (ξ i ; θ pse , λ pse ), θ pse i -θ ne i ≤ 0, ∀i ∈ [n]. (A15)Furthermore, for any i ∈ [n], we haveE ξ i ∼Di(θ pse ) φ i (ξ i ; θ ne , λ ne ) = G (i) θ pse (θ ne ) + ∇g i (θ ne i ) λ ne + ∇ θi PR i (θ ne i , θ ne -i ) -∇ θi PR i (θ ne i , θ ne -i ). (A16) Since (θ ne i , λ ne ) is a saddle point of the Lagrangian L (i) θi,θ ne -i (θ i , θ ne -i , λ ne ) with decision-dependent distribution D i (θ i , θ ne -i ), we have that -∇ θi PR i (θ ne i , θ ne -i ) + ∇g i (θ ne i ) λ ne , θ pse i -θ ne i ≤ 0, ∀i ∈ [n]. (A17)Plugging ( A15), (A16), and (A17) into (A14) yields0 ≤ (λ pse -λ ne ) g (θ pse ) ≤ n i=1 ∇ i PR i (θ ne i , θ ne -i ) -G (i) θ pse (θ ne ) , θ pse i -θ ne i - n i=1 G (i) θ pse (θ pse ) -G (i) θ pse (θ ne ) , θ pse i -θ ne i = n i=1 H (i) θ ne (θ ne ) + G (i) θ ne (θ ne ) -G (i) θ pse (θ pse ) , θ pse i -θ ne i .Then, we haveG θ pse (θ pse ) -G θ ne (θ ne ) , θ pse -θ ne ≤ H θ ne (θ ne ), θ pse -θ ne .From the result in (A6) and the Cauchy-Schwarz inequality, we haveµ - n i=1 L i ε i max j∈[n] √ p ij θ pse -θ ne 2 2 ≤ H θ ne (θ ne ) 2 θ pse -θ ne 2 . Since the cost function J i (•) is G i Lipschitz for any i ∈ [n],along with Assumption 2.2, we haveH θ ne (θ ne ) 2 = n i=1 H (i) θ ne i ,θ ne -i (θ ne i , θ ne -i ) 2 2 ≤ n i=1 G 2 i ε 2 i p ii .Combining the above results yieldsθ pse -θ ne 2 ≤ n i=1 G 2 i ε 2 i p ii µ - n i=1 L i ε i max j∈[n] √ p ij .Further, from Assumption 2.2, we have|PR i (θ pse ) -PR i (θ ne )| ≤ G i θ pse -θ ne 2 + G i ε i n j=1 p ij θ pse j -θ ne j 2 2 ≤ G i 1 + ε i max j∈[n] √ p ij θ pse -θ ne 2 .Then, we have|PR(θ pse ) -PR(θ ne )| = n i=1 |PR i (θ pse ) -PR i (θ ne )| ≤ n i=1 G i 1 + ε i max j∈[n] √ p ij n i=1 G 2 i ε 2 i p ii µ - n i=1 L i ε i max j∈[n] √ p ij .The proof of this section utilizes the following supporting lemmas. Lemma E.1. Based on the update rule of the dual variable λ in Algorithm 1, for any γ t ≥ 0,λ t i ∈ R m + , i ∈ [n], and t ∈ [T ], we have that n i=1 γ t λ t i 2 2 ≤ nB 2 . Lemma E.2. Define λ t := 1 n n i=1 λ ti the average of the dual variable over all players at the tth iteration. Then, for any γ t ≥ 0 and t ∈ [T ], we have the following relationship:- T t=1 n i=1 γ t (λ t i ) g i (θ t i ) ≤ - T t=1 n i=1 γ t λ g i θ t i + n 2 1 + T t=1 γ 2 t λ 2 2 + 9 2 T t=1 n i=1 λ t i -λ t 2 2 + 2(1 + √ n)B T t=1 γ t n i=1 λ t i -λ t 2 + 4nB 2 T t=1 γ 2 t .Moreover, we require the following Lemma on the weight matrix A. Lemma E. E e t h 2 ≤ nC 1 -β + n √ n -1(G + √ nBG g ) 1 -β T t=1 γ t = O T t=1 γ t . Moreover, the sum of e t ih 2 2 over h ∈ [n] and t ∈ [T ] satisfies T t=1 n h=1 E e t h 2 2 ≤ 2nC 2 1 -β + 2n(n -1)(G + √ nBG g ) 2 (1 -β) 2 T t=1 γ t = O T t=1 γ t .Lemma E.5. With the definition λ t := 1 n n i=1 λ t i , we have the following relationship on the consensus error of the dual variable λ t i , given by λ t i -λ t , for all i ∈ [n] and t ∈ [T ]:T t=1 n i=1 λ t i -λ t 2 ≤ 2(n + √ n)B 1 -σ 2 (A) T t=1 γ t = O T t=1 γ t , T t=1 n i=1 λ t i -λ t 2 2 ≤ 4(n + √ n) 2 B 2 (1 -σ 2 (A)) 2 T t=1 γ t = O T t=1 γ t .Next, we start the proof of Theorem 4.2. For ease of proposition, we define the following gradient mappings: for any t ∈[T ], φ t i (ξ i ; θ i , θ -i , λ) := ∇ i J i (ξ i ; θ i , θ -i , θ) + γ t ∇g i (θ i ) λ, φ t (•) := [φ t 1 (•), • • • , φ t n (•)] , Φ i,t δ (θ, λ) := G (i) δ (θ) + γ t ∇g i (θ i ) λ, and Φ t δ (θ, λ) := Φ 1,t δ (θ, λ), • • • , Φ n,t δ (θ, λ). Then, we haveE θ t+1 -θ pse 2 2 = n i=1 E P Ωi θ t i -γ t φ t i ξ t i ; θ t i , θ t i , λ t i -P Ωi θ pse i -γ t Φ i,t θ pse (θ pse , λ pse ) 2 2 ≤ E θ t -θ pse 2 2 + γ 2 t n i=1 E φ t i ξ t i ; θ t i , θ t i , λ t i -Φ i,t θ pse (θ pse , λ pse ) 2 2 -2γ t n i=1 E θ t i -θ pse i , φ t i ξ t i ; θ t i , θ t i , λ t i -Φ i,t θ pse (θ pse , λ pse ) . (A18)The second term on the right side of (A18) is handled as follows.EQUATION)We have the following results on these three terms in the last inequality of (A19).(a) = 3γ 2 t n i=1 E ∇ θi J i ξ t i ; θ t i , θ t i -G (i) θ t θ t i , θ t i 2 2 ≤ 3γ 2 t σ 2 0 + σ 2 1 E θ t -θ pse 2 2 . (b) = 3γ 2 t n i=1 E G (i) θ t θ t i , θ t i -G (i) θ t θ t + G (i) θ t θ t -G (i) θ t (θ pse ) + G (i) θ t (θ pse ) -G (i) θ pse (θ pse ) 2 2 ≤ 9γ 2 t n i=1 E G (i) θ t θ t i , θ t i -G (i) θ t θ t 2 2 + G (i) θ t θ t -G (i) θ t (θ pse ) 2 2 + G (i) θ t (θ pse ) -G (i) θ pse (θ pse ) 2 2 ≤ 9γ 2 t n i=1 E L 2 i θ t i -θ t -i 2 2 + L 2 i θ t -θ pse 2 2 + L 2 i ε 2 i max j∈[n] p ij θ t -θ pse 2 2 ,where the last inequality is based on Assumptions 2.2 and 2.4. Further, since the constriant functiong i (•) is G g Lipschitz for all i ∈ [n], we have that (c) ≤ 6γ 4 t n i=1 E ∇g i θ t i λ t i 2 2 + 6γ 4 t n i=1 E ∇g i (θ pse i ) λ pse 2 2 ≤ 6γ 2 t G 2 g n i=1 E γ t λ t i 2 2 + 6γ 4 t nG 2 g λ pse 2 2 ≤ 6γ 2 t nB 2 G 2 g + 6γ 4 t nG 2 g λ pse 2 2 ,where the last inequality is based on Lemma E.1.Plugging the results of (a), (b), and (c) into (A19) givesγ 2 t n i=1 E φ t i ξ t i ; θ t i , θ t i , λ t i -Φ i,t θ pse (θ pse , λ pse ) 2 2 ≤ 3γ 2 t σ 2 0 + 3γ 2 t σ 2 1 + 3 n i=1 L 2 i 1 + ε 2 i max j∈[n] p ij E θ t -θ pse 2 2 + 9γ 2 t n i=1 L 2 i E θ t i -θ t -i 2 2 + 6γ 2 t nB 2 G 2 g + 6γ 4 t nG 2 g λ pse 2 2 . (A20)Next, we deal with the last term on the right side of (A18). First, we have the following inequality:E φ t i ξ t i ; θ t i , θ t i , λ t i -Φ i,t θ pse (θ pse , λ pse ) = E G (i) θ t θ t i , θ t i -G (i) θ pse (θ pse ) + γ t E ∇g i θ t i λ t i -∇g i (θ pse i ) λ pse .Moreover, we haveEQUATIONEQUATIONEQUATIONwhere the last inequality is from Assumptions 2.2, 2.3, 2.4 and the Cauchy-Schwarz inequality.Further, we haveEQUATIONwhere the last inequality uses the fact that g (θ pse ) λ t ≤ 0.Define µ := µ - n i=1 L i ε i max j∈[n] √ p ij , ν := 3 σ 2 1 + 3 n i=1 L 2 i 1 + ε 2 i max j∈[n] p ij , and π := 3σ 2 0 + 6nB 2 G 2 g + 6nG 2 g λ pse 2 2 + 4CG g λ pse .Plugging the results in (A20), (A21), and (A22) into (A18) yieldsEQUATIONLet sup t≥1 γ t ≤ µ ν , then 1 -2 µγ t + νγ 2 t ≤ 1 -µγ t . Thus, we haveE θ t -θ pse 2 2 ≤ 1 µγ t E θ t -θ pse 2 2 -E θ t+1 -θ pse 2 2 + 4C µ n i=1 L i E θ t i -θ t -i 2 + 9γ t µ n i=1 L 2 i E θ t i -θ t -i 2 2 + 2γ t µ n i=1 E B λ t i -λ t 2 -g i θ t i λ t i + πγ t µ .Summing the above inequality over t ∈ [T ] and plugging into the result of Lemma E.2 yieldsEQUATIONwhere in the last inequality is based on the fact that 1 γt -1 γt-1 ≥ 0 because γ t is a non-increasing sequence. Further, we have the following relations:n i=1 L 2 i E θ t i -θ t -i 2 2 ≤ max i L i n i=1 h =i θ t ih -θ t h 2 2 = max i L i n h=1 e t h 2 2 , (A26) n i=1 L i E θ t i -θ t -i 2 ≤ max i L i n i=1 h =i θ t ih -θ t h 2 2 ≤ max i L i n n i=1 h =i θ t ih -θ t h 2 2 ≤ max i L i √ n n h=1 e t h 2 , (A27)where the last inequality is based on the fact that√ a + b + c ≤ √ a + √ b + √ cfor any a, b, c ≥ 0. Plugging (A25), (A26) and (A27) into (A24) and utilizing the results in Lemmas E.4 and E.5, we have thatEQUATIONSince any λ ∈ R m + satisfies the above inequality, by setting λ =[ T t=1 γt n i=1 g i (θ t i )] + n(1+ T t=1 γ 2 t ), we have that2 µ λ T t=1 γ t n i=1 g i θ t i - n µ 1 + T t=1 γ 2 t λ 2 2 = T t=1 γ t n i=1 g i θ t i + 2 2 µn 1 + T t=1 γ 2 t . (A29)As the terms in (A29) is non-negative, omitting it in (A28) givesT t=1 E θ t -θ pse 2 2 ≤ O 1 µγ T + 1 µ T t=1 γ t . Furthermore, since E ξ i ∼D(θ pse ) |J i (ξ i ; θ t i , θ pse -i ) -J i (ξ i ; θ pse )| ≤ G i θ t i -θ pse i 2 , for any i ∈ [n], we have that R i (T ) = T t=1 E ξ i ∼D(θ pse ) J ξ i ; θ t i , θ pse -i -J (ξ i ; θ pse ) ≤ G i T t=1 θ t i -θ pse i 2 ≤ G i T T t=1 θ t i -θ pse i 2 2 ≤ O   T µ 1 γ T + T t=1 γ t   , ∀i ∈ [n].On the other hand, plugging (A29) into (A28) and omitting the non-negtive termT t=1 E θ t -θ pse 2 2 , we have T t=1 γ t n i=1 g i θ t i + 2 2 µn 1 + T t=1 γ 2 t ≤ O 1 µγ T + 1 µ T t=1 γ t . T t=1 γ t n i=1 g i θ t i + 2 ≤ O   1 γ T + T t=1 γ t 1 + T t=1 γ 2 t   .Then, we prove thatR g (T ) ≤ O   1 γ T 1 γ T + T t=1 γ t 1 + T t=1 γ 2 t   . E.1 Proof of Lemma E.1From the update rule of the dual variables, for anyλ t i ∈ R m + , i ∈ [n], and t ∈ [T ], we have that n i=1 λ t+1 i 2 2 ≤ n i=1 n j=1 a ij 1 -γ 2 t λ t j + γ t g i (θ t i ) 2 2 ≤ n i=1 n j=1 a ij (1 -γ 2 t )λ t j + γ 2 t g i (θ t i ) γ t 2 2 ≤ n i=1 n j=1 a ij (1 -γ 2 t ) λ t j 2 2 + g i (θ t i ) 2 2 ≤(1 -γ 2 t ) n i=1 λ t i 2 2 + n i=1 g i (θ t i ) 2 2 ≤(1 -γ 2 t ) n i=1 λ t i 2 2 + nB 2 .We next boundn i=1 λ t i 2 2 , ∀t ∈ [T ] by deduction. First, since λ 1 i = 0, γ 1 ≤ 1, and g i (θ 1 i ) 2 2 ≤ B 2 , ∀i ∈ [n], we have that n i=1 λ 2 i 2 2 ≤ n i=1 g i (θ 1 i ) 2 2 ≤ nB 2 ≤ nB 2 γ 2 1 . Assume that n i=1 λ t i 2 2 ≤ nB 2 γ 2 t-1 . Since {γ t } t∈[T ] is a non-incerasing sequence, n i=1 λ t i 2 2 ≤ nB 2 γ 2 t-1 ≤ nB 2 γ 2 t and thus n i=1 λ t+1 i 2 2 ≤ (1 -γ 2 t ) nB 2 γ 2 t + nB 2 = nB 2 γ 2 t. Therefore, for any t ∈ [T ], we haven i=1 λ t+1 i 2 2 ≤ nB 2 γ 2 t ≤ nB 2 γ 2 t+1 , i.e., n i=1 γ t λ t i 22 ≤ nB 2 , which completes the proof.From the update rule of the dual variables λ i , for any λ ∈ R m + , we have thatEQUATION)where we use the fact 1 -γ 2 t ≤ 1 in (A30). Next, we simplify the terms in (A30). First, based on the inequality (a -b) 2 ≤ 2 a 2 + b 2 for any a, b ≥ 0, we have thatn i=1 n j=1 a ij λ t j -λ t i 2 2 = n i=1 n j=1 a ij λ t j -λ t -λ t i -λ t 2 2 ≤ 4 n i=1 λ t i -λ t 2 2 .In addition, with the result in Lemma E.1, we know thatn i=1 g i θ t i -γ t λ t i 2 2 ≤ 2 n i=1 g i θ t i 2 2 + 2 n i=1 γ t λ t i 2 2 ≤ 2nB 2 + 2nB 2 = 4nB 2 , g i θ t i -γ t λ t i 2 ≤ g i θ t i 2 + γ t λ t i 2 ≤ B + √ nB = (1 + √ n)B.Moreover, based on the fact that n i=1 n j=1 a ij λ t j -λ t i , z = 0 for any z ∈ R m , we have thatn i=1 n j=1 a ij λ t j -λ t i , λ t i -λ = n i=1 n j=1 a ij λ t j -λ t i , λ t i -λ t ≤ 1 2 n i=1 n j=1 a ij λ t j -λ t i 2 2 + λ t i -λ t 2 2 ≤ 5 2 n i=1 λ t i -λ t 2 2 .Furthermore, notice thatλ t i -λ, g i θ t i -γ t λ t i = λ t i -λ, g i θ t i -γ t λ t i 2 2 + γ t λ λ t i ≤ λ t i -λ, g i θ t i + γ t 2 λ 2 2 -λ t i 2 2 ,where the last inequality follows that λ λEQUATION2 ). We also haven i=1 n j=1 a ij λ t j -λ t i 2 ≤ 2 n i=1 λ t i -λ t 2 .Plugging all the above results into (A30), we obtainn i=1 λ t+1 i -λ 2 2 ≤ n i=1 λ t i -λ 2 2 + 9 λ t i -λ t 2 2 + 2γ t λ t i -λ, g i θ t i + γ 2 t λ 2 2 -λ t i 2 2 +4γ t (1 + √ n)B λ t i -λ t 2 + 4nB 2 γ 2 t .Rearranging the terms in the above inequality and summing over t ∈ [T ] givesT t=1 n i=1 γ t λ t i -λ, g i θ t i + T t=1 nγ 2 t 2 λ 2 2 ≥ 1 2 T t=1 n i=1 λ t+1 i -λ 2 2 -λ t i -λ 2 2 - 9 2 T t=1 n i=1 λ t i -λ t 2 2 -4nB 2 T t=1 γ 2 t -2(1 + √ n)B T t=1 γ t n i=1 λ t i -λ t 2 + T t=1 n i=1 γ 2 t 2 λ t i 2 2 .The last term on the right side of the above inequality is non-negative and can be omitted. Besides, since λ 1 i = 0 for all i ∈ [n], thenT t=1 λ t+1 i -λ 2 2 -λ t i -λ 2 2 ≥ -λ 2 2 for any λ T +1 i ∈ R m + . Thus, we have T t=1 n i=1 γ t (λ t i ) g i (θ t i ) -λ g i (θ t i ) ≥ - n 2 1 + T t=1 γ 2 t λ 2 2 - 9 2 T t=1 n i=1 λ t i -λ t 2 2 -2(1 + √ n)B T t=1 γ t n i=1 λ t i -λ t 2 -4nB 2 T t=1 γ 2 t .Rearranging the terms in the above inequality yields- T t=1 n i=1 γ t (λ t i ) g i (θ t i ) ≤ - T t=1 n i=1 γ t λ g i (θ t i ) + n 2 1 + T t=1 γ 2 t λ 2 2 + 9 2 T t=1 n i=1 λ t i -λ t 2 2 + 2(1 + √ n)B T t=1 γ t n i=1 λ t i -λ t 2 + 4nB 2 T t=1 γ 2 t ,which completes the proof.Based on the update rule of θt ih that θ t+1 ih = k =h a ik θ t kh + a ih θ t h , ∀h = i and i, h ∈ [n],we have thate t+1 ih := θ t+1 ih -θ t+1 h = k =h a ik θ t kh + a ih θ t h -θ t+1 h + θ t h -θ t h = k =h a ik e t kh -θ t+1 h -θ t h .Recall that A - h is the weight matrix formed by removing the hth row and hth column of the weight matrix A for any h ∈ [n], and e t h := col e t 1h , • • • , e t (h-1)h , e t (h+1)h , • • • , e t nh . Then,e t+1 h = (A - h ⊗ I d )e t h + 1 n-1 ⊗ θ t+1 h -θ t h . Since β is the maximium eigenvalue of A - h for all h ∈ [n], we have that E e t+1 h 2 ≤ E (A - h ⊗ I d )e t h 2 + E 1 n-1 ⊗ θ t+1 h -θ t h 2 ≤ βE e t h 2 + √ n -1γ t E φ t h ξ t h ; θ t h , θ t h , λ t h 2 ≤ βE e t h 2 + √ n -1γ t E ∇ θ h J h ξ t h ; θ t h , θ t h 2 + √ n -1γ 2 t E ∇g h (θ h ) λ t h 2 ≤ βE e t h 2 + √ n -1γ t (G + G g E γ t λ t h 2 ) ≤ β t E e 1 h 2 + √ n -1 t-1 k=0 β k γ t-k (G + √ nBG g ). (A31)Further, since θ 1 ih = 0 for any i, h ∈ [n], then, from Assumption 2.3, E e 1 ih 2 = θ 1 h 2 ≤ C. Summing the above inequality over t ∈ [T ] and h ∈ [n], we obtainT t=1 n h=1 E e t h 2 ≤ nC T t=1 β t-1 + n √ n -1(G + √ nBG g ) T t=1 t-2 k=0 β k γ t-k-1 ≤ nC 1 -β + n √ n -1(G + √ nBG g ) T k=1 T t=k+1 β t-k-1 γ k ≤ nC 1 -β + n √ n -1(G + √ nBG g ) 1 -β T k=1 γ k .On the other hand, taking square on both sides of (A31), we haveE e t h 2 2 ≤ 2β t E e 1 h 2 2 + 2(n -1)(G + √ nBG g ) 2 t-2 k=0 β k γ t-k-1 2 . (A32)Using the Cauchy-Schwarz inequality yieldst-2 k=0 β k γ t-k-1 2 ≤ t-2 k=0 β k t-2 k=0 β k γ 2 t-k-1 ≤ t-2 k=0 β k γ t-k-1 1 -β . (A33)Plugging (A33) into (A32) and summing over t ∈ [T ], we have thatT t=1 n h=1 E e t h 2 2 ≤ 2nC 2 T t=1 β t + 2n(n -1)(G + √ nBG g ) 2 1 -β T t=1 t-2 k=0 β k γ t-k-1 ≤ 2nC 2 1 -β + 2n(n -1)(G + √ nBG g ) 2 (1 -β) 2 T k=1 γ k . E.4 Proof of Lemma E.5 Let ω t i := 1 -γ 2 t j∈Ni a ij λ t j + γ t g i θ t i +-j∈Ni a ij λ t j . Then, for any i ∈ [n], we have thatEQUATIONThe 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 λ i for any i ∈ [n], we have thatEQUATIONCombining (A35) and (A36) yields ≤ 2, we have that∆ t+1 = (A ⊗ I m ) ∆ t + I - 11 T n ⊗ I m ω t o , ∀t ∈ [T ].n i=1 λ t+1 i -λ t+1 2 = ∆ t+1 2 = (A ⊗ I m ) ∆ t + I - 11 T n ⊗ I m ω t o 2 ≤ (A ⊗ I m ) ∆ t 2 + I - 11 T n ⊗ I m ω t o 2 ≤ σ 2 (A) ∆ t 2 + 2 ω t o 2 ≤ 2 t-1 k=0 σ 2 (A) k ω t-k o 2 ≤ 2(n + √ n)B t-1 k=0 σ 2 (A) k γ t-k ,where the last inequality is based on the result in (A34). Summing the above inequality over t ∈ [T ] yieldsT t=1 n i=1 λ t i -λ t 2 ≤ 2(n + √ n)B T t=1 t-2 k=0 σ 2 (A) k γ t-1-k ≤ 2(n + √ n)B 1 -σ 2 (A) T k=1 γ k .Similarly to the calculation ofT t=1 n h=1 e t h 2 2 in Section E.3, we have that T t=1 n i=1 λ t i -λ t 2 2 ≤ 4(n + √ n) 2 B 2 (1 -σ 2 (A)) 2 T k=1 γ k .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. In 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 its own production quantity but also on the quantities chosen by its competitors, as they influence the demand price determined In this experiment, we consider a networked Cournot game comprising n firms selling a single commodity across m markets, as illustrated in Fig. 3 . Each firm i ∈ [n] determines its output quantityθ i = col (θ i1 , • • • , θ im ) subject to the constraint of its production capacity Q i that m j=1 θ ij ≤ Q i .Here, θ ij denotes the quantity of player i sold to the jth market. The total quantity allocated to market j is limited by its market capacity B j , satisfying the condition that n i=1 θ ij ≤ B j ∀j ∈ [m]. Thus, the local constraint of player i associated with market j isg ij (θ i ) = θ ij -B j /n, ∀i ∈ [n], j ∈ [m]. Let g i (θ i ) := col (g i1 (θ i ), • • • , g im (θ i )), ∀i ∈ [n].The cost function of firm i is defined asJ i = d i θ i - m j=1 p j θ ij , where d i = col (d i1 , • • • , d im )and d ij represents the cost that firm i sells a unit of its product to the jth market, ∀i ∈ [n], j ∈ [m]. d i includes the cost of raw material, transportation, maintenance, etc. In J i , the term p j denotes the unit demand price of market j determined by its market demand curve and the total production quantity, given byEQUATIONwhere c j , d j Λ j , and τ j > 0 are constants, ξ j is a random variable. Due to the interaction between firms and markets, the demand price can fluctuate with production quantities, represented by ξ j ∼ D j (θ). Note that the quantity-dependent distributions D j (θ) for all j ∈ [m] are unknown by players.For any j ∈ [m], the variable ξ j is defined asξ j = ξ o j + ε α j m j =1 α j n i=1 θ ij ,where ξ o j is the random base component, ε ≥ 0 represents the performative strength of markets, and α j is the relative strength of market j for any j ∈ [m]. According to the law of supply and demand, an increased production quantity generally decreases a market's demand price, which corresponds to the setup that α j ≤ 0 for all j ∈ [m]. Thus, the objective of each play i ∈ [n] in the network Cournot game is formulated bymin θi∈Ωi E pj ∼Dj (θij ,∀i∈[n]),j∈[m]   d i θ i - m j=1 p j θ ij   subject to θ ij + i =i θ i j ≤ B j , ∀j ∈ [m].In the simulation, we set n = 5 and m = 3. The network structure is as depicted in Fig. 3 . Each element of the communication weight matrix A = (a ij ) n×n is set to be a ij = 1 |Ni| , and |N i | is the cardinality of N i . The production capacity Q i is randomly and uniformly drawn from [10, 12] for all i ∈ [5] , and the market's capacity B j is randomly and uniformly drawn from [10, 15] for all j ∈ [m]. All entries in d i , ∀i ∈ [n] are randomly and uniformly drawn from [1, 1.5] . The distribution of ξ o j is set to min(max(N (2.5, 1), 2.5), 7.5). The performative power α j is randomly and uniformly drawn from (-1, 0], for all j ∈ [3] . Other settings are: Λ j = 10, c j = 10, d j = 5 and τ j = 2, ∀j ∈ [3] .Fig. 4 compares the demand prices of three markets at PSE and NE with performative strength ε = 0.2, 0.4, and 0.6 and Fig. 5 compares the corresponding serving quantities of five firms to these three markets. The results suggest that, although a larger performative strength leads to a 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.We further examine an example of a ride-share market, where multiple platforms compete to maximize their individual revenue by offering shared rides in competitive areas, taking into account operational 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. at 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 {p j } as in the network Cournot game, given by (A37). Additionally, the maintenance costs associated with platform operations may vary across locations due to factors such as distance or labor costs. Let d i ∈ R m represent the cost vector of platform i at all areas. Then, the inverse of the revenue function for each platform can be expressed asJ i = - m j=1 p j θ ij + d i θ i , ∀i ∈ [n].Assume that each platform only offers one type of ride. Considering the diverse ride characteristics, such as shape and speed, we use h i to denote the spatial occupancy of each ride offered by platform i. The accommodated ride quantity at each location is constrained by B j due to parking availability and road conditions, such that n i=1 h i θ ij ≤ B j . Then, the objective of each platform i ∈ [n] in the ride-share market is formulated asmin θi∈Ωi E pj ∼Dj (θij ,∀i∈[n]),∀j∈[m]   - m j=1 p j θ ij + d i θ i   subject to h i θ ij + i =i h i θ i j ≤ B j , ∀j ∈ [m]. (A38)The simulation setup is based on dataset from a prior Kaggle competition.2 Our study focuses on 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, Q i , from the range [200, 400] for each platform i ∈ [3] . Similarly, the accommodated capacity, B j , is randomly and uniformly drawn from [50, 150] for all j ∈ [8] . All entries in d i , ∀i ∈ [n] are randomly and uniformly drawn from [0.2, 2.2]. The distribution of ξ o j is set as min(max(N (1, 1), 1), 5). Additionally, we set the following values for all areas j ∈ [8]: Λ j = 5, c j = 5, d j = 5, and τ j = 2. Fig. 6 compares the convergence of the time-average revenues of these three platforms: Uber, Lyft, and Via, denoted by -1 t t t =1 E p t ∼D(θ t ) [J i (p t ; θ t )]. We consider three performative strengths: It is observed that, with a mild performative strength ε, 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. 7 shows the convergence of the time-average constraint violations at eight areas by Algorithm 1, denoted by 1 t t t =1 3 i=1 g ij (θ t i ), j = 1, • • • , 8, with performative strengths of ε = 0.1, 0.2, and 0.3. The constraints hold for all three performative strengths. However, as ε increases, the platform tends to allocate fewer rides. This may be attributed to larger market fluctuations associated with a higher ε, leading to a more conservative allocation. Fig. 8 compares the normalized distance between θ t and the NE point θ ne , denoted as θ tθ ne 2 / θ t 2 , with performative strengths: ε = 0.1, 0.2, and 0.3. The result is quantitatively analogous to the findings presented in Fig. 8 . Firstly, θ t gradually approaches θ ne with iterations. Secondly, a higher performative strength leads to a wider normalized distance between the convergent point of θ t and θ ne . Fig. 9 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 is 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 to the eight locations are illustrated in Fig. 11 . 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 , we 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. The data is publicly available at https://www.kaggle.com/brllrb/uber-and-lyft-dataset-boston-ma 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Besides 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.
questions: 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.
- 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: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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}$?

- 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)?

[a] Wood, Killian, and Emiliano Dall’Anese. ``Stochastic saddle point problems with decision-dependent distributions." SIAM Journal on Optimization 33.3 (2023): 1943-1967.

- 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. 
    
- 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.
    
- 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?

- 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?
    
- How does the spectral gap of graph ${\cal G}(A)$, i.e., graph topology, affect the convergence results in Theorem 4.2?

- 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?
questions: questions: **Typo List**: 

- Line 176, "there exists a constant **$C\leq 0$** such that ...", it should be $C\geq 0.$

- After Line 208, second line of optimization problem, $g_i(u_i)$ should be $g_i(\theta_i)$.

- In the problem after Line 727, symbol $\theta$ does not use same font. Same typo in equation (A37).
limitations: limitations: Please answer the questions in weakness part. I will reconsider the rating based on the author's response.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. The proposed algorithm looks very similar to that in Lu et al., 2020.
questions: questions: Why is the condition for $\mu$ different in E&U of PSE and NE?

In assumption 4.1, what does $\nabla_\theta J(\xi,\delta)$ mean? why is the right hand side independent on $\delta$?

Some minor issues:
Some citations should be changed to \citep instead of \citet

Line 224: $p_{ij} \propto $ should be $p_{ij} \leq$
limitations: limitations: The weakness section lists some limitations of this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: No
questions: questions: 1. Is Theorem 3.4 just a simple corollary of Theorem 3.3?

2. 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: limitations: The authors did discuss the limitation

Comments: title: Follow-Up: Request for NeurIPS Rebuttal Response
comment: I appreciate the authors’ detailed response. Regarding the novelty of the technique, I agree with Reviewer dWNU that the constraint condition is not the primary challenge in non-cooperative games, as the use of primal-dual algorithms to tackle Lagrangian form is a natural approach. Existing work [a] already provides a more general framework for min-max problems with performativity. Additionally, the convexity assumption on the constraint in Assumption 2.5 of the submitted paper appears to be somewhat strong.

In Section 4, the convergence analysis in Theorem 4.2 indicates that performative shifts affect the regret bound by a constant factor, but this may not be an intrinsic challenge that performativity can bring in the analysis of primal-dual algorithm.

Therefore, I would like to maintain my original rating of borderline reject.
Dear Reviewer,

I would be grateful if you could respond to the authors' rebuttal.

Thanks,
AC
Dear Reviewer ReB3:

Thank you again for taking the time to review our paper and provide your valuable feedback. As the rebuttal period comes to a close, we wanted to kindly check if our clarifications in the rebuttal have satisfactorily addressed the concerns raised in your initial review. Your feedback is invaluable to us.

If so, we respectfully request you to consider updating your review score based on our responses. However, if you have any remaining questions or need further clarification from us, please do not hesitate to let us know.

Once again, we sincerely appreciate your time and consideration. Your prompt response would be greatly appreciated.

Sincerely,

Authors of the paper
Thank you for the responses.
Many thanks for your response.
I thank the authors for the detailed response. I have no further questions.