# On the Computational Complexity of Performative Prediction

arXiv: https://arxiv.org/abs/2601.20180 · HTML: https://mlsanity.com/paper/2601.20180/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 30 of 31)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [How to Learn when Data Reacts to Your Model: Performative Gradient Descent](https://mlsanity.com/paper/2102.07698/) (2021)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [Performative Prediction with Neural Networks](https://mlsanity.com/paper/2304.06879/) (2023)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Strategyproof Linear Regression in High Dimensions](https://mlsanity.com/paper/1805.10693/) (2018)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss](https://mlsanity.com/paper/2405.17922/) (2024)
- [Incentivizing Truthfulness Through Audits in Strategic Classification](https://mlsanity.com/paper/2012.09147/) (2020)
- [Pure-Circuit: Tight Inapproximability for PPAD](https://mlsanity.com/paper/2209.15149/) (2022)
- [Performative Prediction on Games and Mechanism Design](https://mlsanity.com/paper/2408.05146/) (2024)
- [Distributionally Robust Performative Prediction](https://mlsanity.com/paper/2412.04346/) (2024)
- [Improved Hardness Results for Min-Max Optimization with Coupled Constraints](https://mlsanity.com/paper/2411.03248/) (2024)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion](https://mlsanity.com/paper/2506.17698/) (2025)
- [Tight Lower Bounds and Improved Convergence in Performative Prediction](https://mlsanity.com/paper/2412.03671/) (2024)
- [Constant Rank Bimatrix Games are PPAD-hard](https://mlsanity.com/paper/1402.3350/) (2014)
- [Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria](https://mlsanity.com/paper/1909.03210/) (2019)
- [Tree Polymatrix Games are PPAD-hard](https://mlsanity.com/paper/2002.12119/) (2020)
- [Tight Inapproximability for Graphical Games](https://mlsanity.com/paper/2209.15151/) (2022)
- [On the Hypomonotone Class of Variational Inequalities](https://mlsanity.com/paper/2410.09182/) (2024)

## Built on by (most cited first, 2 of 2)

- [The Stability of Online Algorithms in Performative Prediction](https://mlsanity.com/paper/2602.24207/) (2026)
- [Stabilizing Performative Feedback Loops with Minimal Model Deployments](https://mlsanity.com/paper/2609.14065/) (2026)

## Abstract (arXiv)

Performative prediction captures the phenomenon where deploying a predictive model shifts the underlying data distribution. While simple retraining dynamics are known to converge linearly when the performative effects are weak (ρ < 1), the complexity in the regime ρ > 1 was hitherto open. In this paper, we establish a sharp phase transition: computing an ε-performatively stable point is PPAD-complete -- and thus polynomial-time equivalent to Nash equilibria in general-sum games -- even when ρ = 1 + O(ε). This intractability persists even in the ostensibly simple setting with a quadratic loss function and linear distribution shifts. One of our key technical contributions is to extend this PPAD-hardness result to general convex domains, which is of broader interest in the complexity of variational inequalities. Finally, we address the special case of strategic classification, showing that computing a strategic local optimum is PLS-hard.