Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos
Authors: Georgios Piliouras
Fang-Yi Yu
Venue: ICLR 2022 Submitted (2022)

Abstract: The recent framework of performative prediction is aimed at capturing settings where predictions influence the target/outcome they try to predict. In this paper, we introduce a natural multi-agent version of this framework, where multiple decision makers try to predict the same outcome.  We showcase that such competition can result in interesting phenomena by proving the possibility of phase transitions from stability to instability and eventually chaos. Specifically, we present settings of multi-agent performative prediction where under sufficient conditions, their dynamics lead to global stability and optimality. In the opposite direction, when the agents are not sufficiently cautious in their learning/updates rates, we show that instability and in fact formal chaos is possible. We complement our theoretical predictions with simulations showcasing the predictive power of our results. 

Under review as a conference paper at ICLR 2022
MULTI-AGENT PERFORMATIVE PREDICTION: FROM GLOBAL STABILITY AND OPTIMALITY TO CHAOS
Anonymous authors Paper under double-blind review
ABSTRACT
The recent framework of performative prediction (Perdomo et al. 2020) is aimed capturing settings where predictions influence the target/outcome they want predict. In this paper, we introduce a natural multi-agent version of this frame- work, where multiple decision makers try predict the same outcome. We show- case that such competition can result in interesting phenomena by proving the possibility of phase transitions from stability instability and eventually chaos. Specifically, we present settings of multi-agent performative prediction where un- der sufficient conditions their dynamics lead to global stability and optimality, the opposite direction, when the agents are not sufficiently cautious in their learn- ing/updates rates, we show that instability and fact formal chaos possible. We complement our theoretical predictions with simulations showcasing the predic- tive power of our results.
INTRODUCTION
Performative prediction (Perdomo et al. 2020 is recently introduced framework that focuses natural but largely unexplored element of supervised learning. In many practical cases the predictive model affect the very outcome that it is trying to predict. For example, predictions about which part of road network will have high congestion trigger responses from the drivers which affect the resulting traffic realization leading shift of the target distribution. In such settings, (Perdomo et al. 2020) explored conditions for the existence and approximate optimality of stable equilibria of such processes.
One possible way to interpret the performative prediction setting is a single agent "game", where the predictive agent is playing game against himself. An agent chooses the parameters of his model as his actions but the predictive accuracy/cost. of the model depends on his own past actions. Fixed points of this process do not allow for profitable deviations. Once cast in this light, it becomes self-evident that the restriction to single predictive agent/model is arguably only the first step in capturing more general phenomena where there is closed loop between predictive models and their environment. This motivates our central question: What is the interplay between stability, optimality in cases where multiple predictive models operate in parallel to each other? Can the competition be- tween multiple models lead to novel phenomena such as phase transitions from stability instability and chaos?
A natural setting consider for example is market competition, where multiple hedge funds trying to simultaneously predict future prices, volatility financial instruments. Of course as they upon their predictions they also move the prices of these commodities in highly correlated way. As more agents enter the market and the competition becomes increasingly fierce, is it possible that some point the market flips from quickly discovering accurate stable predictions reflecting the underlying market fundamentals to self-induced unpredictability and chaos? When it comes to performative prediction can too many cooks spoil the soup?
Our model Standard supervised learning consists of three components: a set of predictive mod- els, a loss function, and a data distribution. The learner (agent) observes samples of the distribution, and then decides a predictive model. When predictions performative, the agent's 's decision of predictive model influences the data distribution. Thus, instead of a fixed data distribution, pre- dictive prediction also has distribution map: mapping from the agent's predictive models to

---

Under review as a conference paper at ICLR 2022
data distributions. We further propose multi-agent performative prediction which model the influ- ence of multiple agents' decisions on the data distribution, and ask whether these influence leads to convergent chaotic systems.
To understand the framework of multi-agent performative prediction. we study a natural regression problem with multi-agent location-scale distribution maps (definition 2.2] where the agents' influ- ence is linear in the agents' models. Specifically, the data consist of features and outcomes. For each agent i [na]. his influence on the distribution of outcome is his model weighted by scalar X > O. When n 1. our multi-agent location-scale distribution map is special case of location- scale family in Miller et al.) (202T). ). In the market example, each hedge fund company tries predict the price (outcome) based on macroeconomic data or other information (features). These influence parameters A An can be seen as each hedge fund's capital that can influence the distribution of the future price.
Finally, we consider the agents do not know the dependency between their model and the data distribution, and they can only improve their predictive models myopically and iteratively. In this paper, the agents myopically use a reinforcement learning algorithm, exponentiated gradient for linear regression (Kivinen & Warmuth 1997), to improve their predictive models in rounds. We study the long-term behavior, and ask if the system converge to the performative stable and optimal point, or behave chaotically.
Our results We first study basic properties of multi-agent preformative prediction with multi- agent location-scale distribution map. We show 1) the existence of performative stable point in our setting (proposition 3.1) and 2) the performative stability and performative optimality equivalent
(proposition 3.2) This equivalence allows us to focus on the dynamical behavior of the system.
In section 4 we introduce learning dynamics to the multi-agent performative prediction, and study their long-ferm behavior. We provide a threshold result which depends on the learning rates of exponentiated gradient descent and the collective influence. Theorem 4.1 shows the dynamics of exponential gradient descent converge to the performative stable and optimal point when the learn- ing rate small enough. Our convergence result in theorem [4T holds when the feature space multi-dimensional, and every learning agent can use different learning rates starting at arbitrarily interior states. Our exact convergence result also works in the single-agent performative predic- tion setting. Contrarily, previous convergent results in Perdomo et al. (2020); Miller et al. (2021); Mendler- Dünner et al. (2220) only show that their dynamics converge to a small neighborhood of the performative stable point.
On the other hand, section 4.2 shows the dynamics can have chaotic behavior if the collective in- fluence Ln is large enough. Specifically, theorem 4.6 shows that even when the feature space is in R.2 these systems provably exhibit Yi-Yor chaos, when the collective influence E, A; is large enough. This implies that there exists uncountable "scrambled" set that given any conditions in the set, the liminf of the distance between these two dynamics is zero, but the lim- sup of their distance positive. (definition (.4] The chaotic result in theorem 4.6) also holds for the original single-agent performative prediction so long as the agent's 's influence is large enough, and, thus, complements previous performative prediction works on convergence behavior, which primarily consider that the agent's influence on the data distribution is sufficiently small. Moreover, no matter how small the agents' learning rates, theorem shows that chaos inevitable some performative predictions settings when the number of agents exceeds carrying capacity. After that the system becomes totally unpredictable with small perturbations exploding exponentially fast.
initial
Finally, section 5 provides numerical examples of our dynamics and show convergent and chaotic behavior. Additionally, through simulation, we demonstrate that our convergent and chaotic results also hold when the agents only access noisy estimation of the gradient and conduct stochastic exponentiated gradient descent.
Related work Data distribution shift is not a new topic in ML, but earlier works focused primarily on exogenous changes to the data generating distribution. Performativity is machine learning was introduced by Perdooo et al. 2022)). The original work and several follow-ups study the discrep- ancy between performative stability and performative optimality and prove approximated conver-
Wee highlight our revision in color.
2

---

