The reflexivity threshold: A phase transition for multi-agent performative prediction

Ahmed Mahrous; Roberto Di Pietro

The reflexivity threshold: A phase transition for multi-agent performative prediction

NeurIPS 2026 · Accepted · 2026

TL;DR

When predictions change the data that future models learn from, interactions between learners can amplify feedback. We study a spectral threshold separating stable retraining from worst-case learning failure.

Abstract

Many learning systems are performative: once deployed, their predictions change the data distribution on which future models are trained. In multi-agent settings, this feedback is routed through a network of interacting learners, so stability depends not only on the strength of performativity but also on who affects whom. We study repeated retraining in multi-agent performative prediction and identify a spectral threshold that separates stable learning from worst-case learning obstruction. Prior work often collapses cross-agent feedback into a scalar contraction constant, missing this network structure. We instead introduce the reflexivity matrix Γ, which records how strongly one agent’s deployment can move another agent’s best response, defined from per-agent gradient sensitivities and curvature parameters. The threshold occurs when the spectral radius of this matrix crosses one. Below the threshold, repeated retraining converges geometrically to a unique performatively stable equilibrium, with cumulative excess loss bounded uniformly in the time horizon. Above the threshold, we construct supercritical instances in which decentralized learning provably fails: every local-information learner incurs cumulative excess loss that grows linearly in the horizon. Together, these results characterize the threshold behavior through upper and lower bounds and recover the single-agent scalar threshold from prior work as a special case.

Citation

Ahmed Mahrous and Roberto Di Pietro. 2026. The reflexivity threshold: A phase transition for multi-agent performative prediction. Advances in Neural Information Processing Systems.

Download .bib

