SPADE: Stochastic Payoff-Based Algorithm for Decentralized Equilibria in Decision-Dependent Games with Coupled Constraints

In learning problems within politics, finance, or operations, agents' decisions and predictions can influence the underlying data-generating process - a phenomenon known as the *performative effect* (Perdomo et al., 2020). We study this effect in decentralized noncooperative games with coupled constraints, where data distributions depend endogenously on players' actions. In practical settings, agents may not know the functional form of their objectives and can only observe realized payoffs from played actions. Our main contribution is SPADE (**S**tochastic **P**ayoff-based **A**lgorithm for **D**ecentralized **E**quilibria), a low-communication cost distributed algorithm in which each player randomly perturbs its action and updates using payoff observations. We show that when data are sampled from players' unperturbed actions, SPADE converges to the performatively-stable equilibrium (PSE). We also present SPADE-NE, in which both data and payoffs are induced by the deployed actions, and prove convergence to the harder Nash equilibrium (NE) under an additional smoothness assumption. Finally, we propose SPADE-MP, a multipoint-feedback approach that retains near full-information guarantees and improves empirical convergence to NE. We support our results through numerical experiments on networked Cournot competition and show significant improvements in reducing communication overhead.