Under review as a conference paper at ICLR 2022
gence of learning dynamics, e.g., stochastic gradient descent, iterative empirical risk minimiza-
tion. (Mendler-Düimee et al. 2020 Drusvyatskiy & Xiao 2020 Izzo et al. al.] (022)) Performativity of
prediction is also related to several applications: strategic classification (Hardt et al. 2016), retrain-
ing [Bartlett (992); Kuh et al. 1990).
Inspired by the instability of training algorithms in ML applications such Generative Adversarial Networks (GANs), there has been lot of recent interest in understanding conditions (particularly
in multi-agent systems) where learning behavior may be non-equilibratinn/unttaabl (Cheung & Tao
2020
Balduzzi et al., 2020; Flokas et al. 2020 Andrade et al. 2021] Letcher 202 10 Giannou et al.
2021 The (in (in)stabilityy and performance of exponentiated gradient descent in particular (also re-
ferred to as Multiplicative Weights Updates) and other closely related dynamics has attracted lot
of attention (Cohen al.
2017 |Bailey & Piliouras] 2018: Cheung 2018 Panageas et al. 2019 Vadori et 20211. The technique of Li-Yorke chaos has recently found applications across several different domains such as routing games, Cournot games and blockchain
Cheung & Piliouras] 2020
2017 Chotibut et al. 2020 Bielawski et al. 2021 Cheung al.) 2021 Leonardos et al. 2021). To our knowledge, this is the first time where such formal chaotic results established in settings related performative prediction and supervised learning more generally.
protocols (Palaiopanos al.
Another line of related works is learning in games. Specifically, our dynamics can be seen as special cases multiplicative weight update (Hedge algorithms) on congestion games. Previous works Hedge algorithms only show exact convergence when the learning rate is decreasing Kleinberg et al. 2009); Coohen al. (017), and, to best knowledge, our results the first that shows exact convergence of Hedge algorithms with small constant learning rates. Our results also complement the exact convergence result of the linear variant of multiplicative weight update by Palaiopanos
et al. (2017).
2
PRELIMINARY
2.1 MULTI-AGENT PERFORMATIVE PREDICTION
A multi-agent performative prediction comprises n agents deploying their predictive models foi...., with parameters 0 ,, ".. 0" E θ that collectively influence the future data dis- .......," tribution. We formalize such dependency via a distribution map D(.)) which outputs a distribution on the data, D(0), given a models profile 0 = (0) "e....., Ot) E e A loss function E(2, 0') mea- sures the loss of model J on data point z (f O')]. For performative prediction, we further define the decoupled performative loss on distribution mapping D as
and the expected loss on a distribution D is
E(O, 0') == 20 ((z, 0')
where 0' E θ denotes a predictive model, while 0 E e denotes a deployed model profile.
Given the of model Ô, the loss function and the distribution mapping D, each agent in multi-agent performative prediction (O, D) pursues minimal loss on the distribution that they collectively induce. We consider two solution concepts performative optimality and performative stability which generalizes the original ones in Perdomo et al. (2020)
Definition 2.1. Given (0, D), models profile 0+ E O" is performatively optimal if the total loss is minimized,
/' arg min Σ E(0,0') 0ee=
Another desirable property of a model profile is that, given all agents deploy their models, their models are also simultaneously optimal for distribution that their model induces. Formally, Ø' is performatively stable if for all E [n]
(0r)² E arg min ( 0*).
e'ee
The performative optimality does not implies the performative stable point. For performative opti- mal point, the variable for minimization affects both the first and the second argument, but only affect the second one for performative stable point. Now introduce model in this paper.
3

---

Under review as a conference paper at ICLR 2022
Location-scale distribution map In this paper, we study the family of multi-agen location-scae scale map for regression problem where a data point consists of d-dimensional feature and scalar outcome, (a. v)- These are natural classes of distribution maps in which performative effects enter through an additive or multiplicative factor that is linear in 0.
Definition 2.2. Given d E N and d > 2, and @r C R. distribution map D @ - R x R multi-agent location-scale distribution map on n parties there exists static distribution Dx on Rd++1 0 E R and linear functions .......A An from R2 to Ie so that the distribution of (x.y) y) ~ D(0) has the following form: The feature is E I& and noise zo E R is jointly sampled from Dx. Given feature æ E IR and noise To IR, and the the outcome
y
0
A,(0"), )
+ zV-
In this paper, we consider the scaling maps (0) 0,0 for all 0 E θ with scalar A, > 0 for all E [d]. We call À := (A1,..., An) the influence parameters, and L, := Σ A collective influence. Furthermore, we let A := E [xxx] E Iddd be the covariance matrix of the feature, and b := AO + B[xox] E Rd. We will specify the multi agent location-scale distribution map with parameters n, d, X, A, and b.
When n = 1. our multi-agen location scale distribution map is a special case of location scalle family in Miller et al. (2021) where the model may both the outcome y as well as the feature æ.
Predictive Models and Loss Function We consider linear predictive model with constraint where So (z) (0', and the collection of parameter is the d-simplex, O {0 Σi= 0g 1, 0g > 0}. We use mean squared error to measure a predictive model 0' E O on a distribution map with deployed model profile 0 E O", ((,,0' 0') = (()))) [(y --e (x) ) E (xx))>><o)) [(y (ly-0' x)
Given a deployed model profile @ and a predictive model 6', the gradient of the decoupled loss is g(0, 0*) Vo 0¹), and if D is location-scale distribution map, g(0, 0*) (x))) (2(0'. x y) Furthermore, with and b defined in definition 2.2 the gradient can be written as
g(ō V (0, 22 0' Σ 1,0
2b.
Additionally, given deployed model profile 0 and a predictive model profile 0' we define the g(0, (0')),, and g0) g' (0. 9) when the deployed model profile is identical to the predictive model profile. We denote the gradient of agent i's average loss as g0) = Σ, 0ggg for all 0 e Finally, we define E(θ) (E'....,5") )
gradient of agent i's decoupled loss g'
with g E Edd so that for all E [n] and ls E [d] E (0) 6% (igg l.). For brevity, we omit and define g = g()) and g = ( when there is no ambiguity.
2.2 LEARNING DYNAMICS
We consider the agents myopically use a reinforcement learning algorithm exponentiated gradient for linear regression to improve their predictive models in rounds. We first define the original single agent's 's exponentiated gradient for linear regression on sequence of data points here and will state our dynamics on multi agent performative prediction in section 4
Definition 2.3 (iiinnnn & Warmuth (1997)). Given learning rate n > 0, initial parameter O, E θ and sequential of data points (æe, 1r)e21 the exponentiated gradient descent for linear regression iteratively updates the model follows: At round t t+ 1, with previous parameter E θ the exponentiated gradient algorithm updates it to 0:41 so that
02 exp( (2) D, ())
for all l E [d]. 0 = Σ, dτ, (xxpp22n1 It - -))
Note that each exponent 2(0,- x, - 2r, is the k-th coordinate of the gradient of squared error (((,,, vt), 0.) O. which yields the name of exponentiated gradient descent.
4

---

Under review as a conference paper at ICLR 2022
2.3 DYNAMICAL SYSTEM
Definition 2.4. Let (X, be a dynamical system where X' is metric space and f is mapping on X. We say (x,2²) X X is Li-Yorke pair if
lim inf dist(f (f (x). fx()) 0 and lim (fstt(
(X, f) is Li- Yorke chaotic if there is uncountable set S X' (scrambled set) such that any pair of points z * x' E Li- Lorko pair.
MULTI-AGENT PERFORMATIVE LEARNING: STABILITY AND OPTIMALITY
Having introduced multi-agent performative prediction, we show some basic property of our location-scale distribution map with mean squared error as a warm-up. Using the first order condi- tion and potential function argument, we show 1) the existence of performative stable point in our model (proposition) 3.1 and 2) the performative stability and performative optimality are equivalent (proposition 3.2) The proofs of both propositions are in appendix A
We first show the existence and uniqueness of performative stable point through a potential function argument. The first part due to the first order condition of convex optimization. The second part also use the first order condition, and deg (0)) = X (0) for all E [n] and [d].
Proposition 3.1 (existence). Given the family of linear predictive models with constrains θ mean squared error and multi-agent location Docation-scalt scale distribution map with parameters n, d, X, A, b in definition 2.2 0 on (O, D) is performative stable if and only if the gradient (defined in eq. satisfies dh ( (
) for all E [n]] and ls E [d] with 0% O.
Furthermore, if A is positive definite, there exists a unique performative stable point 0-, and 0 also global minimizer of the following convex function for all 9
(0)) = Σ ) A x00 20) A0 26" Σ> ErOO'
While model profile is performative stable does necessary mean the loss is minimized, the fol- lowing proposition shows that optimality and stability are equivalent in our setting.
Proposition 3.2. Given (O, f, D) defined in proposition 3.1 0' is performative stable if and only if Ø- is performatively optimal defined in definition 2.1
4 MULTI-AGENT PERFORMATIVE LEARNING: CONVERGENCE AND CHAOS
In section 3. we study the stability and optimality of location-scale distribution map with mean squared error. Now we ask when each agent myopically improves his predictive model through reinforcement learning but their predictions are performative, what is the long term behavior of the system? Can the system converges to performative stable and optimal point, behave chaotically?
We provide a threshold result depending on the learning rate and the collective influence Ln, Sec- tion 4.1 shows the dynamics converge to the performative stable and optimal point when when the learning rate is small enough. On the other hand, section 4.2 shows the dynamics can have chaotic behavior the collective influence T., large enough.
Now, we define our dynamics (0.)220 formally. each round, each agent accesses the data dis- tribution which influenced by their previous model, and updates his model through exponentiated gradient descent. Specifically, given an initial model profile 0,- O and learning rate profile : (M,.... nn), each agent applies the exponentiated gradient descent with initial parameter 0 and learning rate 77 > O: At round + 1 > 1, each agent i use D(0,) and estimates the gradient of the (expected) loss, g g(0)) defined in eq. and updates his model according to definition 2.3
0i exp(-m:0) (0.)
0: 01 = Σe= 0% expp-xxppe (0.)
for all 2 0, E [m], and & E [d].
(3)
5

