Higher-Order Uncoupled Dynamics Do Not Lead to Nash Equilibrium - Except When They Do
Authors: Sarah Asad Toonsi
Jeff S Shamma
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning in games
Nash equilibrium
Uncoupled Dynamics

Abstract: The framework of multi-agent learning explores the dynamics of how an agent's strategies evolve in response to the evolving strategies of other agents. Of particular interest is whether or not agent strategies converge to well known solution concepts such as Nash Equilibrium (NE). In "higher order'' learning, agent dynamics include auxiliary states that can capture phenomena such as path dependencies. We introduce higher-order gradient play dynamics that resemble projected gradient ascent with auxiliary states. The dynamics are "payoff based'' and "uncoupled'' in that each agent's dynamics depend on its own evolving payoff and has no explicit dependence on the utilities of other agents. We first show that for any specific game with an isolated completely mixed-strategy NE, there exist higher-order gradient play dynamics that lead (locally) to that NE, both for the specific game and nearby games with perturbed utility functions. Conversely, we show that for any higher-order gradient play dynamics, there exists a game with a unique isolated completely mixed-strategy NE for which the dynamics do not lead to NE. Finally, we show that convergence to the mixed-strategy equilibrium in coordination games, comes at the expense of the dynamics being inherently internally unstable.

