acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
performative learning, game theory, payoff-based

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_KHZvOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper studies decentralized games with decision-dependent data distributions and coupled constraints. SPADE uses payoff-based gradient estimates and exchanges only dual variables. Frozen-distribution feedback targets a performatively stable equilibrium; deployed-distribution feedback targets a variational generalized nash equilibrium. SPADE-MP uses two coupled payoff observations to reduce estimator variance. The paper claims O(T^(7/8)) cumulative regret and constraint bounds for its one-point methods and O(T^(3/4)) bounds for SPADE-MP. Experiments use a five -firm, three-market Cournot model and report a sixfold reduction in scalar transmissions per iteration against a dense gradient-based baseline.

Critical strengths
  • Reduced peer communication. Exchanging only dual variables is a meaningful extension of the existing constrained performative-learning framework. It removes the need to transmit full action estimates or know the objective's functional form.
  • Explicit feedback models and variance analysis. The paper distinguishes frozen-distribution, deployed-distribution, and paired-feedback access. Under Assumption 10's coupling, the 2 point estimator's second moment is correctly bounded independently of the smoothing radius.
Critical weaknesses
  • The stated NE convergence assumptions are insufficient. Proposition 1 on page 5, requires an additional monotonicity condition on the indirect mapping Hδ(θ)H_{\delta}(\theta). Theorems 2/4 and 3/5 omit it, yet the proof on page 36 invokes strong monotonicity of the full performative pseudogradient merely from μ^>0\widehat{\mu} > 0. Smoothness in Assumption 9 does not supply nomotonicity. A 2-player counterexample satisfies the listed hypotheses:
D_i(\theta)=\delta_{0.1(1-\cos\theta_i)}.$$ $$J_i(\xi_i;\theta)=\tfrac{1}{2}\theta_i^2-20\xi_i.$$ Here $\mu=L_i=1$, $\varepsilon_i=0.1$, $p_{ii}=1$, and $$\widetilde{\mu}=0.8,\qquad \widehat{\mu}=0.8-\sqrt{0.02}>0.$$ Nevertheless, $$PR_i(\theta_i)=\tfrac{1}{2}\theta_i^2-2(1-\cos\theta_i)$$ is minimized at $\pm1$. SPADE-MP initialized at zero remains there: its antithetic payoff observations are identical, so every gradient estimate is zero. Its NE regret is therefore $$\bigl[2(1-\cos 1)-\tfrac{1}{2}\bigr]T \approx 0.4194T$$ contradicting the claimed sublinear bound. The authors should explicitly assume or correctly establish strong monotonicity of the full performative pseudogradient. Separately, Example 1's smoothness implication needs stronger regularity: $J(\xi;\theta)=\theta^2/2+|\xi|$, with $\xi=c\theta$, has a smooth own-action gradient but a nonsmooth performative risk. - The communication comparison does not establish total savings at matched accuracy. The sixfold reduction is a valid per-iteration comparison against the stated dense-message convention. The one-point methods converge substantially more slowly, while SPADE-MP requires two synchronized deployments with coupled shocks. The paper does not compare total scalar transmissions and payoff queries needed to reach the same equilibrium error.
Questions for authors
  • What corrected hypotheses establish strong monotonicity of the full performative pseudogradient and exclude the counterexample above? Please align every NE theorem and repair Example 1's sufficient conditions.
  • Can you report total communications and payoff-query costs at matched equilibrium accuracy? Also clarify Appendix G.3's statement that all figures use T=10^6, followed by one-point endpoint errors reported after 10^9 iterations
Reviewer_H5fAOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SPADE and its variants for decentralized noncooperative games with performative effects and coupled constraints. Each player estimates gradients from random action perturbations and observed payoffs, then updates their strategy. Depending on how feedback is generated, the paper provides convergence guarantees for a performative-stable equilibrium (PSE) or a Nash equilibrium (NE), and evaluates the algorithms through numerical experiments.

Critical strengths
  1. Learning equilibria with limited observations and communication is an important problem, particularly when players’ decisions affect their data distributions. Extending decentralized performative learning to settings where players do not know their cost functions or have access to gradients is a worthwhile direction.

  2. The paper provides both proofs of convergence guarantees and numerical experiments examining convergence behavior. These results directly address the paper’s research objective.

Critical weaknesses
  1. I find the technical novelty limited. Random perturbation estimators, variance reduction through two-point feedback, and decentralized primal-dual updates are established techniques. The main contribution seems to be their combination in this setting.

  2. The near-full-information guarantee for SPADE-MP depends on Assumption 10, which requires paired multipoint feedback. Although the main text explains this requirement, the abstract’s wording seems too broad given this restriction.

  3. The communication comparison does not show the total communication needed to reach a given accuracy. The authors clearly state that the reduction is per iteration, and Figure 6 accumulates these per-iteration costs. However, the proposed method may require more iterations. This comparison therefore does not establish that it uses less communication to reach the same accuracy. The broader claims about communication efficiency seem to go beyond what the experiments demonstrate.

Questions for authors
  1. Do the NE convergence results also assume that (H_\delta(\theta)) is monotone with respect to (\delta), as stated in Proposition 1?

  2. Under Assumption 10, is there a concrete example where existing methods perform poorly because of noise or similar factors, while the proposed method works well? Such an example would help clarify the advantage of the proposed method.

Reviewer_4ca6OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies decentralized noncooperative games in which actions affect the data-generating distributions, players have coupled constraints, and only realized payoffs are observed. It proposes SPADE for performatively stable equilibria (PSE), SPADE-NE for Nash equilibria (NE), and the two-point variant SPADE-MP. All three replace communicated primal-gradient information with payoff-based perturbation estimators and communicate local dual variables to manage shared constraints. Under strong monotonicity and associated regularity assumptions, the one-point algorithms obtain O(T^{7/8}) cumulative regret and constraint-violation bounds; with coupled two-point feedback, SPADE-MP obtains O(T^{3/4}). Networked Cournot simulations illustrate convergence and a reduction in transmitted scalars relative to a full-information decentralized baseline.

Critical strengths
  • The paper extends payoff-based learning to performative games with coupled constraints, requiring only dual-variable communication rather than exchanging actions or gradients.
  • The distinction between intended-action and deployed-action sampling provides a principled way to target PSE and NE, respectively.
  • The convergence analysis handles zeroth-order estimation, distribution shifts, and dual consensus. SPADE-MP further improves the regret rate from (O(T^{7/8})) to (O(T^{3/4})) through paired feedback.
Critical weaknesses
  • SPADE requires access to intended-action distributions, while SPADE-MP relies on strongly coupled payoff observations. These assumptions may be difficult to satisfy in practical decentralized environments.
  • The evaluation focuses on a single synthetic Cournot setting, leaving robustness across larger networks, different game structures, and more realistic environments unclear.
  • Communication savings are measured per iteration rather than at matched convergence accuracy. Given the slow convergence of one-point methods and the additional payoff queries required by SPADE-MP, the practical efficiency advantage remains uncertain.
Questions for authors
  • For which concrete deployment mechanisms can the paired-feedback condition in Assumption 10 be enforced when an agent cannot control the exogenous shock? What rate or behavior should be expected with independent noise in the two payoff queries?
  • Can the authors compare total payoff queries and total transmitted scalars needed to reach a fixed NE-distance and feasibility tolerance, using both dense and sparse implementations of the Yan–Cao baseline? This would clarify whether per-round communication savings survive the slower convergence.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.