PaperlayerView exact revision on arXiv

Source-linked AI summary

The Reflexivity Threshold: A Phase Transition for Multi-Agent Performative Prediction

Ahmed Mahrous, Roberto Di Pietro

arXiv:2610.29577v1cs.LGcs.AI

TL;DR

Multi-agent performative prediction raises the question of how routed cross-agent feedback affects stability, beyond the scalar view used in much prior work. The paper introduces the reflexivity matrix Γ and establishes a threshold at ρ(Γ) = 1: below it retraining converges with bounded cumulative excess loss, while above it some decentralized learners face linear loss growth over finite horizons.

  • Problem

    In multi-agent performative prediction, deployments shape future data and feedback routing matters, but prior work often reduces cross-agent effects to a scalar condition.

    Source: §1 · p. 1, §7 · p. 9

  • Method

    The paper defines Γ from per-agent gradient sensitivities and curvature, then uses its spectral properties to analyze repeated retraining.

    Source: §1 · pp. 1–2

  • Results

    At ρ(Γ) = 1, the paper finds a threshold: below it retraining converges geometrically to a unique stable equilibrium with bounded cumulative excess loss, while above it constructed instances force linear loss growth for decentralized local-information learners.

    Source: §1 · p. 2, §5 · p. 5, §6 · p. 7

  • Takeaways & Limitations

    The spectral threshold gives a boundary for general stability guarantees under the stated assumptions and recovers the single-agent scalar threshold when k = 1.

    Source: §1 · p. 2, §7 · p. 9

    The main guarantees assume strong convexity in each agent’s own action, exact best-response retraining, and a reflexivity matrix fixed across rounds.

    Source: §7 · p. 10

Abstract

from arXiv · show

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 $\Gamma$, 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 noisy supercritical instances in which every local-information learner incurs expected cumulative excess loss growing linearly for horizons up to order $1/(\rho(\Gamma)-1)$. 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.

1 Introduction

The paper asks when repeated retraining in multi-agent performative prediction converges, where agents’ deployments jointly shape the data and feedback can pass between agents. It introduces a reflexivity matrix to capture this network structure and establishes a spectral threshold separating general stability guarantees from worst-case learning obstruction.

1 Introduction

  • The paper asks whether a general threshold separates stable multi-agent performative learning from unavoidable learning failure.In multi-agent systems, deployments can jointly shape the environment, and feedback routing matters alongside its overall strength.Source: §1 · p. 1
  • The reflexivity matrix Γ records how strongly each agent’s deployment can move another agent’s best response, normalized by the affected agent’s objective curvature.Its entries are defined from per-agent gradient sensitivities and curvature parameters.Source: §1 · pp. 1–2
  • At ρ(Γ) = 1, the paper identifies a phase transition: below it retraining converges geometrically to a unique stable equilibrium with horizon-uniform bounded excess loss.Above the threshold, a constructed supercritical family forces every decentralized local-information learner to incur cumulative loss growing linearly over the stated horizons.Source: §1 · p. 2
  • The threshold recovers the single-agent scalar threshold when there is one agent.The results give a sharp boundary for general stability guarantees under sensitivity and curvature assumptions.Source: §1 · p. 2

2 Related Work

Prior work studies performative prediction largely through single-agent theory, scalar conditions, or spectral criteria for special models. This paper positions its contribution as a matrix-based account of cross-agent feedback paired with a worst-case lower bound.

Performative prediction

  • Single-agent performative prediction formalized stability and retraining convergence, while later work extended the framework across several settings [Perdomo et al., 2020].The paper places its threshold result near the single-agent hardness and lower-bound work [Anagnostides et al., 2026].Source: §2 · p. 2

Multi-agent performativity

  • Earlier multi-agent work used scalar aggregate contraction conditions, whereas this paper preserves per-agent-pair feedback in Γ and adds a worst-case lower bound.The scalar-condition strand includes n-player performative prediction [Narang et al., 2023].Source: §2 · p. 2
  • A spectral characterization for linear-quadratic mean-squared-error models on multiplex networks is model-specific, while Γ is built from primitive agent quantities for general strongly convex losses.The paper also distinguishes its information-theoretic threshold from update-rule phase transitions and no-regret results.Source: §2 · pp. 2–3

