Towards Performatively Stable Equilibria in Decision-Dependent Games for Arbitrary Data Distribution Maps
This work addresses a practical limitation in multi-agent systems like market pricing by enabling convergence to equilibria without relying on impractical smoothness assumptions, though it is incremental as it builds on prior concepts of performative stability.
The paper tackles the problem of finding performatively stable equilibria in decision-dependent games where data distributions shift with players' actions, by proposing a gradient-based sensitivity measure to quantify distribution shifts, and it results in a sensitivity-informed algorithm that achieves lower losses and faster convergence in experiments.
In decision-dependent games, multiple players optimize their decisions under a data distribution that shifts with their joint actions, creating complex dynamics in applications like market pricing. A practical consequence of these dynamics is the \textit{performatively stable equilibrium}, where each player's strategy is a best response under the induced distribution. Prior work relies on $β$-smoothness, assuming Lipschitz continuity of loss function gradients with respect to the data distribution, which is impractical as the data distribution maps, i.e., the relationship between joint decision and the resulting distribution shifts, are typically unknown, rendering $β$ unobtainable. To overcome this limitation, we propose a gradient-based sensitivity measure that directly quantifies the impact of decision-induced distribution shifts. Leveraging this measure, we derive convergence guarantees for performatively stable equilibria under a practically feasible assumption of strong monotonicity. Accordingly, we develop a sensitivity-informed repeated retraining algorithm that adjusts players' loss functions based on the sensitivity measure, guaranteeing convergence to performatively stable equilibria for arbitrary data distribution maps. Experiments on prediction error minimization game, Cournot competition, and revenue maximization game show that our approach outperforms state-of-the-art baselines, achieving lower losses and faster convergence.