| On the Computational Complexity of Performative Prediction | |
| Ioannis Anagnostides∗1 , Rohan Chauhan2 , Ioannis Panageas2 , Tuomas Sandholm1,3 , and | |
| Jingming Yan∗2 | |
| 1 Carnegie Mellon University | |
| 2 University of California, Irvine | |
| 3 Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc. | |
| arXiv:2601.20180v1 [cs.LG] 28 Jan 2026 | |
| {ianagnos,sandholm}@cs.cmu.edu, {ipanagea,rmchauha,jingmy1}@uci.edu | |
| January 29, 2026 | |
| Abstract | |
| 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. | |
| 1 Introduction | |
| Machine learning models are typically developed under the assumption that the deployment envi- | |
| ronment is static: the underlying data distribution remains fixed regardless of the model’s predic- | |
| tions. However, in many high-stakes social and economic domains, this premise is fundamentally | |
| flawed. As sociologists and economists have long observed, models are not merely cameras that pas- | |
| sively record the markets, but engines that actively shape the reality they aim to model [MacKenzie, | |
| 2008]. Similarly, in modern predictive tasks—ranging from credit scoring to spam filtering—the | |
| deployment of a predictive model triggers a shift in the underlying data distribution, as agents | |
| react strategically to the deployed classifier. | |
| This ubiquitous phenomenon was formalized by Perdomo et al. [2020] as performative prediction. | |
| In this setting, the model, parameterized by x ∈ X , induces a distribution D(x) over the data. | |
| The decision-maker is thus facing a moving target: updating the model triggers a shift in the | |
| very objective they seek to minimize. This feedback loop yields two natural solution concepts. | |
| ∗ | |
| These authors contributed equally. | |
| 1 | |
| First, a performatively optimal point minimizes the expected loss over the distribution it induces, | |
| Ez∼D(x) [ℓ(x; z)] (Definition 2.1). In contrast, a performatively stable point is minimizing expected | |
| loss for the fixed distribution it induces (Definition 2.2). | |
| Stability is a key desideratum, ensuring that the model remains invariant under retraining. | |
| Perhaps the most natural algorithmic approach to finding such points is by repeatedly solving the | |
| risk minimization problem—a process coined repeated risk minimization (RRM) by Perdomo et al. | |
| [2020]—until a fixed point is reached. | |
| Definition 1.1 (Perdomo et al., 2020). Repeated risk minimization (RRM) refers to the procedure | |
| whereby, starting from an initial model parameterized by x0 , the following sequence of updates is | |
| performed. | |
| xt+1 = G(xt ) = argmin Ez∼D(xt ) [ℓ(x; z)]. | |
| x∈X | |
| Perdomo et al. [2020] showed that RRM is bound to converge linearly to a performatively stable | |
| point when ρ ∶= Lβ/α < 1. Intuitively, this condition requires that the sensitivity of the distribution | |
| shift L is small relative to the geometry of the loss landscape, governed by its smoothness β and | |
| strong convexity α (Section 2 contains the precise definitions). On the other hand, Perdomo et al. | |
| [2020] observed that RRM can fail to converge even when ρ = 1, which means that performative | |
| effects are marginally stronger. | |
| One might hope to circumvent this by simply increasing the regularization strength α to force the | |
| condition ρ < 1. However, such additional regularization can be destructive, potentially eliminating | |
| the meaningful equilibria. | |
| Despite the significant progress in establishing improved convergence guarantees (e.g., Khor- | |
| sandi et al., 2025, Mofakhami et al., 2023), the complexity of computing performatively stable | |
| points remains poorly understood when ρ ≥ 1. In particular, a fundamental question arises: | |
| Is the failure of RRM simply a limitation of specific retraining dynamics, or is | |
| identifying a performatively stable point intrinsically intractable in the presence of | |
| stronger performative effects? | |
| The failure of RRM—and other algorithms such as repeated gradient descent and performative | |
| gradient descent [Izzo et al., 2021]—when ρ ≥ 1 does not by itself imply intractability. Indeed, as | |
| we show, there are efficient algorithms even when ρ is slightly above 1. | |
| 1.1 Our results | |
| We characterize the computational complexity of performative stability across the spectrum of ρ. | |
| To begin with, we establish the following result. | |
| Theorem 1.2. For any small enough ϵ > 0, computing an ϵ-performatively stable point for some | |
| ρ = Lβ/α ≤ 1 + O(ϵ) is PPAD-hard. | |
| This means that computing performatively stable points is as hard as finding Nash equilibria in | |
| general-sum games [Daskalakis et al., 2009, Chen et al., 2009], which is unlikely to admit efficient | |
| algorithms. There is a basic trade off in Theorem 1.2 worth highlighting: PPAD-hardness persists | |
| even if one is content with a crude approximation ϵ = Θ(1), but that only precludes instances in | |
| which Lβ/α is some additive constant larger than 1. At the other end of the spectrum, PPAD- | |
| hardness kicks in even when Lβ/α − 1 is exponentially small, as long as the desired precision is also | |
| small enough. | |
| 2 | |
| We also show that an ϵ-performatively stable point can be computed in poly(d, log(1/ϵ)) time | |
| when ρ = 1 + Oϵ (ϵ4 ) (Theorem 3.5). This improves upon repeated risk minimization (RRM) and | |
| other natural algorithms. While RRM converges for ρ < 1, the number of iterations scales with | |
| log−1 (1/ρ) ≈ 1/1−ρ when ρ ≈ 1, which blows up when ρ approaches 1. Moreover, a recent result | |
| by Diakonikolas [2025] implies a poly(1/ϵ) algorithm when ρ ≤ 1 + Oϵ (ϵ), matching Theorem 1.2 | |
| in the order of ϵ. As a result, we find the transition from PPAD-hardness to tractability to be | |
| particularly acute. | |
| Furthermore, we establish unconditional, information-theoretic lower bounds, showing that any | |
| algorithm requires exponentially many ERM evaluations to find a performatively stable point | |
| (Corollary 3.7). This holds whether one uses repeated risk minimization or any other more so- | |
| phisticated algorithm. | |
| From a technical standpoint, our hardness results are established through simple, canonical | |
| reductions that encode any variational inequality or fixed point problem as an instance of per- | |
| formative stability (Propositions 3.1 and 3.2). In particular, we show that intractability persists | |
| even in the ostensibly simple setting comprising a quadratic loss and an affine distribution shift | |
| (Theorem 3.4). | |
| The nonexpansive regime We go on to generalize the setup of performative prediction to | |
| general norms, extending the ℓ2 contraction argument of Perdomo et al. [2020] (Section 3.2). In- | |
| terestingly, we observe that in this generalized setting, intractability barriers emerge even in the | |
| contractive regime. Specifically, we show that finding performatively stable points would imply a | |
| complexity theory breakthrough (Proposition 3.10). | |
| The role of the constraint set An important component of our reduction is the geometry of the | |
| domain. Existing hardness results for variational inequalities and fixed points typically rely on the | |
| hypercube X = [0, 1]d . However, this does not always mesh well with machine learning applications; | |
| for example, in the context of performative prediction, training a classifier constrained on the ℓ2 | |
| ball instead is perhaps more natural [Hinton et al., 2012, Goodfellow et al., 2016]. Surprisingly, the | |
| complexity of VIs and fixed points over general constraint sets has received limited attention, with | |
| some exceptions (Section 1.2). We fill this gap by showing that PPAD-hardness persists under any | |
| reasonable convex constraint set (Theorem 3.12). | |
| Strategic classification Finally, we turn to strategic classification [Hardt et al., 2016], which falls | |
| within the scope of performative prediction. We show that finding a local optimum of the perfor- | |
| mative risk—under single-label updates—is PLS-hard (Theorem 4.4); PLS captures the complexity | |
| of (presumably) hard local optimization problems such as local max-cut. This complements the | |
| NP-hardness of Hardt et al. [2016] concerning global performative optimality, and further highlights | |
| the intractability of attaining performative optimality. It shows that local search heuristics—often | |
| employed to sidestep NP-hardness—can fail to efficiently identify stable points. | |
| 1.2 Related work | |
| Following the foundational work of Perdomo et al. [2020], significant attention has been devoted to | |
| the convergence of retraining dynamics. Mendler-Dünner et al. [2020] analyzed stochastic variants | |
| of RRM, distinguishing between “greedy” and “lazy” deployment. In their terminology, greedy | |
| 3 | |
| deployment releases the new model at every step, whereas lazy deployment accumulates multiple | |
| gradient updates before releasing a new model. Zrnic et al. [2021] further refined those dynamics | |
| by studying two-timescale algorithms, showing that separating the timescales of model updates | |
| and the resulting distribution shifts can stabilize learning. Miller et al. [2021] and Izzo et al. | |
| [2021] developed derivative-free methods to optimize the performative risk, targeting optimality | |
| rather than just stability. For more recent pointers, we refer to Khorsandi et al. [2025], Mofakhami | |
| et al. [2023], and references therein. There has been some work addressing misspecification in the | |
| underlying distribution map [Xue and Sun, 2024], but our paper focuses on the standard model. | |
| Strategic classification Performative prediction encompasses the framework of strategic clas- | |
| sification [Hardt et al., 2016, Chen et al., 2018, 2020, Dong et al., 2018], where the distribution | |
| shift arises from individual agents rationally best-responding to the classifier. The performative | |
| prediction framework abstracts the game-theoretic interaction into the distribution map. | |
| For a comprehensive overview of the emerging field of performative prediction, we refer to Hardt | |
| and Mendler-Dünner [2025]. Additional related work appears in Section A. | |
| 2 Preliminaries | |
| √ | |
| Notation For x, x′ ∈ Rd , we use ⟨x, x′ ⟩ for their inner product. ∥x∥2 = ⟨x, x⟩ denotes the | |
| Euclidean norm. ∥ ⋅ ∥ denotes an arbitrary norm. X is a convex and compact subset of Rd that | |
| represents the parameter space of the decision-maker. For x ∈ X , D(x) denotes the distribution | |
| induced by x. We will use the notation Z ∶= ⋃x∈X supp(D(x)). For the sake of exposition, we | |
| sometimes write Oϵ (⋅) to denote the dependence only on the parameter ϵ. | |
| Performative prediction centers on the problem | |
| min Ez∼D(x) [ℓ(x; z)] . (1) | |
| x∈X | |
| We now formally define performative optimality and performative stability. | |
| Definition 2.1 (Performative optimality; Perdomo et al., 2020). A point x∗ ∈ X is performatively | |
| optimal if | |
| x∗ ∈ argmin Ez∼D(x) [ℓ(x; z)] . | |
| x∈X | |
| Performatively optimal points correspond to Stackelberg equilibria [Conitzer and Sandholm, | |
| 2006, von Stackelberg, 1934], as the decision-maker commits to a model, anticipating how the | |
| distribution D will shift in response. In Section 4, we introduce a local version of Definition 2.1 in | |
| the context of strategic classification. | |
| Definition 2.2 (Performative stability; Perdomo et al., 2020). A point x∗ ∈ X is performatively | |
| stable if | |
| x∗ ∈ argmin Ez∼D(x∗ ) [ℓ(x; z)] . | |
| x∈X | |
| Performatively stable points exist under mild assumptions [Perdomo et al., 2020]. They are | |
| in correspondence to Nash equilibria, as the decision-maker selects a model that is optimal for | |
| 4 | |
| the current distribution. Our complexity results leverage this connection to shed light on the | |
| complexity of performative prediction. | |
| The following assumptions are made concerning the loss function and the magnitude of the | |
| distribution shift. | |
| Assumption 2.3. Let ℓ(x; z) be the loss function and D(x) the distribution on Z induced by | |
| x ∈ X. | |
| • (strong convexity) ℓ(x; z) is α-strongly convex with respect to ∥ ⋅ ∥2 : | |
| α | |
| ℓ(x; z) ≥ ℓ(x′ ; z) + ⟨∇x ℓ(x′ ; z), x − x′ ⟩ + ∥x − x′ ∥22 | |
| 2 | |
| for any x, x′ ∈ X and z ∈ Z. | |
| • (smoothness) ℓ(x; z) is β(-jointly) smooth if | |
| ∥∇x ℓ(x; z) − ∇x ℓ(x′ ; z)∥2 ≤ β∥x − x′ ∥2 | |
| and | |
| ∥∇x ℓ(x; z) − ∇x ℓ(x; z ′ )∥2 ≤ β∥z − z ′ ∥2 | |
| for any x, x′ ∈ X and z, z ′ ∈ Z. | |
| • (sensitivity) D is L-sensitive if | |
| W1 (D(x), D(x′ )) ≤ L∥x − x′ ∥2 | |
| for any x, x′ ∈ X , where W1 denotes the Wasserstein-1 distance, or earth mover’s distance. | |
| We define ρ ∶= Lβ/α. In Section 3.2, we also generalize the setup of Assumption 2.3 to general | |
| norms. | |
| We rely on the following notion of approximation. | |
| Definition 2.4. A point x∗ ∈ X is (first-order) ϵ-performatively stable if | |
| ⟨x − x∗ , Ez∼D(x∗ ) [∇x ℓ(x∗ ; z)]⟩ ≥ −ϵ ∀x ∈ X . | |
| When the loss function is convex, the definition above coincides with Definition 2.2 (Claim B.3). | |
| In applications where the loss function is nonconvex [Li and Wai, 2024], Definition 2.4 is the natural | |
| local relaxation of Definition 2.2. Since computing (first-order) performatively stable points lies in | |
| PPAD (Corollary B.2), our hardness result establishes PPAD-completeness for that notion. | |
| Another natural way to measure the approximation error is through the fixed point gap ∥x∗ − | |
| G(x∗ )∥2 , where G is the RRM map (Definition 1.1); as we formalize in Lemmas G.1 and G.2, those | |
| notions are polynomially related. | |
| 3 Complexity of performatively stable points | |
| In this section, we characterize the complexity of performatively stable points. | |
| 5 | |
| A hard class of problems We consider the following class of performative prediction instances. | |
| 1 | |
| min {ℓ(x; z) ∶= ∥x∥22 − x⊺ z} , (2) | |
| x∈X 2 | |
| where z = g(x). (3) | |
| We assume that g is L-Lipschitz continuous, so that ∥g(x) − g(x′ )∥2 ≤ L∥x − x′ ∥2 for any x, x′ ∈ X . | |
| The function ℓ defined in (2) is 1-strongly convex in x and 1-jointly smooth (per Assumption 2.3), | |
| while the sensitivity of D(x) is L. So, ρ = L in this class. | |
| The underlying distribution above is a singleton supported on g(x). (The Wasserstein-1 distance | |
| between two point mass distributions is simply the distance between the two points.) Our reductions | |
| work more broadly for any distribution D(x) such that Ez∼D(x) z = g(x); this could be, for example, | |
| a more well-behaved Gaussian distribution. This holds because Ez∼D(x) [ℓ(x; z)] = Ez∼D(x) [ 21 ∥x∥2 − | |
| x⊺ z] = 12 ∥x∥2 − x⊺ Ez∼D(x) [z], by definition of the loss ℓ in (1). In other words, the choice of | |
| distribution does not alleviate the hardness of the problem. | |
| 3.1 Encoding VIs and fixed points | |
| We now show how a suitable choice of g allows us to encode hard optimization problems. First, we | |
| consider a variational inequality (VI) problem given by a mapping F ∶ X → Rd . An ϵ-approximate | |
| VI solution is a point x∗ ∈ X such that ⟨x − x∗ , F (x∗ )⟩ ≥ −ϵ for all x ∈ X . We observe that by | |
| selecting g ∶ x ↦ x − F (x), an ϵ-performatively stable point of (2)-(3) yields an ϵ-approximate | |
| solution to the VI problem. Furthermore, considering g ∶ x ↦ x − F (x) for a damped (rescaled) | |
| mapping F makes the Lipschitz constant of g—the sensitivity of the distribution—approach 1 | |
| while rescaling the approximation factors between the two problems. We summarize this guarantee | |
| below. | |
| Proposition 3.1 (From VIs to performative stability). For any ϵ > 0 and ϵ′ > 0, computing an ϵ′ - | |
| approximate VI solution of an L-Lipschitz mapping F reduces to computing ϵ-performatively stable | |
| points with ρ ≤ 1 + ϵϵ′ L. | |
| We instantiate and sharpen this reduction in Theorem 3.4 for the class of affine VI problems. | |
| First, we provide a similar reduction for fixed point problems. Here, we are given a continuous | |
| function T ∶ X → X and the problem is to find an ϵ-fixed point thereof. We observe that by selecting | |
| g ∶ x ↦ (1 − λ)x + λT (x) for λ = ϵ/ϵ′ , we arrive at the following theorem. | |
| Proposition 3.2 (From fixed points to performative stability). For any ϵ > 0, computing an ϵ′ - | |
| fixed point of an L-Lipschitz continuous mapping reduces to computing an ϵ-fixed point of the RRM | |
| map G (Definition 1.1) with ρ ≤ 1 + ϵϵ′ L. | |
| It is well-known that fixed points can be reduced to VIs and vice versa, but the reduction above | |
| is particularly direct. We will use it to prove query lower bounds through the result of Hirsch et al. | |
| [1989]. | |
| We now leverage Proposition 3.1 to establish PPAD-hardness for a particularly simple class of | |
| problems: the distribution shift is given by an affine function and the constraint set X is the hyper- | |
| cube. We begin by extracting a useful result from Bernasconi et al. [2024, Theorem 4.4] concerning | |
| the complexity of affine VIs on the hypercube. A closely related result was shown by Rubinstein | |
| [2015] in the context of computing approximate Nash equilibria in polymatrix, binary-action games. | |
| 6 | |
| ρ=1 ρ = 1 + Oϵ (ϵ4 ) ρ = 1 + O(ϵ) | |
| Linear convergence via RRM poly(d, log(1/ϵ)) poly(1/ϵ) Intractable (PPAD-hard) | |
| Perdomo et al. [2020] Theorem 3.5 Diakonikolas [2025] Theorem 3.4 | |
| Figure 1: The complexity landscape for computing ϵ-performatively stable points. | |
| For our purposes, it is convenient to use the lemma as given by Bernasconi et al. [2024] because | |
| of the assumed matrix bounds. For a matrix A ∈ Rd×d , we denote by ∥A∥1 its maximum absolute | |
| column sum and by ∥A∥∞ its maximum absolute | |
| √ row sum. Our proof uses the fact that the spectral | |
| norm ∥A∥2 satisfies the inequality ∥A∥2 ≤ ∥A∥1 ∥A∥∞ . | |
| Lemma 3.3 (Bernasconi et al., 2024). It is PPAD-complete to find a point x∗ ∈ [0, 1]d such that | |
| for all x ∈ [0, 1]d , | |
| ⟨x − x∗ , Ax∗ + b⟩ ≥ −ϵ′ . | |
| This holds even when ϵ′ > 0 is an absolute constant, ∥A∥1 ≤ 1, and ∥A∥∞ ≤ 1. | |
| This allows us to strengthen Proposition 3.1 by establishing PPAD-hardness with sharp con- | |
| stants and for a seemingly simple class of performative prediction instances. | |
| Theorem 3.4. Finding an ϵ-performatively stable point per Definition 2.4 is PPAD-hard even | |
| when Lβ/α ≤ 1 + ϵϵ′ for ϵ′ = 0.088/6 ≈ 0.0147. This is so even when ℓ is a quadratic objective, | |
| ℓ(x; z) = 21 ∥x − z∥22 , and D(x) is given by an affine map. | |
| The simple proof is deferred to Section G. The constant ϵ′ appearing above is obtained by | |
| combining Lemma 3.3 with the inapproximability of Deligkas et al. [2024]. It is worth noting that | |
| for general VIs on the hypercube (without the restriction to affine mappings), an approximation of | |
| even ≈ 12 is PPAD-hard [Deligkas et al., 2023]. | |
| To put Theorem 3.4 into context, Diakonikolas [2025] recently analyzed a relaxation of nonex- | |
| pansiveness, showing that an ϵ-fixed point—which yields an Oϵ (ϵ)-performatively stable point on | |
| account of Lemma G.2—can be computed in poly(1/ϵ) time even when the Lipschitz constant L of | |
| the map satisfies L ≤ 1 + ϵ/D. This means that, subject to a complexity collapse, the bound on ρ | |
| in Theorem 3.4 cannot be improved up to the factor multiplying ϵ. Taken together, we identify an | |
| acute phase transition in the complexity of the problem. | |
| Furthermore, we also establish the following result. | |
| Theorem 3.5. If ρ ≤ 1 + ϵ (per Assumption 2.3), there is a poly(d, log(1/ϵ))-time algorithm for | |
| computing an Oϵ (ϵ1/4 )-performatively stable point. | |
| The approximation we obtain holds even in terms of the RRM fixed-point gap. For the natural | |
| √ | |
| VI counterpart, the approximation would be Oϵ ( ϵ), and even Oϵ (ϵ) in terms of the Minty VI | |
| solution (Proposition D.5). | |
| Theorem 3.5 complements the result of Diakonikolas [2025]: even though we need ρ ≤ 1 + Oϵ (ϵ4 ) | |
| to get an ϵ-performatively stable point, Theorem 3.5 scales logarithmically with 1/ϵ, which is an | |
| exponential improvement. On the other hand, the result of Diakonikolas [2025] is not confined to | |
| 7 | |
| finite-dimensional Euclidean spaces. For an illustration of the different regions in terms of ρ and | |
| their complexity, we refer to Figure 1. | |
| Theorem 3.5 is established by showing how to apply the ellipsoid algorithm on a VI problem | |
| in which the mapping F is only approximately monotone—specifically, hypomonotone (Proposi- | |
| tion D.5). Our observation is that, in such problems, expected variational inequalities in the sense | |
| of Zhang et al. [2025] induce approximate VI solutions, as we formalize in Section D. | |
| An interesting open question is whether Theorem 3.5 can be improved to match the approximation- | |
| expansiveness tradeoff established by Diakonikolas [2025]. | |
| Unconditional lower bounds We next establish unconditional query complexity hardness re- | |
| sults. In the performative prediction setting, the natural query model we consider allows an al- | |
| gorithm to specify a point x ∈ X and receive the induced RRM iterate G(x). We will use the | |
| following seminal lower bound due to Hirsch et al. [1989]. | |
| Theorem 3.6 (Hirsch et al., 1989). For any d ≥ 3, any algorithm that finds an ϵ-fixed point of a | |
| Lipschitz map T ∶ X → X requires at least c(( 1ϵ − 10)L)d−2 steps, where c is an absolute constant | |
| and L is the Lipschitz constant of T (x) − x. | |
| For the class of problems given in (2)-(3), it follows that G(x) = g(x). As a result, under the | |
| reduction of Proposition 3.2, every ERM query outputs (1 − λ)x + λT (x), which reveals as much | |
| information as T (x) itself. | |
| Corollary 3.7. Computing an ϵ-fixed point of the RRM map G (Definition 1.1) even when ρ = | |
| Lβ/α ≤ 1 + Oϵ (ϵ) requires 2Ω(d) ERM queries. This holds even when ϵ is a constant. | |
| 3.2 General norms | |
| Having characterized the complexity spectrum in the Euclidean setting (Assumption 2.3), we turn | |
| to the more general setting. We extend Assumption 2.3 to general norms (Assumption C.1), and | |
| show that the contraction analysis of Perdomo et al. [2020] carries over in this setting.1 | |
| Proposition 3.8. If Lβ/α < 1 per Assumption C.1, the RRM map G (Definition 1.1) is a con- | |
| traction with respect to the norm ∥ ⋅ ∥. In particular, if x∗ is the unique fixed point, | |
| Lβ Lβ t | |
| ∥xt − x∗ ∥ ≤ ∥xt−1 − x∗ ∥ ≤ ( ) ∥x0 − x∗ ∥. | |
| α α | |
| The question now is to characterize the complexity of performatively stable points in this | |
| more general setting. The obvious algorithm that arises from Proposition 3.8 computes an ϵ- | |
| performatively stable point in a number of iterations that grows as log(1/ϵ)(1 − Lβ/α)−1 . When | |
| 1 − Lβ/α ≈ 0, this can be prohibitive. | |
| We first note that, in the regime where ϵ is not too small, this can be improved using Halpern | |
| iteration [Halpern, 1967, Lieder, 2021, Wittmann, 1992, Diakonikolas, 2020]. | |
| Corollary 3.9. If Lβ/α ≤ 1 per Assumption C.1, there is an algorithm that finds an ϵ-performatively | |
| stable point and has complexity linear in 1/ϵ. | |
| 1 | |
| With an abuse of notation we use the same symbols to denote the analogous parameters even though convexity, | |
| smoothness, and sensitivity are now measured differently. The underlying choice of norm will be clear from the | |
| context. | |
| 8 | |
| A3 | |
| Color 2 | |
| Color 1 Color 3 | |
| a⊥ | |
| 0○ | |
| b⊥ | |
| c⊥ Color 1 | |
| A1 A2 Color 3 | |
| Color 2 | |
| Figure 2: Left: Illustration of the proof of Theorem 3.12. Regions outside △A1 A2 A3 are mapped | |
| with corresponding colors. The shaded bands represents the ϵ-thickness strips used in the con- | |
| struction. Inside △A1 A2 A3 the domain forms a triangular grid with colors assigned to the vertices. | |
| Trichromatic triangles correspond to VI solutions, and are highlighted by shading. Right: Direc- | |
| tional vector mapping induced by the coloring. The directions are chosen so that any point outside | |
| △A1 A2 A3 is pushed toward the interior of the triangle. As a result, all VI solutions must lie inside | |
| △A1 A2 A3 . | |
| This is another setting in which RRM is inferior to alternative algorithms. The question that | |
| remains concerns the complexity when ϵ is exponentially small. We observe that this is as hard as | |
| a major open problem in complexity theory [Condon, 1992, Etessami et al., 2020]. | |
| Proposition 3.10. Computing an ϵ-performatively stable point even when the RRM map G (Def- | |
| inition 1.1) satisfies ∥G(x) − G(x′ )∥ < ∥x − x′ ∥ is as hard as solving a simple stochastic game | |
| (SSG). | |
| For this hardness result, it suffices to consider the ℓ∞ norm, and follows from the fact that the | |
| SSG problem reduces to finding fixed points of contractions in the ℓ∞ norm. Unlike our previous | |
| results, the precondition of Proposition 3.10 is in terms of the Lipschitz constant of G, and not the | |
| upper bound Lβ/α (per Assumption C.1). | |
| 3.3 Complexity for general convex domains | |
| While Theorem 3.4 characterizes the complexity of computing performatively stable points, it relies | |
| on prior results established with respect to a hypercube constraint set (that is, [0, 1]d ). However, | |
| this particular constraint set may not always be aligned with practical applications. For example, | |
| in modern machine learning it is often more common to impose an upper bound on the ℓ2 norm | |
| of the parameter x [Goodfellow et al., 2016, Hinton et al., 2012], which translates to an ℓ2 ball | |
| constraint set. | |
| To close this gap in the literature, we extend our hardness result to general convex sets under | |
| the mild assumption that the domain is well bounded ; this is a standard regularity condition in | |
| convex optimization [Grötschel et al., 1993]. | |
| Definition 3.11 (Well-bounded domains). A convex and compact set X is called well bounded if | |
| there exist R1 > 0 and R2 > 0 such that BR1 (0) ⊆ X ⊆ BR2 (0), where BR (0) is the Euclidean ball | |
| centered at 0 with radius R. | |
| 9 | |
| The well-bounded assumption is general and captures many common constraint sets of interest, | |
| including the hypercube and the ℓ2 ball. Our technical approach only requires that X ⊇ BR1 | |
| with respect to a two-dimensional ball, so our analysis can encompass sets that may not be fully | |
| dimensional, as is common in machine learning. Furthermore, without loss of generality, the center | |
| of the balls can be set at the origin by shifting the domain X . | |
| We establish a complexity hardness result for solving variational inequalities (VIs) over well- | |
| bounded domains. | |
| Theorem 3.12. Given a convex and compact domain X ⊂ Rd that is well bounded, an L-Lipschitz | |
| function F ∶ X → Rd , and ϵ = O(2−n ), it is PPAD-hard to find a point x∗ ∈ X such that | |
| ⟨x − x∗ , F (x∗ )⟩ ≤ ϵ ∀x ∈ X . (4) | |
| This holds even when d = 2 and L = O(1). | |
| This result is of broader interest in the complexity of variational inequalities. The requirement | |
| that ϵ is exponentially small is necessary to prove hardness in low dimensions. In stark contrast, | |
| high-precision solutions can be attained in the contractive regime since RRM exhibits linear con- | |
| vergence. | |
| Theorem 3.12 follows from constructing a polynomial-time reduction from the 2D-Sperner | |
| problem, which was shown to be PPAD-complete by Chen and Deng [2009]. Our proof proceeds by | |
| showing that, given a well-bounded domain X , one can locate an equilateral triangle △A1 A2 A3 ⊆ X , | |
| which will serve as the domain for the 2D-Sperner instance. To construct a continuous mapping | |
| F ∶ X → X from the coloring of the 2D-Sperner problem, we carefully design an arithmetic circuit | |
| that converts the coloring of a given point to vectors in Euclidean space. A key technical challenge | |
| is that the arithmetic circuit F is continuous, whereas the coloring in the 2D-Sperner problem is | |
| specified by a boolean circuit and is therefore discontinuous. As a result, F cannot exactly match | |
| the coloring everywhere in X . We address this issue by employing a sampling technique introduced | |
| by Deligkas et al. [2020] which allows us to control the error arising from this mismatch. Figure 2 | |
| illustrates the coloring and the choice of directional vectors respectively. We defer the detailed | |
| proof to Section E. | |
| We next apply our general result to the problem of computing performatively stable points. | |
| We show that, even under a general constraint set, PPAD-hardness persists for some accuracy | |
| ϵ = O(2−n ) when ρ > 1. We summarize this result below. | |
| Corollary 3.13. For any convex compact domain X that is well-bounded, finding an ϵ-performatively | |
| stable point per Definition 2.2 is PPAD-hard even when Lβ/α ≤ 1 + ϵϵ′ for some ϵ′ = O(2−n ). This | |
| is so even when ℓ is a quadratic objective, ℓ(x; z) = 12 ∥x − z∥22 . | |
| The proof is similar to Theorem 3.4, using g(x) = x + ϵϵ′ F (x), where F (x) is the operator in | |
| Theorem 3.12. | |
| Remark 3.14. By choosing ϵ < ϵ′ = O(2−n ), the expansion parameter Lβ/α can be made arbitrarily | |
| close to 1, while PPAD-hardness still persists. | |
| 4 Strategic classification | |
| As highlighted in Section 1.2, performative prediction encompasses the problem of strategic clas- | |
| sification. The complexity of computing performatively optimal points—also known as “strategic | |
| 10 | |
| maxima” in this line of work—was already shown to be NP-hard in the original paper by Hardt | |
| et al. [2016]. Two natural question arise: i) what is the complexity of local performative optimal- | |
| ity? And ii) what is the complexity of performative stability in strategic classification? Concerning | |
| the second question, the class of problems we have considered so far is no longer suitable because | |
| strategic classification is a more structured problem. Before we proceed, let us first recall the basic | |
| definition of strategic classification. | |
| Definition 4.1 (Strategic classification; Hardt et al., 2016). Strategic classification is a game played | |
| betwen the Jury and the Contestant. Let D be a distribution over a population X, c ∶ X × X → R≥0 | |
| a cost function, and h a target classifier. | |
| 1. The Jury first publishes a classifier f ∶ X → {0, 1}, which may depend on the cost function c, | |
| the distribution D, and the target classifier h. | |
| 2. The Contestant, who knows c, h, D, and f , selects a deviation ∆ ∶ X → X. | |
| The payoff to the Jury is Prx∼D [h(x) = f (∆(x))] and the payoff to the Contestant is Ex∼D [f (∆(x))− | |
| c(x, ∆(x))]. | |
| Strategic classification is commonly formulated as a Stackelberg game between the Jury and | |
| the Contestant, in which the Contestant always best-responds to the classifier published by the | |
| Jury, while the Jury seeks to maximize their utility while accounting for the strategic deviation of | |
| the Contestant. The strategic maximum is defined as follows. | |
| Definition 4.2 (Strategic maximum; Hardt et al., 2016). Give a population X, a distribution D | |
| over the population, a cost function c ∶ X × X → R≥0 , and a target classifier h, a classifier f ∗ for | |
| the Jury is said to be at strategic maximum if | |
| f ∗ ∈ argmax Pr [h(x) = f (∆(x))]. | |
| f ∶X→{0,1} x∼D | |
| Strategic local optimality Finding a global optimum in strategic classification has a wide range | |
| of applications, but is computationally intractable. In particular, Hardt et al. [2016] established | |
| NP-completeness. A natural question is to consider local search algorithms for the Jury, who can | |
| explore local moves into nearby configurations with the goal to converge to a local optimum. | |
| We begin by formally defining the notion of local moves for the Jury. Consider a finite population | |
| X with ∣X∣ = n, and a classifier f . We say that the Jury makes a local move to a nearby configuration | |
| by updating the label of a single data point. Formally, a classifier f ′ is a nearby configuration of f | |
| if there exists an index i ∈ [n] such that | |
| f ′ (X) = f (X) ⊕ ei , | |
| where ⊕ denotes the XOR operation and ei is the ith standard basis vector. We denote by N (f ) | |
| the set of all classifiers that can be reached from f with one local move. We now define the notion | |
| of strategic local optimum. | |
| Definition 4.3. Given a finite population X, a distribution D over X, a cost function c, and a | |
| target classifier h, a classifier f ∗ is said to be at strategic local optimum if | |
| Pr [h(x) = f ∗ (∆(x))] = max Pr [h(x) = f (∆(x))]. | |
| x∼D f ∈N (f ∗ ) x∼D | |
| 11 | |
| Prob. ∝ ∑u′ ∈N (u) w(u,u′ ) Prob. ∝ ∑v′ ∈N (v) w(v,v′ ) | |
| xu− xv − | |
| h=0 h=0 | |
| 0.8 0.8 | |
| Strategic move | |
| if f (xu− ) = 1 | |
| x(u,v)+ | |
| f (x(u,v)+ ) = 0 Prob. ∝ 2w(u,v) | |
| h=1 | |
| Strategic move | |
| 0.8 if f (x(u,v)+ ) = 1 | |
| x(u,v)− | |
| f (x(u,v)− ) = 0 Prob. ∝ 2w(u,v) + 1 | |
| h=0 | |
| Figure 3: Our basic edge gadget for edge (u, v). The Jury would like to classify x(u,v)+ as 1, but | |
| x(u,v)− would then strategically deviate to x(u,v)+ . This forces the Jury to pick a classifier such that | |
| f (x(u,v)+ ) = 0 = f (x(u,v)− ). Furthermore, if the Jury switches the label of xu− from 0 to 1, all edges | |
| incident to u in the graph that were previously classified as 0 can profitably deviate to xu− . The | |
| change in the Jury’s utility reflects the change in the weight of the cut induced by f . | |
| We proceed to state the main result of this section. | |
| Theorem 4.4. Given a finite population X, a distribution D over X, a cost function c, and a | |
| target classifier h, it is PLS-hard to find a strategic local optimum as in Definition 4.3. This result | |
| holds even when c is a metric and the target classifier h is provided explicitly to the algorithm. | |
| Theorem 4.4 shows that, unless there is a collapse in the complexity hierarchy (specifically, | |
| P = PLS), finding even a local optimum in strategic classification cannot be achieved in polynomial | |
| time. | |
| The proof of Theorem 4.4 takes an instance of LocalMaxCut problem, which was shown to | |
| be PLS-complete by Schäffer and Yannakakis [1991], and constructs a polynomial-time reduction | |
| to the problem of finding a strategic local optimum. | |
| In particular, let G = (V, E, w) be a weighted undirected graph with edge weights w(u,v) ≥ 0 | |
| for any edge (u, v) ∈ E. We construct an instance of strategic classification consisting of a finite | |
| population X and a non-uniform distribution D over X. For each vertex v ∈ V, we introduce a point | |
| xv− with label h(xv− ) = 0. For each edge (u, v) ∈ E, we introduce two points x(u,v)+ and x(u,v)− | |
| with labels h(x(u,v)+ ) = 1 and h(x(u,v)− ) = 0. We design the cost function c with specific values | |
| such that the admissible deviations of the Contestant satisfy the following: the point x(u,v)− may | |
| deviate only to x(u,v)+ , and the vertex points xu− and xv− may deviate only to x(u,v)+ . Figure 3 | |
| illustrates the gadget for a simple graph with two vertices and one edge, where the dashed edges | |
| represent admissible deviations for the Contestant. | |
| The first observation is that for any classifier f ∗ that is at a strategic optimum, f ∗ (x(u,v)− ) = 0 | |
| and f ∗ (x(u,v)+ ) = 0. This follows from the fact that the distribution D assigns higher probability | |
| to x(u,v)− than to x(u,v)+ . As a result, any classifier that labels either x(u,v)+ or x(u,v)− as positive | |
| will incur a net loss due to misclassifying x(u,v)− . | |
| The result is that the Jury will only label vertex points xv− as positive and improve their utility | |
| through the deviation of x(u,v)+ to the corresponding vertex points xu− or xv− . Through a careful | |
| 12 | |
| design of the distribution weights, we show that any strategically local optimal classifier f ∗ induces | |
| a cut of the original graph G: vertices v ∈ V with f ∗ (xv− ) = 0 lie on one side of the cut, while | |
| vertices u ∈ V with f ∗ (xu− ) = 1 lie on the other. Moreover, the strategic local optimality of f ∗ | |
| ensures the local optimality of the induced cut. We defer the full proof to Section F. | |
| Notably, our construction in Theorem 4.4 based on MaxCut also yields an alternative proof | |
| that finding a global strategic optimum is NP-complete [Hardt et al., 2016]. | |
| Performative stability with endogenous costs Moreover, we establish hardness for com- | |
| puting a Nash equilibrium—which translates to a performatively stable point—in an extension | |
| of Definition 4.1 in which the Jury can also affect the cost incurred by deviating. This extension | |
| captures the fact that, in reality, decision-makers often act as regulators who go beyond merely | |
| classifying [Alhanouti et al., 2025]; they actively dictate the cost structure by imposing sanctions | |
| and penalizing more certain deviation types, for example through audits [Estornell et al., 2021]. We | |
| refer to this setting as strategic classification with endogenous costs (Definition G.3). Compared | |
| to Definition 4.1, our definition also posits that the Jury is constrained to select a classifier from a | |
| specified set of classifiers, and similarly for the Contestant. We find that this class of problems is | |
| rich enough to PPAD-hard problems. | |
| Proposition 4.5. Computing a performatively stable point in strategic classification with endoge- | |
| nous costs is PPAD-hard. | |
| The proof is based on a reduction from a win-loss two-player general-sum game (A, B) [Abbott | |
| et al., 2005]. We associate each column to a separate classifier and each row to a point drawn | |
| uniformly from X. Each classifier fj labels the points in accordance with B∶,j . The target classifier | |
| is taken to be h(x) = 0 for all x ∈ X. The Contestant can pick any constant deviation, and | |
| the payoff matrix A is encoded through the costs, making them the dominant component of the | |
| Contestant’s utility. The detailed argument is deferred to Section G. | |
| This reduction heavily relies on the presence of endogenous costs. The complexity of computing | |
| performatively stable points based on the more common Definition 4.1 remains an open problem. | |
| Because of the particular payoff structure, we suspect that the latter problem may be easier. | |
| 5 Conclusion | |
| We have established a sharp computational phase transition for performative stability, showing | |
| that while slight expansiveness is tractable, the problem quickly becomes PPAD-hard. We also | |
| characterized the complexity of computing local strategic maxima in strategic classification. An | |
| important question that arises from our results is to characterize the complexity of computing per- | |
| formatively stable points in strategic classification per Definition 4.1. Another interesting avenue | |
| for future research is to close the gap between the expansiveness tolerance of our ellipsoid-based | |
| approach (Theorem 3.5), the recent result of Diakonikolas [2025], and the PPAD-hardness estab- | |
| lished in Theorem 3.4, thereby refining the complexity landscape that emerged from our paper | |
| (Figure 1). | |
| 13 | |
| Acknowledgments | |
| Ioannis Panageas is supported by NSF grant CCF- 2454115. Tuomas Sandholm is supported by NIH | |
| award A240108S001, the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, and National | |
| Science Foundation grant RI-2312342. | |
| References | |
| T. Abbott, D. Kane, and P. Valiant. On the complexity of two-player win-lose games. In Symposium | |
| on Foundations of Computer Science (FOCS), 2005. | |
| Y. Alber, D. Butnariu, and I. Ryazantseva. Regularization and resolution of monotone variational | |
| inequalities with operators given by hypomonotone approximations. Journal of Nonlinear and | |
| Convex Analysis, 6(1):23, 2005. | |
| S. Alhanouti, G. Bayraksan, and P. Naghizadeh. Robust strategic classification under decision- | |
| dependent cost uncertainty. In NeurIPS 2025 Workshop MLxOR: Mathematical Foundations | |
| and Operational Integration of Machine Learning for Uncertainty-Aware Decision-Making, 2025. | |
| K. Alomar and T. Chavdarova. On the hypomonotone class of variational inequalities. | |
| arXiv:2410.09182, 2024. | |
| I. Attias, Y. Dagan, C. Daskalakis, R. Yao, and M. Zampetakis. Fixed point computation: Beating | |
| brute force with smoothed analysis. arXiv:2501.10884, 2025. | |
| M. Bernasconi, M. Castiglioni, A. Celli, and G. Farina. On the role of constraints in the complexity | |
| of min-max optimization. arXiv:2411.03248, 2024. | |
| X. Chen and X. Deng. On the complexity of 2d discrete fixed point problem. Theoretical Computer | |
| Science, 2009. Automata, Languages and Programming (ICALP). | |
| X. Chen, X. Deng, and S. Teng. Settling the complexity of computing two-player Nash equilibria. | |
| Journal of the ACM, 56(3):14:1–14:57, 2009. | |
| Y. Chen, C. Podimata, A. D. Procaccia, and N. Shah. Strategyproof linear regression in high | |
| dimensions. In Conference on Economics and Computation (EC), 2018. | |
| Y. Chen, Y. Liu, and C. Podimata. Learning strategy-aware linear classifiers. Neural Information | |
| Processing Systems (NeurIPS), 2020. | |
| A. Condon. The complexity of stochastic games. Information and Computation, 96(2):203–224, | |
| 1992. | |
| V. Conitzer and T. Sandholm. Computing the optimal strategy to commit to. In Conference on | |
| Electronic Commerce (EC), 2006. | |
| C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash | |
| equilibrium. SIAM J. Comput., 39(1):195–259, 2009. | |
| 14 | |
| A. Deligkas, J. Fearnley, and R. Savani. Tree Polymatrix Games Are PPAD-Hard. In International | |
| Colloquium on Automata, Languages, and Programming (ICALP), 2020. | |
| A. Deligkas, J. Fearnley, A. Hollender, and T. Melissourgos. Tight inapproximability for graphical | |
| games. In Conference on Artificial Intelligence (AAAI), 2023. | |
| A. Deligkas, J. Fearnley, A. Hollender, and T. Melissourgos. Pure-circuit: Tight inapproximability | |
| for PPAD. Journal of the ACM, 2024. | |
| J. Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and | |
| strong solutions to variational inequalities. In Conference on Learning Theory (COLT), 2020. | |
| J. Diakonikolas. Pushing the complexity boundaries of fixed-point equations: Adaptation to con- | |
| traction and controlled expansion. arXiv:2506.17698, 2025. | |
| J. Dong, A. Roth, Z. Schutzman, B. Waggoner, and Z. S. Wu. Strategic classification from revealed | |
| preferences. In Economics and Computation (EC), 2018. | |
| D. Drusvyatskiy and L. Xiao. Stochastic optimization with decision-dependent distributions. Math- | |
| ematics of Operations Research, 48(2):954–998, 2023. | |
| A. Estornell, S. Das, and Y. Vorobeychik. Incentivizing truthfulness through audits in strategic | |
| classification. In Conference on Artificial Intelligence (AAAI), 2021. | |
| K. Etessami, C. H. Papadimitriou, A. Rubinstein, and M. Yannakakis. Tarski’s theorem, super- | |
| modular games, and the complexity of equilibria. In Proceedings of the 11th Innovations in | |
| Theoretical Computer Science Conference (ITCS), 2020. | |
| A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure Nash equilibria. In | |
| Symposium on Theory of Computing (STOC), 2004. | |
| J. Fearnley, P. Goldberg, A. Hollender, and R. Savani. The complexity of gradient descent: CLS | |
| = PPAD ∩ PLS. J. ACM, 70(1):7:1–7:74, 2023. | |
| A. Góis, M. Mofakhami, F. P. Santos, G. Gidel, and S. Lacoste-Julien. Performative prediction on | |
| games and mechanism design. In Conference on Artificial Intelligence and Statistics (AISTATS), | |
| 2025. | |
| I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016. | |
| M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. | |
| Springer-Verlag, Berlin, 2nd edition, 1993. | |
| B. Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, | |
| 73(6):957–961, 1967. | |
| M. Hardt and C. Mendler-Dünner. Performative prediction: Past and future. Statistical Science, | |
| 40(3):417–436, 2025. | |
| M. Hardt, N. Megiddo, C. Papadimitriou, and M. Wootters. Strategic classification. In Innovations | |
| in Theoretical Computer Science (ITCS), 2016. | |
| 15 | |
| G. E. Hinton, N. Srivastava, A. Krizhevsky, I. Sutskever, and R. R. Salakhutdinov. Improving | |
| neural networks by preventing co-adaptation of feature detectors. arXiv:1207.0580, 2012. | |
| M. D. Hirsch, C. H. Papadimitriou, and S. A. Vavasis. Exponential lower bounds for finding | |
| Brouwer fix points. Journal of Complexity, 5(4):379–416, 1989. | |
| Z. Huang, L. Khachiyan, and K. Sikorski. Approximating fixed points of weakly contracting map- | |
| pings. Journal of Complexity, 15(2):200–213, 1999. | |
| A. N. Iusem, T. Pennanen, and B. F. Svaiter. Inexact variants of the proximal point algorithm | |
| without monotonicity. SIAM Journal on Optimization, 13(4):1080–1097, 2003. | |
| Z. Izzo, L. Ying, and J. Zou. How to learn when data reacts to your model: Performative gradient | |
| descent. In International Conference on Machine Learning (ICML), 2021. | |
| P. Khorsandi, R. Gupta, M. Mofakhami, S. Lacoste-Julien, and G. Gidel. Tight lower bounds | |
| and improved convergence in performative prediction. In Neural Information Processing Systems | |
| (NeurIPS), 2025. | |
| S. Levine, A. Kumar, G. Tucker, and J. Fu. Offline reinforcement learning: Tutorial, review, and | |
| perspectives on open problems. arXiv:2005.01643, 2020. | |
| Q. Li and H.-T. Wai. Stochastic optimization schemes for performative prediction with nonconvex | |
| loss. In Neural Information Processing Systems (NeurIPS), 2024. | |
| F. Lieder. On the convergence rate of the Halpern-iteration. Optimization Letters, 15(2):405–418, | |
| 2021. | |
| D. MacKenzie. An engine, not a camera: How financial models shape markets. Mit Press, 2008. | |
| R. Mehta. Constant rank bimatrix games are PPAD-hard. In Symposium on Theory of Computing | |
| (STOC), 2014. | |
| C. Mendler-Dünner, J. C. Perdomo, T. Zrnic, and M. Hardt. Stochastic optimization for perfor- | |
| mative prediction. In Neural Information Processing Systems (NeurIPS), 2020. | |
| J. Miller, J. Perdomo, and M. Hardt. Outside the echo chamber: Optimizing the performative risk. | |
| In International Conference on Machine Learning (ICML), 2021. | |
| M. Mofakhami, I. Mitliagkas, and G. Gidel. Performative prediction with neural networks. In | |
| International Conference on Artificial Intelligence and Statistics (AISTATS), 2023. | |
| A. Narang, E. Faulkner, D. Drusvyatskiy, L. Ratliff, and M. Fazel. Multiplayer performative | |
| prediction: Learning in decision-dependent games. In International Conference on Artificial | |
| Intelligence and Statistics (AISTATS), 2023. | |
| C. Papadimitriou. On graph-theoretic lemmata and complexity classes. In Symposium on Founda- | |
| tions of Computer Science (FOCS), 1990. | |
| C. H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of | |
| existence. Journal of Computer and System Sciences, 48(3):498–532, 1994. | |
| 16 | |
| J. C. Perdomo, T. Zrnic, C. Mendler-Dünner, and M. Hardt. Performative prediction. In Interna- | |
| tional Conference on Machine Learning (ICML), 2020. | |
| G. Piliouras and F.-Y. Yu. Multi-agent performative prediction: From global stability and opti- | |
| mality to chaos. In Economics and Computation (EC), 2022. | |
| A. Rubinstein. Inapproximability of Nash equilibrium. In Symposium on Theory of Computing | |
| (STOC), 2015. | |
| A. A. Schäffer and M. Yannakakis. Simple local search problems that are hard to solve. SIAM | |
| Journal on Computing, 20(1):56–87, 1991. | |
| K. Sikorski, C. Tsay, and H. Woźniakowski. An ellipsoid algorithm for the computation of fixed | |
| points. Journal of Complexity, 9(1):181–200, 1993. | |
| H. von Stackelberg. Marktform und Gleichgewicht. Springer, Vienna, 1934. English translation: | |
| Market Structure and Equilibrium, 2011, Springer. | |
| R. Wittmann. Approximation of fixed points of nonexpansive mappings. Archiv der Mathematik, | |
| 58(5):486–491, 1992. | |
| S. Xue and Y. Sun. Distributionally robust performative prediction. Neural Information Processing | |
| Systems (NeurIPS), 2024. | |
| B. H. Zhang, I. Anagnostides, E. Tewolde, R. E. Berker, G. Farina, V. Conitzer, and T. Sandholm. | |
| Expected variational inequalities. In International Conference on Machine Learning (ICML), | |
| 2025. | |
| T. Zrnic, E. Mazumdar, S. S. Sastry, and M. I. Jordan. Who leads and who follows in strategic | |
| classification? In Neural Information Processing Systems (NeurIPS), 2021. | |
| 17 | |
| A Further related work | |
| This section highlights additional related research. | |
| Multiagent performative prediction While the original framework of Perdomo et al. [2020] | |
| considers a single decision-maker, many real-world applications involve multiple agents with differ- | |
| ent objectives. In such settings, the underlying distribution can depend on the joint deployment of | |
| all agents, giving rise to more complex distribution shifts. Piliouras and Yu [2022] formalized this | |
| as multi-agent performative prediction, and showed that standard retraining dynamics can lead to | |
| complex behaviors, ranging from global stability to chaos. Performative prediction in multi-player | |
| settings has since received considerable attention [Narang et al., 2023, Góis et al., 2025]. Although | |
| we draw upon techniques from algorithmic game theory, our results pertain to the single-agent | |
| setting. | |
| Drusvyatskiy and Xiao [2023] analyze performative stability through the lens of stochastic | |
| optimization with decision-dependent distributions, applying proximal-point methods and extra- | |
| gradient algorithms in performative prediction. From a broader standpoint, similar dynamic feed- | |
| back issues are commonplace in reinforcement learning and robotics, where the act of learning | |
| changes the environment [Levine et al., 2020]. | |
| Complexity theory PPAD was introduced by Papadimitriou [1994] and was famously shown to | |
| characterize the complexity of Nash equilibria in two-player general-sum games [Daskalakis et al., | |
| 2009, Chen et al., 2009]. Our PPAD-hardness proof for general convex sets leverages certain tools | |
| developed by Mehta [2014] and Deligkas et al. [2020]. As we highlighted earlier, much of the work | |
| in the complexity of fixed points and variational inequalities has focused on the case where the | |
| constraint set is the hypercube. A notable recent exception is the paper of Attias et al. [2025], | |
| which proves exponential lower bounds when the constraint set is the ℓ2 ball. | |
| PLS was introduced by Schäffer and Yannakakis [1991] to characterize the complexity of (pre- | |
| sumably) hard local optimization problems, such as max-cut under the so-called flip neighborhood. | |
| It is also known to characterize the complexity of pure Nash equilibria in multi-player potential | |
| games [Fabrikant et al., 2004]. As a result, our results imply a polynomial-time equivalence between | |
| the complexity of local performative optimality and pure Nash equilibria in potential games. | |
| B First-order performative stability | |
| In this section, we examine the notion of first-order approximate performative stability, which will | |
| be relevant for analyzing the computational complexity of finding performative stable points. We | |
| note that computing a performatively stable point can be viewed as a fixed point computation | |
| problem (Lemma G.2). Under mild assumptions on the induced distribution D(⋅), if the objective | |
| function ℓ(x; z) is convex in x for all z and jointly continuous in (x, z), a performatively stable | |
| point is guaranteed to exist [Perdomo et al., 2020]. However, when the objective function ℓ(x; z) | |
| is nonconvex in x, the argmin operator in Definition 2.2 may not be efficiently computable. To | |
| address this issue, we consider an alternative definition, which we restate below. | |
| Definition B.1 (Performative stability). A point x∗ ∈ X is (first-order) performatively stable if | |
| for all x ∈ X , it holds that | |
| ⟨x − x∗ , Ez∼D(x∗ ) [∇x ℓ(x∗ ; z)]⟩ ≥ 0. | |
| 18 | |
| By virtue of existing complexity results pertaining to variational inequalities, computing a first- | |
| order performatively stable point lies in PPAD under mild assumptions on the representation of X , | |
| D, and ℓ. This complements Theorem 3.4. | |
| Corollary B.2. Computing an ϵ-performatively stable point is in PPAD. | |
| As we now show, when ℓ(x; z) is convex in x for all z, the notion of first-order performative | |
| stability coincides with the notion of performative stability per Definition 2.2. | |
| Claim B.3. If ℓ(x; z) is convex in x for any z, x∗ ∈ X is a performatively stable point if and only | |
| if x∗ is a first-order performatively stable point. | |
| Proof. Let x∗ ∈ X be a first-order performatively stable point, since ℓ(x; z) is convex in x, for any | |
| x′ ∈ X , we have | |
| Ez∼D(x∗ ) [ℓ(x′ ; z)] − Ez∼D(x∗ ) [ℓ(x∗ ; z)] ≥ Ez∼D(x∗ ) [⟨x′ − x∗ , ∇x ℓ(x∗ ; z)⟩] | |
| = ⟨x′ − x∗ , Ez∼D(x∗ ) [∇x ℓ(x∗ ; z)]⟩ (5) | |
| ≥ 0, (6) | |
| where in (6) we use the definition of first-order performative stability. On the other hand, suppose | |
| x∗ ∈ X is a performatively stable point, for any x′ ∈ X and any α ∈ (0, 1], it holds that | |
| Ez∼D(x∗ ) [ℓ(x∗ ; z)] ≤ Ez∼D(x∗ ) [ℓ(x∗ + α(x′ − x∗ ); z)] . | |
| By Taylor’s theorem | |
| Ez∼D(x∗ ) [ℓ(x∗ + α(x′ − x∗ ); z)] − Ez∼D(x∗ ) [ℓ(x∗ ; z)] = α ⟨x′ − x∗ , Ez∼D(x∗ ) [∇x ℓ(x∗ ; z)]⟩ + o(α). | |
| If ⟨x′ − x, Ez∼D(x∗ ) [∇x ℓ(x∗ ; z)]⟩ < 0, it would imply that for a sufficiently small α > 0, we have | |
| Ez∼D(x∗ ) [ℓ(x∗ + α(x′ − x∗ ); z)] − Ez∼D(x∗ ) [ℓ(x∗ ; z)] < 0, contradicting the fact that x∗ is a per- | |
| formatively stable point per Definition 2.2. The proof is complete. | |
| C Contraction for general norms | |
| This section generalizes the contraction proof of Perdomo et al. [2020] from the ∥ ⋅ ∥2 norm to | |
| arbitrary norms. In particular, we adapt Assumption 2.3 as follows. | |
| Assumption C.1. Let ℓ(x; z) be the loss function and D(x) the distribution on Z induced by | |
| x ∈ X. | |
| • (strong convexity) ℓ(x; z) is α-strongly convex with respect to ∥ ⋅ ∥: | |
| α | |
| ℓ(x; z) ≥ ℓ(x′ ; z) + ⟨∇x ℓ(x′ ; z), x − x′ ⟩ + ∥x − x′ ∥2 | |
| 2 | |
| ′ | |
| for any x, x ∈ X and z ∈ Z. | |
| • (smoothness) ℓ(x; z) is β(-jointly) smooth if | |
| ∥∇x ℓ(x; z) − ∇x ℓ(x′ ; z)∥∗ ≤ β∥x − x′ ∥ | |
| and | |
| ∥∇x ℓ(x; z) − ∇x ℓ(x; z ′ )∥∗ ≤ β∥z − z ′ ∥ | |
| for any x, x′ ∈ X and z, z ′ ∈ Z. | |
| 19 | |
| • (sensitivity) D is L-sensitive if | |
| W1 (D(x), D(x′ )) ≤ L∥x − x′ ∥ | |
| for any x, x′ ∈ X , where W1 denotes the Wasserstein-1 distance, or earth mover’s distance. | |
| Above, we denote by ∥ ⋅ ∥∗ the dual norm of ∥ ⋅ ∥. We point out that the contraction argument | |
| of Perdomo et al. [2020] readily carries over under Assumption C.1. | |
| Proposition 3.8. If Lβ/α < 1 per Assumption C.1, the RRM map G (Definition 1.1) is a con- | |
| traction with respect to the norm ∥ ⋅ ∥. In particular, if x∗ is the unique fixed point, | |
| Lβ Lβ t | |
| ∥xt − x∗ ∥ ≤ ∥xt−1 − x∗ ∥ ≤ ( ) ∥x0 − x∗ ∥. | |
| α α | |
| Proof. Let x, x′ ∈ X , f (y) = Ez∼D(x) ℓ(y; z), and f ′ (y) = Ez∼D(x′ ) ℓ(y; z). Taking the expectation | |
| over z ∼ D(x), it follows that f (y) is α-strongly convex with respect to ∥ ⋅ ∥. Thus, | |
| α | |
| f (G(x)) ≥ f (G(x′ )) + ⟨G(x) − G(x′ ), ∇f (G(x′ ))⟩ + ∥G(x) − G(x′ )∥2 , (7) | |
| 2 | |
| where G is the RRM mapping (Definition 1.1). Since G(x) is, by definition, the unique minimizer | |
| of f , we also have ⟨G(x′ ) − G(x), ∇f (G(x))⟩ ≥ 0 by the first-order optimality condition. In turn, | |
| this implies | |
| α | |
| f (G(x′ )) ≥ f (G(x)) + ∥G(x) − G(x′ )∥2 . (8) | |
| 2 | |
| Combining (7) and (8), we have | |
| ⟨G(x′ ) − G(x), ∇f (G(x′ ))⟩ ≥ α∥G(x) − G(x′ )∥2 . (9) | |
| Furthermore, ⟨G(x′ ) − G(x), ∇ℓ(G(x′ ); z)⟩ is (∥G(x′ ) − G(x)∥β)-Lipschitz continuous in z since | |
| ∣⟨G(x′ ) − G(x), ∇ℓ(G(x′ ); z)⟩ − ⟨G(x′ ) − G(x), ∇ℓ(G(x′ ); z ′ )⟩∣ | |
| ≤ ∥G(x′ ) − G(x)∥∥∇ℓ(G(x′ ); z) − ∇ℓ(G(x′ ); z ′ )∥∗ | |
| ≤ β∥G(x′ ) − G(x)∥, | |
| by β-joint smoothness. Now, for the distribution map D(⋅), Kantorovich-Rubinstein duality yields | |
| ∣Ez∼D(x) g(z) − EZ∼D(x′ ) g(z)∣ ≤ L∥x − x′ ∥ ∀g 1-Lipschitz. | |
| As a result, | |
| ⟨G(x) − G(x′ ), ∇f (G(x′ ))⟩ − ⟨G(x) − G(x′ ), ∇f ′ (G(x′ ))⟩ ≥ −Lβ∥G(x′ ) − G(x)∥∥x − x′ ∥. | |
| By the first-order optimality condition, it also follows that ⟨G(x) − G(x′ ), ∇f ′ (G(x′ ))⟩ ≥ 0 since | |
| G(x′ ) is the minimizer of f ′ . So, | |
| ⟨G(x) − G(x′ ), ∇f (G(x′ ))⟩ ≥ −Lβ∥G(x′ ) − G(x)∥∥x − x′ ∥. (10) | |
| Combining (9) and (10), we conclude that | |
| Lβ | |
| Lβ∥G(x′ ) − G(x)∥∥x − x′ ∥ ≥ α∥G(x) − G(x′ )∥2 Ô⇒ ∥G(x) − G(x′ )∥ ≤ ∥x − x′ ∥. | |
| α | |
| In other words, if Lβ/α < 1, G is a contraction with respect to the norm ∥ ⋅ ∥, as claimed. | |
| Similar extensions are possible for other algorithms beyond repeated risk minimization, such as | |
| repeated gradient descent. | |
| 20 | |
| D Ellipsoid for Euclidean expansive mappings | |
| A well-known result in optimization is that there is a polynomial-time algorithm for computing | |
| fixed points of nonexpansive mappings with respect to the ℓ2 norm [Huang et al., 1999, Sikorski | |
| et al., 1993]; the complexity of this problem is a major open question for more general norms. In | |
| particular, for mappings that are contracting with respect to the ℓ2 norm, there is an algorithm | |
| whose complexity does not depend on the contraction parameter. In the setting of performative | |
| prediction, we begin by observing that this can be used to obtain a significant improvement in the | |
| setting where βL/α ≈ 1. The number of iterations needed to reach an approximate fixed point under | |
| repeated risk minimization is proportional to log(1/ϵ) α1−1 in the regime where βL/α ≈ 1, thereby | |
| βL | |
| blowing up. | |
| Theorem D.1 (Sikorski et al., 1993). Consider a continuous mapping T ∶ X → X , where X is a | |
| subset of the d-dimensional Euclidean space, that is nonexpansive with respect to the ℓ2 norm; that | |
| is, ∥T (x) − T (x′ )∥2 ≤ ∥x − x′ ∥2 for any x, x′ ∈ X . Then there is a poly(d, log(1/ϵ))-time algorithm | |
| that computes an ϵ-fixed point of T . | |
| We provide the simple proof below, as we will use a similar bound in our extension. | |
| Proof of Theorem D.1. We will prove that the operator F ∶ x − T (x) is monotone. That is, ⟨F (x) − | |
| F (x′ ), x − x′ ⟩ ≥ 0 for any x, x′ ∈ X . Indeed, we write | |
| 1 | |
| ⟨F (x) − F (x′ ), x − x′ ⟩ = (∥x − x′ ∥22 − ∥T (x) − T (x′ )∥22 + ∥x − T (x) − x′ + T (x′ )∥22 ) ≥ 0 (11) | |
| 2 | |
| since ∥x − x′ ∥2 ≥ ∥T (x) − T (x′ )∥2 and ∥ ⋅ ∥2 ≥ 0. Now, let x be an ϵ-approximate VI solution | |
| with respect to F , which means that ⟨x′ − x, F (x)⟩ ≥ −ϵ for any x′ ∈ X . In particular, setting | |
| x′ = T (x) yields ⟨T (x) − x, x − T (x)⟩ ≥ −ϵ, or −∥x − T (x)∥22 ≥ −ϵ, which is to say that x is a | |
| √ | |
| ϵ-fixed point of T . Moreover, an ϵ-approximate VI solution with respect to F can be computed | |
| in time poly(d, log(1/ϵ)) since F is monotone. This completes the proof. | |
| There is also a more direct argument that does not go through the monotonicity of the gap | |
| function. In particular, it is possible to develop a separation oracle by relying on the fact that T | |
| is nonexpansive: for any point xk ∈ X , first test whether T (xk ) = xk . If not, the key observation is | |
| that gk = xk − T (xk ) serves as a separating hyperplane. This is so because ⟨xk − x, gk ⟩ ≥ 0 for any | |
| x ∈ X that is a fixed point of T ; since ⟨xk − x, gk ⟩ = ⟨xk − x, F (xk )⟩ = ⟨xk − x, F (xk ) − F (x)⟩ ≥ 0 | |
| by (11). | |
| Corollary D.2. If ρ = Lβ/α ≤ 1 (per Assumption 2.3), there is a poly(d, log(1/ϵ))-time algorithm | |
| for computing an ϵ-performatively stable point. | |
| To put this into better context, it is important to point out that repeated risk minimization | |
| can fail when ρ = 1. For completeness, we include the simple example below. | |
| Example D.3 (Cycling dynamics at the threshold). Consider a one-dimensional setting where X is | |
| centrally symmetric and the loss is the simple quadratic objective ℓ(x; z) = 21 ∥x−z∥2 . This function | |
| is 1-jointly smooth and 1-strongly convex (β = α = 1). Suppose further that the distribution D(x) | |
| is a point mass supported on z = g(x) ∶= −x. The sensitivity of this map is L = 1, resulting in | |
| ρ = Lβ/α = 1. | |
| 21 | |
| The repeated risk minimization (RRM) update at step t minimizes the loss on the distribution | |
| induced by the current iterate xt . Since the distribution is supported on z = −xt , the update | |
| becomes: | |
| 1 | |
| xt+1 = argmin ∥x − (−xt )∥2 = −xt . (12) | |
| x∈X 2 | |
| Starting from any initialization x0 ≠ 0, the algorithm oscillates indefinitely between x0 and −x0 , | |
| failing to converge to the unique performatively stable point x∗ = 0. | |
| Extension to expansive mappings Interestingly, we observe that Theorem D.1 can be ex- | |
| tended when T can be marginally expansive. Let us first present an approach that works for | |
| monotone operators, and we shall then relax the monotonicity assumption. We rely on the notion | |
| of an expected variational inequality (EVI) [Zhang et al., 2025]. In particular, an ϵ-EVI solution | |
| µ ∈ ∆(X ) satisfies | |
| Ex∼µ [⟨F (x), x − x′ ⟩] ≤ ϵ ∀x′ ∈ X . (13) | |
| Zhang et al. [2025] gave a poly(d, log(1/ϵ)) for computing an ϵ-EVI solution. We will first argue | |
| that, for monotone operators, the mean of the distribution x = Ex∼µ [x] is an ϵ-approximate solution | |
| to the Minty VI problem: | |
| ⟨F (x′ ), x′ − x⟩ ≥ −ϵ ∀x′ ∈ X . (14) | |
| Indeed, starting from (13) and using monotonicity, we have that for any x′ ∈ X , | |
| ϵ ≥ Ex∼µ [⟨F (x), x − x′ ⟩] | |
| ≥ Ex∼µ [⟨F (x′ ), x − x′ ⟩] | |
| = ⟨F (x′ ), Ex∼µ [x] − x′ ⟩ | |
| = ⟨F (x′ ), x − x′ ⟩. | |
| Rearranging, this establishes (14). Finally, to go from an ϵ-MVI solution to an approximate VI | |
| solution, we use the following standard lemma. | |
| Lemma D.4 (Relation between ϵ-MVI and SVI). Let F ∶ X → Rd be an operator that is L-Lipschitz | |
| √ | |
| continuous. If x∗ ∈ X is an ϵ-approximate MVI solution, then x∗ is an Oϵ ( ϵ)-approximate | |
| (Stampacchia) VI solution. Specifically, if D is the ℓ2 diameter of X , | |
| √ | |
| ⟨F (x∗ ), x − x∗ ⟩ ≥ −2D Lϵ ∀x ∈ X . (15) | |
| Proof. Let x ∈ X be an arbitrary target point. For any δ ∈ (0, 1], we define the interpolation point | |
| x′ = x∗ + δ(x − x∗ ) ∈ X . Using the fact that x∗ is an ϵ-MVI solution, | |
| ϵ | |
| δ⟨F (x′ ), x − x∗ ⟩ ≥ −ϵ Ô⇒ ⟨F (x′ ), x − x∗ ⟩ ≥ − . | |
| δ | |
| 22 | |
| We now relate F (x′ ) to F (x∗ ) using the Lipschitz continuity of F : | |
| ⟨F (x∗ ), x − x∗ ⟩ = ⟨F (x′ ), x − x∗ ⟩ + ⟨F (x∗ ) − F (x′ ), x − x∗ ⟩ | |
| ϵ | |
| ≥ − − ∥F (x∗ ) − F (x′ )∥2 ∥x − x∗ ∥2 | |
| δ | |
| ϵ | |
| ≥ − − L∥x∗ − x′ ∥2 ∥x − x∗ ∥2 | |
| δ | |
| ϵ | |
| = − − Lδ∥x − x∗ ∥22 | |
| δ | |
| ϵ | |
| ≥ − − LδD2 . | |
| δ | |
| The claim follows by picking δ optimally. | |
| We now extend this approach under hypomonotonicity [Iusem et al., 2003, Alber et al., 2005, | |
| Alomar and Chavdarova, 2024]. In particular, a mapping F satisfies σ-hypomonotonicity for σ > 0 | |
| if | |
| ⟨F (x) − F (x′ ), x − x′ ⟩ ≥ −σ∥x − x′ ∥2 (16) | |
| for all x, x′ ∈ X . Starting again from (13), we have that for any x′ ∈ X , | |
| ϵ ≥ Ex∼µ [⟨F (x′ ), x − x′ ⟩ − σ∥x − x′ ∥2 ] | |
| = ⟨F (x′ ), x − x′ ⟩ − σEx∼µ [∥x − x′ ∥2 ]. | |
| As a result, | |
| ⟨F (x′ ), x′ − x⟩ ≥ −ϵ − σD2 ∀x′ ∈ X . | |
| This means that x is an (ϵ + σD2 )-approximate MVI solution. Combining with Lemma D.4, we | |
| have shown the following. | |
| Proposition D.5. Let F ∶ X → Rd be a ρ-hypomonotone L-Lipschitz continuous operator. There | |
| is a poly(d, log(1/ϵ))-time | |
| √ algorithm for computing an (ϵ + σD2 )-approximate MVI solution, which | |
| is in turn a 2D L(ϵ + σD2 )-approximate VI solution. | |
| We now show how to translate this result for finding fixed points of a slightly expansive mapping | |
| T : ∥T (x) − T (x′ )∥2 ≤ (1 + σ)∥x − x′ ∥2 . As in (11), if F (x) = x − T (x), we have | |
| 1 | |
| ⟨F (x) − F (x′ ), x − x′ ⟩ = (∥x − x′ ∥22 − ∥T (x) − T (x′ )∥22 + ∥x − T (x) − x′ + T (x′ )∥22 ) | |
| 2 | |
| σ2 | |
| ≥ − (σ + ) ∥x − x′ ∥22 | |
| 2 | |
| 2 | |
| for any x, x′ ∈ X . In other words, F is (σ + σ2 )-hypomonotone. Furthermore, if x∗ is an ϵ′ -VI | |
| √ | |
| solution for F , it follows that ∥T (x∗ ) − x∗ ∥2 ≤ ϵ′ . We arrive at the following conclusion. | |
| Proposition D.6. Let T ∶ X → X be a such that ∥T (x) − T (x′ )∥2 ≤ (1 + σ)∥x − x′ ∥2 . There is a | |
| poly(d, log(1/ϵ))-time algorithm for computing an ϵ′ -fixed point of T , where | |
| ¿ ¿ | |
| Á Á 2 | |
| ′ Á | |
| À2DÁ | |
| ϵ =Á À(2 + σ) (ϵ + (σ + σ ) D2 ). | |
| 2 | |
| In particular, if σ ≤ ϵ, ϵ′ = Θϵ (ϵ1/4 ). | |
| 23 | |
| Compared to the recent result of Diakonikolas [2025], the complexity above grows logarithmi- | |
| cally in 1/ϵ, at the cost of being applicable to a narrower regime of ρ. Furthermore, as we highlighted | |
| in Section 3, Proposition D.5 yields a polynomial-time algorithm for computing ϵ-performatively | |
| stable points in the following regime. | |
| Theorem 3.5. If ρ ≤ 1 + ϵ (per Assumption 2.3), there is a poly(d, log(1/ϵ))-time algorithm for | |
| computing an Oϵ (ϵ1/4 )-performatively stable point. | |
| Whether the tradeoff between approximation and expansiveness can be improved to match the | |
| result of Diakonikolas [2025] is an interesting question. As becomes evident from Propositions D.5 | |
| and D.6, the ϵ1/4 factor is an artifact of how approximation is measured. In terms of the VI problem | |
| corresponding to F (x) = x − T (x), our approach yields an Oϵ (ϵ) approximation for a Minty VI | |
| √ | |
| solution and an Oϵ ( ϵ) approximation for a (Stampacchia) VI solution. | |
| E PPAD-hardness for general convex sets | |
| In this section, we generalize the result of Theorem 3.4 from the domain [0, 1]d to general convex | |
| sets. Through out the section, we let n denote the bit-length of the input to the Turing machine. | |
| We start this section by defining the 2D-Sperner problem. Consider the triangle △A1 A2 A3 on a | |
| 2D plane where A0 = (0, 0), A1 = (2n , 0), and A2 = (0, 2n ). We define the triangulation to be | |
| Tn = {p = (p1 , p2 ) ∈ Z2 ∣ p1 ≥ 0, p2 ≥ 0, p1 + p2 ≤ 2n }. | |
| For any 3-coloring function g ∶ Tn → {1, 2, 3}, it is said to be admissible if the following conditions | |
| are met: | |
| • g(Ai ) = i, for all i ∈ {1, 2, 3}; | |
| • For every p on the segment of Ai Aj , g(p) ≠ 6 − i − j. | |
| Definition E.1 (2D-Sperner ; Papadimitriou, 1990). Given a polynomial-time Turing machine | |
| F that produces a admissible 3-coloring g on Tn where g(p) = F (p) ∈ {1, 2, 3} for every p ∈ Tn , the | |
| output of 2D-Sperner is a trichromatic triangle of coloring g. | |
| The PPAD-membership of 2D-Sperner was established by Papadimitriou [1990], Chen and | |
| Deng [2009] showed that 2D-Sperner is PPAD-complete. | |
| Theorem E.2 (Chen and Deng, 2009). 2D-Sperner is PPAD-complete. | |
| We note that even though the PPAD-hardness result for 2D-Sperner is established on a right | |
| triangle, one can generalize this hardness result to arbitrary triangles. | |
| Lemma E.3. For any triangle △A1 A2 A3 where A1 = (0, 0), A2 = (a1 , a2 ) = a, A3 = (b1 , b2 ) = b, | |
| define the triangulation to be | |
| q r | |
| Tn = {p = a + n b ∣ (q, r) ∈ Z2 , q ≥ 0, r ≥ 0, q + r ≤ 2n } . | |
| 2n 2 | |
| Given a polynomial-time Turing machine F ′ that produces an admissible 3-coloring g ′ for all points | |
| p ∈ Tn , it is PPAD-complete to output a trichromatic triangle of coloring g ′ . | |
| 24 | |
| Proof. First, observe that given p, a and b, we can compute coefficients q and r in polynomial time | |
| through standard basis decomposition. The PPAD-membership follows from Sperner’s lemma. To | |
| prove the hardness, given a 2D-Sperner instance (F, 0n ), we construct the coloring g ′ of triangle | |
| △A1 A2 A3 such that for any point p = ( 2qn a, 2rn b) ∈ Tn | |
| g ′ (p) = F ((q, r)). | |
| Since F produces an admissible 3-coloring, it holds that | |
| • g ′ (Ai ) = i, for all i ∈ {1, 2, 3}; | |
| • For every p = ( 2qn a, 2rn b) on the segment of Ai Aj , g ′ (p) = g((q, r)) ≠ 6 − i − j. | |
| Thus we show that g ′ is an admissible 3-coloring over the triangulation Tn . Furthermore, from any | |
| trichromatic triangle of coloring g ′ over Tn , we can recover a trichromatic triangle of coloring g in | |
| Tn in polynomial time. From Theorem E.2, we conclude the problem is PPAD-complete. | |
| We now introduce the problem of ϵ-ThickBrouwer Deligkas et al. [2020], which is a extension | |
| of 2D-Sperner on an arbitrary triangle △A1 A2 A3 such that the coloring g(⋅) satisfies the following | |
| boundary conditions: | |
| For a given ϵ and any p = 2qn a + 2rn b ∈ Tn , it holds that | |
| ⎧ | |
| ⎪ | |
| ⎪1 for all q ≤ 2n ϵ, and for all 2n ϵ < r < (1 − ϵ)2n − q; | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪2 | |
| ⎪ for all r ≤ 2n ϵ, and for all q < (1 − ϵ)2n − r; | |
| g(p) = ⎨ (17) | |
| ⎪ | |
| ⎪ | |
| ⎪3 for all q and r such that (1 − ϵ)2n ≤ q + r ≤ 2n ; | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎩any color in {1, 2, 3} otherwise. | |
| ⎪ | |
| Given a 2D-Sperner instance, one can reduce it to ϵ-ThickBrouwer in polynomial time by | |
| increasing the number of points in the triangle and embedding the original instance in the center | |
| of the new construction. A detailed proof can be found in the paper of Deligkas et al. [2020]. | |
| To map the coloring defined on the grid Tn to the triangle △A1 A2 A3 , we adopt the bit-extraction | |
| technique, which is commonly used in PPAD-reductions. Specifically, consider a triangle △A1 A2 A3 | |
| with vertices A1 = 0, A2 = a, and A3 = b. For any point p inside the triangle △A1 A2 A3 , we can | |
| compute coefficients q and r through standard basis decomposition such that | |
| q r | |
| p= a + n b. | |
| 2n 2 | |
| Algorithm 1 ExtractBit (x, b) | |
| b ← 0.5 | |
| b ← x −b b | |
| b ← b ∗b L | |
| We then apply the bit-extraction scheme Algorithm 1 of Deligkas et al. [2020] to recover the | |
| first n bits of 2qn and 2rn . Operators +b , −b , ∗b denote bounded operations that ensure the outcomes | |
| remain in [0, 1], which can be efficiently implemented through a algorithmic circuit with standard | |
| min and max operations. Notice that when x ≤ 0.5, we have b = 0, and when x ≥ 0.5 + L1 , we have | |
| b = 1. For 0.5 < x < 0.5 + L1 , the value of b may lie anywhere strictly between 0 and 1 due to the | |
| 25 | |
| continuity of the output of the algorithmic circuit. We refer to the first two cases as well-positioned | |
| and the last case as poorly-positioned. To account for the effect of poorly-positioned points, for | |
| any x ∈ [0, 1]2 , we sample k points x1 , x2 , . . . , xk where | |
| 1 1 | |
| xi = x + (i − 1) [ , ]. | |
| (k + 1)2n+1 (k + 1)2n+1 | |
| The following lemma holds for the sample points x1 , . . . , xk . | |
| Lemma E.4 (Deligkas et al., 2020). Setting L = (k + 2)2n+1 , then among points x1 , . . . , xk , at most | |
| two points will be poorly-positioned. | |
| We proceed to restate the main results of this section. | |
| Theorem 3.12. Given a convex and compact domain X ⊂ Rd that is well bounded, an L-Lipschitz | |
| function F ∶ X → Rd , and ϵ = O(2−n ), it is PPAD-hard to find a point x∗ ∈ X such that | |
| ⟨x − x∗ , F (x∗ )⟩ ≤ ϵ ∀x ∈ X . (4) | |
| This holds even when d = 2 and L = O(1). | |
| Proof. Let X ⊂ R2 be a two-dimensional well-bounded domain. From Definition 3.11, there exist a | |
| 2D ball BR1 inside X . Consider an arbitrary triangle equilateral triangle △A1 A2 A3 that lies on the | |
| boundary of BR1 . Without loss of generality,√we assume R1 = 1 and further assume the position of | |
| √ | |
| A1 is at (0, 0), A2 = ( 3, 0) = a, and A3 = ( 23 , 32 ) = b. Let the discretized grid over △A1 A2 A3 be | |
| as defined in Lemma E.3. We set ϵ = 18 and assign colors to the grid points according to (17) such | |
| that the coloring g(⋅) for points on the grid Tn is admissible for the ϵ-ThickBrouwer problem. | |
| For point x ∈ X outside △A1 A2 A3 , the coloring g(x) is defined as | |
| ⎧ | |
| ⎪1 if min{dist(x, A1 A2 ), dist(x, A1 A3 ), dist(x, A2 A3 )} = dist(x, A1 A3 ); | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪2 if min{dist(x, A1 A2 ), dist(x, A1 A3 ), dist(x, A2 A3 )} = dist(x, A1 A2 ); | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪3 if min{dist(x, A1 A2 ), dist(x, A1 A3 ), dist(x, A2 A3 )} = dist(x, A2 A3 ); | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| g(x) = ⎨In terms of ties: | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪1 if min{dist(x, A1 A2 ), dist(x, A1 A3 ), dist(x, A2 A3 )} = dist(x, A1 A2 ) = dist(x, A1 A3 ); | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎪2 if min{dist(x, A1 A2 ), dist(x, A1 A3 ), dist(x, A2 A3 )} = dist(x, A1 A2 ) = dist(x, A2 A3 ); | |
| ⎪ | |
| ⎪ | |
| ⎪ | |
| ⎩3 if min{dist(x, A1 A2 ), dist(x, A1 A3 ), dist(x, A2 A3 )} = dist(x, A1 A3 ) = dist(x, A2 A3 ), | |
| ⎪ | |
| (18) | |
| where dist(x, Ai Aj ) denotes the distance from point x to line Ai Aj . Notice that by construction, | |
| there is no trichromatic triangle outside △A1 A2 A3 . | |
| We move on to map the coloring of x to the operator value F (x). Recall that segment A1 A2 = a | |
| and segment A1 A3 = b, we define a⊥ = (0, 1) to √ be the unit vector orthogonal | |
| √ | |
| to a and pointing | |
| 3 1 3 1 | |
| inside the triangle. Similarly, we define b⊥ = ( 2 , − 2 ) and c⊥ = (− 2 , − 2 ) as the unit vectors | |
| orthogonal to segment A1 A3 and A2 A3 respectively, each pointing inward, as shown in Figure 2. | |
| Since △A1 A2 A3 is a equilateral triangle, it follows that a⊥ + b⊥ + c⊥ = 0. We then map each color to | |
| a different vector such that color 1 is mapped to b⊥ , color 2 is mapped to a⊥ , and color 3 is mapped | |
| to c⊥ . For any point x ∈ X , we first sample k points2 such that | |
| 1 1 | |
| xi = x + (i − 1) [ n+1 | |
| a, b] . | |
| (k + 1)2 (k + 1)2n+1 | |
| 2 | |
| The coloring for any sample point xi outside X is also determined by (18). | |
| 26 | |
| We then extract the first n bits of xi as xi and pass to the boolean circuit to get the corresponding | |
| color. The operator F (x) is then computed as the average of the vectors corresponding to the | |
| colors of sampled points, | |
| 1 k | |
| F (x) = (∑ 1(g(xi ) = 2)a⊥ + 1(g(xi ) = 1)b⊥ + 1(g(xi ) = 3)c⊥ ) , | |
| k i=1 | |
| where 1(g(xi ) = j) denotes the indicator that the coloring of xi is j. | |
| What remains now is to show that from a solution x∗ of (4), one can recover a trichromatic | |
| triangle. We begin by showing that any point within ϵ distance from the boundary of X cannot be | |
| a solution of (4). | |
| If x lies within 2ϵ distance of the boundary of X , it either lies outside of △A1 A2 A3 or is within | |
| ϵ | |
| 2 distance from one of the segment Ai Aj . By the coloring rule in (17) and (18), among the sampled | |
| points x1 , . . . xk , any well-positioned point can only take two of the three colors. Without loss of | |
| generality, we assume that color 2 is missing from all well-positioned sample points of x, the cases | |
| where color 1 or color 3 is missing follow similarly. | |
| From Lemma E.4, at least k − 2 points out of the k sample points are well-conditioned and are | |
| assigned either color 1 or 3. We consider two cases, | |
| • Color 1 is also missing among the well-conditioned sample points. By the coloring | |
| rule in (17) and the the choice of ϵ, it follows that x must lie within distance 2ϵ of segment | |
| √ | |
| A2 A3 . Recall that c⊥ = (− 23 , − 12 ), we consider the x-coordinate of F (x), | |
| √ | |
| 3(k − 2) 2 | |
| F (x)x ≤ −( − ), | |
| 2k k | |
| where the first term comes from the contribution of the k − 2 well-conditioned sample points, | |
| while the second term accounts for the error introduced by the remaining two points. Let | |
| x′ = A1 = (0, 0), we have | |
| ⟨x′ − x, F (x)⟩ ≥ (x′x − xx )F (x)x | |
| √ √ | |
| 3 ϵ 3(k − 2) 2 | |
| ≥( − )⋅( − ) | |
| 2 2 2k k | |
| ≥ ϵ′ , | |
| where the second inequality | |
| √ | |
| holds because x is within ϵ distance from A2 A3 segment, so its | |
| 3 | |
| x-coordinate, xx ≥ 2 − ϵ. The third inequality holds by setting k ≥ 16 and ϵ′ ≤ 8ϵ = 32 | |
| 1 | |
| . | |
| • The well-conditioned sample points contain both color 1 and color 3. From the | |
| coloring rule in (17), x cannot lie within 2ϵ distance with segment A1 A2 . Recall that b⊥ = | |
| √ √ | |
| ( 23 , − 12 ) and c⊥ = (− 23 , − 12 ). Consequently, the averaged direction F (x) also has negative | |
| y-component. Specifically, let F (x)y denote the y-coordinate of F (x), it holds that | |
| k−2 2 | |
| F (x)y ≤ − ( − ). | |
| 2k k | |
| 27 | |
| Let x′ be a point on the segment A1 A2 . Note that since color 1 is missing, by the construction | |
| of the ϵ-ThickBrouwer problem, we also have xy − x′y ≥ 2ϵ . Therefore | |
| ⟨x′ − x, F (x)⟩ ≥ (x′y − xy )F (x)y | |
| ϵ k−2 2 | |
| ≥ ⋅( − ) | |
| 2 2k k | |
| > ϵ′ , | |
| where the last step follows by setting k ≥ 16 and ϵ′ ≤ 8ϵ = 32 | |
| 1 | |
| . | |
| For any point x that lies more than 2ϵ distance away from the boundary, we argue that if x is | |
| a solution for (4), then one can recover a trichromatic triangle for the ϵ-ThickBrouwer problem. | |
| We show this by contradiction, first assume that if color 1 is missing from the well-positioned | |
| sampled points among x1 ⋯xk , like the previous case, we have | |
| k−2 2 | |
| F (x)y ≤ − ( − ). | |
| 2k k | |
| Note that since x is not within 2ϵ distance from the boundary, along the negative y direction, we | |
| can find a point x′ ∈ X that is at least ϵ away from x (i.e., x′ = x − ϵ ⋅ (0, 1)). It then holds that | |
| ϵ k−2 2 | |
| ⟨x′ − x, F (x)⟩ > ⋅( − ) > ϵ′ . | |
| 2 2k k | |
| The cases where color 2 or coloring 3 is missing follow similarly. Therefore we conclude that if | |
| x is a solution of (4), the well-positioned sample points among x1 , . . . , xn must have all three | |
| colors. Observe that ∥xk − x∥∞ < 21n min(∥a∥2 , ∥b∥2 ), which implies that if the well-positioned | |
| points among x1 . . . xk contain all three colors, then x must resides within a trichromatic square | |
| with sides oriented along directions a and b. Such a square can only occur within △A1 A2 A3 . Finally, | |
| the reduction from trichromatic triangles to trichromatic squares of 2D-Sperner is established in | |
| Chen and Deng [2009]. | |
| Note that since the grid Tn has side length O( 21n ), the Lipschitz constant of the operator F (⋅) | |
| F (x) ϵ′ 1 | |
| is O(2n ). Define the rescaled operator F ′ (x) = ′′ | |
| 2n , and let ϵ = 2n = O( 2n ). Then computing a | |
| point x∗ ∈ X such that for any x ∈ X , | |
| ⟨x − x∗ , F ′ (x∗ )⟩ ≤ ϵ′′ | |
| is PPAD-hard. Moreover, the Lipschitz constant for F ′ (⋅) is O(1) and ϵ′′ = O( 21n ). This completes | |
| the proof. | |
| Remark E.5. In our proof the operator F is given by a (well-behaved) arithmetic circuit with n | |
| rational inputs and size that depends polynomially on the description of the 2D-Sperner prob- | |
| lem, which can effectively approximate any Lipschitz continuous function. We refer the reader | |
| to Fearnley et al. [2023] for further background on complexity theory. | |
| Remark E.6. We remark that our construction uses irrational coordinates for the positions of A2 | |
| A3 and for the directional vectors a⊥ , b⊥ , c⊥ , which cannot be represented exactly by a Turing | |
| machine. Nevertheless, our reduction continues to work given a suitably good approximation of | |
| these quantities. A similar technical issue is discussed in Deligkas et al. [2020]. | |
| 28 | |
| F PLS-hardness of finding local optima in strategic classification | |
| In this section, we establish that finding a local optima in strategic classification per Definition 4.1 | |
| is PLS-hard. We first restate the main result we want to prove. | |
| Theorem 4.4. Given a finite population X, a distribution D over X, a cost function c, and a | |
| target classifier h, it is PLS-hard to find a strategic local optimum as in Definition 4.3. This result | |
| holds even when c is a metric and the target classifier h is provided explicitly to the algorithm. | |
| Proof. The proof proceeds via a polynomial-time reduction from the LocalMaxCut problem. | |
| Let G = (V, E, w) be a weighted undirected graph with edge weights w(u,v) ≥ 0 for any edge | |
| (u, v) ∈ E. We construct a strategic classification instance with a finite population X and a non- | |
| uniform distribution D over X. For convenience, we define the weight of a point wD (x) so that | |
| the probability of sampling x ∈ X from D is proportional to wD (x). The population is defined as | |
| follows. | |
| • For each vertex v ∈ V, we introduce a point xv− with label h(xv− ) = 0. The weight of xv− | |
| under distribution D is given by the total weight of edges incident to vertex v, i.e., wD (xv− ) = | |
| ∑u∈N (v) w(u,v) ; | |
| • For every edge (u, v) ∈ E, we introduce a point x(u,v)+ with label h(x(u,v)+ ) = 1, and weight | |
| wD (x(u,v)+ ) = 2w(u,v) ; | |
| • For every edge (u, v) ∈ E, we introduce a point x(u,v)− with label h(x(u,v)− ) = 0, and weight | |
| wD (x(u,v)− ) = 2w(u,v) + 1. | |
| We now define a metric c ∶ X × X → R≥0 . We choose the value such that c(x, x) = 0 and c(x, y) = | |
| c(y, x). Moreover, the metric c takes only two nonzero values, 0.8 and 1.2. These values are chosen | |
| to ensure that the triangle inequality holds, other than that, we can set them to arbitrary value in | |
| the range from (0, 1) and (1, ∞) respectively. The metric is defined as follows. | |
| • For each vertex point xv− , and for every positive edge point x(u,v)+ such that edge (u, v) is | |
| incident to vertex v, we set c(xv− , x(u,v)+ ) = 0.8; | |
| • For each edge positive point x(u,v)+ and corresponding edge negative point x(u,v)− we set | |
| c(x(u,v)+ , x(u,v)− ) = 0.8; | |
| • For all other pairs (x, y), we define c(x, y) = 1.2. | |
| If c(x, y) = 0.8, we call them close to each other. Notice that under this metric c, the Contestant | |
| will only deviate a point x to point y if f (x) = 0, f (y) = 1, and x is close to y. | |
| The first claim is that if f ∗ is at a strategic local optimum, then f ∗ (x(u,v)− ) = 0 and f ∗ (x(u,v)+ ) = | |
| 0 for all edge (u, v) ∈ E. To see this, assume that f ∗ (x(u,v)− ) = 1 for some edge (u, v) ∈ E, then | |
| the Jury can simply deviate to another classifier f ′ that differs with f ∗ with only the prediction of | |
| x(u,v)− . If M is the sum of all the weights of points in X, it holds that | |
| 1 | |
| Pr [h(x) = f ′ (∆(x))] − Pr [h(x) = f ∗ (∆(x))] ≥ (2w(u,v) + 1 − 2w(u,v) ) (19) | |
| x∼D x∼D M | |
| 1 | |
| = , (20) | |
| M | |
| 29 | |
| where (19) holds because changing the prediction of x(u,v)− from 1 to 0 may cause the misclassifica- | |
| tion of the positive edge point x(u,v)+ , but it ensures that the negative edge point x(u,v)− is classified | |
| correctly. As a result, (20) implies that the Jury can strictly improve their utility by deviating to | |
| the classifier f ′ , which contradicts the assumption that f ∗ is a strategic local optimum. | |
| Now suppose f ∗ (x(u,v)+ ) = 1 for some (u, v) ∈ E. Since f ∗ (x(u,v)− ) = 0 and x(u,v)+ and x(u,v)− are | |
| close to each other, the Contestant will deviate x(u,v)− to x(u,v)+ . Consider an alternative classifier | |
| f ′ that differs from f ∗ only in the prediction of x(u,v)+ , we have | |
| 1 | |
| Pr [h(x) = f ′ (∆(x))] − Pr [h(x) = f ∗ (∆(x))] ≥ (−2w(u,v) − (−2w(u,v) − 1)) | |
| x∼D x∼D M | |
| 1 | |
| = , | |
| M | |
| where the first inequality holds because changing the prediction of x(u,v)+ from 1 to 0 may cause the | |
| positive edge point x(u,v)+ to be misclassified, but it ensures that the negative edge point x(u,v)− is | |
| classified correctly. Moreover, any deviations of vertex points xv− can only increase this gap. Thus, | |
| f ∗ cannot be a strategic local optimum, yielding a contradiction. | |
| We conclude that, in order to reach a strategic local optimum, the only points that can be | |
| labeled positively are the vertex points xv− . In this case, the Jury can improve their utility through | |
| the deviation of positive edge points x(u,v)+ to the corresponding vertex points xv− . | |
| We now proceed to analyze the utility of the Jury when the label of a single vertex point xv− is | |
| changed from 0 to 1. Let N (v)+ denote the set of neighbors of vertex v in the original graph whose | |
| corresponding vertex points are labeled 1 by the classifier, and let N (v)− denote the set of neighbors | |
| that are labeled 0. Observe that before changing the label of xv− , for all vertices u ∈ N (v)+ , the | |
| Contestant already deviates the corresponding positive edge points x(u,v)+ to xu− . Hence, those | |
| points will be correctly labeled regardless of the change. In contrast, for every u ∈ N (v)− , the | |
| corresponding positive edge points x(u,v)+ do not deviate before the change, but will deviate to xv− | |
| after the change. | |
| Let f denote the Jury’s classifier before the change and f ′ the classifier after the change. The | |
| resulting difference in the Jury’s utility is | |
| 1 ⎛ ⎞ | |
| Pr [h(x) = f ′ (∆(x))] − Pr [h(x) = f (∆(x))] = ∑ 2w(u,v) − ∑ w(u′ ,v) (21) | |
| x∼D x∼D M ⎝u∈N (v)− u′ ∈N (v) ⎠ | |
| 1 ⎛ ⎞ | |
| = ∑ w(u,v) − ∑ w(u′ ,v) . (22) | |
| M ⎝u∈N (v)− u′ ∈N (v)+ ⎠ | |
| The first term in (21) corresponds to the gain from the correctly labeling positive edge points after | |
| the change, while the second term accounts for the loss introduced by misclassifying the vertex | |
| point xv− . | |
| Similarly, consider the case where the Jury change the label of a vertex point xv− from 1 to | |
| 0. For each vertex u ∈ N (v)+ , the corresponding edge points x(u,v)+ will still be classified positive | |
| since the Contestant will deviate to xu− . However, for every vertex u ∈ N (v)− , edge points x(u,v)+ | |
| will be misclassified, since after the change they no longer have any positively labeled neighbors. | |
| Thus, the resulting change in the Jury’s utility is | |
| 30 | |
| 1 ⎛ ⎞ | |
| Pr [h(x) = f ′ (∆(x))] − Pr [h(x) = f (∆(x))] = − ∑ 2w(u,v) + ∑ w(u′ ,v) (23) | |
| x∼D x∼D M ⎝ u∈N (v)− u′ ∈N (v) ⎠ | |
| 1 ⎛ ⎞ | |
| = ∑ w(u,v) − ∑ w(u′ ,v) . (24) | |
| M ⎝u∈N (v)+ u′ ∈N (v)− ⎠ | |
| Here, the first term in (23) captures the loss from misclassifying edge points x(u,v)+ , while the | |
| second term is due to correctly labeling the vertex point xv− . | |
| Suppose we have a classifier f ∗ which is at a strategic local optimum. By Definition 4.3, (22) is | |
| nonpositive for every vertex u such that xu− is labeled 0, and (24) is nonpositive for every vertex v | |
| such that xv− is labeled 1. Now consider a cut of the original graph defined as follows: each vertex | |
| v ∈ V with f ∗ (xv− ) = 0 is on one side of the cut (negative side), and each vertex with f ∗ (xv− ) = 1 | |
| is placed on the other side (positive side). Since (22) is nonpositive, moving any vertex from the | |
| negative side of the cut to the positive side cannot increase the total weight of the cut. Similarly, | |
| since (24) is nonpositive, moving any vertex from the positive side to the negative side also cannot | |
| improve the cut weight. Thus, we conclude that any locally strategic optimal classifier f ∗ induces | |
| a local max cut on the original graph G. This completes the proof. | |
| G Further omitted proofs | |
| This section contains additional omitted proofs. We begin with Theorem 3.4. | |
| Theorem 3.4. Finding an ϵ-performatively stable point per Definition 2.4 is PPAD-hard even | |
| when Lβ/α ≤ 1 + ϵϵ′ for ϵ′ = 0.088/6 ≈ 0.0147. This is so even when ℓ is a quadratic objective, | |
| ℓ(x; z) = 21 ∥x − z∥22 , and D(x) is given by an affine map. | |
| Proof. Let X = [0, 1]d and let x∗ ∈ X be an ϵ-performatively stable point of (2)-(3). By Defini- | |
| tion 2.4, we have that for all x ∈ X , | |
| ⟨x − x∗ , x∗ − g(x∗ )⟩ ≥ −ϵ. (25) | |
| Now, let g(x) ∶ (I − A)x − b, where A = ϵϵ′ A and b = ϵϵ′ b for A and b as in Lemma 3.3. Finding a | |
| solution x∗ satisfying (25) would imply that for all x ∈ [0, 1]d , | |
| ⟨x − x∗ , Ax∗ + b⟩ ≥ −ϵ′ . (26) | |
| From Lemma 3.3, we conclude that it is PPAD-complete to find a point x∗ satisfying (25). Fur- | |
| thermore, | |
| ∥g(x) − g(x′ )∥ = ∥(I − A)x − (I − A)x′ ∥ | |
| ≤ (∥I∥ + ∥A∥2 ) ∥x − x′ ∥ | |
| √ | |
| ≤ (1 + ∥A∥1 ∥A∥∞ ) ∥x − x′ ∥ | |
| ϵ | |
| ≤ (1 + ′ ) ∥x − x′ ∥ . | |
| ϵ | |
| We conclude that even when Lβ/α ≤ 1 + ϵϵ′ , it is PPAD-complete to find an ϵ-performatively stable | |
| point. | |
| 31 | |
| We next point out the polynomial equivalence between the two natural ways of measuring | |
| approximation for performatively stable points. | |
| Lemma G.1. If ℓ(x; z) is α-strongly convex in x (with respect to the ∥ ⋅ ∥2 norm) for any z ∈ Z | |
| and x∗ is an ϵ-performatively stable point (Definition 2.4), then | |
| √ | |
| ϵ | |
| ∥x∗ − G(x∗ )∥2 ≤ , | |
| α | |
| where G is the RRM map (Definition 1.1). | |
| Proof. Since ℓ(x; z) is α-strongly convex in x for any z, the expected loss f (x) = Ez∼D(x∗ ) [ℓ(x; z)] | |
| is also α-strongly convex. By strong convexity, we have for any x, x′ ∈ X , | |
| ⟨∇f (x) − ∇f (x′ ), x − x′ ⟩ ≥ α∥x − x′ ∥22 . (27) | |
| We now write | |
| ⟨∇f (x∗ ) − ∇f (G(x∗ )), x∗ − G(x∗ )⟩ = ⟨∇f (x∗ ), x∗ − G(x∗ )⟩ − ⟨∇f (G(x∗ )), x∗ − G(x∗ )⟩. | |
| We bound each term separately. First, since x∗ is an ϵ-performatively stable point, we have | |
| ⟨x − x∗ , ∇f (x∗ )⟩ ≥ −ϵ ∀x ∈ X . | |
| Taking x = G(x∗ ), we get ⟨∇f (x∗ ), x∗ − G(x∗ )⟩ ≤ ϵ. Second, since G(x∗ ) = argminx∈X f (x), the | |
| first-order optimality condition yields ⟨x − G(x∗ ), ∇f (G(x∗ ))⟩ ≥ 0 for all x ∈ X , which in turn | |
| implies −⟨∇f (G(x∗ )), x∗ − G(x∗ )⟩ ≤ 0. Combining these bounds with (27), | |
| α∥x∗ − G(x∗ )∥22 ≤ ⟨∇f (x∗ ) − ∇f (G(x∗ )), x∗ − G(x∗ )⟩ ≤ ϵ, | |
| and the proof follows. | |
| Lemma G.2. If ℓ(x; z) satisfies ∥∇x ℓ(x; z) − ∇x ℓ(x′ ; z)∥2 ≤ β∥x − x′ ∥2 , any point x∗ ∈ X such | |
| that ∥x∗ − G(x∗ )∥2 ≤ ϵ, where G is the RRM map (Definition 1.1) is ϵ′ -performatively stable | |
| (Definition 2.4) with ϵ′ = ϵ (Dβ + ∥∇f (G(x∗ ))∥2 ), where D is the ℓ2 diameter of X . | |
| Proof. Let f (x) = Ez∼D(x∗ ) [ℓ(x; z)]. We have | |
| ⟨x − x∗ , ∇f (x∗ )⟩ = ⟨x − x∗ , ∇f (G(x∗ ))⟩ + ⟨x − x∗ , ∇f (x∗ ) − ∇f (G(x∗ ))⟩. (28) | |
| For the first term, we write | |
| ⟨x − x∗ , ∇f (G(x∗ ))⟩ = ⟨x − G(x∗ ), ∇f (G(x∗ ))⟩ + ⟨G(x∗ ) − x∗ , ∇f (G(x∗ ))⟩ | |
| ≥ ⟨G(x∗ ) − x∗ , ∇f (G(x∗ ))⟩, | |
| by the first-order optimality condition of G(x∗ ). Thus, | |
| ⟨x − x∗ , ∇f (G(x∗ ))⟩ ≥ −∥x∗ − G(x∗ )∥2 ∥∇f (G(x∗ ))∥2 ≥ −ϵ∥∇f (G(x∗ ))∥2 . | |
| For the second term in the right-hand side of (28), we use β-Lipschitz continuity of ∇f to get | |
| ⟨x − x∗ , ∇f (x∗ ) − ∇f (G(x∗ ))⟩ ≥ −∥x − x∗ ∥2 ∥∇f (x∗ ) − ∇f (G(x∗ ))∥2 ≥ −ϵDβ, | |
| and the proof follows. | |
| 32 | |
| To conclude, we provide the proof of Proposition 4.5. We begin by stating a variation of Defi- | |
| nition 4.1 that incorporates classifier-dependent costs. It also forces the Jury to select a classifier | |
| from a specified set, and similarly for the Contestant. | |
| Definition G.3 (Strategic classification with endogenous costs). Strategic classification is a game | |
| played between the Jury and the Contestant. Let D be a distribution over a population X, c ∶ | |
| X × X → R≥0 a cost function, and h a target classifier. | |
| 1. The Jury first publishes a classifier fj ∶ X → {0, 1} selected from a set of classifiers {f1 , . . . , fm }. | |
| 2. The Contestant selects a deviation ∆i ∶ X → X selected from a set of deviations {∆1 , . . . , ∆n }. | |
| The payoff to the Jury is Prx∼D [h(x) = fj (∆i (x))] and the payoff to the Contestant is Ex∼D [fj (∆i (x))− | |
| cj (x, ∆i (x))]. | |
| While the Jury has now to decide among a small set of possible classifiers (as opposed to 2∣X∣ ), | |
| we show that computing a performatively stable point is PPAD-hard. | |
| Proposition 4.5. Computing a performatively stable point in strategic classification with endoge- | |
| nous costs is PPAD-hard. | |
| Our reduction makes use of the hardness of Nash equilibria in two-player games. | |
| Definition G.4 (Nash equilibrium). For a two-player game (A, B), with A, B ∈ Rn×m , an ϵ-Nash | |
| equilibrium is a point (x, y) ∈ ∆n × ∆m such that | |
| ⟨x, Ay⟩ ≥ ⟨x̂, Ay⟩ − ϵ and ⟨x, By⟩ ≥ ⟨x, Bŷ⟩ − ϵ ∀(x̂, ŷ) ∈ ∆n × ∆m . | |
| Proof of Proposition 4.5. We reduce from the PPAD-hard problem of computing a Nash equilibrium | |
| of a win-loss game [Abbott et al., 2005]. Let (A, B) ∈ {0, 1}n×m be the payoff matrices for the row | |
| player and column player, respectively. We construct an instance of strategic classification with | |
| endogenous costs as follows. The population domain X = {x1 , . . . , xn } comprises n distinct points. | |
| The underlying distribution D is assumed to be uniform over X. The target classifier is h(x) = 0 | |
| for all x ∈ X. | |
| The Jury chooses a classifier from the set {f1 , . . . , fm }. We associate each classifier fj with the | |
| jth column of the game matrices. We define the classifier’s outputs to have the opposite label from | |
| the column player’s utility matrix: fj (xi ) = 1 − Bij for all xi ∈ X. Moreover, because costs are | |
| endogenous, the Jury’s choice of strategy j also induces a specific cost function cj . | |
| The Contestant chooses a deviation from the set {∆1 , . . . , ∆n }. We restrict these to be constant | |
| deviations, where ∆i maps every input point to the specific point xi corresponding to the ith row. | |
| Now, the payoff to the Jury is Prx∼D [h(x) = f (∆(x))]. As a result, under a classifier fj and a | |
| deviation ∆i , the utility of the Jury reads | |
| Pr [h(x) = fj (∆i (x))] = Pr [fj (∆i (x)) = 0] = 1[fj (xi ) = 0] = Bij , | |
| x∼D x∼D | |
| so this matches the utility of the column player in the original game. To ensure the Contestant | |
| (approximately) maximizes A, we consider the following star metric for each j. Each point xi | |
| is connected to a point x∗ . The cost to go from xi to x∗ is defined as 2M − M Aij for a large | |
| parameter M ≫ 1. Thus, cj (xi , xi′ ) = cj (xi , x∗ ) + cj (xi′ , x∗ ). | |
| 33 | |
| Under a classifier fj and a deviation ∆i , the payoff to the Contestant is | |
| 1 n 1 n | |
| ∑ cj (xi , xi′ ) = fj (xi ) − ∑ cj (xi′ , x ) − cj (xi , x ). | |
| ∗ ∗ | |
| Ex∼D [fj (∆i (x)) − cj (x, ∆i (x))] = fj (xi ) − | |
| n i′ =1 n i′ =1 | |
| The second term above does not depend on the deviation ∆i , so it is strategically irrelevant. | |
| Specifically, we end up with the two-player game with utilities ⟨x, A′ y⟩ + ⟨c, y⟩ and ⟨x, By⟩, where | |
| c = (− n1 ∑ni′ =1 cj (xi′ , x∗ ))m ′ | |
| j=1 , and A = F + M Aij − 2M 1 for Fij = fj (xi ); 1 denotes the all-ones | |
| n m | |
| matrix. Let (x, y) ∈ ∆ × ∆ be Nash equilibrium of this game, which corresponds to a perfo- | |
| matively stable point of the strategic classification instance. We have ⟨x, A′ y⟩ ≥ ⟨x̂, A′ y⟩ for any | |
| x̂ ∈ ∆n , which implies ⟨x, Fy⟩ + M ⟨x, Ay⟩ ≥ ⟨x̂, Fy⟩ + M ⟨x̂, Ay⟩. Since Fij ∈ {0, 1}, it follows that | |
| 1 | |
| ⟨x, Ay⟩ ≥ ⟨x̂, Ay⟩ − M for any x̂ ∈ ∆n . As a result, (x, y) is a 1/M -Nash equilibrium of the original | |
| two-player game. | |
| 34 | |
Xet Storage Details
- Size:
- 113 kB
- Xet hash:
- aafddc9c86d4dc2d1545c186eac24b0e023f5307f60f94a49ec3628a53718ec6
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.