Spectral methods and lower bounds

  • Network-game spectral methods govern payoff coupling, while this paper’s Γ governs distributional feedback through D(w); its lower bound uses the two-point method.The cited extensions to interactive and decision-dependent settings do not cover this performative learning setting [Chen et al., 2024, Cutler et al., 2024].Source: §2 · p. 3

3 Model

The model has agents who jointly deploy actions that induce a shared data distribution, then repeatedly retrain to best responses. Strong convexity, gradient sensitivity, and unconstrained domains provide the assumptions for the paper’s later reduction and convergence analysis.

3 Model

  • The k agents choose a joint deployment profile w that induces a shared endogenous distribution D(w), making the data-generating process depend on their collective actions.Each agent has a loss and minimizes performative risk under the distribution induced by the deployed profile.Source: §3 · p. 3
  • Each agent’s best response optimizes its action for the environment determined by the current deployed profile, and the joint best-response map is B(w).A performatively stable equilibrium is a profile w⋆ satisfying w⋆ = B(w⋆).Source: §3 · p. 3
  • Repeated retraining simultaneously replaces each current deployment with its best response, yielding dynamics w_{t+1} = B(w_t).The central question is whether this sequence converges to a performatively stable equilibrium.Source: §3 · p. 3
  • Strong convexity in each agent’s own action ensures a unique best response, while gradient sensitivity bounds how deployment changes affect each agent’s gradient.The coefficient a_ij measures how agent j’s deployment disturbs agent i’s gradient; a_ii captures self-reflexive effects.Source: §3 · p. 4
  • The feasible sets are unconstrained, W_i = R^{d_i}, and the paper uses blockwise Euclidean norms and a weighted norm for the joint profile.The unconstrained domains make W complete under the norms used for the fixed-point argument.Source: §3 · p. 4

4 The Reduction: From Retraining Dynamics to Γ

The reduction bounds changes in the nonlinear joint best-response map entrywise using a nonnegative matrix Γ. Its spectral properties then support the contraction analysis, while a scalar-agent example shows how retaining network structure can sharpen a certificate.

4 The Reduction: From Retraining Dynamics to Γ

  • Under the model assumptions, changes in the nonlinear best-response map are bounded entrywise by Γ, reducing retraining analysis to the matrix’s spectral properties.This reduction addresses the coupled dynamics arising from the shared endogenous distribution.Source: §4 · pp. 4–5
  • Strong convexity converts gradient perturbations into best-response shifts, so agent j’s effect on agent i is measured by a_ij/µ_i.The gradient-sensitivity bound and curvature act together through this ratio.Source: §4 · pp. 4–5
  • The reflexivity matrix Γ is nonnegative with entries Γ_ij := a_ij/µ_i, retaining pairwise feedback structure for Perron–Frobenius analysis.The rank-one construction later saturates the sensitivity bound along the Perron direction.Source: §4 · p. 5
  • In the scalar-agent quadratic subclass, Γ = C, so the matrix certificate uses ρ(C) < 1 rather than the scalar aggregate condition ||C||_F < 1.The passage states ρ(C) ≤ ||C||_F, making the matrix certificate no more restrictive in this subclass and sometimes stronger.Source: §4 · p. 5

5 Subcritical Regime: Contraction and Bounded Excess Loss

When ρ(Γ) < 1, retraining contracts in a Perron–Frobenius weighted norm, yielding a unique performatively stable equilibrium and geometric convergence. With smoothness in each agent’s own action, cumulative excess loss is bounded independently of the horizon.

5 Subcritical Regime: Contraction and Bounded Excess Loss

  • When ρ(Γ) < 1, retraining converges geometrically from any initialization to a unique performatively stable equilibrium.The contraction holds in a Perron–Frobenius weighted norm.Source: §5 · pp. 5–6
  • Nonnegativity of Γ and ρ(Γ) < 1 yield positive weights q and α < 1, making the retraining map a contraction in the weighted norm.For reducible Γ, a small positive perturbation supplies suitable weights; the contraction factor can be chosen arbitrarily close to ρ(Γ).Source: §5 · pp. 5–6
  • With smoothness in each agent’s own action, cumulative dynamic excess loss is bounded uniformly in T relative to each round’s current best response.The bound depends on the initialization and contraction factor, not the horizon; the benchmark avoids assumptions on how objective values vary with the deployed profile.Source: §5 · pp. 6–7
  • As the contraction factor α approaches 1, the geometric iteration bound and the factor 1/(1 − α^2) in the loss bound deteriorate.Figure 1 illustrates the slowdown as ρ(Γ) approaches one from below.Source: §5 · p. 7