Higher-Order Uncoupled Dynamics Do Not Lead to Nash Equilibrium - Except When They Do
Sarah A. Toonsi
Jeff S. Shamma
Industrial and Enterprise Systems Engineering University Illinois TabannaChaamaign Urbana, Illinois, USA stoomsi22illime
Industrial and Enterprise Systems Engineering University Illinois Ttbana-Champaigy
Urbana, Illinois, USA jshamma@ i lliinis .eduuuuuuuuuuuu..u.......ouu.u edu
Abstract
The framework of multi-agent learning explores the dynamics of how agent's strategies evolve in response to the evolving strategies of other agents. Of particular interest is whether or not agent strategies converge well-known solution con- cepts such as Nash Equilibrium (NE). In "higher-order" learning, agent dynamics include auxiliary states that can capture phenomena such as path dependencies. We introduce higher-order gradient play dynamics that resemble projected gradient ascent with auxiliary states. The dynamics are "payoff-basee based" and "uncoupled" that each agent's 's dynamics depend on its own evolving payoff and has no explicit dependence on the utilities of other agents. We first show that for any polymatrix game with isolated completely mixed-strateg! NE, there exist higher-order gradient play dynamics that lead (locally) to that NE, both for the specific game and nearby games with perturbed utility functions. Conversely, we show that for any higher-order gradient play dynamics, there exists a game with a unique isolated completely mixed-strategy NE for which the dynamics do not lead to NE. Finally, we show that convergence to the mixed-strategy equilibrium in coordination games can come at the expense of the dynamics being inherently internally unstable.
Introduction
The field of learning in games explores how game-theoretic solution concepts emerge the outcome of dynamic processes where agents adapt their strategies in response to the evolving strategies of other agents 2 4) There is multitude of specific cases of learning dynamics/game combinations that result in range of outcomes, including convergence, limit cycles, chaotic behavior, and stochastic stability (5 6
13). The emphasis in the literature is simple adaptive procedures, called "natural" dynamics in (14), that can result in various solution concepts (e.g., Nash equilibrium, correlated equilibrium, and coarse correlated equilibrium). (A separate concern is the complexity associated with such computations (e.g. (15 T6)).)
10 11
One "natural" restriction for learning is that the dynamics of one agent should not depend explicitly on the utility functions of other agents. This restriction was referred to as "uncoupled" dynamics in (I7), where the authors constructed specific anti-co unti-coordination matrix game for which uncoupled learning dynamics could converge to the unique mixed-strategy NE. The dynamics considered in that setting were of fixed order, i.e., the order of the learning dynamics was restricted match the dimension the strategy space. More recent work showed that specific instances of fixed order uncoupled learning dynamics can never lead mixed-strategy NE (8). Furthermore, there exist games for which any fixed order learning dynamics are bound to have an initial condition starting from which the dynamics do not converge NE (19).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The restriction on the order of the learning dynamics in learning mixed-strategy NE turns out to be essential. In particular, by introducing additional auxiliary states, (20) showed that higher-order learning could overcome the obstacle of convergence to NE in the same anti-coordination game considered (17) while remaining uncoupled.
Higher-order learning in games can be seen as a parallel to higher-order optimization algorithms, such as momentum-bon baasttduu--ddddddde-e or optimistic gradient algorithms (e.g.. (2] 22)). Such algorithms utilize history to update the underlying search parameter. In this way, there is a path dependency on the trajectory of information. An early utilization of higher-order learning in (3). in which player's strategy update uses two stages of history of an opponent's 's strategies in zero-sum setting to eliminate oscillations. Similar ideas were used in (24). Reference (25) modified gradient-based algorithms through the introduction of a cumulative (integral) term. In (20) higher-order dynamics were used to create myopic forecast of the action of other agents. Authors (26) introduce a version of higher-order replicator dynamics and show that, unlike fixed order replicator dynamics, weakly dominated strategies become extinct. Reference (27) utilizes the system theoretic notion of passivity to analyze a family of higher-order dynamies.
In this paper, we further explore the implications of learning dynamics that are uncoupled. We address "payoff based" dynamics, in which the learning dynamics depend on the evolution of a payoff vector that is viewed as an externality. When players are engaged in game, then the payoff stream of one agent depends on the actions of other agents. However, the learning dynamics themselves do not change based on the source of the payoff streams.
First, we show that for any polymatrix game with a mixed-strategy NE, there exist payoff-hased dynamics that converge locally that NE. This result is established by making a connection between convergence to NE and the existence of decentralized stabilizing control (28) 29). A consequence of the payoff-based structure is that the dynamics also converge to the NE of nearby perturbations of the original game. The form of higher-order learning used for this stability result is higher-order gradient play, which generalizes gradient ascent. Next, we show that for any such dynamics, there exists a game with a unique stxetdstrattgy NE that is unstable under given dynamics. The tool utilized classical analysis method in feedback control systems known as root-locus (e.g., (30), (BI)), which characterizes the locations of the eigenvalues of a matrix as a function of a scalar parameter. combination of the above results suggests the lack of universality on the side of both learning dynamics and games. While any mixed-strategy NE can be stabilized by suitable higher-order gradient dynamics, any such dynamies can be destabilized by a suitable anti-coordination game. Finally, we examine the implications of higher-order dynamics being able to converge the mixed-strategy NE of a 2 x 2 coordination game, which has two pure NE and one mixed-strategy NE. We show that such higher-order gradient play dynamics must have an inherent internal instability, which makes them unsuitable, not irrational, as a model of learning.
2 Payoff-based learning dynamics
2.1 Finite polymatrix games
We consider finite (normal form) games over mixed-strategies There are n players. The strategy space of player i E {1, 2, ..., n1 is the probability simplex, A(k;), where k; is positive integer and A(-) is defined as (xx) = { 8 E R= 8, 2 0,j = I,..., K, & Σj= 83 =1} The utility function of player i is a function u;: (bh1) x... x (kk..) + TR. We sometimes will write u4 (z(,,..., .n)) = u, x-1), for x, E (k:) and xー E X-4, where X = A(k1) x ... x A(k-1) x A(k++)) x ... x A (kk.)
For convenience, we will restrict our discussion to pairwise interactions, also called polymatrix games. That is, the utility function of player is defined as
u ..., Fn) x
MyJay
n....,n.3 j. $ i. We can write the utility function of player as the inner for matrices, Maj. j = 1,...,
product u, u,(x), [n,) = x.. Px(x=:) where (z(x-)) = Σ My E R&. Accordingly, each element of P((x-s) can be viewed as a payoff that is associated with a component of player i's strategy vector, 24.

---

LD,
P1
X1
LD
P1
Xx
Max
Ma
My
Ma
Figure 1: Payoff-based learning dynamics (LD;) in feedback with game matrices (Mis)).
Nash equilibrium (NE) is tuple (æi, xn) E X' such that for all = 1, n,
u, (x 2 u, (x,,, Vx, E Akk)). completely mixed-strategy NE is such that each of is in the interior the simplex.
2.2 Fixed order learning
Our model of learning is a dynamical system that relates trajectories of payoff vector, (t).). to trajectories the strategy, (t). In particular, learning dynamics for player are specified by
function f: A(k) x R & according
(t(t)
(t),
where (f) E (kks and R. - R We assume implicitly that fi and p, are such that there exists unique solution whenever (0) A (kk)). We further assume that the dynamics satisfy the invariance property that
(0) E (k:)) x. (1) E ((:),
V.
Note that we define learning dynamics without specifying the source of the payoff vector, (f).). hence the terminology "payoff-based", Only once a player coupled with other players in game through their own (possibly heterogeneous) learning dynamics is when we make the connection (t)) (t)
This formulation illustrated in Figure where the LD; denote mayoff-based learning dynamics that interconnected through the game matrices, Mij- Note that such learning dynamics uncoupled by construction since each player can only access its own payoff vector. There is no dependence on the payoff stream of other players. Indeed, there is no dependence the parameters of one's utility function.
2.3 Higher-order learning
The learning dynamics described in the previous section have fixed order associated with the dimension of the strategy space. Higher-order learning dynamics allow for the introduction of auxiliary states as follows. For any fixed order learning dynamics, fú, we can define higher-order version as
(t) fi(x. + ((()))))))())0))))))))))))) (t) = (p.,,,,,
(3a)
(3b)
As before, x; (t) E ((k)) and p: R4 - A The new variable z; E R represents l dimensional auxiliary states that evolve according to the deddendddntt dynamics, 9i- These enter into the original fixed order dynamics through d; Accordingly, we can view pt(t) + o (p,(t), 2x) as a modified payoff stream that captures path dependencies in P,, and the original learning dynamics react to this modified payoff stream.
As with the fixed order counterparts, there is no specification of game parameters in higher-order learning dynamics. In order to enforce that the auxiliary states have no effect on the equilibria of games, make the following assumption.
3

---

Assumption 2.1. Pf and 2; are an equilibrium of the higher-order dynamics, i.e.,
= (.(p,,
then
i (p x77 = 0.
This assumption assures that the auxiliary states represent purely transient phenomena that disappear at equilibrium.
Example 1 (Anticipatory higher-order dynamics). A special case of higher-order dynamics is
2 X(p: - -2) Φ: - >>ppp -24,,
where the the higher-order modification is the linear system (see Appendix A.1
-X
AI
-xXI
and 7, R... Intuition behind the connection to anticipation can be seen by viewing X(p; - 24) as an approximation of pi. and so pt(t) + (t)p:(t) 24 (f)) z p:(t +)). Similar higher-order dynamics were used in reference (20) for smooth fictitious play to overcome the lack of convergence of uncoupled dynamics to NE in the anti-coordination game analyzed by (I7). See also reference (3)
for an analysis with replicator dynamics.
Anticipatory higher-order dynamics can also be linked to optimistic optimization algorithms (e.g.. An Euler discretization of step size, h, results in
122
2 + hA(ps - 2z),
with a modified payoff stream of
Pi + Φi - Pi >X(p; 21).
Setting h = 1/2 and 1/A results in
+ Φ; = p: + (ps - 2,)
= + (p: P,
where the superscripts '+' and '_' indicate the next and previous discrete time steps, respectively. There also optimistic variants of discrete-ting time no-regret learning algorithmss (33 34 35) that guarantee faster convergence rates to coarse correlated equilibria compared to the standard versions.
Gradient play
The main results of the paper will examine the behavior of gradient play and higher-order gradient play, which are the focus of this section.
3.1 Fixed order gradient play
In gradient play dynamics, player adjusts its strategy in the direction of the payoff stream, i.e.,
+ +p] - 34 $ = IT [r
where H [x] : R"
(n) is the projection of x into the simplex, i.e., (x)
arg ming |||-
The terminology "gradient play" stems from the gradient of agent's utility function in (T) with respect to its own strategy, namely Vz, (,,, x-1) P((x_.) = Σ j- Myy.y. As was done
in the description of payoff-basee based learning, we replace P3 (x with the payoff stream p. without regard the game matrices Mij-
Our primary concern will studying these dynamics near a completely mixed-strategy NE. To this end, let x" (æ),..., x be an isolated completely mixed-strategy NE. The strategy vector x;

---

Yi
u1
Ny
Preprocessing
K
NO
Pi
Gradient
2
Play
Figure 2: Cascade representation of linear higher-order dynamics for gradient play.
evolves on the simplex, which is subset of dimension k; 1. Hence, the local behavior of the dynamics around z is characterized by evolution on a lower-dimensional subset. Thus, we can write
3y = x + New;
(5)
where
(6) Therefore, w, E Rkk represents deviations from x and satisfies wt(() = (z) - x²). When all players utilize fixed order gradient play, the collective dynamics near completely mixed mixed-strategy NE take the form
1º = & NIN.=I.
i Mw,
where
O
M12
M13
Min
M21
M23
M2n
N1
=
M3i
M32
0
Man
N, =
(8)
N₂
Maa
M,
Ma
Given the zero trace M, standard gradient play is always unstable a completely mixed-strategy NE (see Appendix A.3 for stability conditions). Also, for this equilibrium to be isolated, M must be non-singular. Otherwise, M has non-trivial null space leading to an equilibrium subspace.
3.2 Higher-order gradient play
We will be interested in specific form of higher-order gradient play that uses the following linear structure of higher-order dynamics:
è; = -; + II Is + N. + H, p. =x))
& E,g, + F.(NT P: -))
NTP: vi,
for some matrices E,, F. G2 and H, Here, the auxiliary states are 2; (v,,E.), which enter into the dynamics through (P,, &,, 04) = N,GG,G, + H,(NTp: p; v;)), where N; is defined as in (6).
The motivation behind this structure, illustrated in Figure 2 assures the enforcement of Assump- tion 2.I] The payoff stream is first preprocessed by specific linear system to produce y, and then by general linear system K; to produce u, The matrices (Ei, Fi, G,, Hi) create the dynamical system
E, Gi
F
K,
H4
that maps = NTp: u = G.C: + Hiy: via É = EgE; + Fay- The preprocessing system has the property (see "washout filters" Appendix A.2) that if (t) converges to constant, then (t) converges to zero. Accordingly, when E, is non-singular, the preprocessing system guarantees Nash stationarity, i.c.,
lim (t) (z), (7, Vi
then x² (x (......, ) the payoff modification, and the preprocessing system ensures compliance with Assumption 2.1
NE. To conclude, the linear system K; the central entity that performs
5

---

3.3 Local stability analysis
As before, we can analyze the behavior near a completely strategy NE x* through the variable wy defined as in (5). Using the fact that N Eeer Myzaj = 0, we can write the local dynamics of player as
ú N Mig Nww + GES. + H. (.( Σ
MynN v-)
5. E,G, F
MrrNawy 1s)
à
NT
MyyN - vi.
The collective dynamics near a mixed-strategy NE can be written as
(1 + HMM
G
H
10'
FM
F
(10)
M
where F,F,G, and H are block diagonal matrcies with appropriate dimensions and M is defined in
N Local stability of completely mixed NE is determined by whether the above collective dynamics
stable, i... the dynamics matrix in 10 is stability matrix.
4 Uncoupled dynamics that lead to mixed-strategy NE
4.1 Decentralized control formulation
The stability of a mixed-strategy equilibrium is tied to the existence of K1, K2..., Kn so that the linear system in (10) is stable. When the K; have yet be determined, rewrite (10)
M 0
M
-1
+
(11a)
(M
-I)
(11b)
v
41
where
11
and the y and uy are to be related through K;,
Un
4.2 Decentralized stabilization
Let
A B
P~
C 0
with
M M -))
B-((). -- (M -1).
A
B B-
(12)
We first establish that P can be stabilized by verifying the conditions for stabilizability and detectabil- ity (see Appendix A.3). The assumption that M is non-singular stems from our interest in isolated NE
Proposition 4.1. For M non-singular, the pair (A,B) stabilizable, and the pair (A,C) de- tectable.
While Proposition 4.1 establiisss that P can be stabilized, that property alone is inadequate for purposes. In particular, for the learning dynamics to uncoupled, we seek to establish decentralized stabilization (see Appendix A.4) according to the partition
A
10
+
B
y: = C.
10
(13)
à
i=1

---

where
(M - B: = (8))
-())
A= (M
C. = (Mio -E,)
(14)
Here, Mis denotes the 2t block row of M, i.c.,
Mi = M, 1) Mitt1))
N MmnNn)
and
-
... 0).
2 position
where 7 has dimension (suppressed in the notation) of k; 1
Theorem 4.1. For any isolated (i.e., M is non-singular) completely mixed-strategy NE, there exist uncoupled higher-order gradient play dynamics such that (70) stable.
The proof of Theorem 4.1 relies on the conditions of Theorem A. and is presented in Appendix B.1
Theorem should be viewed statement regarding whether uncoupled learning in itself is a barrier to learning dynamics leading to NE. The theorem makes no claim that the higher-order learning dynamics interpretable (e.g., in anticipatory learning). Nor does the theorem offer guidance on how agents may construct the matrices of higher-order learning that lead to convergence. In the next section, will see that, while the structure universal, any specific of parameters is not universal in that one can construct a game for which they do not lead to NE. Despite the lack of universality, there is inherent robustness that is consequence of stability. The following follows from standard arguments on linear systems.
Proposition 4.2. Let the K and Mej, 1...., n. and j 1,,,,, ni be such that (TO) is stable. Then there exists a > O such that (10 is stable with the Mij replaced by any Mig as long as My Mij < for all i = l,..., n and j L,.., nt
In words, this proposition guarantees that learning dynamics that lead NE for specific game continue to do so for nearby games.
4.3 Stabilization through single higher-order player
The previous section's 's analysis allowed all players to utilize higher-order learning. In some cases, may not be necessary for players to utilize higher-order learning. In this section, we present sufficient conditions under which single player using higher-order gradient play with the remainder utilizing fixed order gradient play can still lead to NE.
Assumption 4.1.
A. Let (w, X) be left eigenvalue pair of M, ie..
T M Xw
with Re(A] 0 and wT (wf w partitioned consistently with 88. Then w; A 0 for all
B. Let (v, X) be a right eigenvalue pair of M, i.e.,
Mu = Xu, "T) partitioned consistently with 8 Then vs #
with Re[A] 2 0 and (Nf for all i.
Recall the definitions of A, B,, and C, from 14
Proposition 4.3. Let M be non-singular and satisfy Assumption 4.1 Then for any the puir (A, B:) stabilizable and the pair (A, C.) is detectable.
is possible for completely mixed-strategy NE to be stabilized where a single player utilizes higher-order gradient play with the remaining players utilizing fixed order gradient play.
As consequence of Proposition 4.3

---

Non-convergence to NE in higher-order gradient play
We now show that linear higher-order gradient play dynamics need not lead NE. Given any such dynamics, we construct game with unique NE that is unstable under given dynamics.
5.1 The Jordan anti-coordination game
The Jordan anti-coordination game, introduced in (36), was used in (17) prove that fixed order uncoupled learning dynamics do not lead to NE. The game consists of three players with
41 (21, = - (i 22, (3( = 22 (i 0 uz x1) = x3 (1 x1,
2) 1)²² We will let ((a) denote the Jordan anti-coordination game but with the utility function of player I modified to un (#1, = o (222 where μ RR,. Since scaling payoff's does not change the nature of the game, l(p) has the same unique NE as (11).
and a unique mixed-strategy NE at xं = 23 = x (5
5.2 Destabilization using rescaled anti-coordination
Suppose all three players use variants of linear higher-order gradient play in l(x). As before, denote the higher-order dynamics of player i as the linear dynamical system (9) To study the local behavior of the dynamics around the unique mixed-straee strettstrateyy NE of I(p), we define wa (t), wy((), and (t) as in (). Then, we analyze the local stability of the mixed-stratess NE through (10).
The following lemma will be essential in proving our main result.
Lemma 5.1. Lel A E Raxn, E Rax1 and C E RR1x IJCB = CAB = 0, and CA B + 0. some m 2 2. Then for sufficiently large μ > 0, A - pBC is not a stability matrix.
The proof of Lemma 5.1 is presented in Appendix B.2 2nd it uses root-locus arguments (see references 31 30)..
Proposition 5.1. If linear higher-order gradient play dynamics are locally exponentially stable at the unique NE (1),, then there exists O such that the unique NE of ((p) is unstable under such dynamics.
The proof of Proposition 5.1
presented in Appendix B.3 The main idea of the proof is to write the local dynamics matrix in the form A - ,BC, and then use Lemma 5.1 We also provide a similar proof for sufficiently small y in Appendix
The results might be puzzling because, for all μ > O, all games ((u) are strategically equivalent. Convergence guarantees for learning dynamics are usually established amongst classes of games. Thus, is generally expected that dynamies will behave similarly for all games a particular class. In this case, design linear learning dynamics that are affected by simple rescaling of the payoff matrices.
Strong stabilization of mixed-strategy NE
Results from Section imply that the mixed-strategy NE in a two-player x (identical-interes) coordination game can be stabilized. Here, we argue why dynamics that stabilize this mixed-strategy cquilibrium are reasonable. Specifically, we show that such dynamics must be inherently unstable as open system, i.e., as dynamics that respond to an exogenous payoff stream, and this instability problematic with respect such payoffs.
First, we inspect which type of mixed-strategy NE requires unstable learning dynamics for stabiliza- tion. For this purpose, consider the system in 122 for
k
ki 2:
0
m12
0
0
0
M22
0
m12
-1
0
0
B
0
0
C
m21
12
0
0
-1
(15)
7721
-1/
0
8

---

Figure 3: Single-player stabilization of the Jordan game.
Around am isolated mixed-strategy NE, the matrix A above should be non-singular. Accordingly, it must be that m12 # 0 and m21 # O. The ability stabilize system via another stable system referred to as strong stabilization (see Appendix (..3). The next proposition gives sufficient condition under which isolated mixed-strategy NE is not strongly stabilizable.
Proposition 6.1. If m2 0, then 15) not strongly stabilizable.
The proof of Proposition 6.1 uses the "parity interlacing principle" (see reference (37) and is presented in Appendix B.4
The nature of the game can be inferred from the scalars m2 and m221. For example in zero-sum games have M12 -M which gives
m N NT -N -221-
In coordination games, we have M12 M21, which gives
m12 = N FM2 = N M = m21
Therefore, the mixed-strategy NE in coordination game is not strongly stabilizable.
Now let us examine the implications of inherently unstable learning dynamics. A reasonable expectation of learning dynamics that in the case of constant payoff vector, i.e. p.(t) = pp, we expect
lim x,(t)= = 3(p"), +0
where B(p") is a best response to p", i...
3(p") arg max ar p"
2. E.EA(K.)
For any higher-order gradient play dynamics, if E, is a stability matrix, then whenever (t p" for some constant vector p", one can show (t) -> 0, which implies that x. (f) is generated by standard gradient play dynamies in the limit. However, if (t) = p" and the dynamics are inherently unstable, the term (tG need not vanish. Indeed, one can construct p" such that (t()) does not converge the best response of p" (see the example in Section 7.2). The inability of learning dynamics to converge to the best response of constant payoff vector does not reflect "natural" behavior.
7 Numerical experiments
7.1 Jordan anti-coordination game: Stabilization through a single player
The payoff matrices of the Jordan notiicoordin game, introduced Section 5.1 satisfy As- sumption 4. Therefore, we can stabilize its mixed-stratepp NE, allowing only one player to use higher-order learning while others continue to use standard gradient play. For this purpose, let & E IR and choose H1 7A, Gi ー>, Fi = À and E -X, where À = 50 and 5. Such dynamics resemble anticipatory gradient play but on the filtered low-dimensional payoff. Figure illustrates convergence of the players' strategies to NE,

---

(a) Stabilization of the mixed- strategy NE.
(b) Inherently unstable dynamics
do not converge to best response
of p = (0 1)
Figure 4: Stabilizing the mixed-strategy equilibrium of coordination game and its consequences.
7.2 Stabilization of mixed-strategy NE in coordination games
Consider the (identical interest) coordination game:
U1 (2) = zf () 1 22. u2( x1) = 22 ( 1 11.
The game has two pure strategy NE and one completely mixed-strategy NE at x* =²= Consider the following set of parameters for higher-order gradient play: Eg A. -2,
G = 7A, H1 = ~ F2 = - X2 F2 = X2, G2 = - 22 and H2 = 72 The numerical values À = 0.5, 7 20, A2 50, and 7/2 1. Figure 4a illustrates convergence to the mixed-strategy
NE of this coordination game. Suppose we break the feedback loop and use p² =
1) as the
input to the first player dynamics. The response to such input is illustrated in Figure 4b We see that Eg > 0 is a scalar, and so &1 grows without bound. The strategy ø1. which is projected to the simplex, converges to 0)* which is not a best response to the input p"
Concluding remarks
To recap, studied the role of higher-order gradient play with linear higher-order dynamics. We showed that for any game with an isolated completely mixed-strategy NE, there exist higher-order gradient play dynamics that lead to that NE, both for the original game and for nearby games. On the other hand, we showed that for any higher-order gradient play dynamics, the dynamics do not lead to NE for suitably rescaled anti-coordination game. We also provided an argument against dynamics that lead to the mixed-strategy NE in coordination game, showing they are not reasonable.
Regarding the higher-order gradient play dynamics that lead to NE, the interpretation of the results herein should not be that these dynamics are either descriptive model of learning or a prescriptive recommendation for computation. Rather, the results possible or impossible in multi-agent learning. that sense, they may be seen as a complement to the contributions in (17). Namely, dynamics being uncoupled is not barrier to converging to mixed-strates NE when allowing higher-order learning.
contribution towards delineating what
More generally, the present results open new questions related to the discussion in (14 what constitutes "natural" learning dynamics. the case of anticipatory higher-order learning, there is clear interpretation of the effect of higher-order terms. However, it is unclear how to interpret general higher-order dynamics. Furthermore, the results herein regarding inherent instability of higher-order dynamics that converge to the mixed-strategy NE of coordination game suggests that higher-order learning can be "unnatural". Possible restrictions on dynamics, in addition to being uncoupled, could include having asymptotic regret; maintaining qualitative behavior in the face of strategically equivalent games (cf., Section 5.2); or having an interpretable relationship between payoff streams and strategic evolutions such "passivity", which generalizes and extends the notion of contractive games to contractive learning dynamics (e.g., (8 39 40)..
In terms of limitations, the current paper only addresses the payoff vector setup and does not address the setup where players only have access to instantaneous scalar payoffs. Furthermore, results in Sections 5 and are limited to certain setups and require further generalization.
10

---

References
[1] D. Fudenberg and D. K. Levine, The Theory of Learning in Games. Economic Learning and Social Evolution Series, MIT Press, 1998.
[2] D. Fudenberg and D. K. Levine, "Learning and equilibrium," Annual Review of Economics, vol. 1, no. pp. 385-320500 2009.
[3] Hart, "Adaptive heuristics," Econometrica, vol. 73, no. 5, pp. 1401-1430, 2005,
[4] H. Young. Strategic Learning and its Limits. Ame Ryde memorial lectures, Oxford University Press, 2004.
[5] S. Hart and A. Mas-Colell, "A simple adaptive procedure leading to correlated equilibrium," Econometrica, vol. 68, no. 5, pp. 1127-1150, 2000.
[6] U. Berger, "Fictitious play in 2xn games," Journal of Economic Theory, vol. 120, no. pp. 139-154, 2005.
[7] D. Monderer and I.. S. Shapley, "Fictitious play property for games with identical interests." Journal of Economic Theory, vol. 68, no. 1.pp 258-265, 1996.
[8] Shamma and G. Arslan, "Unified convergence proofs of continuous-time fictitious play," IEEE Transactions on Automatic Control, vol. 49, no. 7, pp. 1137-1141, 1141, 2004.
[9] L. S. Shapley, "Some topics in two-person games," in Advances in Game Theory (L. Shapley, M. Dresher, and A. Tucker, eds.), pp. 1-29, Princeton, NJ: Princeton University Press, 1964.
[10] D. Foster and Young, "On the nonconvergence of fictitious play in coordination games." Games and Economic Behavior, vol. 25, no. 1, pp. 79-96, 1998.
[11] D. P. Foster and R. V. Vohra, "Calibrated learning and correlated equilibrium," Games and Economic Behavior, vol. 21, no. 1, pp. 40-55, 1997.
[12] G. Piliouras and Shamma, "Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence," in Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 861-873, 2014.
[13] H. Young, Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, 1998.
[14] S. Hart and A. Mas-Colell, Simple Adaptive Strategies. WORLD SCIENTIFIC, 2013.
[15] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, "The complexity of computing Nash equilibrium," SIAM Journal on Computing, vol. 39, no. 1, pp. 195-259, 2009.
[16] Y. Babichenko and A. Rubinstein, "Communication complexity of approximate Nash equilibria," Games and Economic Behavior, vol. 134, pp. 376-398, 2022.
[17] S. Hart and A. Mas-Colell, "Uncoupled dynamics do not lead to Nash equilibrium," American Economic Review, vol. 93, pp. 1830-1836, December 2003.
[18] E.-V. Vlatakis Saanakii-Gaargk.uunis,, L. Flokas, T. Lianeas, P. Mertikopoulos, and G. Piliouras, "No- regret learning and mixed Nash equilibria: They do not mix," in Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and Lin, eds.), vol. 33, pp. 1380-1391, Curran Associates, Inc., 2020.
[19] J. Milionis, C. Papadimitriou, G. Piliouras, and K. Spendlove, "An impossibility theorem in game dynamics," Proceedings of the National Academy of Sciences, vol. 120, no. 41, 2023.
[20] Shamma and G. Arslan, "Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria," IEEE Transactions on Automatic Control, vol. 50, pp. 312-327, March 2005.
[21] M. Muehlehach and M. Jordan, "Optimization with momentum: Dynamical, control-theoretic. and symplectic perspectives," J. Mach. Learn. Res., vol. 22, no. 1, 2021.

---

[22] C. Daskalakis and I. Panageas. "The limit points of (optimistic) gradient descent in min-ma max optimization." in Advances in Neural Information Processing Systems (NeurIPS), 2018.
[23] Başar, "Relaxation techniques and asynchronous algorithms for on-line computation of non- cooperative equilibria," Journal of Economic Dynamics and Control, vol. 11, no. 4, pp. 531-549, 1987.
[24] J. Conlisk, "Adaptation in games: Two solutions to the Crawford puzzle," Journal of Economic Behavior & Organization, vol. 22, 1, pp. 25-50, 1993.
[25] S. Flam and J. Morgan, "Newtonian mechanies and Nash play," International Game Theory Review, vol. 06, 07 2003.
[26] R. Laraki and P. Mertikopoulos, "Higher order game dynamics," Journal of Economic Theory, vol. 148, pp. 2666-2695, 06 2013.
[27] B. Gao and L. Pavel, "On passivity, reinforcement learning and higher order learning in multiagent finite games," IEEE Transactions on Automatic Control, vol. 66, no. 1, pp. 121-136, 2021.
[28] S.-H Wang and E. Davison, "On the stabilization of decentralized control systems," IEEE Transactions Automatic Control, vol. 18, no. 5, pp. 473-478, 1973.
[29] E. Davison and T. Chang. "Decentralized stabilization and pole assignment for general proper systems," IEEE Transactions on Automatic Control, vol. 35, no. 6, pp. 652-664, 1990.
[30] A. M. Krall, "An extension and proof of the root-locus method," Journal of the Society for Industrial and Applied Mathematics, vol. 9, no. 4, pp. 644-653, 1961.
[31] A. M. Krall, "The root locus method: A survey," SIAM Review, vol. 12, no. pp. 64-72, 1970.
[32] G. Arslan and S. Shamma, "Anticipatory learning in general evolutionary games." " Proceed- ings of the 45th IEEE Conference on Decision and Control, pp. 1289-62944 2006.
[33] V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire, "Fast convergence of regularized learning in games," " in Advances in Neural Information Processing Systems (C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, eds.), vol. 28, Curran Associates, Inc., 2015.
[34] X. Chen and B. Peng, "Hedging in games: Faster convergence of external and swap regrets," in Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, eds.), vol. 33, pp. 18990-18999, Curran Associates, Inc., 2020.
[35] C. Daskalakis, M. Fishelson, and N. Golowich, "Near-optimal no-regret learning in general games," in Advances in Neural Information Processing Systems (M. Ranzato, A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, eds.), vol. 34, pp. 27604-27616, Inc., 2021.
Curran Associates.
[36] J. Jordan, "Three problems in learning mixed-strateen Nash equilibria," Games and Economic Behavior, vol. no. 3, pp. 368-386, 1993.
[37] D. Youla, Bongiorno, and C. Lu, "Single-loop fecaback-stabllizatioo of linear multivariable dynamical plants," Automatica, vol. 10, no. 2, pp. 159-173, 1974.
[38] M. J. Fox and S. Shamma, "Population games, stable games, and passivity," Games, vol. 4, no. 4, pp. 561-583, 2013.
[39] M. Arcak and N. C. Martins, "Dissipativity tools for convergence to Nash equilibria in population games," IEEE Transactions on Control of Network Systems, vol. 8, no. 1, pp. 39-50, 2021.
[40] L. Pavel, "Dissipativity theory game theory: On the role of dissipativity and passivity in Nash equilibrium seeking," IEEE Control Systems Magazine, vol. 42, no. 3, pp. 150-164, 2022.
[41] J. P. Hespanha, Linear Systems Theory: Second Edition. Princeton University Press, 2018.
[42] W. J. Rugh, Linear System Theory. Prentice Hall, 1996.
12

---

[43] M. Hassouneh, H.-C. Lee, and E. Abed, "Washout filters in feedback control: benefits, limita- tions and extensions," " in Proceedings of the 2004 American Control Conference, pp. 3950-3955, 2004.
13

---

Appendices
In Appendix A we review some relevant topics from linear systems theory. In Appendix B we provide proof's of theorems, lemmas, and propositions that were presented the paper. In Appendix we provide an alternative destabilization proof for sufficiently small gain μ..
A Background on linear systems
Here, we review some standard background material for linear dynamics systems. There are several references (e.g., (4 42)) with more detailed exposition.
A.1 Notation
The partitioned matrix
A B C D
represents a general linear dynamical system
#(t) Ax(t) + Bu(t),
z(0) 2o
(16a) (16b)
v(t) = Cr((t) + Du(t)
whose solution is
v(1) Ce At [( CeAlt-T)Bul dr + Du(().
The variables E R", u E R and E IR here are used temporarily as generic placeholders (and
( (CD
AAl assigns the label
will play a different role in the ensuing discussion). The notation P P to the dynamics I6.
A.2 Washout filters In the special case of
P ~ (-1+-
where
i(t) -x(t) u(t),
z(0) = To
u(t) -x(() u(t)
and x, u. E RR", it straightforward to show that
lim u(t) = u. 6100
then
lim y(t) =
1
Linear systems with this property are known as "washout filters". For an extended discussion, see reference 43)
A.3 Stability and stabilization
A matrix, M, is stability matrix if, for every eigenvalue, X. of M, Re(A] < O.
A
B
The linear system, P ~~
is stable a stability matrix.
C
D
14

---

E G
The linear system
stabilizes P if the combined linear dynamics
H
f Ax Bu
5 = E + Fy
G Hy
y = Cr
or
A BHC
BG
x E
FC
E
M
are stable, i.., M is a stability matrix.
The following conditions necessary and sufficient for the existence of such a K. For all complex with Re[A] 2 0:
The pair (A, is stabilizable: (A AI
B) has full row rank.
The pair (A, C) is detectable:
A AI) has full column rank.
The linear system K strongly stabilizes P if (i) K stabilizes P and (ii) E is a stability matrix. Necessary and sufficient conditions for the existence strongly stabilizing K are presented in reference (37).
A.4
Decentralized stabilization
(a
A B
Let P ~
with A having dimensions n x n, have the structure
Ci 1
B = (B1
B&) & ==
Ck
for some integer Suppose there exist linear systems
)
Fi
Ex
Fk
K
Kg
G1
Hi
Gk
H
such that the combined linear dynamics
U1
= Ax + (Bi
B&)
uk
à EiG. + Fil1
:
& FaEK + FRik
GIE1 H191 :
GREL + H
91 Ci
:
Cg.
15

---

are stable. Then the (K1.... .... Kx) achieve decentralized stabilization of P. The previous conditions of (A, B) stabilizable and (A, C)) detectable are necessary, but sufficient, conditions for decentralized stabilization.
The following theorem from reference 29 provides necessary and sufficient conditions for decen- tralized stabilization. First, for any partition QUR
R = = {1, ......, k define B| as the matrix formed Bk) with indices in Q, i.c.
by extracting the block columns of B (B1
8 (Bor
Baga))
with {ar .. --1-)
Q. Likewise, define C/ as the matrix formed from the block rows of
C
C
i.c.
Cn
Cla
CriAn
with {ri...., r R R.
Theorem A.1 ((2). Theorem 3). There exist (K1..., Kx) that achieve decentralized stabilization of P if and only
rank AA- AI
b = n
C
for all complex with Re[A] 2 0 and all partitions, Q R [1,2, k}.
The above rank condition must hold for all partitions QU R = {l,... kj. R one recovers
the rank condition for (centralized) stabilizability, Likewise, Q 1 results in the rank condition for detectability.
B Proofs
B.1 Proof of Theorem 4.1
We will examine the conditions of Theorem A.I on the system (33 rank of
14p. We need to inspect the
A AI
A
Bl
ClR
0
for all partitions QU R (1,2. n). Note that the partitions of either Q or R () are already covered by Proposition 4.1.
First, note that
MM-X
(Egr
Enqi)
B1 (A-I
M
- -( + 1)/
ClR
0
M|R
-IR
Let M be an f x matrix. Then
Σ (k. - 1)-
We need the rank of the above matrix be 28 for all À with Re[X] Because of the presence of A - AI, loss of rank below 2/ is only possible at eigenvalues of A. Since we are only concerned with Re[X] 2 we focus on eigenvalues of M (which excludes À by hypothesis, since M is non-singular).
Without affecting the rank, block rows corresponding Rt to the rescaled bottom block row to get
multiply the bottom block row by - (A + 1) and add the middle
M - AI
(Eg,
Eqie1)
(A-AI Al
23 = rank
rank
M
- -(A+1)7
0
Cl
0
XMIn
0
16

---

Switching the top and bottom block rows results in
MMI
0
M
- 1
M-XI
0
(Egz
EqrR))
We can now exploit the block triangular structure. The bottom block row provides a row rank of
Σ
(Kg
1),
REQ
The middle block row provides row rank of Finally, the top block row provides a row rank of
Ek 1 1).
The last assertion because M is non-singular, by hypothesis, and therefore has linearly indepen- dent rows. Since Q PUR R [l,...n}, we have the desired row rank of 28.
B.2
Proof of Lemma 5.1
Define
H(s) = C(sl - -(s--A)- AB
Since (s) is a rational function, we can write it as
H p(s)
g(8)
for polynomials p and that have common roots. The assumption that CA B o for some assures that (s) is not identically equal to zero.
Suppose that for some μ and s' that is not an eigenvalue of A.
g(s') + up(s') = 0.
Then s' is an eigenvalue of A pBC, since
det Is'I -BBC) = det [s'I - A] det [I
det [s'I - A] PC A)
det [s'I - A] (g(s') + uP(6') g(s')
Note that the roots of gss) are subset of the roots of det [s] rewrite Hs)) as
A]. For sufficiently large [s], we can
H(s) 1
1
C(I A) -)-BB B
8
C
4 B. sh
By assumption, CB = and CAB which implies that the first two terms of the series equal
zero. Accordingly.
lim sup |s| [H)) oo. |+|+00
The main implication here that the degree of q(s) is least 3 more than the degree of p(s). Root-locus arguments in references (30) and 31I (asymptote rule) imply that
q(s) + up(s)
has roots with positive real parts for large μ.

---

B.3
Proof of Proposition 5.1
The local dynamics matrix in the game (p)) can be written in the form A pBC with
0
C1
H1
0
0
Hh
(1 +
Ha)
G3
H3
0
0
(1 +
H2)
0
0
G2
H2
0
0
E1
Fi
0
0
0
0
Fi
A
0
0
0
0
0
B
0
0
0
Fa
F3
0
0
0
1
0
F2
0
0000
1000
0000
0
E2
0
-
F22
0
-1
0
-1
(17a)
C
0
0 0)
(17b)
where reordered the variables according to (W1, Wy, 12 E1, U1, E3. U3 E2, U2) for convenience. Following the same arguments in proving Lemma 5.1 if CATB = 0 for all m, then eigenvalues of A BC the same as the eigenvalues of A. Writing in block matrix form yields
A [An A12
A21
A22
where An is 3 3. Notice that An is strictly lower triangular, and A21 is strictly block lower triangular. Now examine
det [s[ - A] = det [s] Ani det [(sI- - A22) As - An AA2]
One show that (sl A11) A12 is strictly block lower triangular. Therefore, have det [sl-A] A = det [s] Anl det [s/ - A22] Thus, A has eigenvalues at with multiplicity 3 or more because of An By exponential stability, there exists m 2 2 such that CAA" o 0. Since CB = 0, and CAB = 0, we can now apply Lemma 5.1
B.4 Proof of Proposition 6.1
Reference compute
37
presents a necessary and sufficient condition for strong stabilizability. First, we
T(s)= A)-
8 8+1 M
There is blocking zero (i.e.. T(s) 0) at 0 and |s] - co. According to reference (37). necessary and sufficient condition for strong stabilizability is that there should an even number of eigenvalues in between such pairs of real zeros. This property is known as the "parity interlacing principle". The eigenvalues of are 11,-1, -, + /212m and so there a single (and hence, an odd number) of real eigenvalue in between two real zeros of (s)).
C Destabilization with a sufficiently small μ
The proof in Section can be modified to consider non-convergence over bounded games, e.g..
||Milla < 1 Vi,j.
Consider first the following lemma.
Lemma C.1. Let E Raxn, B E RRax1 and C E RR1x Assume that A has eigenvalues at 0 with multiplicity' 3 or more. Then for sufficiently small μ 0, A μBC is not stability matrix.
Proof. As the proof of Lemma 5.1, we have
det [s] (A μBC) det |s] (g(s)) + mp((s) 1 4(s)
Recall that the roots of q(()) are a subset the roots of det [s] - A]. If q(s) does not have at least roots at zero, then A - μBC is not stability matrix. Otherwise, root-locus arguments in references (30), and (31) (angle of departure rule) imply there exist roots of g(s) + pp((s) with positive real parts
for small μ.
18

---

Using the structure of the local dynamics and the fact that A in (7a) has eigenvalues at 0 with multiplicity 3 or more, one can directly use Lemma C.I to show the existence of sufficiently small offending js.
19


Reviews:
[{"review_id": "dYMJsVCEEg", "reviewer": "Reviewer_f6g4", "summary": "This paper shows the lack of universality on the side of both games and learning dynamics (even for higher-order ones)! Particularly, for any game with a mixed-strategy Nash equilibrium (NE), there exists uncoupled payoff-based (possibly high-order) dynamic converging locally to the NE. However, any such dynamics can also be destabilized by a suitable anti-coordination game. Notably, the paper uses classical analysis methods in feedback control systems. Highlighted similarities between higher-order learning in games and higher-order optimization algorithms, such as momentum-based or optimistic gradient algorithms, are also interesting.", "questions": "- What is the main obstacle to address instantaneous scalar payoffs rather than payoff vector setup?", "limitations": "The limitations are highlighted explicitly.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The widely studied fictitious play dynamics are known to converge equilibrium in many interesting games but not all of them, e.g., see Shapley's counterexample. Therefore, researchers were looking for a learning dynamic that can converge to equilibrium in every game to justify equilibrium analysis. However, Hart and Mas-Colell, Ref. (16), proved the negative result that there does not exist (first-order) uncoupled learning dynamics that can converge to equilibrium in anti-coordination games, and therefore, there cannot be universally convergent (uncoupled) learning dynamics.\n\nLater, Shamma and Arslan, Ref. (17), showed that higher-order learning dynamics can converge to equilibrium in anti-coordination games. This paper provides a more general result saying that for any game (with a mixed-strategy Nash equilibrium), there exists a (possibly high-order) payoff-based learning dynamic that can converge locally to that equilibrium. Seeing this, researchers may start looking for universally convergent higher-order learning dynamic that can converge to equilibrium in every game. However, the paper proves the negative result that given any such higher-order dynamics, there always exists a certain anti-coordination game in which the dynamics do not converge to equilibrium. Therefore, we can view this paper as a generalization of Hart and Mas-Collel's seminal negative result to higher-order learning dynamics.\n\nNote that Foster and Young designed uncoupled stochastic rules, known as regret testing, that can converge probabilistically to Nash equilibrium in every two-player strategic-form game. However, the convergence is in the relatively weak sense by saying that players will be at equilibrium most of the time though they may move away from it.\n\nNote also that complexity results related to Nash equilibrium computation are not relevant since the paper focuses on asymptotic convergence for finite games. A mixed-strategy Nash equilibrium always exists in strategic-form games, with finitely many player and action.\n\nBecause of these reasons, I believe that this result is worth being taught in (advanced) game theory courses.\n\nI acknowledge that I have read the rebuttal.", "weaknesses": "- Figures might include captions with more detailed descriptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Question>> What is the main obstacle to address instantaneous scalar payoffs rather than payoff vector setup?\n\nWe believe that the present results can be used to analyze instantaneous scalar payoffs in the case of discrete-time learning with randomized action selection.\n\nThe continuous time ordinary differential equations (ODEs) presented in this paper can be seen as the ODEs that emerge from the ODE method of stochastic approximation (e.g., Benaim, “A dynamical system approach to stochastic approximations, 1996) to analyze discrete time stochastic iterations. Prior work (Fudenberg and Levine, “Consistency and cautious fictitious play”, 1995) illustrates how the scalar payoff case of fictitious play can be analyzed using such methods. This approach also was utilized to analyzed higher-order learning under scalar payoffs for the specific case of “anticipatory” higher order learning (Arslan and Shamma, “Distributed convergence to Nash equilibria with local utility measurements”, 2004). Likewise, we believe that the case of instantaneous scalar payoffs can be addressed using the setting in the present paper as the basis of the emergent ODEs of stochastic approximation.\n\nWeakness>> Figures might include captions with more detailed descriptions.\n\nThe final version will revisit the figure captions to add more details."}, {"review_id": "FzBKQvyAP0", "reviewer": "Reviewer_VfQG", "summary": "\nThe paper shows that for any finite game with an isolated completely mixed Nash Equilibrium, there exist a payoff based higher-order\ngradient play dynamics that lead (locally) to that Nash equilibrium, both for this game and all payoff nearby games. Conversely, they show that for\nany higher-order gradient play dynamics, there is a game with a unique isolated completely mixed Nash equilibrium for which that dynamics do not locally converge to that Nash Equilibrium. \n\n Hart and A. Mas-Colell proved using an anti-coordination game that no first-order uncoupled dynamics leads to the unique interior Nash equilibrium of that game.  Shamma and Arslan (2005) proved that there are higher order dynamics which leads to that equilibrium. This paper shows that this extends to all games.  \n", "questions": "\n - Are your dynamics more general than all the previously studied one (such as [18, 19, 20, 23] etc)?\n - Do you have any micro-foundation of your higher order dynamics?\n", "limitations": "The converse result (for any higher-order dynamics, there is a game with a unique isolated completely mixed Nash equilibrium) is proved only for gradient play dynamics and not all higher order dynamics ! \n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Tools used are, up to my knowledge, not standard in evolutionary game theory: decentralized stabilizing control and root-locus which characterizes the locations of the eigenvalues of a matrix as a function of a scalar parameter!", "weaknesses": "\nThe biggest weakness for me is that there is no micro-foundation of the class higher order dynamics nor a comparison with the previously studied higher order dynamics.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Question>> Are your dynamics more general that all the previously studied ones (such as [18, 19, 20, 23] etc)?\n\nThe above papers are specific instances of higher-order dynamics. Setting aside continuous-time/discrete-time differences, the framework of higher-order learning outlined in Section 2.3 is more general. The convergence results of Section 4 shows that higher-order gradient play is sufficient to lead to any mixed-equilibrium, and so more generality is not needed. \n\n\nQuestion>> Do you have any micro-foundation of your higher-order dynamics?\n\nThe issue of micro-foundations depends on the specifics of the higher-order dynamics. The structure presented in Section 2.3 allows a higher-order augmentation to existing learning rules for which there are micro-foundations (e.g., Sandholm, “Population Games and Deterministic Evolutionary Dynamics”, in Handbook of Game Theory with Economic Applications, 2015). These learning rules have agents reacting to the payoffs, and higher-order dynamics can capture path dependent phenomena in these payoffs such as recency bias (e.g., Fudenberg and Levine, “Recency, consistent learning, and Nash equilibrium”, 2014).\n\nWeakness>> The biggest weakness for me is that there is no micro-foundation of the class higher order dynamics nor a comparison with the previously studied higher order dynamics.\n\nSee above response to the questions raised by this reviewer."}, {"review_id": "KzRCCht9EO", "reviewer": "Reviewer_mLZz", "summary": "This paper studies higher order payoff based learning, and in particular higher order gradient play in this setting. The authors show that for games with isolated completely mixed NE, there are higher-order gradient play dynamics that converge to that NE. Moreover, that same NE is converged to in ‘nearby’ games as well. However, the authors also show that there exist anti-coordination games where higher-order gradient play dynamics fail to converge to NE. Finally the authors also argue that dynamics that do lead to NE in a coordination game must be inherently unstable.", "questions": "For the higher order dynamics, is there intuition about the bandit setting where players only observe (potentially random) realizations of their payoffs? This seems more reasonable for the cases where payoff vectors are large/there are a large number of players and complexity is a concern.", "limitations": "The authors adequately addressed the limitations of the dynamics studied.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I find the paper to be well structured and readable. The results in the context of uncoupled learning dynamics in games are also interesting and meaningfully extend existing ideas into higher order dynamics.", "weaknesses": "A weak point in the paper for me is that the results are based upon the assumption that the mixed NE is a practically useful solution concept in learning in games. However, recent works have shown that the NE can often not only be a poor metric for players’ performance, but also it is unnatural for players using decentralized dynamics to converge to an NE in general games. Thus, for a paper that focuses on higher order learning it would have been much more compelling to focus on a more complete picture of higher order gradient dynamics. What characterizes stable equilibria/fixed points for these dynamics in this setting? In cases where NE are not stable, what do the dynamics look like? In my opinion, a broader view of the dynamical system properties would make the results more interesting and useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Question>> For the higher order dynamics, is there intuition about the bandit setting where players only observe (potentially random) realizations of their payoffs? This seems more reasonable for the cases where payoff vectors are large/there are a large number of players and complexity is a concern.\n\nAs noted by the reviewer, a main issue is where payoff vectors are large (a large number of players need not imply a large payoff vector). We believe that the present results can be used to analyze instantaneous scalar payoffs in the case of discrete-time learning with randomized action selection.\n\nThe continuous time ordinary differential equations (ODEs) presented in this paper can be seen as the ODEs that emerge from the ODE method of stochastic approximation (e.g., Benaim, “A dynamical system approach to stochastic approximations, 1996) to analyze discrete time stochastic iterations. Prior work (Fudenberg and Levine, “Consistency and cautious fictitious play”, 1995) illustrates how the scalar payoff case of fictitious play can be analyzed using such methods. This approach also was utilized to analyzed higher-order learning under scalar payoffs for the specific case of “anticipatory” higher order learning (Arslan and Shamma, “Distributed convergence to Nash equilibria with local utility measurements”). Likewise, we believe that the case of instantaneous scalar payoffs can be addressed using the setting in the present paper as the basis of the emergent ODEs of stochastic approximation.\n\n\nWeakness>> A weak point in the paper for me is that the results are based upon the assumption that the mixed NE is a practically useful solution concept in learning in games. However, recent works have shown that the NE can often not only be a poor metric for players’ performance, but also it is unnatural for players using decentralized dynamics to converge to an NE in general games. Thus, for a paper that focuses on higher order learning it would have been much more compelling to focus on a more complete picture of higher order gradient dynamics. What characterizes stable equilibria/fixed points for these dynamics in this setting? In cases where NE are not stable, what do the dynamics look like? In my opinion, a broader view of the dynamical system properties would make the results more interesting and useful.\n\nThe question of the relevance of Nash Equilibrium is a long standing one that won’t be resolved in this paper. Nonetheless, interest in Nash Equilibrium remains widespread. Also, studying higher-order uncoupled dynamics is an interesting topic on its own. We further believe that these results may be relevant to settings other than mixed-strategy Nash equilibrium, such as higher-order multi-agent learning in the absence of strict convexity.\n\nAs recognized by the reviewer, recent work shows the lack of natural decentralized dynamics to converge to a NE in general. This paper contributes to that line of work in relaxing the requirement of generality (Section 4), but also showing the lack of universality (Section 5). Furthermore, the topic of strong stabilization reinforces that the lack of natural dynamics to converge to the mixed equilibrium of a coordination game (Section 6).\n\nRegarding the characterization of stable equilibria (beyond eigenvalues), the results of this paper establish that it depends on both the specifics of the game and the structure of higher-order dynamics."}, {"review_id": "gC6uJMAAzr", "reviewer": "Reviewer_ZZgJ", "summary": "This paper studies multi-agent learning dynamics and the central question is if there is an iterative learning process in a multiplayer game that leads to a Nash equilibrium. There has been substantial prior work on this question for many specific games and learning strategies—generally it is not the case that known dynamics lead to a Nash equilibrium and this is perhaps frustrating as it would be convenient to be able to find Nash equilibria this way. The authors approach this problem in a way that is novel, as far as I know, by specifying a class of interesting/acceptable learning dynamics and using tools from feedback control systems to prove properties of that class. For interesting/acceptable, they require that dynamics are \"payoff based,\" which essentially limits the ability of each agent to see \"into\" the action space of other agents, and, I believe for tractability of the analysis, they limit the dynamics to a kind of generalized higher-order gradient play. They specifically show that\n1. If a game has a strictly mixed Nash equilibrium, there exist payoff-based dynamics that converge locally to that NE. (As a consequence, they show that these dynamics also converge to NE of \"nearby\" games.)\n2. However, there is no \"overall good\" dynamics—for any such dynamics, there exists a game with unique mixed NE such that these dynamics are unstable at that NE.", "questions": "I would be interested in the authors' thoughts on whether they view the class of higher-order dynamics they study as restrictive or not. It would be helpful to know, of the papers they cite, in which cases their dynamics class subsumes that of the methods proposed by that paper.", "limitations": "Yes, this is a theoretical work and the assumptions of the theorems are clearly stated.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The results are likely to be novel and provide important context to those who study multi-agent learning dynamics. As is typical, there are some asterisks (the particular learning dynamics are general, but I think the broader questions could motivate looking at an even more general class). The negative result about games with a unique NE seems particularly strong.\n\nThe authors have done substantial work to make the results interpretable, at least on the surface, to a broader audience that is not familiar with the control-theoretic tools they are using. I would challenge the authors to go even further with this (see weaknesses below).\n\n", "weaknesses": "For someone who is not familiar with the specific tools the authors use, the paper is quite hard to follow, even if the game-theoretic aspects are clear and familiar. Appendix D has some worked examples with plots in them. I would suggest thinking about whether it is possible to move some of this content to the main paper. The figures in the paper itself are not that helpful and could be improved, potentially with more detail. The paper lacks good figures currently.\n\nAnything the authors can do to further broaden the context of their results would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Question>> I would be interested in the authors' thoughts on whether they view the class of higher-order dynamics they study as restrictive or not. It would be helpful to know, of the papers they cite, in which cases their dynamics class subsumes that of the methods proposed by that paper.\n\nFor the convergence results of Section 4, more restrictions strengthen the results in that additional structures are not needed. The framework set forth in Section 2.3 does capture prior classes of higher-order learning dynamics characterized by differential equations. The paper goes on to restrict its attention to higher-order gradient learning.\n\nWeakness>> For someone who is not familiar with the specific tools the authors use, the paper is quite hard to follow, even if the game-theoretic aspects are clear and familiar. Appendix D has some worked examples with plots in them. I would suggest thinking about whether it is possible to move some of this content to the main paper. The figures in the paper itself are not that helpful and could be improved, potentially with more detail. The paper lacks good figures currently. Anything the authors can do to further broaden the context of their results would be helpful.\n\nWorking within the page limitations, one possibility is to move the proof sketches to the appendix and bring a couple of examples to the main body. The message of Figure 1 is an important one to make the connection to feedback systems. We will improve the caption to reinforce this message."}, {"review_id": "Ifo8JUBVMN", "reviewer": "Reviewer_tNmK", "summary": "The paper studies higher order dynamics, i.e., dynamics that can rely on more auxiliary states than those limited by the dimensionality of the action spaces, in network games with pairwise interactions between players. Importantly, these dynamics only depend on the sequence of payoff signals that each player receives and are, thus, called uncoupled (an important property in multi-agent settings). The paper shows that linear versions of such dynamics can locally lead to any isolated mixed Nash equilibrium. However, for each such dynamic, there exists a \"simple\" anticoordination game for which this dynamic will not work, i.e., will not stabilize the unique isolated mixed NE. Furthermore, as the paper explains, a linear dynamic that converges to a mixed NE may not be meaningful after all.\n\n**Post-rebuttal**: After reading the other reviews and the authors' responses, I conclude that my concerns stem from my limited understanding of the techniques that are used in the paper. In response, I increase my score from 3 to 5 (and the contribution subscore from 2 to 3) to reflect my evaluation of the results, but I decrease my confidence from 3 to 2 to reflect that I didn't not understand (parts of) the techniques used in the paper.", "questions": "- Can the authors address the weaknesses mentioned above? \n- Line 22: not the most updated list of papers. Here is an indicative reference to help the authors locate more recent papers in the area in my opinion: https://papers.nips.cc/paper_files/paper/2020/file/0ed9422357395a0d4879191c66f4faa2-Paper.pdf\n- Line 77: P_i(x_-i) and P(x_-i): I don't understand the subscript i in P_i. Also, the next sentence in lines 77-78 is even more confusing.\n- Line 80: is \"a\" tuple (and other such minor typos - the paper needs a proofreading)\n- Equations (4), (5) and (7): I had a hard time to follow the derivation of these equations. This is one instance of my comment above that the paper is highly not self-contained.\n- Line 160: wasn't y_i defined above as \\dot v_i? Is that the same?\n- Line 171: stabilizability and detectability seem to be important but are only defined in the Appendix. I think that the paper needs to be rewritten in a way that it is self-contained and easier to follow.\n- Line 241: locally exponentially stable - the same here. This notion has not been defined before.\n- Line 288-289: I missed this argument. Is it that the dynamics fail to monotonically improve with respect to input payoffs (line 282)? Again, I couldn't understand the argument without relying on the Appendix.\n- Lines 297/304: anticipatory higher-oder learning/passivity, contractive games - another series of terms that are used without having being defined before. At least the conclusions should be accessible by a wider audience, but this is not the case. ", "limitations": "Yes, adequately.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper provides existence results for uncoupled dynamics that (locally) converge to mixed Nash equilibria. To do so, the paper creates higher-order dynamics that overcome known limitations of lower-order dynamics, i.e., of dynamics whose dimension is constrained by the dimension of the action spaces. \n- The main takeaways of the paper are clearly presented.\n", "weaknesses": "- The paper is hihgly not self-contained. There is a strong reliance to prior literature and to the appendix. \n- As a result of the above and of the complicated notation, the paper was very hard for me to read. Although, I couldn't follow some parts and I couldn't verify the derivation of some results, the results seems plausible and the main takeaways are still clear (as mentioned above). \n- I found the motivation of main dynamics in line 140 (paragraph 3.2) inadequate - but this may be related to the fact, that the exposition was not good enough for me to be able to follow.\n- While the results inform the discussion on paper [16], they are merely existential and quite general. So, their practical and theoretical scope may be rather limited.\n- The paper could have done a better job in building upon more recent literature regarding convergence of dynamics to NE in games. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Question>> Can the authors address the weaknesses mentioned above?\n\nSee below for an item-by-item discussion. \n\nQuestion>> Line 22: not the most updated list of papers. \n\nThe list of papers, while admittedly brief, is representative and covers the qualitative aspects of convergence or non-convergence. We are glad to visit the suggested reference and papers cited therein. The suggested reference is a nice complement to the present paper in that it contrasts what can be concluded with and without higher-order dynamics.\n\nQuestion>>  Line 77: I don't understand the subscript in P_i. Also, the next sentence in lines 77-78 is even more confusing.\n\nThe subscript $i$ indicates that $P_i$ is the payoff vector of player $i$ which as mentioned has the same dimension as the strategy vector $x_i$. The subscript was mistakenly dropped in line 77. The sentence in line 78 suggests viewing each entry of $P_i$ as a payoff associated to a certain strategy of player $i$.\n\nQuestion>> Line 80: is \"a\" tuple (and other such minor typos-\n\nA final version will take care of all the minor editorial issues\n\nQuestion>> Equations (4), (5), and (7): I had a hard time to follow the derivation of these equations.\n\nAs strategies evolve on the simplex, it is beneficial to project dynamics to their natural dimension (e.g., the simplex in R^3 is two-dimensional). The variable $w_i$ represents movement on this low-dimensional subspace. A revision can reinforce this interpretation.\n\nQuestion>> Line 160: wasn't y_i defined above as \\dot v_i? Is that the same?\n\nThe specific linear dynamics that ensure compliance with Assumption 2.1 have an internal state denoted by $v_i$ and the equation $\\dot{v_i} =  ...... $ describes the evolution of the state $v_i$. The variable $y_i$ is the output of this specific linear system.\n\nQuestion>> Line 171: stabilizability and detectability seem to be important but are only defined in the Appendix. \n\nWithout going into the definitions, an implication of stabilizability and detectability is the existence of *coupled* learning dynamics that lead to Nash Equilibrium. This is a clear prerequisite to the existence of uncouple learning dynamics. A revision can reinforce this point.\n\nRegarding the paper being self-contained, the paper uses both basic concepts from control theory as well as less widely utilized ones (decentralized stabilization and strong stabilization). Accordingly, we believe that a peripheral value of the paper is bringing these concepts to the forefront in multi-agent learning.\n\nQuestion>> Line 241: locally exponentially stable \n\nThe notion is a basic one in the study of dynamical systems. A revision can add a reference.\n\nQuestion>> Line 288-289: Is it that the dynamics fail to monotonically improve with respect to input payoffs (line 282)?\n\nThe issue is that the dynamics fail to converge (monotonically or not) to a best response to *constant* payoff vector. A revision can better explain this point.\n\nQuestion>> Lines 297/304:  At least the conclusions should be accessible by a wider audience, but this is not the case.\n\nThere are two parts to this paragraph. The first is that there is a discussion to be had on what constitutes “natural”. This is stated plainly. The second part, which is less accessible, points to candidate notions with references, some more familiar than others (e.g., no regret vs passivity). A revision can try to broaden the accessibility\n\n\nWeakness>> The paper is highly not self-contained. There is a strong reliance to prior literature and to the appendix.\n\nWe are doing our best work within the page limitations to bring into the paper what is essential to the main contributions and refer to prior literature and appendix for background and support. The current approach maintains the flow of the paper while providing a thorough overview in the appendix to help the reader navigate the paper.\n\nWeakness>> As a result of the above and of the complicated notation, the paper was very hard for me to read. Although, I couldn't follow some parts and I couldn't verify the derivation of some results, the results seems plausible and the main takeaways are still clear\n\nWe are encouraged to hear that the main takeaways are clear. As mentioned previously, a peripheral value of the paper is that it brings in new tools to multi-agent learning, and we trying to work with the page restrictions accordingly.\n\nWeakness>> I found the motivation of main dynamics in line 140 inadequate\n\nThe main dynamics are a special case of the general form in Section 2.3 where (i) the baseline learning rule is gradient-play and (ii) the higher-order modification is restricted to be linear. The payoff vector is processed through specific linear dynamics (call it a preprocessing phase) to ensure compliance with assumption 2.1, and then the output $y_i$ of the preprocessing procedure is used in the general decision dynamics (which are also linear). We can reinforce this interpretation in a revision.\n\nWeakness>> While the results inform the discussion on paper [16], they are merely existential and quite general. So, their practical and theoretical scope may be rather limited.\n\nThere is a clear theoretical contribution to delineate what is or is not possible under uncoupled learning rules. Furthermore, the control-theoretic tools used herein enable the analysis of higher-order multi-agent learning beyond widely studied cases such as zero-sum games or pure strategy equilibria. Regarding the statement that the results are merely existential, there are approaches in the control theory literature to construct higher-order dynamics. We chose to omit these constructions since the focus here is on fundamental limits under uncoupled learning.\n\nWeakness>> The paper could have done a better job in building upon more recent literature\n\nWe can include more recent literature, such as the paper mentioned by the reviewer. However, none of the recent literature addresses the specific questions of the present paper.\n\n\n"}]

Author rebuttal:

Meta-review: This paper examines the (im)possibility of convergence to Nash equilibrium in polymatrix games under higher-order learning dynamics. The authors' main result is that, for every polymatrix game with an isolated, fully mixed Nash equilibrium, there exists a higher-order gradient-based dynamical system for which this equilibrium is stable. On the flip side, the authors also show that for a specific, projection-type dynamical system, the mixed Nash equilibrium of Jordan's matching pennies game is unstable.

The reviewers appreciated the paper's technical contributions and most of the reviewers' concerns were addressed satisfactorily during the discussion phase. The main issues that were raised concerned the paper's readability from a wider audience, and the fact that no microfoundations (or other type of justification) were given for the dynamics that "detect" a given mixed equilibrium.

The readability issue is mostly due to the fact that the authors are employing notions and terminology from control theory, which are not sufficiently standard in the field at large; for this, I would urge the authors to take advantage of the extra page to provide more context and explanations for some of the lesser-known tools and techniques that they employ (including the definition of the dynamics, the notion of "washout filters", etc.).

The microfoundations issue is more tricky: since this is an existence result, the authors' approach is justified in juxtaposition to the impossibility result of Hart & Mas-Colell; at the same time, if the dynamics that detect a given mixed equilibrium only work for a particular game and are otherwise non-convergent, then, in the absence of solid microfoundations, the authors' existence result is somewhat weakened.

Regardless, even with the above limitations, the paper's analysis and results provide a number of fruitful insights into a difficult problem, so there were no objections to an "accept" recommendation. My own assessment is aligned with the reviewers' consensus, and I am happy to recommend acceptance as well.

I would only like to draw attention to the following point: the authors' analysis concerns *polymatrix* games, not the mixed extension of finite games. This does not weaken the paper's contributions, but it does mean that the paper's setting is not quite the same as classical finite games. This should be made clearer in the abstract and the introduction as, otherwise, it could lead to confusion in the literature.
Decision: Accept (poster)