---

Under review as a conference paper at ICLR 2022
We will use superscript to denote agent, i E [n], and subscript for time, 2 0, and index of feature,
k, L E [d]. Recall that the gradient of agent i's average loss is g'(0) = Σ figi (0). and eq. (3)
can be rewritten as
0 exp(- (0.))
e (g (8.)))))))))) (6.))
Finally, given 0* and E [d].
Σ 0 exp(- (0.))
Σ 8 (2
we define the support of 0 as S. [d] {k (0*) > 0}. and S. == [d] \ S Then 0 is an equilibrium fixed point) of eq. if
gi
9' (0"), for all [n], St
(4)
We say a fixed point of eq. (3) is isolated if there exists an open set of it so that no other fixed point is in the set. Additionally, the performative stable condition in proposition 3.1 equivalent to
gi (0 g0*)) and ()²) g for all E [m], k E S., S,.
(5)
Therefore, the set of fixed points of eq. 3 contains the performative stable point.
4.1 CONVERGING WITH SMALL LEARNING RATE
In this section, show when the learning rate of each agent is small enough the the dynamics in eq. 3 converge to performative stable point. Specifically, if the parameter of multi-agent perfor- mative learning (n, d, A, A) is fixed, the dynamics in eq. (3) converge to performative stable point when 77 is "small" enough.
By eq. 5 0 is a performative stable if the gradient in the support is no less than the average gradient. We call performative stable point 0 proper if the gradient of non-support coordinate greater than the average gradient: for all E [n] S., (0') g(()). The below theorem shows if the performative stable point is proper and equilibria satisfying eq. (4) are isolated, eq. (3) converges when max; ?ii is small enough and the ratio of n//n,; bounded for all and j.
Theorem 4.1 (Convergence). Consider a constant R. > O, and a multi-agent performative learning setting with parameter d, A, b. X such that A is positive definite, the performative stable point 0 is proper and its equilibria (defined in eq. (4)) are isolated. There exists 77 > 0 so that dynamic in eq. (3 with learning rate profile n converges to the performative stable point, lim 02 0-, if the initial state is an interior point and n satisfies max; T) S T), and max, n/// min; 7/ S R.y
Informally, when the learning rate r are small, 0 in eq. o can be approximated by solution of an ordinary diffcrential equation, @f where the initial condition is T(0) = 0g and
di 0 (t)
d
7)s 0f (T) of (i()))
(6)
|m>||
for all t > 0 E [n], and & E [d]. We formalize this intuition in the proof of lemma 4.4 Note that the set of fixed points of eq. (6 identical eq. (3) and satisfies eq. (4).
The proof of theorem verges to the performative stable point. Then we study the relationship between eq. and eq. (6) and prove the eq. (3) also converges to performative stable point.
has two parts. First we show the continuous approximation eq. 66) con-
From Potential Function Convergence of Equation (6) In this section, theorem 4.2 shows the dynamics of eq. (6) converge to performative stable point which will be useful to show the
convergence of eq. B
Theorem 4.2. all points satisfying eq. are isolated and A is positive definite, and 0(0) is in the interior of @", the limit lim; O(t 0* is the performative stable point.
Theorem 4.2 can be seen as the continuous version of theorem 4.1
Compared to theorem 4.1 theo- rem 4.2 does not require that the performative stable point is proper, but theorem 4.2 also implicitly requires the ratio of learning rate between any two agents is bounded.
To prove theorem
we prove lemma 4.3 which shows that + eq. (2) is potential function for eq. (6) so that time derivative of Φ is decreasing for all non-fixed points. Then, in the proof of theorem 4.2, we further prove that the dynamics in eq. ( converge to performative stable points
when the initial condition (0) is an interior point. The proof is similar to a proof in Kleinberg et al.
2009), and is presented in appendix B

---