6 Supercritical Regime

Above the threshold, a noisy supercritical construction makes learning difficult for every decentralized learner with local information. Its equilibria separate as the excess above threshold shrinks, while observations remain statistically indistinguishable over a horizon of order 1/ε.

6 Supercritical Regime

  • For every ε > 0, a supercritical family with ρ(Γ) = 1 + ε forces every decentralized local-information learner to incur linear cumulative excess loss for T = O(1/ε) rounds.The lower bound concerns noisy observations; indistinguishability is established even under a stronger centralized observation model.Source: §6 · pp. 7, 9
  • The construction uses a nonnegative symmetric rank-one matrix Γε with ρ(Γε) = 1 + ε and noise variance σ^2 ε = 8Δ^2/ε.The hidden environment parameter is ν ∈ {−1, +1}.Source: §6 · p. 8
  • The equilibria lie 2Δ/ε apart, and misidentifying the hidden sign yields instantaneous excess loss at least Δ^2/2.The contraction factor ε along the distinguishing direction cancels the 1/ε equilibrium separation.Source: §6 · pp. 8–9
  • The lower bound uses the fixed-equilibrium comparator; for the constructed quadratic family, it also holds under the dynamic comparator.The two comparator goals generally differ: one measures identification of the stable equilibrium, the other one-step adaptation to the current environment.Source: §6 · p. 9
  • The two environments remain statistically indistinguishable through a horizon c0/ε, leaving equal-prior testing error bounded below by an absolute constant.The KL argument uses a stronger centralized observation model, so it also applies to decentralized learners.Source: §6 · p. 9

7 Discussion

The discussion frames Γ as a network-sensitive stability certificate and distinguishes its asymptotic threshold from finite-horizon amplification and empirical measurability. It also states the assumptions and open extensions that bound the results’ scope.

7 Discussion

  • At k = 1, Γ reduces to a11/µ1, recovering the single-agent contraction threshold of Perdomo et al. [2020].For multiple agents, Γ preserves pairwise feedback structure, unlike a scalar aggregate.Source: §7 · p. 9
  • Even when ρ(Γ) < 1, non-normality can cause transient growth, so spectral radius captures asymptotic behavior but not all finite-horizon amplification.The discussion points to numerical range and pseudospectra as possible refinements.Source: §7 · p. 10
  • Estimating ρ(Γ) is difficult because each aij is counterfactual and µi is not directly observed, making estimation a causal-identification problem.The resulting certificate can be conservative and depend on the chosen block geometry; failure of ρ(Γ) < 1 alone does not diagnose instability.Source: §7 · p. 10
  • A fixed-reference quadratic penalty replaces Γij by aij/(µi + λi), potentially restoring the certificate while changing the objective and generally the equilibrium.Source: §7 · p. 10
  • The main guarantees assume strong convexity in each agent’s own action, exact best-response retraining, and a fixed Γ; which supercritical systems remain learnable is open.The lower bound establishes a worst-case obstruction, not that every supercritical Γ is unlearnable; coordination and damped retraining are possible extensions or design levers.Source: §7 · p. 10

A Full Proof of Theorem 8

The proof bounds how well a learner can distinguish two environments, then links misidentification to excess loss over a horizon proportional to 1/ε. The appendix also specifies synthetic simulation protocols for Figure 1.