@inproceedings{reflexivity-threshold-2026,
  author = {Mahrous, Ahmed and Di Pietro, Roberto},
  title = {{The reflexivity threshold: A phase transition for multi-agent performative prediction}},
  year = {2026},
  booktitle = {Advances in Neural Information Processing Systems},
  note = {Accepted at NeurIPS 2026},
  url = {https://amahrous.com/papers/reflexivity-threshold/}
}

Full text

1 Introduction

Many learning systems, once deployed, change the environment that later generates their training data. A credit scoring model can change how applicants behave; an algorithmic trading strategy can move the price data on which future strategies are trained. This feedback effect is the focus of performative prediction. Existing theory largely studies the case of one learner facing the consequences of its own deployment. Many real systems, however, contain multiple learners whose deployments jointly shape the environment.

The multi-agent setting is not simply a larger version of the single-agent problem; it introduces different difficulties. Feedback can travel across agents: one agent’s deployment changes the data distribution, which changes another agent’s retraining problem, which may itself affect the data distribution or other agents. Stability therefore depends not only on the overall strength of performativity, but also on how feedback is routed through the agent network.

We ask whether there is a general threshold separating stable multi-agent performative learning from unavoidable learning failure. When does repeated retraining converge to a stable equilibrium?

We answer this question through a reflexivity matrix Γ with entries Γ ij := aij/µi , measuring how strongly agent j ’s deployment can move agent i ’s best response, after normalizing by the curvature of agent i ’s objective. Thus Γ records who affects whom, and how strongly, in the performative feedback network.

Our main result is a phase transition at ρ (Γ) = 1, where ρ (Γ) is the spectral radius of Γ. This quantity captures the largest asymptotic amplification factor of the feedback network. If ρ (Γ) < 1, Preprint.

cross-agent feedback dissipates: repeated retraining is a contraction in a Perron–Frobenius weighted norm, converges geometrically to a unique performatively stable equilibrium, and incurs bounded cumulative excess loss. Above the threshold, this positive guarantee cannot be extended. We construct supercritical systems in which every decentralized local-information learner suffers cumulative loss that grows linearly with time, regardless of the retraining rule. The spectral radius of the reflexivity matrix therefore separates stable adaptation from unavoidable amplification in multi-agent performative systems.

Contributions. First, we introduce the reflexivity matrix Γ, a nonnegative matrix whose entry Γ ij records how strongly agent j ’s deployment can move agent i ’s best response, as determined by per-agent gradient sensitivities and curvature constants. We prove an entrywise best-response sensitivity bound that reduces the nonlinear retraining dynamics to a spectral comparison through Γ, making Perron–Frobenius theory available for the multi-agent performative setting. Second, we prove the subcritical side of the threshold: if ρ (Γ) < 1, repeated retraining is a contraction in a Perron–Frobenius weighted norm, yielding a unique performatively stable equilibrium, geometric convergence from any initialization, and cumulative dynamic excess loss bounded uniformly in the time horizon. Third, we prove the supercritical side: for a rank-one family with ρ (Γ) = 1 + ε , every decentralized local-information learner incurs cumulative excess loss Ω(∆² T ) over horizons T = O (1 /ε ). Together, these results identify ρ (Γ) = 1 as a boundary for stability guarantees and recover the single-agent scalar threshold from prior work when k = 1.

2 Related Work

This paper draws on three lines of research. The first is the single-agent theory of performative prediction, which introduces the framework we extend. The second is the multi-agent theory of performative prediction and decision-dependent games, which is where our contribution is most directly positioned. The third is the combined tradition of spectral methods for network games and statistical lower bound techniques, from which we import two standard technical tools.

Performative prediction. Perdomo et al. [2020] introduced performative prediction in a single-agent setting, formalizing performative stability and convergence of repeated retraining under sensitivity conditions. Subsequent work largely retained this single-agent viewpoint while extending the framework to stochastic, causal, nonconvex, and sequential settings [Mendler-Dünner et al., 2020, Miller et al., 2021, Brown et al., 2022, Hardt et al., 2022, Mofakhami et al., 2023, Mandal et al., 2023]. Closest to our threshold result, Anagnostides et al. [2026] established hardness and lower bounds at the single-agent scalar threshold. We depart from this line by studying decentralized multi-agent retraining, where performative feedback is cross-agent and the scalar threshold is replaced by the spectral condition ρ (Γ) = 1.

Multi-agent performativity. The multi-agent extension is the most direct predecessor of our work, and the literature divides into three strands.

The first establishes scalar contraction conditions for convergence. Narang et al. [2023] formalized n -player performative prediction with a scalar aggregate threshold ρ < 1, and analogous scalar conditions appear in cooperative consensus learning [Li et al., 2022], decentralized games with coupled constraints [Yan and Cao, 2024], and a Wasserstein-free variant [Zhong et al., 2025]. We depart from this strand on two axes. We replace the scalar aggregate with a matrix Γ that preserves per-agent-pair feedback, and we pair the upper bound with a worst-case information-theoretic lower bound above the threshold.

The second develops spectral characterizations in special models. Wang et al. [2023] derived a necessary-and-sufficient spectral condition for a linear-quadratic mean-squared-error model on multiplex networks. Their spectral object is a weighted adjacency matrix with exogenous structure, and the condition is specific to the linear-quadratic model. Our Γ is built from primitive per-agent quantities, applies to general strongly convex losses, and is paired with a lower bound.

The third identifies dynamical phase transitions. Piliouras and Yu [2023] proved a transition from stability to Li–Yorke chaos as update aggressiveness grows under scalar aggregate influence. Their threshold is dynamical and concerns the long-run behavior of specific update rules; ours is informationtheoretic and applies to every decentralized local-information learner.

Spectral methods and lower bounds. Two technical traditions supply tools used in our analysis without serving as competing frameworks. Spectral conditions for equilibrium uniqueness and stability are well established in network games [Ballester et al., 2006, Bramoullé et al., 2014, Parise and Ozdaglar, 2019], where the spectral radius governs payoff coupling: agent j ’s action enters agent i ’s utility directly. In our setting, it governs distributional feedback through D ( w ), and Γ is built from gradient sensitivities and curvature constants rather than payoff coefficients. Our lower bound uses the two-point method [Tsybakov, 2009]; recent extensions to interactive [Chen et al., 2024] and decision-dependent [Cutler et al., 2024] settings do not cover our performative learning setting. Our construction is tailored to multi-agent performative feedback over a finite horizon.

3 Model

This section specifies the multi-agent performative prediction model used throughout the paper. We describe the agents, their objectives, the dynamics of repeated retraining, and the assumptions that underlie the reduction of Section 4.

There are k agents. Each agent i ∈{ 1 , . . . , k} chooses a deployment wi from a feasible set Wi = R^di . The joint deployment profile is w := ( w 1 , . . . , wk ) ∈W := W 1 × · · · × Wk . The deployed profile induces a shared endogenous distribution D ( w ) over observations z ∈Z . This distribution represents the data-generating process that all agents face after the profile w has been deployed. The dependence of D on w captures the performative nature of the system: the environment that agents observe is shaped by their own collective actions.

Each agent i has a loss function ℓi : Wi × Z → R and aims to minimize its performative risk

Figure, table, or displayed equation from PDF page 3

The two arguments of Fi play distinct roles. The first, ui , is the candidate action optimized by agent i . The second, w , is the deployed profile that determines the environment through D ( w ). Retraining couples these roles by replacing the deployed profile with agents’ optimized actions.

For each agent i and each deployed profile w , the best response is

Figure, table, or displayed equation from PDF page 3

Definition 1 (Performatively stable equilibrium) . A profile w^⋆ ∈W is a performatively stable equilibrium if w^⋆ = B ( w^⋆ ) .

At a performatively stable equilibrium, each agent’s deployed action is optimal for the distribution induced by the joint deployment. Existence of such an equilibrium is not assumed; it is derived in Section 5 as a consequence of the spectral condition on the reflexivity matrix.

We study the repeated retraining dynamics in which every agent simultaneously replaces its current deployment with its best response,

Figure, table, or displayed equation from PDF page 3

with initialization w 0 ∈W . The central question of the paper is when the sequence {wt} converges to a performatively stable equilibrium, and when convergence fails.

Main assumptions. Three assumptions are used throughout the paper. The first two are local to individual agents and enter the reduction of Section 4. The third is a mild regularity condition on the feasible sets that allows application of Banach’s fixed-point theorem.

Strong convexity makes Bi ( w ) unique and quantifies agent i ’s resistance to gradient perturbations. Larger µi means that the best response is less sensitive to changes in the data distribution.

Assumption 2 (Gradient sensitivity to the deployed profile) . For each i, Fi is continuously differentiable in ui, and there exist nonnegative constants aij ≥ 0 for all i, j ∈{ 1 , . . . , k} such that for every agent i, every candidate action ui ∈Wi, and every pair of deployed profiles w, w^′ ∈W,

Figure, table, or displayed equation from PDF page 4

Gradient sensitivity quantifies how a change in the deployed profile affects each agent’s first-order condition. The coefficient aij measures how much agent j ’s deployment disturbs agent i ’s gradient. If agent j has no effect on agent i ’s optimization problem, then aij = 0. Larger values of aij indicate stronger cross-agent coupling. The diagonal coefficient aii captures agent i ’s own self-reflexive effect through the environment.

Assumptions 1 and 2 are the only two channels through which agents interact mathematically in this paper. Every downstream result is derived from these two assumptions and their combination in Section 4. The reflexivity matrix Γ of Section 4 is built from exactly the parameters {µi} and {aij} introduced here.

Assumption 3 (Unconstrained domains) . Each feasible set is Wi = R^di .

This makes W complete under the norms used below, enabling Banach’s fixed-point theorem, and ensures that retraining stays in W .

Throughout, xi denotes agent i ’s block of a vector x ∈ R^d_1 × · · · × R^dk , with Euclidean norm ∥· ∥ . The spectral radius of M is ρ ( M ), and for q ∈ R^k ++^{we write}^{∥x∥q_:= max}^{i∥xi∥/qi.}

4 The Reduction: From Retraining Dynamics to Γ

The retraining dynamics wt +1 = B ( wt ) are nonlinear and couple all k agents through the shared endogenous distribution D ( w ). Direct analysis of these dynamics is difficult without additional structure. This section introduces the reduction used throughout the paper: under the assumptions of Section 3, changes in the nonlinear map B are bounded entrywise by a nonnegative matrix Γ. The spectral properties of Γ can therefore be used to bound the dynamics of B .

The first step bounds the shift in any agent’s best response induced by a shift in the deployed profile. The bound is linear and decomposes cleanly across agents.

Theorem 2 (Best-response sensitivity) . Under Assumptions 1–2, for every agent i and every pair of deployed profiles w, w^′ ,

Figure, table, or displayed equation from PDF page 4

The proof uses each structural assumption once: gradient sensitivity bounds the performative change in agent i ’s gradient, and strong convexity converts it into a best-response change. Their interaction appears only through aij/µi , the ratio of agent j ’s disturbance to agent i ’s curvature, which measures how much j can shift i ’s best response.

The weights in Theorem 2 define the central object of the paper.

Definition 3 (Reflexivity matrix) . The reflexivity matrix is the k × k nonnegative matrix Γ with entries Γ ij := aij/µi, for i, j = 1 , . . . , k.

In terms of Γ, Theorem 2 states that for every i and every w, w^′ ,

Figure, table, or displayed equation from PDF page 5

The vector of best-response shifts is therefore dominated entrywise by the product of Γ with the vector of action shifts.

The matrix Γ is the central reduction object. It is built from primitive per-agent quantities rather than imposed as an aggregate Lipschitz constant, and its nonnegativity makes Perron–Frobenius theory available for the weighted-norm contraction argument below. The rank-one construction in Section 6 saturates (4) along the Perron direction, so the same spectral radius governs both the upper and lower sides of the threshold.

5 Subcritical Regime: Contraction and Bounded Excess Loss

This section proves the positive side of the threshold. Under the assumptions of Section 3, if ρ (Γ) < 1, then the retraining map is a contraction in a Perron–Frobenius weighted norm. This yields a unique performatively stable equilibrium, geometric convergence from any initialization, and a cumulative excess-loss bound that does not grow with the time horizon.

Contraction via Perron–Frobenius. The best-response sensitivity inequality (4) bounds how differences between two deployed profiles translate into differences between their best-response profiles. When ρ (Γ) < 1, Perron–Frobenius theory provides positive weights under which this bound becomes a contraction in a weighted norm. A contraction in a weighted norm means that two deployment profiles become closer after one retraining step, once each agent’s deviation is rescaled by a positive weight. The weights account for heterogeneous feedback across agents.

Theorem 4 (Weighted contraction below threshold) . Suppose Assumptions 1–2 and 3 hold, and ρ (Γ) < 1 . Then there exist a positive vector q ∈ R^k ++^{and a constant α ∈(0}^_,_1)^{such that}

Figure, table, or displayed equation from PDF page 5

where the weighted norm is defined by

Figure, table, or displayed equation from PDF page 5

Proof. Since Γ is nonnegative and ρ (Γ) < 1, Perron–Frobenius theory guarantees the existence of a vector q ∈ R^k ++^{and a constant}^{α ∈(0}^{_,_1) satisfying}

Figure, table, or displayed equation from PDF page 5

If Γ is reducible, apply the argument to the perturbed matrix Γ η := Γ + η 11^⊤ for η > 0 chosen small enough that ρ (Γ η ) < 1; the strictly positive Perron eigenvector q of Γ η then satisfies Γ q ≤ Γ ηq = ρ (Γ η ) q , and we set α := ρ (Γ η ) ∈ ( ρ (Γ) , 1).

Fix w, w^′ ∈W and an agent i . By the definition of the weighted norm, ∥wj −wj^{_′∥≤qj ∥w−w′∥q_for} every j . Substituting this bound into the best-response sensitivity inequality (4) and then applying (5) yields

Figure, table, or displayed equation from PDF page 5

Dividing by qi > 0 and taking the maximum over i gives the claim.

Equivalently, for any α ∈ ( ρ (Γ) , 1), one can choose positive weights q such that Γ q ≤ αq . The contraction factor can therefore be made arbitrarily close to ρ (Γ). The proof uses only two facts: Γ is nonnegative and ρ (Γ) < 1.

The contraction theorem gives the standard fixed-point consequences. Since B is a contraction on the complete space ( W, ∥· ∥q ), Banach’s fixed-point theorem applies.

Corollary 5 (Existence, uniqueness, and geometric convergence) . Under the conditions of Theorem 4:

1. The retraining map B admits a unique fixed point w^⋆ ∈W, which is the unique performatively stable equilibrium of the system.

2. For every initialization w 0 ∈W, the iterates wt +1 = B ( wt ) satisfy