Under review as a conference paper at ICLR 2022
Lemma 4.3. Given a solution of eq. (6, the time derivative of 4 in eq. eq. (6, and negative at all other points. Furthermore,
②2 is 0 at fixed points of
2
d 1 (0(1)) dt
-1 2E, Th E, ArTI
Σ Xem 2 figi gitl
min; A
(E(())
2 ni E, Am
From Approximation to Convergence of Equation Given the convergence of eq- we show the dynamics of eq. (3) also converges to performative stable point. The argument has two stages. We first show given any neighborhood of performative stable points D, eq. (3) will hits D and stay in D in finite amount steps in lemma Then lemma 4.5 shows that eq. converges to performative stable point which completes the proof of theorem|. 4.1
Lemma 4.4. Given any open set D E O that contains the performative stable point, there exists Th small enough so that for all 0g O there exists so that 0, D for all
The proof is based on standard approximation result of numerical solution to ordinary differential equations, and is presented in appendix [
Lemma 4.5. Let 0* is the performative stable point and D is a small enough neighborhood of Ô Besides the condition in theorem 4.1 if the initial condition of eq. (3. Oo is in D and 0, E D for
all t 2 0, the limit of eq. is the performative stable point lim O, 0+
The proof uses the fact that the right-hand side of eq. (3) decreases as the dynamic converges to the fixed point. Therefore, even though the learning rate profile is fixed, the error between eq. (3) and eq. (6) vanishes as they converge to the fixed point. We present the proof in appendix D
4.2 CНAOS WITH CONSTANT LEARNING RATE
Now we want to ask the converse question in section 4.1 Do the dynamics in eq. (3) still converge, if the learning rate is fixed, as the number of agent increases? Alternatively, do the dynamics converge when the agents have overwhelming influence on the data distribution?
Theorem 4.6ssoos that the dynamies is Li- York chaotic when Ln Eg A is large even with d 2. Note that large Ln may be due to a fixed number of agent which have overwhelming influence, or the number of agents is large. The later case implies for any small 1). no matter how cautious the agents are, as number of agent increases the chaos inevitably occurs.
Theorem 4.6. Given a multi-party induced location scale family distribution with A. b, d = 2, and a common learning rate 1) 0, all agents use the exponentiated gradient with a common learning rate 1) in eq.
3 and A is diagonally dominant, there exists a carrying capacity L* such that if T. Ei= > I the dynamics (0.) is Li- Li-Yorke chaotic and thus has periodic orbits
of all possible periods.
To prove theorem 4.6 we show there exists an uncountable scrambled set defined in definition 2.4 First we consider all agents start from the same initial model, and show the dynamics eq. can be captured by the following function,
Vr []
x + (1 x) exp(u(r- - v))
with proper choice of E I and E R. Note that is equilibrium, and controls steepness. First, when all agents start from the same initial model, 0j = O, for all E [n]. and use the same learning rate 17, their models are identical for all t 2 For all t there exists 0 so that 0; 0, for all i. Additionally, since d = 2, we can use a single parameter to encode a linear predictive model with constraints. Given 0 E θ A2, define p(0) 0, [0, 1] and omit the input 0 when is clear. Thus, we can rewrite the dynamics as pt = p(O,) which are one-dimensional dynamics on [0, 1), and P++1
Pt
We set
P++(1 nlo (8,) 0116.55
(1 + L)(22 - -A2,1 + (b) - b2)
aLL) 22 (1 + L) (A111 AA, -221 + A22) and B(L)
(1+ L) -A1, A2,1 + A2,2)
7

---

Under review as a conference paper at ICLR 2022
and write on a(Ln) and Bn B(Ln). By direct computation the dynamic of pt is Pt+1 S (pt)
where an encodes the update pace and 3, is an equilibrium of the dynamic. We further set Ao == Ag.3-Ag,1
A1.1 A1.2 222 and Ó(L) :- - which converges to zero as L oo. If A is diagonally dominant (L) is positive and increasing for all 2 0. Additionally, because A1.1 A1.2 and
A2. 12,1 are positive, we permule the coordinate so that 8xx (0, 1/2]. With Li et al.
1982). the lemma below implies existence of period three points and the proof is in appendix
Lemma 4.7. If 9oo E 1/2), there exists a constant L > so that if L 2 L', there exists trajectory Zg; 11 T2. and Vi with (a(2),3(L)(z.) 2i+1 such that T3 To 21-
Proof of theorem 4.6 First by lemma 4.7 for all I, > I,", there exists trajectory Ho, T1, T2 43 so that Z3 < zo < 31. Additionally, existence of such trajectory implies the exists of period three
points by Li al. (1982). Finally, by the seminal work of & Yorke (1975), it implies that the map
Li- York chaotic.
SIMULATION
0.8
0.8
0.8
0.2
02-
0.2
100
80
100
20
40
60
80
100
(a) (14, 0.001) without noise
(b) (1.4, 0.05) without noise
(c) (14, 0.05) without noise
3.0
1.0
1.0
0.6
0.5
0.6
0.4
0.4
0.4
100
m 100
1.00
0.0
0.0
0.0
(d) (14, 0.001) with noise
(c) (1.4, 0.05) with noise
(f) (14, 0.05) with noise
Figure 1: Here we plot the temporal behavior of Pt starting Po 0.2 for 100 rounds under various
L and 7), and noisy estimation of gradient of mean squared error with m samples. The top row (figs. to Icb present different combination of (L, 17), and bottom row (figs. 1d to If) consider the gradient is estimated from m = 10 and m 100 samples.
Now we simulate the one-dimensional dynamics in eq. 7 and collective influence L.
8 of one agent with different learning rate
We first define location-scale distribution map. Let the feature x1, X2 and noise are mutually independent Gaussian distribution with zero mean, and the variance are E[x3] E[xa] 1. Finally, 8 0. Therefore,
3, E [[ 7, and
0 and b = A + [[xxx
0
A = E xx
=
7
8

---

Under review as a conference paper at ICLR 2022
Given learning rate "7 > 0, and collective influence L, have aLL) 20m(1 L), and the performative stable point (()) = 0.7.
The top row of fig. I shows the temporal behavior of pt under different (L, 17). The bottom in fig. demonsttratss our (convergent and chaotic) results are robust even when the value of gradient is noisy. Specifically, we consider at each round I, instead of gi (0.) - g (0.) 2(1 + 101,-11, A10 the agent replace and b with empirical moments on samples. This process can be seen as a stochastic exponentiated gradient descent which uses a stochastic estimation of the gradient.
We can see chaotic behavior happens in fig. 1c with L = 14 and r = 0.05, and such behavior persists in fig. when the evaluations of gradient are noisy. On the other hand, when the learning rate is small enough (figs. la and [bb the dynamics converge to the performative stable point 0.7. Furthermore, figs. and the dynamics converge even with noisy estimation of gradient.
Finally, fig. 2 shows the temporal behavior of the loss. Under the same setting as fig. Ic fig. 2b shows not only the temporal behavior Pt is chaotic, but also the mean squared loss. On the other hand, under the same setting fig. la fig. 2a shows convergent behavior of loss.
100
(a) (14, 0.001) without noise
(b) (14, 0.05) without noise
Figure 2: The temporal behavior of the total cost for 100 rounds under various 1).
CONCLUSION
We introduce framework of multi-agent performative prediction and investigate whether classical reinforcement learning algorithms can converge or behave chaotically depending the collective influence the agents model and learning rate. However, we view our example as only scratching the surface of the work of multi-agent performative predictions.
Our framework leads to several new theoretical problems. particular, would be interesting to understand whether this threshold is generic and if our results still hold on other reinforcement learning algorithms or other general multi multi-agent distribution maps. Our framework also provides a new viewpoint several applications. One natural application is strategic classification. Hardtt al. (201)) this context, our framework can be seen as strategic learners in strategic classification problem where both data and classifiers deployed models in conventional strategic classification, which is not captured in our multi-agent location-scale distribution map. It would be interesting to investigate our dynamics in the context of strategic prediction. Another application is pricing trrateyy/prediction, where multiple companies predict the demand function and set their prices.
strategic. However, the features also respond to the
Both our digital and real-world environments are increasingly under the influence of or ever more powerful and numerous MI. systems. As these algorithms trigger actions that change the state of the system that produces their joint input data (e.g., Al-triggered ads shown to users affecting their behavior, or automated trading systems affecting stock prices, etc), they are effectively forming closed loop systems and can no longer be understood fully in isolation. As we show in this paper, even fairly simple and innocuous such settings can exhibit phase transitions going from optimal behavior to chaos. We believe such phenomena that this paper sets out some useful building blocks by bringing together optimization/perfrmmnnc analysis with Lyapunov theory and chaos theory.
worthy of careful investigation and we hope

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work showcases the possibility of competing prediction algorithms leading to instability and chaos. Extra steps should be taken, whenever possible, so that related systems operate within the range of parameters leading to stability. We hope that our work helps both by identifying potential threat ML systems as well as providing some guidance on how to counter or minimize it.
REPRODUCIBILITY
All of our theoretical results are stated fully, including previous definitions and results on which they are based. They are accompanied by proofs, either in the main paper or in the appendix. The setting of our simulation results stated fully in the main paper.
REFERENCES
Gabriel P Andrade, Rafael Frongillo, and Georgios Piliouras. Learning in matrix games can be arbitrarily complex. In Conference on Learning Theory (COLT), 2021.
James P. Bailey and Georgios Piliouras. Multiplicative weights update in aero-sum games. In ACM Confernce on Economics and Computation, pp. 321-338, 2018.
David Balduzzi. Wojeiech M Czamecki, Thomas W Anthony, Ian M Gemp, Edward Hughes, Joel Z Leibo, Georgios Piliouras, and Thore Graepel. Smooth markets: A basic mechanism for organiz- ing gradient-based learners. 2020.
Peter I. Bartlett. Learning with slowly changing distribution. In Proceedings of the fifth annual workshop on Computational learning theory, pp. 243-252, 1992.
Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Grzegorz Kosiorowski, Michal Misi- urewicz, and Georgios Piliouras. Follow-the-regullaiieee--ee routes to chaos in routing games.
ICML, 2021.
Yun Kuen Cheung. Multiplicative weights updates with constant step-size in graphical constant-sum games. In NeurlPS 2018, pp. 5532-3542, 2018.
Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. In NeurIPS 2020, 2020.
Yun Kuen Cheung and Yixin Tao. Chaos of learning beyond zero-sum and coordination via game decompositions. In International Conference on Learning Representations, 2020.
Yun Kuen Cheung, Stefanos Leonardos, and Georgios Piliouras. Learning in markets: Greed leads to chaos but following the price is right. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence IJCAI 2021, Virtual Event Montreal, Canada, 19-27 August 202/, pp. 111-117. ijeai.org, 2021. doi: 10.24963/jjai.222211 2021/16.
Thiparat Chotibut, Fryderyk Falniowski, Michal Misiurewicz, and Georgios Piliouras. The route to chaos in routing games: When is price of anarchy too optimistic? NeurlPS, 2020.
Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6372-6381, 2017.
Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-dependent distributions, 2020.
Lampros Flokas, Emmanouil- Hamaanoul--Vaslleios Vlatakis Vlatakis-Gkaragee GaaakiiuGaar,,,uuiis,, Thanasis Lianeas, Panayotis Mer- tikopoulos, and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
10

---

Under review as a conference paper at ICLR 2022
Angeliki Giannou, Emmanouil- Vasileios Vlatakis- Gkaragkounis, and Panayotis Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. COLT, 2021.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifica- tion. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 111-122, 2016.
Zachary Izzo, Lexing Ying, and James Zou. How to learn when data reacts your model: perfor- mative gradient descent. arXiv preprint arXiv:2102.07698, 2021.
Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. information and computation, 132(1):1-63 1997.
Robert Kleinberg, Georgios Piliouras, and Êva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the forty-firtt annual ACM symposium on Theory of computing, pp. 533-542, 2009.
Anthony Kuh, Thomas Petsche, and Ronald Rivest. Learning time-varying concepts. In NIPS, pp. 183-189, 1990.
Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen, Stratis Skoulakis, and Georgios Pil- iouras. Dynamical analysis of the cip-1559 ethereum fee market, 2021.
Alistair Letcher. On the impossibility of global convergence in multi-loss optimization. In Interna- fional Conference on Learning Representations, 2021.
Tien-Yien Li and James A. Yorke. Period three implies chaos. The American Mahematical
Monthly, 82(10):985 992, 1975. ISSN 00029890, 19300972. URL http:// www. istor.
oxc/stablee2318254
Yien Li, Michal Misiurewicz, Giulio Pianigiani, and James A. Yorke. Odd chaos.
Physics Letters A. 87(6)227--273,
1982. ISSN 0375-9601. doi: https///oo..or//00
001600375-96001129996222 URL httt:///wwwwcceeeeeeeeeeeeee wtt.://eett.comccceeeeeeeeee Aar.cieepp11/31559018889595
Celestine Mendler-Dünner, Juan C Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic optimiza- tion for performative prediction. arXiv preprint arXiv:2006.0663 2020.
John Miller, Juan C Perdomo, and Tijana Zmic. Outside the echo chamber: Optimizing the perfor- mative risk. arXiv preprint arXiv:2 2021.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights up- date with constant step-size in congestion games: Convergence, limit cycles and chaos. CoRR, abs/1703.01 133, 2017. URL http::t:://arrt
wwwp//gg//s....... 01138
Ioannis Panageas, Georgios Piliouras, and Xiao Wang. Multiplicative weights updates as a dis- tributed constrained optimization algorithm: Convergence to second-order stationary points al- most always. In International Conference on Machine Learning, pp. 4961-4969, PMLR, 2019.
Juan Perdomo, Tijana Zmic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pp. 7599-7609. PMLR, 2020.
Nelson Vadori, Rahul Savani, Thomas Spooner, and Sumitra Ganesh. Consensus multiplica- tive weights update: Learning to learn using projector-bass game signatures. arXiv preprint arX1v:2106.02615, 2021.
11

---

Under review as a conference paper at ICLR 2022
A PROOFS AND DETAILS IN SECTION 3
Proof of proposition 3.7 First under the mean squared loss function, each agent i's decoupled per- formative loss function ((6', 0¹) is convex in O'. Thus, for linear predictive model, we can apply the KKT conditions definition 2.1 so that collection of predictive models f @n is performatively stable if and only if for all i [n|] & E [d] with 0% O. a E(0', 0") S dee where 0' = Therefore, with
((0", @*) for all E [d]
0 is performative stable if
(0)) (i())
holds for all i E [n] and & [d] with 0% 0.
With eq. we now show that there exists unique performative stable point 0 by proving that 1) eq. is strictly convex, and 2) 0 a minimizer of First, to show strictly convex, is sufficient show the Hessian of & positive definite. Because & is quadratic function on O", the
Hessian of & is constant matrix in gudxnd By the partial derivative of eq. 2 for all i. E [n]] and (k a0ta0! Φ 2 if + and (V- ik 2A, A).
k, E [d]. we have (V
8
Let L E Ruxa with Lej 2dz if + j and 2A,(1 + A;) which positive definite because A for all E [n]. Then, the Hessian of + is the Kronecker product of L and A,
21 +1)4
2A1AA
V2Φ= =
LOAAA
2
2A, (1+
Because and are both positive definite, Hessian is also positive definite. Therefore, & strictly convex, and there exist a unique minimum of in the compact set O". Now we show 0* is performative stable if and only if 0* is minimizer of Φ. By the first order condition and the partial derivative of eq. (2). the minimum of eq.
2 at 0* if and only if g (0*) S g (0*) for all E [n] k, E [d] with (8*) { > 0. Therefore, 0* the minimum of if and only if 0* a performative
stable point.
Proof of proposition 3.2 Given a profile of models 0, the total cost is
Σ ( (0)') =
IR ((x))) - 0¹ x
Σ Ago0 0:) 00) +
Σ
E
0
which is a convex function on Ø E O Additionally,
a th0
E( = (1+ (1 ( +
Σ
Xigi (1 g2
which is the gradient of decoupled performative loss scaled by (1+ Thus, we can apply the KKT conditions and the minimum happens if and only if eq. (9) holds.
B PROOF AND DETAILS FOR THEOREM 4.2
Proof of lemma 4.3
By chain rule,
d 4 (()))
i (ō(t)
d
Σ
O(t,
(10)
di
00 [d]
di
kEjn]
the time derivative of the potential function is zero if the dynamics is fixed point of eq. (6)
12

---

Under review as a conference paper at ICLR 2022
Now compute closed form of the time derivative and show the derivative is zero only if the dynamics at fixed point of eq. 66) Here we omit the imput to simplify the notation.
Φ (((1))
Σ
of (1)
of(1)
gl (+())) (by eqs. 6 and TO
dt
00
|m]]
i
Σ Amn Σ
(9k) 02
Σ figt g
(by the partial derivative of eq.
1
Σ
Am Σ
0 (29ia 2(gh)))
(because Σ, 1)
2||m||
-1
E
Am
Σ
0.01 -gi)²
2|/m/111
AJEI
Now we bound the time derivative.
211/7/11
Σ Ammi
(((1))
di
Σ
E
Amn - -g/
= 1)
VEIM]
Σ
(by Cauchy inequality)
IV
Σ
Σ Sa - si)
(by triangle inequality)
(E(m)
LE(d]
Therefore, & (+(((t))= only if 0% -Zeini viot) fixed point of eq. 66.
0 for all [m]] and &s e [d] which is
We can further simplify the bound by E. Because Ei,- Amm fig gf
>
(min; Amn) Es (()) (min: Acn)) [I((0)) (()) 2Σ, ni L, Avts (E(0)
min dcn
O
Proof of theorem
When the fixed points are isolated satisfying eq.
44. by lemma 4.3 the dy-
namics in eq. 6 converges to a fixed point of eq. (6). / E e". Because 0" is fixed point, for all i [n], [d].
(0 (0)()) -i = (0r) Σ (0 (ia gi = 0
By proposition 3.1 the fixed point condition implies each coordinate of the gradient of loss in support are identical, of (0-) = g' (0*) for all i and & E S,. Thus, if the fixed point 0 is not performative stable, there exists and x with (0*), 0 so that g (0') ('()). Furthermore, exp(-mg') (0+) Ex exp((nng;(*)) We can pick small enough and define
U. = 10 exp(-mggt > Σ 01 exp(-n.9)) +
(1I)
which contains 0+ and is an open because ğ and the exponential function continuous. Since ē(() converges to 0 as t -> oo, there exists time te so that for all 2 t.. H(t) E U.. However, (()) E U. and @(1) an interior point, we get d de (1) > 0 by eqs. (6) and 11 Therefore, (t) is positive and increasing for 2 tc. We reached a contradiction because of (t) (0*) = 0.
Therefore, 0¹ is performative stable point.
13

---

Under review as a conference paper at ICLR 2022
C PROOF ANS DETAILS FOR LEMMA 4.4
To prove lemma 4.4 show the dynamic eq. can be approximated by eq. 66 and the error vanishes as 7) decreases. Thus, we can show the dynamic can hit arbitrary neighborhood of the performa- tive stable point. We further use & to show the dynamic will stay in the neighborhood. Below we state two ancillary lemmas to control the error of our approximation.
We define an error vector E(() E Rnndd between eqs. (3 and (6)
so that
0 exp(n 9k)) 0 n:Ch
ne (0) = Σ, ff exp(n: 9f
We omit the input 0 of E and ē, E(,)) when there is no ambiguity. We show if the the error vector is small, & is decreasing in dynamics eq. (
Claim C.1 (Approximated potential). There exist Ca. that for all and 0g O", the difference of eq. ( on eq. (3) satisfies
min; Nn 11E:1 + max Aon max
क (0.++)) ((,)) S 2 E dmn
(k((
|| + dcs 0 0
i,k.0
Claim C.2. If max; yi is small enough and satisfies eq.
12
there exists a constant so that
let 0 s C for all i E [n²] k E d.. and 0 e 0
The proofs of these two claims are based on first order approximation.
Proof of claim C.7 By the partial derivative of eq. 2 we have 00L00
(()) 21, if i
and
(()) 2A,(1 + Ar) Thus, the second order partial derivatives of O can bounded by the twice C4 == max, >, + 1) maxx, Ar,, By Taylor's expansion, we have
86 88
((0(1)) ((,)
<V.(O.) (0+.1 6.) + 2C2 2
800) 1) (0.) + ne(((())) + &C,, (
+
S Σ
iE kE|d]
(by the partial derivative of eq. (2)
= E
Amegiaei + Aonoi + +CCC 0011
ie RE|M]
Exmiliaa )
-1 5 2, Am
Σ
Aoiiiiat &Cs 1041 - 0ill (by lemma 4.3
iE(m).EE[d
Therefore, we have
((0+1)) -(())))))(())))))))) min: X312
112 + max A max (0) -|)ll + dccs 0..1 - -0,11-0111 0.1,
2 Ae7
i,k
which completes the proof.
Proof of claim C.2 By if is small enough and satisfies eq. 12 we have (g - gf < 1, and
0g + v1:0% (g' of) 0f (3'- -g)) ) < of + 0 (g' gf 5 Additionally, with { (g' gt)) we can rewrite
o (g' sf)² for all i, k: and 0 O
# < ":0" (0' - met < 0% + 2 22 (g' -gi
14

---

Under review as a conference paper at ICLR 2022
Therefore, the error can be upper bounded as
n E - 0 + mEt + 5n gi)²² - (0% + m = 2 0 gi)²
e
Σ 0j 7:
because Σ, 07 and Σ cl 0. For lower bound, we have,
n 0f + nk + (5" 0i}² (0% + mett) 2 -(6 + n:Et)
0g + m.hh
emj
Σ
0i - gi)²
2
If we set == e emax 0 Σ 2/6'('' , because In I 17:2 lo S 1 by eq.
12 and
0g 2 1, we have (0) C.
Proof of lemma 4.4
Because D is open, we set D' that 0- D'. D' D, and
Su (0))
1/2 ögD (00). We will pick 7h small enough that 6(+1 D for all
O, E D' C D. The proof has two parts: we first show the dynamics eq. 3 hits the set D. Then we
prove eq. 3 stays in afterward.
By theorem 4.2 there exists T so that Ō(() E D'. Now by Gronwall's inequality we can set 17, small enough so that 01/l E D. Formally, given the dynamics in eq. (3) we define right-continuous step functions (t) [ee and E(() = E(({e)) for all 2 0. Then the dynamics in eq. 3 can be written as
(t) - 02 = Σ 11 ,,,,) Σ (..) + r(.c 176 1/ ()(ss) + me (s) ds
==0
s=0
On the other hand, the solution of eq.
(6 can be written as
O (0) = 7h
M /. 1iih
ds (1(s)) ds =n ( ci (1(7l())) ds
Because & continuous and 2 is compact, there exists > so that 4 is I-Lipschitz with respect to one norm for all i and k. Thus, the difference between above equations is
0% (4) 02 (1mlll)) Sm L' [((((())) ((((v))) ds + ni S (s)
Lpl. J |0(0) H(n>) ds + n²Ct (T-Lipschitz and claim C.2
Therefore, by Gronwall's inequality and ni S n, we have
((t) -((1m)11) s nnndL J |((s)) क {(ml))))|
||, ds + (n.) < (n=) adCCeenndl
Because ((T) E D', we can pick n, small enough so that ((7/[1/])1) = [r/ilnll E D and @00 ((/mm)) < infggn (0)).
Now we show the second part that 0, E D for all / 2 [T/1|//]]- First, with claim C.1 we will prove
that the potential function is decreasing for all 0, & D' when n/ small enough. We estimate three terms claim C.1 separately. First, because 0* D' and 6m) I is compact, min ||{(()]l
[]
exists. Then min, 22 2Σ. Xmhh
| = 2(max; 9/) By claim C.2 max; den max, ; 1o (0) ||]]] =
O(max; )) Finally, &Ca 0 0. [ 0(mxx ). Therefore, there exists 7) small enough so that the potential function ((0++1) (0,) < 0 for all 0, & D' and Therefore ((0)) <
min ø (0)) for all > [F/l|/]] which completes the proof.
15

---

Under review as a conference paper at ICLR 2022
D PROOFS AND DETAILS FOR LEMMA 4.5
Lemma shows the value of is decreasing in eq. 6 and the decrease rate lower bounded by
the one norm of g. Thus, if we can show the error between eq. (3) and eq. 6 is bounded by ||ı||
have the value of + is also decreasing eq. (3) The main challenge is that because E(Ø*) 0,
we need to control the error as converges to zero but 17. is fixed.
We first show three ancillary claims, claim D.1 to D.3 Claim D.1 show the vanishing components
of 02 decrease rapidly once the dynamic is in D. Claim D.2 and D.3 show the supporting component
also decrease once the vanishing components are small enough.
Given (n, d, A, A), we define the following constants C1 := 1 max,,
l C2 := (
C3 == ed max C2). and C₁ == max, (, + 1) max AR,-- We require the maximum learning rate is bounded by 7/ which satisfies the following conditions.
1
max 0.
(0) S 2
(12)
T/ ndC3s max [E(0)]1: 1
(13)
Additionally, given the bound of learning rate ratio,
max; Th min,
I Ro, we requires
min; X2 16 E, A
4
R
min C's max; (Ae) max |gl dCs
(14)
max ni Note that min of can pick small enough so that the following conditions holds.
is less then the right hand side of eq. 14). On the other hand, by lemma 4.4 we
min (0)) S min of
(15)
2 kEE.
kE(n)
We first show for all i and E 5, fi decreasing and converges to zero exponentially fast as f increases. Because Ø- is a proper performative stable, {ee) - = e - (6") >
(m) for all and l E Sr. We take 7/,, 61, and D small enough so that for all 0 E D and all learning rate profile v) with max 17, S 77,
not < (1 - e1) Σ ofe mot iiiiie [n], S.
(16)
Claim D.1 (Vanishing components). Given na 61, and D in eq. 16 if E for all t 2 0, for all i [n] and S,, 0% (t) is decreasing and for all 2
S 0f S 06
Proof of claim L.I. By eq. (16), for all t 8 Therefore, 0f decreasing, and 0f S 0b
0i E, Fú expl 9:9..))
expl mi
(1 ci 0
Claim D.2. There exists a constant C3 such that for all Ø E e with 81 > 0 so that [E((0)] 2 2v5,, and (0) < for all E [n] and k E S., then
(0)) S Cs
(17)
for all i E [n] and le [d].
Claim D.2 shows the one norm of is much bigger than the vanishing components, the error term e can be bounded by the |Е Moreover, claim D. ensures that the vanishing components decrease rapidly, the condition of claim D.2 readily holds.
16

---

Under review as a conference paper at ICLR 2022
Proof of claim D.2
Given @ and ò1 > that satisfy the condition, first show two inequalities to for supporting and vanishing component respectively. For a vanishing compo-
bound (g' g
nent & Si,
max 1
loft
10 - g - 4C1 61 S C
(18)
Then for a supporting component E Sy, with eq. (15) we have
1
2
(g'0' - -
(,L6ED 0f (ol(g' r min; & (0*)
SA < C2l
(19)
Now we use above two inequalities to approximate eq.
3
For nominator, because + x S
exp(x) < +1+++ + 5 for all æ S 1, 02 exp(na 9kl) 2 0 +m (g' g = of + On the
other hand, because T7: (g' - g I 1 by eq. 12 02 ( - 9k)) - 0f + + 50 - -
By eqs. (88) and (1)). we have
0 S (e
0g mi z 2 max max(Ci, C2)
(20)
For denominator, we sum over eq.
20 Because Σ, 0 = and Σ, 0g g = 0, we have
S
Σ 0je (0' of)
5 2 max
ed
12
(21)
Given E [n] and & E [d], we apply the above equation to eq.
(3
For upper bounds, we have
0% exp(n: 9h))
(O.)
02,x mi
Σ, 0j exp(1: -gi)
, moi((d) - -0 m.Ei,
(by eq. 21
e emax C1,, C2) 1111
(by eq. 20
For lower bounds.
0g explpxl0 -k)))
n/. ((,))
0₂ n:St.
Σ, f3 exp(1%: 1/ (g' - 9il)
0₂ + +niEi,
0i - S/.
(by eqs. (00 and 21
1 ed max
n P1
ed (Cixx(Ci, C2)
2 - (0i + m
(1/(1 x)) 2 x))
2
2 ed max 22)
0 S 1 and n.tk S by eq. 12
Therefore, with C3 ed max O2) we finish the proof.
Claim D.3. There exists 62 > 0 so that for all 0, E T and 61 > 0 so that (g())) 2 2 and
(o.)) S 8, for all i [n]] and h E 5,, then ((0++)) +0.O)) S c2 +=
Proof claim D.3
By claim C.I
min; XP11
|E + max A max gf (0) || + dC 10 8. 1
((0.+1) ( < 2 2 Amn
k
We can bound the later two terms by claim D.2 For the second term, || S ndCCa E. For the third term,
|0+ - 0.11
(nlEi Cani (E
<ax na El + ndC's max oi EE.
2ax ||
( (by eq. B3
17

---

Under review as a conference paper at ICLR 2022
With above inequalities, by eq. 14), we have min, Aing
TE, Aoy
>
max, don max ,,, (0) and
min: Ann 4d max; vf. Therefore there exists a constant
A.
min; AZTR
max don max lat IndCa - Cd max m/ > 0 i,k,
62 = 2 AmTi
so that ((0++1) - ((.) -(().)))((())))) < -22 1E:1
Proof of lemma 4.5 To prove lim 0 = 0-, there are two equivalent ways to measure the progress, besides 0 0" ||. First because 0' is an isolated fixed point of eq. 6 0, converges to 0 if and only if lim E Ö. On the other hand, because + is strictly convex and and 0 is the minimum point, 0g converges to Ø- if and only lim; ((0.) = ming (0). With these two equivalent conditions, given any > 0, there exists 8 0 so that ||0 0- || when
{ 0 0
0 E V/8
$(0)
max G
Therefore, it is sufficient for us show for all 8 > 0, there is ts so that O V. for all t tg. With technical claim DlaimmD.[jee [o.]to/... D.2 our proof has two parts. First we show that the dynamic hits Vg. Then, the dynamic stays Va.
For the first part, given 8> O and O < C < 1, by claim there exists Ti such that each vanishing component [6i,ul S C for all t 2 Tı. Then by claim D.3 there exists T2 Ti such that
11 11 S C8. Otherwise, the value of & decreases by a nonzero constant 62 E 2 Ce252 > 0 at each round which contradicts that the minimum of bounded.
For the second part, if ||ε:|1 wise, there exists
C5 < 5 for all 2 T2. then we finish the proof. Other- 2 T2 so that || S C8 ||E/+1ll1. Now we prove that (0 <
max S8 (0)). Because the difference between 0,-1 and 0, is ||0,+1 0,1l1 S
max; mill= + max; v/ || II < 2 max; m1l when n, is small enough, and E is a Li-shccciitz ① for some constant Le in one norm, we have
C8 < +11+ & 11 + 1 - -E11 $ 11 + 2L max max 11 S 8,
(22)
when C' is small enough so that C(1 + 2Lg max, mH) S 1. Therefore, ||E+1]]1 S 8 and 4 20 S maxx:ij )) 58 (0'). Finally, because K S C282/4 for all / 2 r + 1, by claim D.3 the
potential function is decreasing for all t 2 T + 1, unless || I C8. Both make the potential function less than max ; 1 sa ((0') which completes the proof.
E PROOF AND DETAIL FOR THEOREM 4.6
Proof of lemma 4.7 Define Pι(x) = (L) (((L)))))) which is increasing for all L because al (L) >
O. With PL, ((()))(())=)) = z =+(1-1] (x))) Take x1 (L) = =1 := 1- 1-1/a(L), x2 = 222 :=
(L)), and (L) 33 := (((L),)12((2(())) We will define xo (L) later. We will
omit and use Ii, 22, and T3-
To define xa (L), we set v(L) = /(L)/2, and want to show
fa(1), > x1,
(23)
which is equivalent (a(L) 1)(1 - v())) exp( PL (PL())))) < y(L). When L is large enough, have B(L) E (20x= 48x, Additionally because a(L) O, we have Pr(y(L)) -fo(L)8(L) <
(L))3 Therefore, we have (a(L) - 1)(1 =(L))eel < a(L)e-a(L)) a < 8x <
(T.) when T. is large enough, and prove eq. 23 On the other hand, because ((L) f and
18

---

Under review as a conference paper at ICLR 2022
(L( 0, we have (B)L)) ((L) < 2 +1). Moreover, (8x0 < 1- - a(L)>
holds when L is large enough. These imply
(B B(L) < (1)).
(24)
Combining eqs.
23 and 24 by intermediate value theorem, there exists 2o such that
fa(t)))(1)(00) = 21 with y < zu < ((L) < ø1-
(25)
Now we show I3 < T0- With (L) = L/) and < 2j < 1, we have 22 = (E)) = Because 300 < 1/2, when large enough, xn xI())
a(L) (x1))
exp())
1 (L) ((2((L)) + 3) and, thus, (11 a(L) _1)) Therefore, have
(3 ((L)
32 S (L)) exp -a(L)
(26)
Finally, because P2(12) 2 P2( -B(1), we get
22
x3 (== 5
22 + (1- x22) cxp( (a(())))))))
42 cx))(((()))(())
1 (=())((((L))) -1)
<o)cxp(a(L)3(E)
(since cxp(a(L))(L)) when L is large)
Ca(L)exp (a(L) ((L)) 3
B(L)
(eq. 26)
(L)(L) (((T) 2 1)
1
=.. exp
Finally, because 930 < 1//2, I3 converges to 0 when T. is large enough. Therefore,
T3 < y < 20.
(27)
By eqs.
25 and
27
we have 33 < 4o < Ij which completes the proof.
19


Reviews:
[{"review_id": "p2sYdgV0Vgn", "reviewer": "Reviewer_xAh2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths:\n\n(1) The problems and settings are presented clearly, the results and intuitions are also explained without obscurity. The paper is well written and easy to follow.\n\n(2) The results look correct and good as far as I have checked. As claimed, this is the first time \"where such formal chaotic results are established in settings related to performative prediction and supervised learning more generally\". I think this paper makes a reasonable contribution.\n\nweakness:\n\n(1) The technical novelty and difficulty seem restricted to me.\n\n(1a) The first main result of \"using small learning rate EGD is stable\" is kind of a standard result as expected, and also the techniques are based on standard analysis (potential functions and approximating continuous gradient flows).\n\n(1b) The second main result of \"using large enough learning rate EGD is Li-Yorke chaotic\" is also similar to existing work, e.g., the observation of EGD is chaotic in other games (Palaiopanos et al., 2017). The analysis is based on similar idea of constructing a recurrent behaviour with period three. \n\nAs far as I can see, the main difference and novelty is to apply those relevant techniques in performative prediction, which is a bit different with traditional supervised learning. However, performative prediction itself is also a special kind of game / reinforcement learning, which makes the contribution seem not very insightful given we have existing observation of EGD is chaotic in other game settings.", "summary_of_the_paper": "This paper studied the different behaviours of using exponentiated gradient descent (Def. 2.3) in linear regression with different learning rates. The setting is called performative prediction, which can be viewed as a special case of reinforcement learning (after the model makes a prediction, the environment returns a feedback by changing the data distribution).\n\nThe main results consist of two parts, for small enough and large learning rates:\n\n(i) with small enough learning rate, the authors proved that the exponentiated gradient descent is \"stable\" (asymptotically converges to some global minimizer). The proof is based on standard analysis of studying a potential (surrogate/Lyapunov) function for the mean squared error, and arguing that the gradient flow vanishes only if the potential approaches $0$, which implies that the convergence of the flow. Then the discrete gradient update is approximating the flow well if the stepsize is small enough.\n\n(ii) if the learning rate is larger than some threshold value, the authors then showed that the exponentiated gradient descent became Li-Yorke chaotic, where it can periodically oscillate for infinitely many times. The main idea is to use Eq. (7) to characterize the dynamics, and show that under some conditions Eq. (7) induces a sequence of { x_i }_{ i >= 1}, with some recurrent behaviours as shown in Lemma 4.7.\n\nThe authors then verified the theoretical findings using simulations on simple examples.", "summary_of_the_review": "Overall, I think this paper makes a reasonable contribution, showing that the behaviours of using exponentiated gradient descent differ with using different learning rates. However, given there already exist observations and results about exponentiated gradient descent could be chaotic in several game settings, and the performative prediction studied in this paper is also a special game setting, I consider the contributions and technical novelty in this work on an incremental level.\n\n\n----update----\n\nI would like to thank the authors for the feedback. My main concerns are addressed and thus I would increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MN7GKmpBdC3", "reviewer": "Reviewer_RUeS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Main Review\n\nThe paper is clearly written and its main theorems are supported by proofs and numerical simulations.\nThe strength of the paper is that it extends \na relatively new model (2020) to a cooperative multi-agent setting. \nThe extension to the multi-agent case has both positive \nand negative results \n(convergence and chaos),\nand the authors provide theoretical justification for both occurances by leveraging \npast work on learning in potential games.\nThese results are already known for other classes of conjestion games, so the authors support the \nprevious literature \nby showing that they are also true for constrained linear models in this class of problems.\n\nWe agree with the authors that this work only scratches the surface of the in multi-agent performative prediction. \nThe model is an original and novel contribution (to the best of my knowledge), but the results are confirmatory. The results are mostly shown by previous work already since the model trivially has a potential function. So it is unclear to me if the work is significant for this venue.\nI also think some commentary on stability concept (the second part of definition 2.1) would be helpful towards motivating the significance of the work.\nHow does the multi-agent stability concept differ from the stability concept in (Perdomo 2020)? \nCan you point to the differences (existence, uniqueness or stability..) \nor what makes this class much more challenging to solve? This could be useful for future work in understanding when chaos occurs, for example.\n\nThe quality of the paper can be improved in some minor ways, especially by paying attention to details. \nFor example, the last equation on page 3, the pipe operator in the lefthand side is undefined. \nAlso, the use of \\theta_0 is different in section 2.1 and 2.2, and I think it can be confusing.\nSection 2.3 just consists of a definition and nothing else. Can you explain it or at the very least provide a reference?\nThere is a typo in the last sentence of section 3.\nPay attention to capitalization, and espeically in the reference list, where many typos can be found.\n\n(A minor comment on style: \nthere is a missed opportunity to \nmaintain the parallelism \nof \"convergence to chaos\" in your title\nin Figure 1 by \nsorting the figures in that order, ie putting (a) and (d) in the rightmost column.)\n", "summary_of_the_paper": "The paper analyzes the performative prediction setting (Perdomo 2020)\nwhere multiple agents perform gradient descent to converge to a performatively optimal point.\nThe agent are modeled by constrained linear predictive models which are used for linear regression.\n\nThe authors show that the learning dynamics \nconverges to the multi-agent performatively stable point\nfor small learning rates. \nThe stable point coincides with the optimal point where the sum of the agent's losses are minimized. \nThe requirement for convergence is that the hessian of the loss must be positive definite, which is satisfied by existence of a potential function.\n\nThe authors also show \nthat the dynamics exhibits Li-York chaos for large enough learning rates.", "summary_of_the_review": "\n\nOverall the paper has a central point by presenting a framework of multi-agent learning. The model is cooperative, so a potential function exists and learning converges for slow learning rate regime. \nA discussion section is lacking, in particular with regard to the significance of the work and results. \nWhat insights can be provided by the analysis from the paper?\nCurrently the conclusion section include mostly a list of future applications. \n\nThe claims in the paper are supported and correct to the best of my knowledge. The significance of the results is debatable but the model is indeed novel. The empirical data shows an example of chaos and two examples of convergence, with and without noise. In my opinion, the model is novel enough for me to recommend a 6, but the technical results are expected and perhaps maybe that can push it to below the acceptance threshold.\n\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KcAN9i4I6Kx", "reviewer": "Reviewer_jNt2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe framework of performative predictions is very interesting, with potential applications that are beyond the standard supervised learning methods. Its extension to a multiagent setting widens the  applicability of the framework in the real world.\nThe paper studies the emergence of instabilities both theoretically and empirically.\n\nWeaknesses:\n1. I am not convinced by some of the derivations:\n1.1. Proof of Prop 3.1 should be very simple but it is confusing. The authors refer to the \"KKT condition\" --which is itself confusing as the KKT are a set of conditions that have to hold together, not just one--, but it is not clear which one of the KKT conditions is referred by the inequality on the partial derivatives. What does it mean that the partial derivative on one component, $k$, is less or equal than the partial derivative in another component, $l$?\n1.2. In the second part of the proof of Prop 3.1, the authors use the positive definite Hessian to prove strict convexity, do they mean strong convexity?\n1.3. A performative optimal point (Def 2.1) is just a Pareto solution of the multiobjective problem (indeed it could probably be generalised to any convex combination of each agent's losses). On the other hand, performative stability is a global solution of the objective problem, and is a much stronger condition than the Performative (Pareto) optimality. Indeed, it is trivial to show that the former implies the latter, so I don't understand the comment before Prop. 3.2.\n1.4. In Eq. (4), the authors define the fixed point of (3) as the average gradient. Why is so? The argument at the end of page 5, in which they multiply numerator and denominator by the average gradient seems rather loose, since you could multiply both factors by any other value and still claim that this value is the convergence point. I think they have to formally prove that:\n$\\lim_{k \\rightarroy \\infty} g_k^i(\\theta) = \\overline{g}^i(\\theta) \\in \\Re^d$.\nPerhaps this apparently circular reasoning can be easily fixed by proving Theorem 4.1 before Eq. (4). \n\n2. Discussion of connection with related approaches is missing. \n2.1. The proposed approach reminds me of the replicator dynamics from evolutionary game theory, for which the emergence of chaos has also been studied. \n2.2. In order to prove performative stability, could the authors rely on the strong-monotonicity of the gradient and well known results for finite-dimensional variational inequality theory (see, e.g., Scutari et al., 2010)?\n2.3. Conditions on the learning rate for the chaotic behaviour of gradient descent have been studied in the literature. How the current results relate to these previous results? \n\n3. The simulations show oscillatory behaviour, but it is not clear from the experiments that this is actually chaotic behaviour. I would have expected to see at least sensitivity to initial conditions, and ideally negative Lyapunov exponents computed from the time series.\n\n\nMinor comment:\nIt is clear that the algorithm will converge for small enough learning rate, and it can oscillate or diverge beyond that threshold. Some motivation on why it is important to study the chaotic behaviour in particular would help to appreciate the impact of this work.\n\n\n(Scutari et al., 2010), Gesualdo Scutari, Daniel P. Palomar, Francisco Facchinei, and Jong-Shi Pang, \"Convex Optimization, Game Theory, and Variational Inequality Theory\", IEEE Signal Processing Magazing 35, May 2010\n", "summary_of_the_paper": "The paper introduces a multiagent extension of the performative prediction framework in which multiple agents try to predict the same outcome, which influences the outcome they want to predict. The paper then shows scenarios and conditions for stability and for chaotic behaviour.\n", "summary_of_the_review": "The extension of the performative predictions framework to multiagent systems is an interesting problem. and even the scenario under study with linear predictors and MSE loss greatly simplifies the analysis, I appreciate this is a first step.\nThis is mainly a theoretical paper, but some of the mathematical derivations have raised some questions.\n\nMetareview\n----------------\nThe authors have responded to most of my comments clearing my concerns on the derivations. I think that an experiment showing sensitivity to initial conditions is missing. Although the novelty seems incremental with respect to previous works, there are a few small innovations, so I am increasing my score to 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors extend the performative prediction framework of Perdomo et al. (2020) to a multi-agent, game-theoretic setting, and they examine how and when multi-agent performative learning may lead to performative stability/optimality.

The authors' results and contributions can be summarized as follows:
- They consider a multi-agent location-scale distribution map with parameters constrained in a simplex, and they study the dynamics of an exponentiated gradient descent algorithm (EGDA for short) inspired by Kivinen and Warmuth (1997).
- If the learning rate is small enough, the authors show that EGDA converges to a performatively stable point (under the same assumptions that guarantee existence of a convex potential).
- On the other hand, if the learning rate is large, the algorithm behaves chaotically.

The reviewers' initial assessment was mixed, but after the authors' rebuttal, some concerns were partially addressed and the scores of the paper were upgraded to borderline positive. On a point-by-point basis, the authors' result on the convergence of EGDA with a small learning rate was appreciated by the reviewers, but it was not otherwise deemed significant enough relative to existing convergence results for gradient methods. Instead, most of the discussion centered on the authors' result on chaos (Theorem 4.6), which was viewed as the most significant contribution of the paper. However, continued discussion between committee members revealed that this result follows directly from Theorem 3.11 and Corollary 3.12 of the arxiv preprint "A family of chaotic maps from game theory" by T. Chotibut, F. Falniowski, M. Misiurewicz, and G. Piliouras <https://arxiv.org/abs/1807.06831>, which is not discussed in the paper. [As was pointed out, the update map (7) of the paper coincides with the update rule (7) of the arxiv preprint, and the proof techniques are likewise identical.]

This overlap with previous work was considered a "big omission" and it pushed the paper below the acceptance threshold. In the end, the paper was not supported by any of the reviewers, so a "reject" recommendation was made.
Decision: Reject