A Full Proof of Theorem 8

  • The minimax testing error for distinguishing the two environments stays at least p0 > 0 for all t ≤ c0/ε.The proof establishes the bound under a stronger centralized observation model, so it also applies to decentralized learners.Source: A Full Proof of Theorem 8 · p. 12
  • Misidentifying the environment places the action on the wrong side of the midpoint between equilibria, yielding ε = ∆ on the error event.The equilibrium locations are ∆/ε from the origin on opposite sides along v; the contraction factor ε and equilibrium separation factor 1/ε cancel.Source: A Full Proof of Theorem 8 · p. 12
  • Summing the per-round lower bound through T rounds gives cumulative loss growing linearly for horizons up to order 1/ε.The proof uses the testing-error lower bound for each t ≤ c0/ε, then sums over t.Source: A Full Proof of Theorem 8 · p. 13

B Simulation Details for Figure 1

  • Figure 1’s phase diagram estimates subcritical hitting times across 100 trajectories, while its trajectory panel compares normalized distances for selected spectral radii and a non-normal instance.The phase-diagram curve reports the median and interquartile band; the trajectory curves report mean log-distance with pointwise interquartile bands.Source: B Simulation Details for Figure 1 · p. 13

C Approximate and Empirical Retraining

The section extends contraction-based stability to retraining with bounded or vanishing errors and relates empirical optimization error to the resulting iterate bound. It qualifies this as conditional on assumptions needed for statistical rates.

C Approximate and Empirical Retraining

  • With retraining errors bounded by η̄, the asymptotic distance to the equilibrium is at most η̄/(1 − α); if errors vanish, iterates converge to the equilibrium.These conclusions use the contraction conditions of Theorem 4.Source: C Approximate and Empirical Retraining · p. 14
  • For empirical retraining to an exact minimizer, first-order optimality and strong convexity yield an error bound from the empirical gradient discrepancy.The section obtains ηt by dividing by µi qi and maximizing over agents.Source: C Approximate and Empirical Retraining · p. 14
  • The stability statement is conditional; deriving probabilities or sample-size rates for the gradient-error event requires additional statistical assumptions on losses and samples.Source: C Approximate and Empirical Retraining · p. 14

1. Claims

  • The claims checklist says the introduction’s stated contributions and scope reflect the theoretical claims and assumptions.It names strong convexity, exact best-response retraining, and decentralized local information as scope qualifications.Source: §1 · p. 15

2. Limitations

The supplied passage indicates that the paper discusses its limitations in Section 7.

2. Limitations

  • The paper discusses limitations in Section 7.Source: §2 · p. 15

3. Theory assumptions and proofs

The paper reports explicit assumptions and proofs for its theoretical results, and provides materials and details for reproducing its synthetic simulations.

3. Theory assumptions and proofs

  • The theoretical results state their assumptions, with main-text proofs for the subcritical results and the lower-bound proof in Appendix A.The listed assumptions include strong convexity, gradient sensitivity, unconstrained domains, smoothness, and decentralized information.Source: §3 · p. 15

4. Experimental result reproducibility

  • Simulation code, seeds, dependencies, and reproduction commands are provided in the supplementary material.The setup details are described in Appendix B.Source: §4 · p. 16

5. Open access to data and code

  • The simulations use synthetic matrices without external datasets, and supplementary instructions reproduce Figure 1.The supplementary material includes code, seeds, and dependencies.Source: §5 · p. 16

6. Experimental setting/details

  • The main text gives details needed to understand the simulations, while Appendix B specifies the full details for Figure 1.The code is also provided.Source: §6 · p. 17

7. Experiment statistical significance

The paper reports variability summaries for its simulations but does not report compute-resource requirements. Its ethics checklist describes the work as theoretical and simulation-based, without a dedicated societal-impact discussion.

7. Experiment statistical significance

  • Panel 1a reports medians with interquartile bands, while Panel 1b reports mean log-distances with pointwise interquartile bands.The bands summarize variation across base matrices and initializations in Panel 1a, and across the draws described in Appendix B in Panel 1b.Source: §7 · p. 17

8. Experiments compute resources

  • The paper does not report compute resources, though it states the synthetic simulations can be reproduced with standard CPU resources.The checklist marks compute-resource reporting as No.Source: §8 · p. 17

9. Code of ethics

  • The work uses theoretical analysis and synthetic simulations, with no human subjects or substantial-misuse-risk artifacts, but lacks a dedicated societal-impact discussion.The authors state they do not identify a clear direct path to negative applications.Source: §9 · p. 18
Loading 2610.29577v1…