Research map / Learning theory and algorithms / Submodular and game algorithms
Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies performative prediction in decentralized noncooperative games with coupled inequality constraints, giving existence/uniqueness conditions for PSE and NE, a distance bound between them, and a decentralized stochastic primal-dual algorithm with sublinear regret and constraint violation.
Problem
Endogenous distribution shifts in decentralized noncooperative games where players' data distributions depend on all players' decisions and players face coupled inequality constraints, with only neighbor communication.
Approach
Formulates coupled decision-dependent distributions in a constrained decentralized game, derives E&U conditions for PSE and NE, bounds the distance between PSE and NE via strong duality (without joint strong convexity), and designs a decentralized stochastic primal-dual algorithm with consensus-based estimates of other players' decisions.
Key results
- Proposed primal-dual algorithm achieves regret and constraint violation scaling as O(T^{3/4}) with diminishing stepsize (eta=1/2), matching the no-performativity rate.
- Theorem gives PSE-NE distance bound ||θ^pse−θ^ne|| ≤ Gε/(µ−Lε) in the symmetric case.
- Numerical experiments show time-average regrets and constraint violations approach zero, and PSE and NE revenues are close.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase performative strength (ε = 0.2, 0.4, or 0.6) | Decentralized stochastic primal-dual algorithm · Networked Cournot game | normalized distance to NE | Hurt |
| Use the proposed algorithm with performativity rather than the case without performativity | Decentralized stochastic primal-dual algorithm · Decentralized noncooperative game | performative regret convergence order: O(T^{3/4}) | No clear effect |
| Use the proposed algorithm with performativity | Decentralized stochastic primal-dual algorithm · Networked Cournot game | time-average regret and constraint violation | Helped |
Surprising findings
- Performative effect slows convergence (coefficient 1/eµ amplified) but does not change the convergence order relative to the non-performative case.
- PSE and NE remain close in total revenue even when the distance between them grows with performative strength.
Limitations
- Assumes monotonicity of the performative mapping H in the NE analysis (following prior work), not proven in general.
- Convergence requires contraction-type conditions on sensitivity parameters (eµ > 0) that may be restrictive.
- Experiments are limited to simulated Cournot and ride-share markets.
Experimental setup
Datasets: simulated networked Cournot game (five firms, three markets) ride-share market simulation
Benchmarks: networked Cournot game ride-share market
Metrics: performative regret constraint violation normalized distance between iterate and NE total revenue
Baselines: repeated risk minimization NE under perfect distribution knowledge
Builds on: performative prediction (Perdomo et al., 2020) repeated risk minimization Wang et al., 2023 performative games Narang et al., 2023 performative games Lu et al., 2020 decentralized noncooperative games
Closest papers by meaning
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.87)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
- Paradoxes of Game Theoretic Equilibria and Price of Anarchy (NeurIPS 2026 · similarity 0.87)
- The Stability of Online Algorithms in Performative Prediction (NeurIPS 2026 · similarity 0.86)
- Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach (AAAI 2025 · similarity 0.86)
- On Tractable $\Phi$-Equilibria in Non-Concave Games (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.