Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions

Wenjing Yan, Xuanyu Cao

Introduction

Standard machine learning often operates under the assumption that data is drawn from a static distribution. However, in real-world deployments, models frequently alter the very environments they are designed to predict. For instance, a ride-sharing application adjusting its pricing model will shift user behavior, thereby changing the data collected for future optimizations. This phenomenon is formalized as Performative Prediction (PP).

While previous research has explored PP for isolated models or unconstrained games, this paper tackles a more complex and realistic scenario: decentralized noncooperative games with coupled constraints.

The Challenge: Decentralized Games with Coupled Constraints

Imagine several competing firms (players) aiming to minimize their individual costs. Their collective decisions shift the market's underlying data distribution. Crucially, these players must also adhere to shared, or coupled, constraints—such as total market capacity or regulatory limits—without the oversight of a central coordinating authority.

The primary challenge in this setting is identifying a stable operating point when the "ground truth" data distribution is a moving target, continuously influenced by the actions of all players.

Methodology: Equilibria and the Primal-Dual Algorithm

To navigate this dynamic environment, the authors formulate the problem as a game where players seek two distinct types of equilibria:

  1. Performative Stable Equilibrium (PSE): A steady state where every player’s model is optimal for the specific data distribution that the model itself induces. At this point, no player has an incentive to retrain their model.
  2. Nash Equilibrium (NE): The true optimum, where players explicitly account for the fact that their actions will change the data distribution.

Decentralized Stochastic Primal-Dual Algorithm

To efficiently compute the PSE, the authors introduce a novel decentralized algorithm where players only communicate with immediate neighbors in a network. The algorithm relies on three core mechanisms:

  • Consensus Building: Because individual costs depend on the collective actions of all players, each participant maintains and updates an estimate of others' strategies.
  • Primal-Dual Approach: To manage the shared inequality constraints, the algorithm employs dual variables, which act as internal penalties or prices for constraint violations.
  • Stochastic Updates: The system utilizes noisy, sampled data rather than requiring perfect knowledge of the distribution mapping, ensuring practical applicability in real-world scenarios.

Key Insights and Theoretical Guarantees

The paper makes several significant theoretical contributions to the field of performative prediction:

  • Bounding the PSE-NE Gap: A major breakthrough in this work is the derivation of the first upper bound on the distance between the PSE and the NE in a constrained game. While the PSE is computationally more tractable, the NE represents a more rigorous optimum. The authors prove that if the environment's distribution is not overly sensitive to model changes, the PSE serves as a highly accurate proxy for the NE.
  • Robust Convergence Under Performativity: A common concern in PP is that feedback loops might destabilize the system. The authors prove that their algorithm achieves sublinear convergence. Specifically, it yields a regret and constraint violation bound of $\mathcal{O}(T^{3/4})$. This demonstrates that while performative effects introduce complexity, they do not degrade the fundamental order of the convergence rate compared to static environments.
  • Managing Coupled Constraints: The research shows that decentralized consensus mechanisms are sufficient to keep all players within shared safety boundaries, even as the underlying data distribution shifts.

Empirical Validation

Rather than relying on standard static datasets, the authors validate their theoretical findings using two sophisticated simulations:

  1. Networked Cournot Game: A classic economic model featuring five firms competing across three markets with limited capacities.
  2. Ride-Share Market Simulation: Built on a real-world Kaggle dataset of NYC ride-sharing trips (Uber, Lyft, and Via). This simulation models how pricing decisions across different city zones affect demand distributions, and how platforms must compete while respecting traffic and parking constraints.

In these experiments, the algorithm successfully converged to the PSE. Furthermore, the results confirmed the theoretical distance bound: as "performative strength" (the degree to which decisions affect data) increased, the gap between the PSE and NE grew but remained strictly manageable.

Limitations and Future Directions

While the paper provides robust theoretical foundations, the mathematical proofs rely on certain assumptions that present opportunities for future research:

  • Strong Monotonicity: The guarantees depend on cost functions being strongly monotone. This assumption may not hold for highly complex, non-convex models like deep neural networks.
  • Linear Distribution Sensitivity: The results assume the distribution shift is relatively smooth (Lipschitz continuous in the Wasserstein-1 metric). Extreme or discontinuous shifts in environmental behavior could violate these conditions.

Future work could extend this framework to accommodate non-convex cost functions or dynamic scenarios where the network communication structure itself evolves over time.

Summary updated

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.
BibTeX
@inproceedings{yan2024decentralized,
  author = {Wenjing Yan and Xuanyu Cao},
  title = {{Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=KqgSzXbufw},
}
Figure