Paper deep dive
Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games
Hédi Hadiji, Sarah Sachs
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/9/2026, 1:47:29 AM
Summary
This paper investigates the stability and last-iterate convergence of the optimistic exponential weights (optEW) algorithm in two-player bimatrix games. It allows for asymmetric step sizes and establishes a sufficient condition for global convergence in zero-sum games, alongside an almost-tight threshold for asymptotic stability in general games, both primarily governed by the product of the step sizes and the Jacobian at equilibria.
Entities (6)
Relation Signals (5)
Optimistic Exponential Weights → appliedto → Bimatrix Games
confidence 95% · We study bimatrix two-player games and investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method.
Nash Equilibrium → istargetof → Optimistic Exponential Weights
confidence 90% · investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method.
Step Sizes → determines → Asymptotic Stability
confidence 85% · Our second main result provides an almost-tight threshold for asymptotic stability and instability, again in terms of products of the step sizes, for general bimatrix games.
Zero-Sum Games → exhibits → Last-Iterate Convergence
confidence 85% · establishes, under the assumption that the set of fixed points is finite, a sufficient condition for global last-iterate convergence in the special case of zero-sum games
Jacobian Matrix → characterizes → Asymptotic Stability
confidence 80% · We give a characterization of the stability in terms of the product of the step sizes ηxηy and the Jacobian at an equilibrium.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study bimatrix two-player games and investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method. In contrast to prior work, we allow the step sizes $\eta_x$ and $\eta_y$ to differ. Our first main result establishes, under the assumption that the set of fixed points is finite, a sufficient condition for global last-iterate convergence in the special case of zero-sum games, which constrains only the product $\eta_x\eta_y$ of the step sizes. This condition is practically relevant and partially explains empirically observed behavior. Our second main result provides an almost-tight threshold for asymptotic stability and instability, again in terms of products of the step sizes, for general bimatrix games. This result is primarily of theoretical interest. We derive several known results and practically relevant step size bounds for special cases and illustrate our results by experiments.
Tags
Links
- Source: https://arxiv.org/abs/2607.07517v1
- Canonical: https://arxiv.org/abs/2607.07517v1
Trouble viewing inline? Open PDF directly →
Full Text
182,902 characters extracted from source content.
Expand or collapse full text
Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games Hédi Hadiji Laboratoire des Signaux et Systèmes, CentraleSupélec, Paris, France Sarah Sachs School of Mathematics, University of Bristol, Bristol, United Kingdom Abstract We study bimatrix two-player games and investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method. In contrast to prior work, we allow the step sizes ηx _x and ηy _y to differ. Our first main result establishes, under the assumption that the set of fixed points is finite, a sufficient condition for global last-iterate convergence in the special case of zero-sum games, which constrains only the product ηxηy _x _y of the step sizes. This condition is practically relevant and partially explains empirically observed behavior. Our second main result provides an almost-tight threshold for asymptotic stability and instability, again in terms of products of the step sizes, for general bimatrix games. This result is primarily of theoretical interest. We derive several known results and practically relevant step size bounds for special cases and illustrate our results by experiments. Keywords: Optimistic Exponential Weights, Bimatrix Games, Stability, Convergence. 1 Introduction We consider bimatrix games Γ(A,B) (A,B) with payoff matrices A,B⊤∈ℝdx×dyA,B ^d_x× d_y. Denote by Δdx _d_x and Δdy _d_y the probability simplices in ℝdx R^d_x (respectively ℝdy R^d_y). The x-player chooses x∈Δdxx∈ _d_x to maximize x⊤Ayx Ay, while the y-player chooses y∈Δdyy∈ _d_y to maximize y⊤Bxy Bx. A Nash equilibrium [x⋆,y⋆][x ,y ] satisfies x⋆∈argmaxx∈Δdxx⊤Ay⋆,y⋆∈argmaxy∈Δdyy⊤Bx⋆.x ∈ _x∈ _d_xx Ay , y ∈ _y∈ _d_yy Bx . A central question in game theory and learning in games is whether simple, efficient iterative algorithms converge to such equilibrium points. Classical dynamics such as Gradient Descent-Ascent and Multiplicative Weights Update are known to exhibit cycling and fail to converge even in simple bilinear games (see, e.g., Bailey and Piliouras (2018); Cheung and Piliouras (2019); Mertikopoulos et al. (2018b)). This has motivated significant interest in simple modifications of these algorithms that mitigate this issue. A prominent approach is the optimism framework (Chiang et al., 2012; Rakhlin and Sridharan, 2013; Syrgkanis et al., 2015), which underlies algorithms such as Optimistic Gradient Descent–Ascent and optimistic exponential weights (optEW). In this paper, we study the stability of Nash equilibria under optimistic exponential weights dynamics (and variants thereof) in two-player bimatrix games. That is, all coordinates i∈1,…,dxi∈\1,…,d_x\ and j∈1,…,dyj∈\1,…,d_y\ are updated as xt+1,i∝xt,iexp(ηx[A(2yt−yt−1)]i) and yt+1,j∝yt,jexp(ηy[B(2xt−xt−1)]j),x_t+1,i \,x_t,i ( _x[A(2y_t-y_t-1)]_i) and y_t+1,j \,y_t,j ( _y[B(2x_t-x_t-1)]_j)\,, (1) where ηx,ηy>0 _x, _y>0 are the step sizes. There are two fundamentally different settings for the step size choices: (1) constant step sizes and (2) time-dependent step sizes. We study the convergence behavior of (zt)t∈ℕ=((xt,yt))t∈ℕ(z_t)_t∈ N=((x_t,y_t))_t∈ N under constant, potentially unequal step sizes. We refer to this setting as using asymmetric step sizes, noting that related literature sometimes describes it as ‘two-time-scale’ step sizes (Lin et al., 2025). We adopt the former terminology to clearly distinguish our setting from time-varying step size schemes for saddle-point problems with stochastic feedback. In the classical two-time-scale framework, the step size sequences (ηx,t)( _x,t) and (ηy,t)( _y,t) are assumed to be not summable but square summable and satisfy ηx,t/ηy,t→0 _x,t/ _y,t→ 0 as t→∞t→∞ (Borkar, 1997, 2025). Existing analyses often rely on simultaneously controlling both step sizes, which results in a step size requirement ηx=ηy _x= _y, or controlling the individual step sizes, which results in step size requirements on maxηx,ηy \ _x, _y\. Such conditions do not capture the product dependence as suggested by empirical observations (see Figure 1). Our results align with these experiments. Contributions: 1. Global convergence results under sufficient step size conditions: We give a sufficient product-type step size condition guaranteeing that, from relative-interior initialization, optimistic exponential weights dynamics in zero-sum games globally converge to the set of fixed points. If, in addition, the fixed-point set is finite, then the last iterate converges to a Nash equilibrium. 2. Local convergence for general games: We study the stability of equilibria of the optEW dynamics. We give a characterization of the stability in terms of the product of the step sizes ηxηy _x _y and the Jacobian at an equilibrium. The step size criterion is almost tight, meaning if ηxηy∈(0,c) _x _y∈(0,c) stability follows, and if ηxηy∈(c,∞) _x _y∈(c,∞) instability follows. However, the case ηxηy=c _x _y=c is indeterminate. 3. Empirical Studies and Open Research Directions: We provide extensive numerical experiments that (a) show that our theoretical results closely match observed behavior and (b) highlight open research questions that cannot be explained by our results. Our first result provides a practical step size condition and establishes convergence over a wider range of step sizes than previously known. The second result, while primarily of theoretical interest, offers a foundation for the commonly observed phenomenon that algorithms perform well beyond their formal step size guarantees. Motivation and Broader Context: While our results are primarily of fundamental theoretical interest, our findings are also motivated by several practical considerations. For example, for non-convex-concave optimization, different step sizes are often used to guarantee convergence of the concave maximization subproblem while maintaining overall stability (see, e.g., Lin et al. (2025) and references therein). Similar asymmetries arise in bilevel optimization, where the inner problem is typically updated more aggressively than the outer problem (e.g., Hong et al. (2023)), and in stochastic games, where players may experience different feedback variances (e.g., Sayin and Cetiner (2022)). Product-based conditions capture the relevant invariant for stability, while the ratio governs finer properties (e.g. basin size) that we study empirically (cf. Section 5). Related Literature: Our work is most closely related to the work by De Montbrun and Renault (2025), who analyze optimistic gradient descent in unconstrained general-sum bilinear games and characterize sharp stability regions via the eigenvalues of the induced linear system. Although their focus is not on asymmetric step sizes, their analysis implies a similar product-dependence of the step sizes in unconstrained bilinear games. For more details and an in-depth discussion, see Section 4.5. Fiez and Ratliff (2021) also study the role of asymmetric step sizes in game dynamics, showing that gradient descent-ascent with a sufficiently large but finite timescale-separation ratio converges locally to strict local minmax/Stackelberg equilibria in smooth nonconvex-nonconcave zero-sum games, while non-equilibrium critical points become unstable. Conceptually, our work is also closely related to the research on replicator dynamics and discretized variants thereof. The exponential weights method can be viewed as an Euler discretization of the replicator dynamics. This is a well-known connection; for details, see, e.g., Falniowski and Mertikopoulos (2025). The discrete-time nature of multiplicative weights is known to produce recurrence, cycling, and chaotic behavior in games (Mertikopoulos et al., 2018b; Falniowski and Mertikopoulos, 2025). Examples of stability analysis for replicator dynamics include Weibull (1995), Hofbauer and Sigmund (1998), Sandholm (2010), and references therein. For the equal step size regime, a large body of work establishes convergence guarantees of optimistic or extra-gradient-type dynamics under suitable step size conditions. These methods have a long history: extra-gradient and related prediction-correction schemes go back at least to Korpelevich (1976) and Popov (1980). In online learning, optimistic mirror descent, optimistic follow-the-regularized-leader, and optimistic exponential weights arise from the predictable-sequences framework of Chiang et al. (2012); Rakhlin and Sridharan (2013). They have become central in the study of last-iterate convergence in games, since methods such as gradient descent-ascent and multiplicative weights may cycle or exhibit unstable behavior even for zero-sum games (Bailey and Piliouras, 2018; Mertikopoulos et al., 2018b; Cheung and Piliouras, 2019). In convex-concave and monotone settings, this optimistic structure yields positive stability results. Asymptotic convergence guarantees were proved for optimistic mirror descent and stochastic extra-gradient variants by Mertikopoulos et al. (2018a) and Hsieh et al. (2019). Daskalakis and Panageas (2018) studied the limit points and local stability of optimistic gradient dynamics, while Daskalakis and Panageas (2019) proved last-iterate convergence for optimistic multiplicative-weights dynamics. Lei et al. (2021) extended this to local last-iterate convergence with constant step size using a spectral analysis approach. See Section 4.5 for a detailed discussion. We note that the focus of this line of literature is on improving the convergence rates; thus, comparisons should be made with caution due to the conceptual differences. 1.1 Notation We denote sets by curly letters, e.g., Z. Sets of equilibria are indicated by stars, i.e., ⋆ Z , and (if distinction is necessary for clarity) sets of fixed points of an operator T by tildes, e.g., ~(T) Z(T). Furthermore, for set A, we let relintrelint A denote the relative interior. We denote by ℝ+ R_+ the set of non-negative real numbers. For d∈ℕd , let Δd:=x∈ℝ+d:⊤x=1 _d:=\x ^d_+:1 x=1\ denote the probability simplex in ℝd R^d. For matrix M∈ℝn×dM∈ R^n× d, we denote by ‖M‖1→∞:=maxi,j|Mi,j| \|M \|_1→∞:= _i,j |M_i,j | and ‖M‖ℓ2\|M\|_ _2 denotes the ℓ2 _2 operator norm. For vector v∈ℝdv∈ R^d, we let diag(v)∈ℝd×ddiag(v)∈ R^d× d denote the diagonal matrix with v as the diagonal. By d1_d we denote the all-ones vector in ℝd R^d; we omit the dimension whenever it is clear from the context. We denote the canonical basis vectors in ℝd R^d by e1,…ede_1,… e_d. By ⊙ we denote the Hadamard (entry-wise) multiplication and ExpExp denotes the component-wise exponential function. Throughout the paper, we use the convention that 0∉ℕ0 ∈ N. 2 Algorithm and General Results Our analysis builds on techniques from discrete dynamical systems. Thus, we define an operator Φm _m corresponding to the optimistic exponential weights method in a two-player game. The optimistic updates depend on the last two gradients seen, so the corresponding mapping operates on the product of simplices Δ^:=(Δdx×Δdy)×(Δdx×Δdy)⊂ℝ2(dx+dy) :=( _d_x× _d_y)×( _d_x× _d_y) ^2(d_x+d_y). We also introduce a parameter m∈(0,1]m∈(0,1], which controls the impact of the optimistic updates. We recover the usual optEW (as stated in (1)) when m=1m=1. In the limit m↓0m 0, the update approaches standard exponential weights. For any vector v∈ℝdv ^d with v⊤≠0v 1≠ 0, define Pd(v)=(∑i=1dvi)−1v,P_d(v)= ( _i=1^dv_i )^-1v\,, and Φm=[z1,z2,z3,z4]∈ℝdx×ℝdy×ℝdx×ℝdy|∑i=1dxz1,iexp(ηx[A((1+m)z2−mz4)]i)≠0and∑j=1dyz2,jexp(ηy[B((1+m)z1−mz3)]j)≠0 D_ _m= \[z_1,z_2,z_3,z_4] ^d_x×R^d_y×R^d_x×R^d_y |\\ _i=1^d_xz_1,i ( _x[A((1+m)z_2-mz_4)]_i)≠ 0 _j=1^d_yz_2,j ( _y[B((1+m)z_1-mz_3)]_j)≠ 0 \ The map we consider is Φm:Φm→ℝ2(dx+dy)(z1z2z3z4)↦(Pdx(z1⊙Exp(ηxA((1+m)z2−mz4)))Pdy(z2⊙Exp(ηyB((1+m)z1−mz3)))z1z2). _m: \ aligned & D_ _m&→& R^2(d_x+d_y)\\ & pmatrixz_1\\ z_2\\ z_3\\ z_4 pmatrix& & pmatrixP_d_x (z_1 ( _xA((1+m)z_2-mz_4)) )\\[4.0pt] P_d_y (z_2 ( _yB((1+m)z_1-mz_3)) )\\[4.0pt] z_1\\[4.0pt] z_2 pmatrix aligned .\,. (2) We note that on the domain Φm D_ _m, PdP_d is always well defined and Φm(Δ^)⊆Δ _m( ) . Moreover, the sequences (xt)t∈ℕ(x_t)_t∈ N and (yt)t∈ℕ(y_t)_t∈ N are iterates of the optimistic exponential weights method, cf. (1), if and only if Zt=(xt,yt,xt−1,yt−1)Z_t=(x_t,y_t,x_t-1,y_t-1) satisfies Zt+1=Φ1(Zt)Z_t+1= _1(Z_t) for all t∈ℕt∈ N and Z0∈Δ^Z_0∈ . Ultimately, we are interested only in the iterates of Φm|Δ _m|_ . Crucially, we note that the repeated iterations in the ambient space Φm D_ _m are not well defined since Φm(Φm) _m( D_ _m) is not necessarily a subset of Φm D_ _m. We emphasize that this is not used, and the ambient extension is used solely to compute the differential. Fixed points of Φm _m We start with a characterization of the fixed points for Φm|Δ . -1.2pt _m | |_ . Theorem 2.1. For any m∈(0,1]m∈(0,1] and ηx,ηy>0 _x, _y>0, the set of fixed points of Φm|Δ . -1.2pt _m | |_ is: ~(Φm|Δ^)=[z1,z2,z3,z4]∈Δ^|z1=z3∈Δdx,z2=z4∈Δdy,∀i,j∈supp(z1),(Az2)i=(Az2)j,∀k,l∈supp(z2),(Bz1)k=(Bz1)l Z( . -1.2pt _m | |_ )= \[z_1,z_2,z_3,z_4]∈ \; |\; aligned &z_1=z_3∈ _d_x,\;z_2=z_4∈ _d_y,\\ &∀ i,j∈ *supp(z_1),\;(Az_2)_i=(Az_2)_j,\\ &∀ k,l∈ *supp(z_2),\;(Bz_1)_k=(Bz_1)_l aligned \ The proof is deferred to Appendix A. We define the set of points corresponding to the set of Nash equilibria lifted in dimension as ⋆=[x⋆,y⋆,x⋆,y⋆]:[x⋆,y⋆] is a Nash equilibrium⊆Δ^. Z =\[x ,y ,x ,y ]:[x ,y ] is a Nash equilibrium\ \,. With a slight abuse of terminology, we refer to ⋆ Z as ‘the set of Nash equilibria’. Remark 2.1. All Z∈⋆Z∈ Z are fixed points of Φm _m but a fixed point Z∈~(Φm|Δ^)Z∈ Z( . -1.2pt _m | |_ ) is not necessarily in ⋆ Z . As an example, consider a game with a unique fully mixed Nash equilibrium. Then (ei,ej,ei,ej)(e_i,e_j,e_i,e_j), i∈1,…,dx,j∈1,…,dyi∈\1,…,d_x\,j∈\1,…,d_y\ are fixed points of Φm|Δ . -1.2pt _m | |_ (and of Φm _m), but are not contained in ⋆ Z . To define stability and instability of a set ⊂ S⊂ Z, we denote the distance d(Z,):=infZ′∈‖Z−Z′‖d(Z, S):= _Z ∈ S \|Z-Z \|. Definition 2.1 (Invariant, Stable, Asymptotically Stable and Globally Attracting Sets). Let F:→F: Z→ Z and let ⊆ C Z. We say C is a (forward) invariant set if F()⊆F( C) C. A set ⊂ S⊂ Z is 1. (Lyapunov) stable, if for all ϵ>0ε>0 there exists a δ>0δ>0, such that for any n∈ℕn∈ N and any z∈z∈ Z with d(z,)<δd(z, S)<δ, we have d(Fn(z),)<ϵd(F^n(z), S)<ε; 2. an attracting set if there exists δ>0δ>0 such that for any z∈z∈ Z with d(z,)<δd(z, S)<δ, we have d(Fn(z),)→n→∞0d(F^n(z), S) [n→∞]0; 3. asymptotically stable if S is a stable and attracting set. We call S unstable if it is not stable. We call S globally attracting on Z if d(Fn(z),)→n→∞0d(F^n(z), S) [n→∞]0 for any z∈z∈ Z. In particular, if S is a singleton, we call it a stable/unstable, asymptotically stable, or globally attracting fixed point. Ultimately, we are interested in the attractiveness and stability of the set corresponding to the Nash equilibria ⋆ Z . We note that the definition of Lyapunov stability requires the sequence to stay in Z. Again, note that this does not necessarily hold for the ambient space Φm D_ _m. Thus, we restrict to Δ for our global convergence result. 3 Global Convergence for Zero-Sum Games In this section, we restrict Φm|Δ . -1.2pt _m | |_ to m=1m=1, that is Φ1|Δ . -1.2pt _1 | |_ . Furthermore, we add the standing assumption that the initial Z0Z_0 is from the relative interior of Δ . We show that for the special case of zero-sum games, the dynamics converge to ⋆ Z if ηxηy‖A‖1→∞2⩽16 _x _y\,\|A\|_1→∞^2 16. Our argument consists of two steps: 1. In Theorem 3.1, we use a Lyapunov-style argument to show that ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is globally attracting; 2. We show that, under the assumption that ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is finite, every accumulation point of the dynamics is an equilibrium in Theorem 3.2. Theorem 3.1. Consider a zero-sum game Γ(A,−A⊤) (A,-A ). Assume Z0∈relintΔ^Z_0 and 0<ηxηy∥A∥1→∞2⩽16.0< _x _y\,\|A\|_1→∞^2 16\,. Then the set of fixed points ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is globally attracting with respect to relintΔ^relint . For a formal proof, see Appendix C.1. We note that Theorem 3.1 does not show convergence to the set of Nash equilibria. Recall the example from Remark 2.1. In this example, the pure actions are repelling, but ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is globally attracting. Intuitively, this implies that the dynamics will not converge to the repelling fixed points, but only to the Nash equilibria, which we show formally in the following theorem. Theorem 3.2. Consider Γ(A,−A⊤) (A,-A ) and assume Z0∈relintΔ^Z_0 and ηx,ηy _x, _y satisfy the step size condition of Theorem 3.1. Further, assume that ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is finite. Let (Zt)t∈ℕ(Z_t)_t be the sequence of iterates defined by Zt=Φ1(Zt−1)Z_t= _1(Z_t-1). Then, (Zt)t∈ℕ(Z_t)_t converges and the limit Z∞Z_∞ is a Nash equilibrium; that is, Z∞∈⋆Z_∞∈ Z . For a proof, see Appendix C.2. While our results cover a wide range of step sizes, note that even for these toy examples, we can observe two limitations: (1) the step size bound is not tight; and (2) we observe a similar behavior for non-zero-sum games, which is not covered by Theorem 3.2. In Section 4, we provide (partial) answers to these open questions. Remark 3.1. Consider a zero-sum game Γ(A,−A⊤) (A,-A ) where A has at least one non-zero entry. For step sizes ηx=ηy _x= _y with 0<ηxηy⩽1/(82‖A‖ℓ22)0< _x _y 1/(8^2 \|A \|^2_ _2), the results in Wei et al. (2021) imply last iterate convergence of 11-optEW. Observe that 1/(82‖A‖ℓ22)<1/(6‖A‖1→∞2)1/(8^2 \|A \|^2_ _2)<1/(6 \|A \|_1→∞^2). However, we emphasize that their focus is on convergence rates. (a) Rock-Paper-Scissors (b) Non-Zero-Sum Matching Pennies Figure 1: Estimated convergence and divergence of 11-optEW as a function of ηxηy _x _y. The dynamics are labeled as convergent if they reach an ϵε-neighbourhood of the Nash equilibrium within 10 00010\,000 iterations. The non-convergence for ηxηy<0.01 _x _y<0.01 is due to the finite-time cut-off. For zero-sum games, the step size range shown in Theorem 3.2 is highlighted. For both games, see Appendix F for details. 3.1 Why m=1m=1? In our result, we focused on vanilla optimistic exponential weights, namely 11-optEW. The local stability results in Section 4.4.1 show that, for m⩽1/2m 1/2, fully mixed equilibria in the stated zero-sum setting are locally unstable. Hence, no result asserting global asymptotic stability can hold in that regime. The case m∈(12,1)m∈( 12,1), however, remains unclear. In Section 5.3.1, we provide numerical evidence suggesting that m-optEW global convergence may fail for m∈(12,1)m∈( 12,1) with step sizes that still guarantee asymptotic stability (cf. Section 4). Establishing this rigorously remains an interesting open problem. 4 Local Convergence We now characterize the asymptotic stability and instability of fixed points and equilibria under the m-optEW dynamics as a function of the product of the step sizes. Our main local result is that stability can be read off from the Jacobian of the dynamics at a fixed point, once it is restricted to the hyperplane containing the simplex. We then show that the corresponding spectrum admits an explicit description in terms of a smaller local matrix Mx(Z)M_x(Z) (cf. (4)), from which one obtains that, for equilibria, stability depends only on the product ηxηy _x _y. Notation: For any finite-dimensional real linear map T:E→ET:E→ E and any real T-invariant subspace V⊆EV E, the notation eig(T|V),eig~(T|V),eig (T|_V ), eig (T|_V ), and ρ(T|V)ρ (T|_V ) denotes the spectrum, the spectrum without multiplicities, and the spectral radius of the complexified restriction (T|V)ℂ:Vℂ→Vℂ.(T|_V)_C:V_C→ V_C. When a real matrix or real linear map is applied to a vector in a complexified space, we use its complex-linear extension and suppress the subscript ℂC whenever it is clear from the context. The modulus of a complex number c∈ℂc is denoted by |c| |c |. 4.1 Stability and the Jacobian We follow a standard method and evaluate the eigenvalues of the differential of the function Φm _m defining the dynamics at the fixed point. There are, however, some technical hurdles we need to handle • We are interested in Φm|Δ _m|_ and Δ has an empty interior, so the computation of its differential is non-trivial. Recall, we defined Φm _m as a function Φm→ℝd D_ _m ^d, where Φm D_ _m is open, so the computation of its differential is straightforward via standard rules. However, the mapping of interest is the restriction of Φm _m to Δ . • Equilibria may occur on the boundary of Δ . There, the differential is not a priori enough to characterize stability. Theorem 4.1 is a key technical result to handle these technical challenges. Define the linear part of the hyperplane containing Δ as, L=[h1,h2,h3,h4]∈ℝdx×ℝdy×ℝdx×ℝdy∣hk⊤=0 for all k∈1,2,3,4.L=\[h_1,h_2,h_3,h_4] ^d_x× R^d_y×R^d_x× R^d_y h_k 1=0 for all $k∈\1,2,3,4\$\\,. Recall that to discuss the eigenvalues of the restricted Jacobian JΦm(Z)|LJ_ _m(Z)|_L, one first has to show that L is invariant under JΦm(Z)J_ _m(Z). Theorem 4.1. Let Z∈Δ^Z∈ denote a fixed point of Φm _m. That is, Z∈~(Φm|Δ^)Z∈ Z( . -1.2pt _m | |_ ). Then JΦm(Z)L⊂LJ_ _m(Z)L⊂ L. Moreover, Z is an asymptotically stable fixed point for Φm|Δ . -1.2pt _m | |_ if the spectral radius satisfies ρ(JΦm(Z)|L)<1ρ ( . -1.2ptJ_ _m(Z) | |_L )<1, and Z is unstable if ρ(JΦm(Z)|L)>1ρ ( . -1.2ptJ_ _m(Z) | |_L )>1. The proof is deferred to Appendix D.3. It combines four main ingredients. First, one computes the Jacobian of Φm _m at a fixed point. Second, one shows that the relevant local dynamics is obtained by restricting Φm _m to the affine space Z+LZ+L, and that the corresponding linearization is given by the restricted Jacobian JΦm(Z)|LJ_ _m(Z)|_L. Third, one applies standard local dynamical systems arguments to this restricted dynamics. Finally, because fixed points may lie on the boundary of Δ , the instability statement requires an additional argument adapted to the constrained setting. The borderline case ρ(JΦm(Z)|L)=1ρ ( . -1.2ptJ_ _m(Z) | |_L )=1 is not covered by this criterion: The linearization alone does not suffice in general to determine stability. 4.2 The Spectrum of the Jacobian Notation and definitions We provide a characterization of the stability of a fixed point Z in terms of a local matrix Mx(Z)M_x(Z). Let Z be a fixed point of Φm _m. Then Z=[x,y,x,y]Z=[x,y,x,y], and we denote by Sx:=i∈[dx]∣xi>0S_x:=\i∈[d_x] x_i>0\ and Sy:=j∈[dy]∣yj>0S_y:=\j∈[d_y] y_j>0\ the supports of the two strategies, with cardinalities nx:=|Sx|n_x:=|S_x| and ny:=|Sy|n_y:=|S_y|. Since Z is a fixed point, the payoffs are constant on the supports, so we may define vx:=(Ay)iv^x:=(Ay)_i for any i∈Sxi∈ S_x and vy:=(Bx)jv^y:=(Bx)_j for any j∈Syj∈ S_y. We also write Lx:=h∈ℝnx∣h⊤=0L_x:=\h ^n_x h 1=0\ and denote by ΠSx∈ℝnx×dx _S_x ^n_x× d_x the coordinate-selection matrix associated with the supports. For i∈1,…,dxi∈\1,…,d_x\ and j∈1,…,dyj∈\1,…,d_y\, let 1,i:=exp(ηx((Az2)i−vx))w_1,i:= \! ( _x ((Az_2)_i-v^x ) ) and 2,j:=exp(ηy((Bz1)j−vy))w_2,j:= \! ( _y ((Bz_1)_j-v^y ) ), and collect the off-support terms in W=1,i∣i∈1,…,dx∖Sx∪2,j∣j∈1,…,dy∖Sy.W=\w_1,i i∈\1,…,d_x\ S_x\∪\w_2,j j∈\1,…,d_y\ S_y\\,. (3) We further write H(z):=diag(z)−zz⊤H(z):=diag(z)-z . The reduced matrix governing the nontrivial part of the spectrum is then Mx(Z)=ΠSxH(z1)AH(z2)BΠSx⊤∈ℝnx×nx.M_x(Z)= _S_xH(z_1)AH(z_2)B _S_x ^n_x× n_x\,. (4) Finally, for any λ∈ℂ∖m/(m+1)λ \m/(m+1)\, define the rational map Qm(λ)=λ2(λ−1)2((m+1)λ−m)2.Q_m(λ)= λ^2(λ-1)^2((m+1)λ-m)^2\,. Main result We are now ready to state the main theorem of this section, which characterizes the spectrum of JΦm(Z)|LJ_ _m(Z)|_L via Mx(Z)M_x(Z). We note that the following theorem does not account for multiplicities of eigenvalues; however, for the stability analysis, multiplicities are irrelevant. Theorem 4.2. Let Z∈Δ^Z∈ be a fixed point of Φm _m and assume nx⩾nyn_x n_y. The spectrum of the Jacobian without multiplicities is eig~(JΦm(Z)|L)∖0=(W∪Qm−1(eig~(ηxηyMx(Z)|Lx)))∖0. eig (J_ _m(Z)|_L ) \0\= (W∪ Q_m^-1 ( eig ( _x _yM_x(Z)|_L_x ) ) ) \0\\,. The proof consists of carefully following the eigenvalues and eigenvectors, and is detailed in Appendix D.1. We exclude the eigenvalue λ=0λ=0 for technical reasons (the reduction to the equation involving QmQ_m requires dividing by λ). The value 0 plays no role in the stability analysis, since it is strictly less than one. An important feature of Theorem 4.2 is that it separates the spectrum into two parts: the off-support eigenvalues are collected in W, and the support-restricted eigenvalues are governed by Qm−1(eig(ηxηyMx(Z)|Lx)).Q_m^-1\! (eig ( _x _y . -1.2ptM_x(Z) | |_L_x ) ). The off-support eigenvalues may depend on (ηx,ηy)( _x, _y) separately, but they do not affect the stability analysis of Nash equilibria. For example, if the fixed point Z corresponds to a quasi-strict Nash equilibrium111A Nash equilibrium is quasi-strict if all best response pure actions have positive support., then every eigenvalue in W has modulus strictly smaller than 11; whereas if Z does not correspond to a Nash equilibrium, then at least one eigenvalue in W has modulus strictly larger than 11. Thus, the off-support spectrum distinguishes Nash equilibria from non-equilibrium fixed points. Conditional on Z corresponding to a quasi-strict Nash equilibrium, all off-support eigenvalues are already stable, and the remaining stability information is determined solely by the product ηxηy _x _y through the spectrum of ηxηyMx(Z)|Lx _x _yM_x(Z)|_L_x. Building on this property, we derive results for special cases in Section 4.4. Remark 4.1. The assumption that the support of the x-player is greater than or equal to the y-player’s support can be eliminated by noting that a similar result holds when ny⩾nxn_y n_x. Define ΠSy _S_y , LyL_y and My(Z)M_y(Z) analogously. Then eig~(JΦm(Z)|L)∖0=(W∪Qm−1(eig~(ηxηyMy(Z)|Ly)))∖0. eig ( . -1.2ptJ_ _m(Z) | |_L ) \0\= (W∪ Q_m^-1 ( eig ( _x _y . -1.2ptM_y(Z) | |_L_y ) ) ) \0\\,. Since the matrices My(Z)|Ly . -1.2ptM_y(Z) | |_L_y and Mx(Z)|Lx . -1.2ptM_x(Z) | |_L_x share their non-zero complex spectrum, eig~(JΦm(Z)|L)∖0=(W∪Qm−1(eig~(ηxηyMy(Z)|Ly))∪Qm−1(eig~(ηxηyMx(Z)|Lx)))∖0. eig ( . -1.2ptJ_ _m(Z) | |_L ) \0\= (W∪ Q_m^-1 ( eig ( _x _y . -1.2ptM_y(Z) | |_L_y ) )∪ Q_m^-1 ( eig ( _x _y . -1.2ptM_x(Z) | |_L_x ) ) ) \0\\,. This identity holds without any assumptions on the support size. Note, however, that for many special cases, for example, unique pure or unique fully mixed Nash equilibria, we have nx=nyn_x=n_y. Thus, the characterization with respect to either Mx(Z)|Lx . -1.2ptM_x(Z) | |_L_x or My(Z)|Ly . -1.2ptM_y(Z) | |_L_y is sufficient. 4.3 Interpretation and Illustrations Let Ωm=μ∈ℂ|∀λ∈ℂ with Qm(λ)=μ⇒|λ|<1 _m= \μ \;|\;∀\,λ with Q_m(λ)=μ |λ|<1 \ A consequence of Theorem 4.2 is that a quasi-strict Nash equilibrium is an asymptotically stable fixed point of m-optEW if all eigenvalues of ηxηyMx(Z) _x _yM_x(Z) restricted to LxL_x lie in Ωm _m, that is eig(ηxηyMx(Z)|Lx)⊆Ωmeig ( . -1.2pt _x _yM_x(Z) | |_L_x ) _m. Note that Ωm=∅ _m= for m∈(0,12]m∈(0, 12], which provides the intuition behind Corollary 4.1. See Figure 2 for an illustration of Ωm _m. Figure 2: The blue region indicates all solutions of Qm(λ)=zQ_m(λ)=z that have modulus less than one. 4.4 Consequences The following results are direct consequences of Theorem 4.2 and Theorem 4.1. The first corollary relies on the observation that Ωm=∅ _m= for m∈(0,1/2]m∈(0,1/2]. For a formal proof, see Appendix E.1. Corollary 4.1. Consider the game Γ(A,B) (A,B) with dx⩾dy⩾2d_x d_y 2 and assume that there exists a fully mixed Nash equilibrium Z⋆∈⋆Z ∈ Z . Suppose m∈(0,1/2]m∈(0,1/2]. If Mx(Z⋆)|Lx . -1.2ptM_x(Z ) | |_L_x is non-singular, then Z⋆Z is an unstable fixed point for the Φm _m dynamics for any step size choices ηx,ηy>0 _x, _y>0. The next corollary follows from the definition of the set W. We noted before that for an equilibrium, all values in W are strictly less than one. However, this does not hold for fixed points that are not equilibria. Corollary 4.2. Suppose Z∈~(Φm|Δ^)∖⋆Z∈ Z( . -1.2pt _m | |_ ) Z , that is, Z is a fixed point but not a Nash equilibrium. Then Z is unstable under the Φm _m dynamics for any ηx,ηy>0 _x, _y>0. Proof. By Theorem 4.2, the nonzero eigenvalues of JΦm(Z)|LJ_ _m(Z)|_L contain the set W. If [x,y][x,y] is not a Nash equilibrium, then by the characterization of W above, at least one element of W has modulus strictly larger than 11. Hence ρ(JΦm(Z)|L)>1ρ (J_ _m(Z)|_L )>1, and Theorem 4.1 gives the claim. ∎ Recall, an equilibrium is strict if it is pure (that is, SxS_x and SyS_y are singletons) and (Ay⋆)i<(x⋆)⊤Ay⋆(Ay )_i<(x ) Ay , and (Bx⋆)j<(y⋆)⊤Bx⋆(Bx )_j<(y ) Bx for all i∉Sxi∉ S_x and j∉Syj∉ S_y. The following corollary is a well-known result (see, e.g., Mertikopoulos and Sandholm (2016), Giannou et al. (2021)). Corollary 4.3. If Z⋆∈⋆Z ∈ Z corresponds to a strict Nash equilibrium, then it is an asymptotically stable fixed point for Φm _m for any m∈(0,1]m∈(0,1] and ηx,ηy>0 _x, _y>0. Proof. Since Z⋆Z is a strict Nash equilibrium, it is pure, so SxS_x and SyS_y are singletons, hence nx=ny=1n_x=n_y=1. Hence Lx=0L_x=\0\ and therefore eig(Mx(Z⋆)|Lx)=∅eig ( . -1.2ptM_x(Z ) | |_L_x )= . Moreover, for every i∉Sxi∉ S_x and j∉Syj∉ S_y, strictness implies elements of W are strictly smaller than 11. By Theorem 4.2, every nonzero eigenvalue of JΦm(Z⋆)|LJ_ _m(Z )|_L therefore has modulus strictly smaller than 11, and thus ρ(JΦm(Z⋆)|L)<1ρ (J_ _m(Z )|_L )<1. Theorem 4.1 implies that Z⋆Z is asymptotically stable. ∎ Corollary 4.4. Let Z∈~(Φm|Δ^)Z∈ Z( . -1.2pt _m | |_ ). If there exists μ∈eig(Mx(Z)|Lx)∪eig(My(Z)|Ly)μ \ ( . -1.2ptM_x(Z) | |_L_x) \ ( . -1.2ptM_y(Z) | |_L_y) such that μ∈ℝμ and μ>0μ>0, then Z is unstable for any value of m and any choices of ηx,ηy∈(0,∞) _x, _y∈(0,∞). Proof. Due to Theorem 4.2 and Remark 4.1, it suffices to show that for any ηx,ηy∈(0,+∞) _x, _y∈(0,+∞) there exists λ∈ℝλ with |λ|>1 |λ |>1 such that Qm(λ)=ηxηyμQ_m(λ)= _x _yμ. This holds since Qm(1)=0Q_m(1)=0 and Qm(λ)→+∞Q_m(λ)→+∞ as λ→+∞λ→+∞ and QmQ_m is continuous on [1,+∞)[1,+∞). ∎ An example of such an unstable equilibrium is the fully mixed Nash equilibrium x⋆=y⋆=[12,12]x =y =[ 12, 12] in the coordination game Γ(A,B) (A,B) where A=B=[1001].A=B= bmatrix1&0\\ 0&1 bmatrix\,. In this case 14∈eig(My(Z)|Ly) 14 \ ( . -1.2ptM_y(Z) | |_L_y) which implies that Z=[x⋆,y⋆,x⋆,y⋆]Z=[x ,y ,x ,y ] is unstable for any value of m and choices of ηx,ηy∈(0,∞) _x, _y∈(0,∞). 4.4.1 Zero-Sum Games Theorem 4.3. Consider a zero-sum game with a unique fully mixed Nash equilibrium Z⋆∈⋆=Z⋆Z ∈ Z =\Z \. Then Z⋆Z is asymptotically stable for Φm|Δ . -1.2pt _m | |_ if 0<ηxηyρ(Mx(Z⋆)|Lx)<2m−1m2(2m+1),0< _x _yρ ( . -1.2ptM_x(Z ) | |_L_x )< 2m-1m^2(2m+1)\,, and unstable if ηxηyρ(Mx(Z⋆)|Lx)>2m−1m2(2m+1). _x _yρ ( . -1.2ptM_x(Z ) | |_L_x )> 2m-1m^2(2m+1)\,. In particular, if m⩽1/2m 1/2 and dx,dy⩾2d_x,d_y 2, then Z⋆Z is an unstable fixed point of Φm _m. For a proof, see Appendix E.3. We note that the result is primarily of theoretical interest since the step size bounds depend on Z⋆Z . However, we observe that H(z)H(z) is a covariance matrix and therefore ‖H(zi⋆)‖ℓ2⩽12 \|H(z_i ) \|_ _2 12 for i∈1,2i∈\1,2\. Hence ρ(Mx(Z⋆)|Lx)⩽‖H(z1⋆)‖ℓ2‖H(z2⋆)‖ℓ2‖A‖ℓ22⩽14‖A‖ℓ22,ρ ( . -1.2ptM_x(Z ) | |_L_x ) \|H(z_1 ) \|_ _2 \|H(z_2 ) \|_ _2 \|A \|_ _2^2 14 \|A \|_ _2^2\,, which gives us the simple and potentially loose criterion for the stability of a Nash equilibrium: ηxηy‖A‖ℓ22<4(2m−1)m2(2m+1). _x _y \|A \|_ _2^2< 4(2m-1)m^2(2m+1)\,. Comparing this result with the global bound in Section 3, we observe that this bound allows for larger ηxηy _x _y and for m∈(12,1]m∈( 12,1] while guaranteeing asymptotic stability. However, Theorem 4.3 does not guarantee global convergence, as the results in Section 3 do. 4.4.2 The class of 2×22× 2 games The class of games with 22 players and 22 actions is also amenable to a detailed study. Consider A=[abcd],B=[efgh].A= bmatrixa&b\\ c&d bmatrix, B= bmatrixe&f\\ g&h bmatrix\,. The Nash equilibria are of the form x⋆=(p,1−p)⊤,y⋆=(q,1−q)⊤x =(p,1-p) , y =(q,1-q) where p,q∈[0,1]p,q∈[0,1]. Further, x⋆x is fully mixed if (e−g)(h−f)>0(e-g)(h-f)>0, and y⋆y is fully mixed if (d−b)(a−c)>0(d-b)(a-c)>0. The complements/substitutes split is classical in game theory; see, e.g., Rapoport (1966). Learning dynamics in 2×22× 2 games, including Experience Weighted Attraction and replicator limits, are studied, for instance, by Pangallo et al. (2022). Theorem 4.4. Suppose p,q∈(0,1)p,q∈(0,1). Define ΔA:=a−b−c+d,ΔB:=e−f−g+h, _A:=a-b-c+d\,, _B:=e-f-g+h\,, and threshold E:=1p(1−p)q(1−q)|ΔAΔB|2m−1m2(2m+1).E:= 1p(1-p)q(1-q)| _A _B| 2m-1m^2(2m+1)\,. Then [x⋆,y⋆][x ,y ] is a locally asymptotically stable fixed point for Φm _m if ΔAΔB<0 and 0<ηxηy<E, _A _B<0 and 0< _x _y<E, and an unstable fixed point if ΔAΔB<0 and ηxηy>E. _A _B<0 and _x _y>E\,. In particular, [x⋆,y⋆][x ,y ] is unstable for every ηx,ηy _x, _y if ΔAΔB>0 _A _B>0. For a proof, see Appendix E.4. 4.4.3 Low Dimensional Games with Unique Fully Mixed Equilibria For games with a unique fully mixed Nash equilibrium and dx=dy⩽5d_x=d_y 5, there exists an explicit closed-form formula expressing the spectrum as a polynomial in the entries of the game matrices A,BA,B. Theorem 4.5. Let Γ(A,B) (A,B) and assume the Nash equilibrium is unique and fully mixed and that the dimensions of the game matrices satisfy dx=dy⩽5d_x=d_y 5. Then the non-zero spectrum of JΦm(Z⋆)|L . -1.2ptJ_ _m(Z ) | |_L can be expressed explicitly in terms of the entries of A and B. A proof can be found in Appendix E.5. The proof relies on a closed-form expression for the Nash equilibrium, which holds for any dimension but requires uniqueness and full support. The closed-form solution for the spectrum is obtained via the roots of the characteristic polynomial. This is only possible if Mx(Z)|Lx . -1.2ptM_x(Z) | |_L_x is sufficiently small, since no general radical formula exists for degrees greater than or equal to five. 4.5 Remarks on related results Consider a game Γ(A,B) (A,B) with A,B⊤∈ℝdx×dyA,B ∈ R^d_x× d_y, played over the unconstrained strategy spaces ℝdx R^d_x and ℝdy R^d_y; that is, the x-player maximizes x⊤Ayx Ay over ℝdx R^d_x and the y-player maximizes y⊤Bxy Bx over ℝdy R^d_y. The optimistic gradient method (OGM) is xt+1=xt+ηxA(2yt−yt−1)yt+1=yt+ηyB(2xt−xt−1). casesx_t+1=x_t+ _xA (2y_t-y_t-1 )\\ y_t+1=y_t+ _yB (2x_t-x_t-1 )\,. cases Note that this algorithm applies only to unconstrained bimatrix games. This is the setting of De Montbrun and Renault (2025), whose general-sum bilinear games (x⊤A~y,x⊤B~y)(x Ay,x By) with A~,B~∈ℝdx×dy A, B∈ R^d_x× d_y correspond to Γ(A,B) (A,B) via A~=A A=A and B~=B⊤ B=B . In particular, the matrices B~⊤A~ B A and A~B~⊤ A B appearing in their analysis are BABA and ABAB in our notation. From their analysis, the following result follows as a corollary. Corollary 4.5. Consider the game Γ(A,B) (A,B) with dx=dyd_x=d_y and assume eig(BA)eig\ (BA) are real and eig(BA)⊂(−∞,0)eig\ (BA)⊂(-∞,0). Then [x⋆,y⋆]=[0,0][x ,y ]=[0,0] is the unique Nash equilibrium of the unconstrained game. Consider OGM with asymmetric step sizes ηx,ηy>0 _x, _y>0. The corresponding fixed point is an asymptotically stable fixed point of the OGM dynamics if 0<ηxηyρ(−BA)<13,0< _x _yρ (-BA )< 13\,, and unstable if ηxηyρ(−BA)>13. _x _yρ (-BA )> 13\,. The result follows from a small modification of Proposition 3.7 in De Montbrun and Renault (2025). For the convenience of the reader, we add a note on the necessary modification in Appendix E.6. Analogously, the same modification applied to Theorem 3.8 in De Montbrun and Renault (2025) yields global exponential convergence of the OGM iterates to a Nash equilibrium under the assumption that ηxηyρ(−BA)<14 _x _yρ (-BA )< 14, provided additionally that eig(BA)∪eig(AB)⊂(−∞,0]eig\ (BA) \ (AB)⊂(-∞,0] and that either A and B are square and invertible or ΛA,B _A,B (defined in Appendix E.6) is diagonalizable. Lei et al. (2021) establish local last-iterate convergence of 1-optEW for general constrained convex-concave min-max problems by proving that the 1-optEW Jacobian is Schur stable for sufficiently small equal step size. This is a standard, well-established analysis approach where the two analyses share some similarities. A central technical obstacle in the setting of Lei et al. (2021) is that the payoff is convex-concave rather than bilinear. The Jacobian contains additional Hessian blocks and is no longer reducible to a skew-symmetric structure with purely imaginary eigenvalues. One of their key technical contributions relies on Ky Fan’s inequality, which relates the real parts of the eigenvalues of a matrix to the eigenvalues of its symmetrized part. When specialized to bimatrix zero-sum games, the following result aligns with their computations. Corollary 4.6. Consider a zero-sum game Γ(A,−A⊤) (A,-A ) with a fully mixed Nash equilibrium Z⋆Z and a non-singular game matrix A∈ℝd×dA∈ R^d× d. Then Z⋆Z is asymptotically stable for 1-optEW if 0<ηxηyρ(Mx(Z⋆)|Lx)<13.0< _x _yρ (M_x(Z )|_L_x )< 13\,. We restrict to fully mixed and non-singular game matrices for two technical reasons. First, Lei et al. (2021) requires the Hessian restricted to the equilibrium support to be invertible; in bilinear zero-sum games, this holds if and only if the two supports have the same size and the corresponding game matrix is nonsingular, excluding standard examples such as rock-paper-scissors and matching pennies. Second, full support avoids some of the boundary issues. Lei et al. (2021) write the update as a map on a product of simplices and analyze the Jacobian at the equilibrium. This Jacobian is well defined for any point in the interior of the constraint space; however, for the product of simplices, this is empty. One can interpret their Jacobian computation as coming from the smooth ambient formula for the exponential-weights update, locally extended around the simplex wherever the normalization denominators remain nonzero, or equivalently as a derivative along the affine/tangent directions of the constraint set (cf. Lemma D.4). Our analysis specialized to m=1m=1 and zero-sum games makes this rigorous for the linear case. 5 Experiments and Open Questions In this section, we present empirical studies illustrating our theoretical results. In all examples, we opt for the simplest possible model for illustration. Namely, many examples use low-dimensional toy models, specifically games with two or three actions, because they allow details to be visualized without dimensionality reduction. Even in 2×22× 2 games, the experiments support and illustrate our theory while raising interesting questions for future work. 5.1 Landscape 2×22× 2 Non-Zero-Sum Games The product-dependent stability criterion shows the existence of a basin of attraction, but does not quantify the width of the basin of attraction nor quantify convergence rates. In this section, we consider a non-zero-sum variant of matching pennies Γ(A,B) (A,B). A=[−113−1]andB=[2−1−11].A= bmatrix-1& -1\\ -3&-1 bmatrix B= bmatrix -2&-1\\ -1& -1 bmatrix\,. This game has a unique fully mixed Nash equilibrium, see Appendix F for details. We use the results from Theorem 4.4 for step size computation. That is, for ϵ>0ε>0, we set η⋆(m)=(1−ϵ)1p(1−p)q(1−q)|ΔAΔB|2m−1m2(2m+1).η (m)=(1-ε) 1p(1-p)q(1-q)| _A _B| 2m-1m^2(2m+1)\,. The step sizes are defined as a function of m and the ratio c. That is ηx(m,c)=η⋆(m)c and ηy(m,c)=cη⋆(m). _x(m,c)= η (m)c and _y(m,c)= cη (m)\,. (5) Using a 2×22× 2 game allows us to project the simplex to the interval [0,1][0,1] using the variable transform p′≜[p,1−p]⊤p [p,1-p] . We use this in the plots where the vertical axis corresponds to the 22-dimensional simplex and the horizontal axis to a varying parameter. Figure 3: Distance to the Nash equilibrium for the non-zero-sum matching pennies variant. Parameter m is fixed to m⋆m , the ratio between the step sizes varies depending on c∈[1,100]c∈[1,100]. Figure 4: Distance to the Nash equilibrium for the non-zero-sum matching pennies variant. The ratio between the step sizes c is fixed to 11, parameter m varies. 5.1.1 Dependence on the Step Size Ratio In this section, we illustrate the dependence on the ratio c. We define m⋆=1+54m = 1+ 54. Note that m⋆=argmaxm∈(0,1]2m−1m2(2m+1)m = *argmax_m∈(0,1] 2m-1m^2(2m+1) and 2m⋆2m is the golden ratio. We initialize m⋆m -optEW with Z0i=[x0i,y0,x0i,y0]Z^i_0=[x^i_0,y_0,x^i_0,y_0] where y0=[1/4,3/4]⊤y_0=[1/4,3/4] is fixed and x0i∈Δ2x_0^i∈ _2 from an equidistant grid over the simplex. Figure 3 shows the norm distance to the Nash equilibrium after T=10 000T=10\,000 iterations of m⋆m -optEW with step sizes ηx(m⋆,c) _x(m ,c) and ηy(m⋆,c) _y(m ,c) for varying ratio c on the horizontal axis. Specifically, for each x0ix_0^i, the color indicates mint∈[T/2,T]‖Zti−Z⋆‖ _t∈[T/2,T] \|Z^i_t-Z \|. The Nash equilibrium x⋆x is marked in white. As can be seen in Figure 3, the unique Nash equilibrium is clearly asymptotically stable, hence empirically verifying our theoretical results. However, we also observe that the basin of attraction depends on c and, for this experiment, its diameter appears to decrease as c increases. In particular, for c≳13c 13, the basin of attraction does not cover the full simplex. This leads to the natural next question about the dependence on m, which we investigate in the next section. Figure 5: Distance to the Nash equilibrium for the non-zero-sum matching pennies variant. The ratio between the step sizes c is fixed to 2020, parameter m varies. 5.1.2 Dependence on m In the previous section, we fixed m⋆m . Contrasting this, we repeat the experiments with fixed c and vary over m. Figure 4 illustrates the dependence on m with c=1c=1. As can be seen, the experiments suggest that the diameter of the basin decreases as m approaches 12 12. In Figure 5, we repeat the same experiments with c=20c=20. Recall from Figure 3 that for m=m⋆m=m and c=20c=20, the basin of attraction does not cover the full simplex. This observation raises the natural question whether this changes as m varies. As the experiments suggest, the basin of attraction remains stable for m∈(0.5,0.6]m∈(0.5,0.6]. Again, these experiments confirm and illustrate the asymptotic stability of the Nash equilibrium shown in Theorem 4.4. We note that the theoretical results provide the existence of a basin of attraction, but no quantitative characterization. The observations from the experiments lead to an interesting open question on which we elaborate in Section 5.3.2. Figure 6: Experiment illustrating the benefits of ηx≪ηy _x _y. Clearly c=100c=100 achieves better convergence than c∈10−1,1c∈\10^-1,1\. 5.1.3 Benefits of ηx≪ηy _x _y While our theoretical results are primarily of fundamental interest, the preceding examples naturally raise the question: Why use asymmetric step sizes? In addition to the motivation given in the introduction, we illustrate their benefit with a simple toy example based on a general-sum game with differing scales. A more in-depth case study is beyond the scope of this paper. Consider the matching pennies game Γ(A,−A⊤) (A,-A ) (see Appendix F). Our experiments are run for the non-zero-sum variant Γ(1αA,−αA⊤) ( 1αA,-α A ) with α=10α=10. The total number of iterations is T=1 000T=1\,000, and m=m⋆m=m . Figure 6 shows the initial and final norm distances of N=1 000N=1\,000 random samples from Δ2×Δ2 _2× _2 with varying choices of c and step sizes as defined in (5). Unsurprisingly, c=100c=100 achieves better empirical results than c=10−1c=10^-1 or c=1c=1. While we note that this controlled scale mismatch is only a toy example, it illustrates potential practical benefits. 5.2 A 4×44× 4 Non-Zero-Sum Game In this section, we also study a 4×44× 4 game with a non-fully mixed equilibrium. See Appendix F for details. As a proxy for convergence, Figure 7 and Figure 8 show the norm distance after T=1 000T=1\,000 iterations. We sample N=2 000N=2\,000 points: N/2N/2 are from an ϵε-neighbourhood of the equilibrium, and N/2N/2 are random points close to the boundaries of Δ4×Δ4 _4× _4. To interpret the plot, note that points above the diagonal move closer to equilibrium after T iterations, while points on or below it show no progress. The ϵε-neighbourhood is marked by a dashed line. Figure 7: Convergence with various choices of c. Figure 8: Convergence with various choices of m. 5.3 Open Questions 5.3.1 Global Convergence for Zero-Sum Games and m∈(12,1)m∈ ( 12,1 ) Consider the following variant of rock-paper-scissors Γ(A,−A⊤) (A,-A ) with A=[0a−1−101a1−10].A= bmatrix -0& -a&-1\\ -1& -0& - 1a\\ -1&-1& -0 bmatrix\,. We let a=10a=10. Note that this zero-sum game has a unique, fully mixed Nash equilibrium. As observed in Theorem 4.5, this allows us to calculate the step size threshold analytically. In the following experiments we choose ηx=ηy=(1−ϵ)ρ(Mx(Z⋆)|Lx)−12m⋆−1(m⋆)2(2m⋆+1), _x= _y=(1-ε) ρ ( . -1.2ptM_x(Z ) | |_L_x )^-1 2m -1(m )^2(2m +1)\,, where ϵ=0.01ε=0.01 ensures asymptotic stability and m⋆m is set to half the golden ratio. Figure 9 illustrates proximity and potential non-convergence. We note that this empirical observation provides some evidence that there exists m∈(1/2,1)m∈(1/2,1) and ηx,ηy _x, _y such that the equilibrium is asymptotically stable, but global convergence may not hold. However, we emphasize that numerical errors cannot be ruled out. Figure 9: We run m⋆m -optEW for T=10 000T=10\,000 iterations. The initial y0y_0 is fixed at [0.45,0.45,0.1]⊤[0.45,0.45,0.1] . Left plot: We initialize m⋆m -optEW with (x0i,y0)(x_0^i,y_0) where x0ix_0^i is from a grid defined at equidistances 0.010.01 over the simplex. The color indicates the minimal norm distance to the equilibrium (zti)t∈ℕ=(xti,yt)t∈ℕ(z^i_t)_t∈ N=(x_t^i,y_t)_t∈ N reaches over the iterations t∈[T/2,T]t∈[T/2,T]. Right plot: This graph shows the norm distances and means thereof for all (zti)t∈ℕ(z^i_t)_t∈ N with mint∈[T/2,T]‖zti−z⋆‖⩾0.2 _t∈[T/2,T] \|z_t^i-z \| 0.2. Note that for some of the sequences mint∈[1,T/2]‖zti−z⋆‖<0.2 _t∈[1,T/2] \|z_t^i-z \|<0.2. 5.3.2 Basin of Attraction and Convergence Rates The experiments in, e.g., Figure 5 suggest that the basin of attraction does not cover the full simplex for some parameter choices. Characterizing the basins of attraction with respect to these parameters can be an interesting follow-up question. 6 Conclusion We studied optimistic exponential weights in two-player bimatrix games with constant, potentially asymmetric step sizes. Our results show that the relevant stability conditions naturally depend on the product ηxηy _x _y, rather than on the two step sizes separately: in zero-sum games, this yields a global convergence guarantee to Nash equilibria, while in general games, our local spectral analysis characterizes stability through a reduced matrix at equilibrium. Via this technical result, we provide a sharper stability analysis of m-optEW with uneven step sizes. The experiments illustrate and support our results, but they also highlight open questions. Acknowledgements We thank Andrea Celli for his support. During parts of the project, Sachs was supported by European Union – Next Generation EU funds, component M4.C2, investment 1.1. - CUP: J53D23007170001 and the London Mathematical Society, Scheme 4, grant 42508. Appendix A Omitted Proofs of Section 2 We first show some basic invariance properties of exponential weights. Proposition A.1 (Invariance). Let Z=[z1,z2,z3,z4]∈ΦmZ=[z_1,z_2,z_3,z_4]∈ D_ _m and Φm(Z)=[z1′,z2′,z1,z2] _m(Z)=[z_1 ,z_2 ,z_1,z_2]. Then for every coordinate, z1,i′=0⇔z1,i=0andz2,j′=0⇔z2,j=0.z_1,i =0 z_1,i=0 z_2,j =0 z_2,j=0. In particular, if Z∈relintΔ^Z , then Φm(Z)∈relintΔ _m(Z) . Proof. By definition, z1′=Pdx(z1⊙Exp(ηxA((1+m)z2−mz4)))z_1 =P_d_x\! (z_1 ( _xA((1+m)z_2-mz_4)) ). By definition of Φm D_ _m, the normalizer is nonzero, and the exponential factor is strictly positive in every coordinate, so z1,i′=0⇔z1,i=0z_1,i =0 z_1,i=0. The same argument holds for z2′z_2 . If Z∈relintΔ^Z then all coordinates of z1,z2,z3,z4z_1,z_2,z_3,z_4 are strictly positive. Combined with the strict positivity of the exponential function yields the claim. ∎ A.1 Proof of Theorem 2.1 Proof of Theorem 2.1. Let Z=[z1,z2,z3,z4]∈Δ^Z=[z_1,z_2,z_3,z_4]∈ . By the definition of Φm _m, Φm(Z)=Z _m(Z)=Z is equivalent to z1=Pdx(z1⊙Exp(ηxA((1+m)z2−mz4))),z2=Pdy(z2⊙Exp(ηyB((1+m)z1−mz3))),z3=z1,z4=z2. casesz_1&=P_d_x\! (z_1 \! ( _xA((1+m)z_2-mz_4) ) ),\\ z_2&=P_d_y\! (z_2 \! ( _yB((1+m)z_1-mz_3) ) ),\\ z_3&=z_1, z_4=z_2. cases This is equivalent to z3=z1,z4=z2,z1=Pdx(z1⊙Exp(ηxAz2)),z2=Pdy(z2⊙Exp(ηyBz1)). casesz_3&=z_1, z_4=z_2,\\ z_1&=P_d_x\! (z_1 ( _xAz_2) ),\\ z_2&=P_d_y\! (z_2 ( _yBz_1) ). cases Define Cx:=∑ℓ=1dxz1,ℓexp(ηx(Az2)ℓ).C_x:= _ =1^d_xz_1, \! ( _x(Az_2)_ ). Since z1∈Δdxz_1∈ _d_x, we have supp(z1)=Sx≠∅ *supp(z_1)=S_x≠ and Cx>0C_x>0. By Proposition A.1, the zero pattern of the first block is preserved by the update. Hence, the coordinates outside SxS_x impose no additional condition. Therefore, z1 z_1 =Pdx(z1⊙Exp(ηxAz2)) =P_d_x\! (z_1 ( _xAz_2) ) ⇔∀i∈Sx,z1,i=z1,iexp(ηx(Az2)i)Cx ∀ i∈ S_x, z_1,i=z_1,i ( _x(Az_2)_i)C_x ⇔∀i∈Sx,exp(ηx(Az2)i)=Cx ∀ i∈ S_x, ( _x(Az_2)_i)=C_x ⇔∀i,j∈Sx,(Az2)i=(Az2)j. ∀ i,j∈ S_x, (Az_2)_i=(Az_2)_j\,. For the last step, we used that ηx>0 _x>0. Combined with the observation that the argument for z2z_2 is identical, we note that Z is a fixed point of Φm|Δ . -1.2pt _m | |_ if and only if z3=z1∈Δdx,z4=z2∈Δdy,z_3=z_1∈ _d_x, z_4=z_2∈ _d_y, and the payoff vectors Az2Az_2 and Bz1Bz_1 are constant on the supports of z1z_1 and z2z_2, respectively. ∎ Appendix B General Technical Results Recall from the main part that by ⊙ we denote the Hadamard (entry-wise) multiplication and ExpExp denotes the component-wise exponential function. In this section, we also use entry-wise division, denoted by ÷⃝ , and the component-wise logarithm LogLog. Throughout the section, we let (Zt)t∈ℕ(Z_t)_t∈ N denote a sequence generated by Zt=Φm(Zt−1)Z_t= _m(Z_t-1) with m∈(0,1]m∈(0,1]. We always assume that Z0∈Δ^Z_0∈ and for some results we use the stronger assumption that Z0∈relintΔ^Z_0 . This assumption is indicated for each result. For each t∈ℕt∈ N, write Zt=[xt,yt,xt−1,yt−1]Z_t=[x_t,y_t,x_t-1,y_t-1] and Z1:t=[Z1,…,Zt]Z_1:t=[Z_1,…,Z_t], with the convention Z1:0=∅Z_1:0= . Further, we let y¯1:t=∑s=1tys y_1:t= _s=1^ty_s and x¯1:t=∑s=1txs x_1:t= _s=1^tx_s with the convention that x¯1:0=y¯1:0=0 x_1:0= y_1:0=0. Further, for x∈Δd,x′∈relintΔdx∈ _d,x _d, we denote the Kullback-Leibler (KL) divergence by KL(x,x′)=∑i=1dxilogxixi′KL(x,x )= _i=1^dx_i x_ix_i . We use the convention that 0log0=00 0=0. B.1 Known Results For completeness, we include several well-known results for the exponential weight updates and bounds for the KL divergence. For a proof of these results, see, e.g., Cesa-Bianchi and Lugosi (2006). Proposition B.1 (Pinsker’s inequality). For any x,x′∈Δdx,x ∈ _d, KL(x,x′)⩾12‖x−x′‖12. (x,x ) 12 \|x-x \|_1^2\,. Proposition B.2 (Three-point identity for KL-divergence). For any x∈Δdx∈ _d and y,z∈relintΔdy,z _d, KL(x,z)=KL(x,y)+KL(y,z)+⟨x−y,Log(y÷⃝z)⟩.KL(x,z)=KL(x,y)+KL(y,z)+ x-y,Log(y z) \,. Now define the log-sum-exp potentials ψx(Z1:t):=1ηxlog⟨x1,Exp(ηxA(y¯1:t+m(yt−y0)))⟩,ψy(Z1:t):=1ηylog⟨y1,Exp(ηyB(x¯1:t+m(xt−x0)))⟩. array[]l ψ^x(Z_1:t):= 1 _x x_1,Exp\! ( _xA ( y_1:t+m(y_t-y_0) ) ) ,\\[8.0pt] ψ^y(Z_1:t):= 1 _y y_1,Exp\! ( _yB ( x_1:t+m(x_t-x_0) ) ) . array (6) We set ψ(Z1:t):=ψx(Z1:t)+ψy(Z1:t)ψ(Z_1:t):=ψ^x(Z_1:t)+ψ^y(Z_1:t) and use the convention that ψx(Z1:0)=ψy(Z1:0)=0ψ^x(Z_1:0)=ψ^y(Z_1:0)=0. Proposition B.3 (Logit identity). Consider the game Γ(A,B) (A,B) and assume Z0∈relintΔ^Z_0 . Then, for every t⩾1t 1, 1. Log(xt+1÷⃝xt)=ηxA((1+m)yt−myt−1)+ηx(ψx(Z1:t−1)−ψx(Z1:t)),Log(x_t+1 x_t)= _xA((1+m)y_t-my_t-1)+ _x (ψ^x(Z_1:t-1)-ψ^x(Z_1:t) )1\,, 2. Log(yt+1÷⃝yt)=ηyB((1+m)xt−mxt−1)+ηy(ψy(Z1:t−1)−ψy(Z1:t)).Log(y_t+1 y_t)= _yB((1+m)x_t-mx_t-1)+ _y (ψ^y(Z_1:t-1)-ψ^y(Z_1:t) )1\,. Proof. We prove the identity for the x-player; the proof for the y-player is analogous. By iterating the m-optEW update, for every coordinate i∈1,…,dxi∈\1,…,d_x\, [xt+1]i=[x1]iexp(ηx[A∑s=1t((1+m)ys−mys−1)]i)∑k=1dx[x1]kexp(ηx[A∑s=1t((1+m)ys−mys−1)]k).[x_t+1]_i= [x_1]_i \! ( _x [A _s=1^t ((1+m)y_s-my_s-1 ) ]_i ) _k=1^d_x[x_1]_k \! ( _x [A _s=1^t ((1+m)y_s-my_s-1 ) ]_k ). The sum simplifies to ∑s=1t((1+m)ys−mys−1)=m(yt−y0)+y¯1:t=:Yt(m). _s=1^t((1+m)y_s-my_s-1)=m(y_t-y_0)+ y_1:t=:Y_t^(m)\,. Since Z0∈relintΔ^Z_0 , all iterates remain strictly positive, so the coordinate-wise logarithm of the ratio is well defined. Taking the logarithm of the quotient gives log[xt+1]i[xt]i=ηx[A(Yt(m)−Yt−1(m))]i+ηx(ψx(Z1:t−1)−ψx(Z1:t)). [x_t+1]_i[x_t]_i= _x[A(Y_t^(m)-Y_t-1^(m))]_i+ _x (ψ^x(Z_1:t-1)-ψ^x(Z_1:t) ). Finally, Yt(m)−Yt−1(m)=(1+m)yt−myt−1.Y_t^(m)-Y_t-1^(m)=(1+m)y_t-my_t-1. This proves the first identity. The second follows from an analogous argument. ∎ Lemma B.1. Consider a bimatrix game Γ(A,B) (A,B) and assume Z0∈Δ^Z_0∈ . Let Z∞=(x∞,y∞,x∞,y∞)∈~(Φm|Δ^)Z_∞=(x_∞,y_∞,x_∞,y_∞)∈ Z( . -1.2pt _m | |_ ) be a fixed point of Φm _m. Assume that one of the following two alternatives holds: (I) there exist ı^∉supp(x∞) ∉ *supp(x_∞) and j∈supp(x∞)j∈ *supp(x_∞) such that (Ay∞)ı^>(Ay∞)j.(Ay_∞)_ >(Ay_∞)_j\,. In this case, assume [x0]j>0[x_0]_j>0 and define Rt:=[xt]ı^[xt]j;R_t:= [x_t]_ [x_t]_j; (I) there exist k^∉supp(y∞) k∉ *supp(y_∞) and ℓ∈supp(y∞) ∈ *supp(y_∞) such that (Bx∞)k^>(Bx∞)ℓ.(Bx_∞)_ k>(Bx_∞)_ \,. In this case, assume [y0]ℓ>0[y_0]_ >0 and define Rt:=[yt]k^[yt]ℓ.R_t:= [y_t]_ k[y_t]_ . Then there exist constants δ>0δ>0, ϵ>0ε>0, and τ>0τ>0 such that: 1. Exponential growth: for every t∈ℕt∈ N, ‖Zt−Z∞‖<δ⟹Rt+1⩾eϵRt.\|Z_t-Z_∞\|<δ R_t+1 e^εR_t. 2. Bounded ratio: for every Z=[x,y,x′,y′]∈Δ^Z=[x,y,x ,y ]∈ , ‖Z−Z∞‖<δ⟹R(Z)<τ,\|Z-Z_∞\|<δ R(Z)<τ, where R(Z)=xı^/xj,in case (I),yk^/yℓ,in case (I).R(Z)= casesx_ /x_j,&in case (I),\\ y_ k/y_ ,&in case (I). cases Proof. We prove case (I), the case (I) is analogous. Set g:=(Ay∞)ı^−(Ay∞)j>0,β:=[x∞]j2>0.g:=(Ay_∞)_ -(Ay_∞)_j>0, β:= [x_∞]_j2>0. For any Z=[x,y,x′,y′]Z=[x,y,x ,y ], define the continuous local payoff-difference map Γx(m)(Z):=[A((1+m)y−my′)]ı^−[A((1+m)y−my′)]j. _x^(m)(Z):=[A((1+m)y-my )]_ -[A((1+m)y-my )]_j. Since Z∞=[x∞,y∞,x∞,y∞]Z_∞=[x_∞,y_∞,x_∞,y_∞], we have (1+m)y∞−my∞=y∞.(1+m)y_∞-my_∞=y_∞. Therefore Γx(m)(Z∞)=(Ay∞)ı^−(Ay∞)j=g. _x^(m)(Z_∞)=(Ay_∞)_ -(Ay_∞)_j=g. By continuity, there exists δ1>0 _1>0 such that ‖Z−Z∞‖<δ1⟹Γx(m)(Z)>g2.\|Z-Z_∞\|< _1 _x^(m)(Z)> g2. Moreover, since j∈supp(x∞)j∈ *supp(x_∞), we have [x∞]j>0[x_∞]_j>0. Thus there exists δ2>0 _2>0 such that ‖Z−Z∞‖<δ2⟹xj>β.\|Z-Z_∞\|< _2 x_j>β. Let δ:=minδ1,δ2,ϵ:=ηxg2,τ:=δβ.δ:= \ _1, _2\, ε:= _xg2, τ:= δβ. We first show the exponential growth statement. Since the normalization factors in the update operation cancel, we obtain Rt+1=Rtexp(ηxΓx(m)(Zt)).R_t+1=R_t \! ( _x _x^(m)(Z_t) ). If ‖Zt−Z∞‖<δ\|Z_t-Z_∞\|<δ, then ‖Zt−Z∞‖<δ1\|Z_t-Z_∞\|< _1, and hence Γx(m)(Zt)>g2. _x^(m)(Z_t)> g2. Therefore Rt+1=Rtexp(ηxΓx(m)(Zt))⩾Rtexp(ηxg2)=eϵRt.R_t+1=R_t \! ( _x _x^(m)(Z_t) ) R_t \! ( _xg2 )=e^εR_t. This proves the exponential growth statement in case (I). It remains to prove the bounded-ratio statement. Let Z=[x,y,x′,y′]∈Δ^Z=[x,y,x ,y ]∈ satisfy ‖Z−Z∞‖<δ.\|Z-Z_∞\|<δ. Since ı^∉supp(x∞) ∉ *supp(x_∞), we have [x∞]ı^=0[x_∞]_ =0. Thus xı^=|xı^−[x∞]ı^|⩽‖Z−Z∞‖<δ.x_ =|x_ -[x_∞]_ | \|Z-Z_∞\|<δ. On the other hand, since δ⩽δ2δ _2, we have xj>β.x_j>β. Consequently, R(Z)=xı^xj<δβ=τ.R(Z)= x_ x_j< δβ=τ. This proves the bounded-ratio statement in case (I). ∎ Appendix C Omitted Proofs from Section 3 C.1 Proof of Theorem 3.1 Key Technical Results A key ingredient is the Lyapunov function, consisting of a KL-divergence, a cross-term gap function, and the log-sum-exp ψ defined in equation (6). For Z=[x,y,x′,y′]∈relintΔ^Z=[x,y,x ,y ] , let φ(Z):=φx(Z)+φy(Z) (Z):= ^x(Z)+ ^y(Z) with φx(Z):=12ηx ^x(Z):= 12 _x KL(x,x′), and φy(Z):=12ηyKL(y,y′); (x,x ), and ^y(Z):= 12 _yKL(y,y )\,; and define a gap function capturing the cross terms as gap(Z):=⟨x,Ay′⟩−⟨y,A⊤x′⟩. (Z):= x,Ay - y,A x \,. The Lyapunov function is V(Z1:t):=ψ(Z1:t−1)+φ(Zt)−gap(Zt).V(Z_1:t):=ψ(Z_1:t-1)+ (Z_t)-gap(Z_t). Before we show our key technical lemma, we derive an identity for ψ from Proposition B.3 in the special case of zero-sum games and m=1m=1. Proposition C.1 (ψ identity). Consider the game Γ(A,−A⊤) (A,-A ) and denote by (Zt)t∈ℕ(Z_t)_t∈ N a sequence with Z0∈relintΔ^Z_0 and Zt+1:=Φ1(Zt)Z_t+1:= _1(Z_t). Then for every t⩾1t 1 1. ψx(Z1:t−1)−ψx(Z1:t)=−xt+1⊤A(2yt−yt−1)+1ηxKL(xt+1,xt)ψ^x(Z_1:t-1)-ψ^x(Z_1:t)=-x_t+1 A(2y_t-y_t-1)+ 1 _xKL(x_t+1,x_t); 2. ψy(Z1:t−1)−ψy(Z1:t)=(2xt−xt−1)⊤Ayt+1+1ηyKL(yt+1,yt)ψ^y(Z_1:t-1)-ψ^y(Z_1:t)=(2x_t-x_t-1) Ay_t+1+ 1 _yKL(y_t+1,y_t) ; and ψ(Z1:t−1)−ψ(Z1:t)= ψ(Z_1:t-1)-ψ(Z_1:t)= −xt+1⊤A(2yt−yt−1)+(2xt−xt−1)⊤Ayt+1 -x_t+1 A(2y_t-y_t-1)+(2x_t-x_t-1) Ay_t+1 +1ηxKL(xt+1,xt)+1ηyKL(yt+1,yt). + 1 _xKL(x_t+1,x_t)+ 1 _yKL(y_t+1,y_t). Proof. Again, we only show the first identity; the second identity follows the analogous argument. Using the definition of the KL-divergence, Proposition B.3 and that xt+1∈Δdxx_t+1∈ _d_x, we obtain 1ηxKL(xt+1,xt) 1 _xKL(x_t+1,x_t) =1ηx⟨xt+1,Log(xt+1÷⃝xt)⟩ = 1 _x x_t+1,Log(x_t+1 x_t) =xt+1⊤A(2yt−yt−1)+ψx(Z1:t−1)−ψx(Z1:t). =x_t+1 A(2y_t-y_t-1)+ψ^x(Z_1:t-1)-ψ^x(Z_1:t). Rearranging yields ψx(Z1:t−1)−ψx(Z1:t)=−xt+1⊤A(2yt−yt−1)+1ηxKL(xt+1,xt).ψ^x(Z_1:t-1)-ψ^x(Z_1:t)=-x_t+1 A(2y_t-y_t-1)+ 1 _xKL(x_t+1,x_t). Analogously, ψy(Z1:t−1)−ψy(Z1:t)=(2xt−xt−1)⊤Ayt+1+1ηyKL(yt+1,yt).ψ^y(Z_1:t-1)-ψ^y(Z_1:t)=(2x_t-x_t-1) Ay_t+1+ 1 _yKL(y_t+1,y_t). Adding the two identities gives the third claim. ∎ Lemma C.1 (Key Technical Lemma). Consider a zero-sum game Γ(A,−A⊤) (A,-A ). Assume that Φ1 _1 is defined with ηx,ηy>0 _x, _y>0 and 6ηxηy‖A‖1→∞2⩽16 _x _y \|A \|^2_1→∞ 1. Let (Zt)t∈ℕ(Z_t)_t∈ N be the sequence generated by Zt+1=Φ1(Zt)Z_t+1= _1(Z_t) with Z0∈relintΔ^Z_0 . Using the definitions above, the sequence 1. (ψ(Z1:t))t∈ℕ (ψ(Z_1:t) )_t∈ N is bounded from below by a constant; 2. (V(Z1:t))t∈ℕ (V(Z_1:t) )_t∈ N is non-increasing; and 3. ‖Zt−Zt−1‖→t→∞0 \|Z_t-Z_t-1 \| [t→∞]0. Proof. Let Z⋆=[x⋆,y⋆,x⋆,y⋆]∈⋆Z =[x ,y ,x ,y ]∈ Z . Applying the three-point identity (Proposition B.2), Proposition B.3 and Proposition C.1 yields 1ηxKL(x⋆,xt)−1ηxKL(x⋆,xt+1) 1 _xKL(x ,x_t)- 1 _xKL(x ,x_t+1) =1ηxKL(xt+1,xt)+1ηx⟨x⋆−xt+1,Log(xt+1÷⃝xt)⟩ = 1 _xKL(x_t+1,x_t)+ 1 _x x -x_t+1,Log(x_t+1 x_t) =(1)1ηxKL(xt+1,xt)+⟨x⋆−xt+1,A(2yt−yt−1)⟩ (1)= 1 _xKL(x_t+1,x_t)+ x -x_t+1,A(2y_t-y_t-1) =ψx(Z1:t−1)−ψx(Z1:t)+⟨x⋆,A(2yt−yt−1)⟩. =ψ^x(Z_1:t-1)-ψ^x(Z_1:t)+ x ,A(2y_t-y_t-1) . For (1)(1) we used that ⟨x⋆−xt+1,c⟩=0 x -x_t+1,c1 =0 for any c (here c=ηx(ψx(Z1:t−1)−ψx(Z1:t))c= _x(ψ^x(Z_1:t-1)-ψ^x(Z_1:t))). Analogously, 1ηyKL(y⋆,yt)−1ηyKL(y⋆,yt+1)=ψy(Z1:t−1)−ψy(Z1:t)−⟨y⋆,A⊤(2xt−xt−1)⟩. 1 _yKL(y ,y_t)- 1 _yKL(y ,y_t+1)=ψ^y(Z_1:t-1)-ψ^y(Z_1:t)- y ,A (2x_t-x_t-1) . Therefore, 1ηxKL(x⋆,xt)−1ηxKL(x⋆,xt+1)+1ηyKL(y⋆,yt)−1ηyKL(y⋆,yt+1) 1 _xKL(x ,x_t)- 1 _xKL(x ,x_t+1)+ 1 _yKL(y ,y_t)- 1 _yKL(y ,y_t+1) is equal to ψ(Z1:t−1)−ψ(Z1:t)+⟨x⋆,A(2yt−yt−1)⟩−⟨y⋆,A⊤(2xt−xt−1)⟩ ψ(Z_1:t-1)-ψ(Z_1:t)+ x ,A(2y_t-y_t-1) - y ,A (2x_t-x_t-1) =ψ(Z1:t−1)−ψ(Z1:t)+⟨x⋆,A(yt−yt−1)⟩−⟨y⋆,A⊤(xt−xt−1)⟩ =ψ(Z_1:t-1)-ψ(Z_1:t)+ x ,A(y_t-y_t-1) - y ,A (x_t-x_t-1) +⟨x⋆,Ayt⟩−⟨y⋆,A⊤xt⟩. x+ x ,Ay_t - y ,A x_t . Summing over t=1,…,Tt=1,…,T yields 1ηx(KL(x⋆,x1)−KL(x⋆,xT+1))+1ηy(KL(y⋆,y1)−KL(y⋆,yT+1)) 1 _x (KL(x ,x_1)-KL(x ,x_T+1) )+ 1 _y (KL(y ,y_1)-KL(y ,y_T+1) ) =ψ(Z1:0)−ψ(Z1:T)+⟨x⋆,A(yT−y0)⟩−⟨y⋆,A⊤(xT−x0)⟩ =ψ(Z_1:0)-ψ(Z_1:T)+ x ,A(y_T-y_0) - y ,A (x_T-x_0) +∑t=1T(⟨x⋆,Ayt⟩−⟨y⋆,A⊤xt⟩) + _t=1^T ( x ,Ay_t - y ,A x_t ) ⩾ψ(Z1:0)−ψ(Z1:T)−(⟨x⋆,Ay0⟩−⟨y⋆,A⊤x0⟩), ψ(Z_1:0)-ψ(Z_1:T)- ( x ,Ay_0 - y ,A x_0 )\,, where the last inequality is due to Z⋆∈⋆Z ∈ Z . Rearranging ψ(Z1:T)⩾ψ(Z1:0)−(1ηxKL(x⋆,x1)+1ηyKL(y⋆,y1))⏟=:k1−(⟨x⋆,Ay0⟩−⟨y⋆,A⊤x0⟩).ψ(Z_1:T) ψ(Z_1:0)- ( 1 _xKL(x ,x_1)+ 1 _yKL(y ,y_1) )_=:k_1- ( x ,Ay_0 - y ,A x_0 )\,. Since, by assumption, Z0∈relintΔ^Z_0 the term k1k_1 is bounded by a constant. Thus (ψ(Z1:t))t∈ℕ(ψ(Z_1:t))_t∈ N is bounded from below by a constant independent of T. Next, we prove the descent inequality, that is, we show that (V(Z1:t))t∈ℕ(V(Z_1:t))_t∈ N is non-increasing. By definition, V(Z1:t)−V(Z1:t+1)V(Z_1:t)-V(Z_1:t+1) is equal to ψ(Z1:t−1)− ψ(Z_1:t-1)- ψ(Z1:t)−gap(Zt)+gap(Zt+1) ψ(Z_1:t)-gap(Z_t)+gap(Z_t+1) +12ηxKL(xt,xt−1)+ + 12 _xKL(x_t,x_t-1)+ 12ηyKL(yt,yt−1)−12ηxKL(xt+1,xt)−12ηyKL(yt+1,yt). 12 _yKL(y_t,y_t-1)- 12 _xKL(x_t+1,x_t)- 12 _yKL(y_t+1,y_t)\,. Using the entropy identity from Proposition C.1 and the definition of the gap function, yields V(Z1:t)− V(Z_1:t)- V(Z1:t+1) V(Z_1:t+1) =−(xt+1)⊤A(2yt−yt−1)+(2xt−xt−1)⊤Ayt+1−xt⊤Ayt−1 =-(x_t+1) A(2y_t-y_t-1)+(2x_t-x_t-1) Ay_t+1-x_t Ay_t-1 +xt−1⊤Ayt+(xt+1)⊤Ayt−xt⊤Ayt+1 +x_t-1 Ay_t+(x_t+1) Ay_t-x_t Ay_t+1 +12ηxKL(xt,xt−1)+12ηyKL(yt,yt−1)+12ηxKL(xt+1,xt)+12ηyKL(yt+1,yt), + 12 _xKL(x_t,x_t-1)+ 12 _yKL(y_t,y_t-1)+ 12 _xKL(x_t+1,x_t)+ 12 _yKL(y_t+1,y_t)\,, After regrouping the bilinear terms, we obtain =−(xt+1−xt)⊤A(yt−yt−1)+(xt−xt−1)⊤A(yt+1−yt) =-(x_t+1-x_t) A(y_t-y_t-1)+(x_t-x_t-1) A(y_t+1-y_t) +12ηxKL(xt,xt−1)+12ηyKL(yt,yt−1)+12ηxKL(xt+1,xt)+12ηyKL(yt+1,yt). + 12 _xKL(x_t,x_t-1)+ 12 _yKL(y_t,y_t-1)+ 12 _xKL(x_t+1,x_t)+ 12 _yKL(y_t+1,y_t)\,. By Fenchel’s inequality and the definition of the operator norm, −(xt+1−xt)⊤A(yt−yt−1) -(x_t+1-x_t) A(y_t-y_t-1) ⩾−3ηy2‖A⊤(xt+1−xt)‖∞2−16ηy‖yt−yt−1‖12 - 3 _y2\|A (x_t+1-x_t)\|_∞^2- 16 _y\|y_t-y_t-1\|_1^2 ⩾−3ηy‖A⊤‖1→∞22‖xt+1−xt‖12−16ηy‖yt−yt−1‖12, - 3 _y\|A \|_1→∞^22\|x_t+1-x_t\|_1^2- 16 _y\|y_t-y_t-1\|_1^2\,, and analogously, (xt−xt−1)⊤A(yt+1−yt) (x_t-x_t-1) A(y_t+1-y_t) ⩾−3ηx‖A‖1→∞22‖yt+1−yt‖12−16ηx‖xt−xt−1‖12. - 3 _x\|A\|_1→∞^22\|y_t+1-y_t\|_1^2- 16 _x\|x_t-x_t-1\|_1^2. Therefore, by Pinsker’s inequality (cf. Proposition B.1), V(Z1:t)−V(Z1:t+1)⩾ V(Z_1:t)-V(Z_1:t+1) (14ηx−3ηy‖A⊤‖1→∞22)‖xt+1−xt‖12 ( 14 _x- 3 _y\|A \|_1→∞^22 )\|x_t+1-x_t\|_1^2 +(14ηy−3ηx‖A‖1→∞22)‖yt+1−yt‖12 + ( 14 _y- 3 _x\|A\|_1→∞^22 )\|y_t+1-y_t\|_1^2 +112ηx‖xt−xt−1‖12+112ηy‖yt−yt−1‖12. + 112 _x\|x_t-x_t-1\|_1^2+ 112 _y\|y_t-y_t-1\|_1^2. By the step size condition, (note that ‖A⊤‖1→∞=‖A‖1→∞\|A \|_1→∞=\|A\|_1→∞) 14ηx−3ηy‖A⊤‖1→∞22⩾0,14ηy−3ηx‖A‖1→∞22⩾0. 14 _x- 3 _y\|A \|_1→∞^22 0, 14 _y- 3 _x\|A\|_1→∞^22 0. Hence V(Z1:t+1)⩽V(Z1:t)V(Z_1:t+1) V(Z_1:t) for all t. To show part 3, we note that V(Z1:1)V(Z_1:1) is a constant. Further, since ψ(Z1:t)ψ(Z_1:t) is bounded from below and the KL-divergence is non-negative, while gap(Zt)gap(Z_t) is bounded on the compact set Δ , the sequence (V(Z1:t))t∈ℕ(V(Z_1:t))_t∈ N is bounded from below. Summing over t gives ∑t=1∞(112ηx‖xt−xt−1‖12+112ηy‖yt−yt−1‖12)<∞. _t=1^∞ ( 112 _x\|x_t-x_t-1\|_1^2+ 112 _y\|y_t-y_t-1\|_1^2 )<∞\,. Consequently, ‖xt+1−xt‖1→0,‖yt+1−yt‖1→0.\|x_t+1-x_t\|_1→ 0, \|y_t+1-y_t\|_1→ 0. Because Zt=(xt,yt,xt−1,yt−1),Z_t=(x_t,y_t,x_t-1,y_t-1), we conclude that ‖Zt−Zt−1‖→0.\|Z_t-Z_t-1\|→ 0\,. This completes the proof. ∎ Proof of Theorem 3.1. By Proposition A.1, the orbit remains in Δ . Since Δ is compact, the sequence (Zt)t∈ℕ(Z_t)_t∈ N has at least one accumulation point. We first show that every accumulation point of (Zt)t∈ℕ(Z_t)_t∈ N is a fixed point of Φ1 _1. Let Z¯ Z be an accumulation point. Then there exists a subsequence (Ztk)k∈ℕ(Z_t_k)_k∈ N such that Ztk→Z¯.Z_t_k→ Z. By Lemma C.1, Part 3, we have ‖Zt+1−Zt‖→0. \|Z_t+1-Z_t \|→ 0. Hence ‖Ztk+1−Ztk‖→0, \|Z_t_k+1-Z_t_k \|→ 0, and therefore Ztk+1→Z¯.Z_t_k+1→ Z. By continuity of Φ1 _1 on Δ , Z¯=limZtk+1=limΦ1(Ztk)=Φ1(Z¯). Z= Z_t_k+1= _1(Z_t_k)= _1( Z)\,. Thus, every accumulation point of the orbit belongs to the fixed-point set ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ). It remains to show that the distance to ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) converges to zero. Suppose, for contradiction, that d(Zt,~(Φ1|Δ^))d(Z_t, Z( . -1.2pt _1 | |_ )) does not converge to 0. Then there exist ϵ>0ε>0 and a subsequence (Ztk)k∈ℕ(Z_t_k)_k∈ N such that d(Ztk,~(Φ1|Δ^))⩾ϵfor all k∈ℕ.d(Z_t_k, Z( . -1.2pt _1 | |_ )) ε all k∈ N. By compactness of Δ , after passing to a further subsequence if necessary, we may assume that Ztk→Z¯Z_t_k→ Z for some Z¯∈Δ Z∈ . By the first part of the proof, Z¯ Z is a fixed point, i.e. Z¯∈~(Φ1|Δ^) Z∈ Z( . -1.2pt _1 | |_ ). Since the distance function Z↦d(Z,~(Φ1|Δ^))Z d(Z, Z( . -1.2pt _1 | |_ )) is continuous, we obtain d(Ztk,~(Φ1|Δ^))→d(Z¯,~(Φ1|Δ^))=0,d(Z_t_k, Z( . -1.2pt _1 | |_ ))→ d( Z, Z( . -1.2pt _1 | |_ ))=0, contradicting d(Ztk,~(Φ1|Δ^))⩾ϵd(Z_t_k, Z( . -1.2pt _1 | |_ )) ε for all k. Therefore d(Zt,~(Φ1|Δ^))→0.d(Z_t, Z( . -1.2pt _1 | |_ ))→ 0. Since this holds for any Z0∈relintΔ^Z_0 , ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is globally attracting with respect to relintΔ^relint . ∎ C.2 Proof of Theorem 3.2 C.2.1 Convergence to a single fixed point The key ingredient is that the whole sequence converges to a single fixed point. We obtain this from the structure of the ω-limit set Ωω:=⋂N⩾1Zt:t⩾N¯, _ω\;:=\; _N 1 \Z_t:t N\\,, combined with two facts that the consecutive increments vanish (Lemma C.1, Part 3) and Δ is compact. We add the following well-known results for completeness. Proposition C.2 (Connectedness of the limit set). Let (Ut)t∈ℕ(U_t)_t∈ N be a sequence in a compact metric space with ‖Ut+1−Ut‖→0\|U_t+1-U_t\|→ 0, and let Ωω=⋂N⩾1Ut:t⩾N¯ _ω= _N 1 \U_t:t N\ be its ω-limit set. Then Ωω _ω is nonempty, compact, and connected. Proof. Ωω _ω is a decreasing intersection of nonempty compact sets in a compact space, hence nonempty and compact. Suppose, for contradiction, that Ωω _ω is disconnected, say Ωω=K1⊔K2 _ω=K_1 K_2 (disjoint union) with K1,K2K_1,K_2 nonempty compact and 2δ:=d(K1,K2)>02δ:=d(K_1,K_2)>0. Define the 11-Lipschitz function g(t):=d(Ut,K1)g(t):=d(U_t,K_1), so that |g(t+1)−g(t)|⩽‖Ut+1−Ut‖→t→∞0.|g(t+1)-g(t)| \|U_t+1-U_t\| [t→∞]0. Because K1⊆ΩωK_1 _ω, we have g(t)<δ/2g(t)<δ/2 for infinitely many t. Since K2⊆ΩωK_2 _ω and d(K2,K1)⩾2δd(K_2,K_1) 2δ, we have g(t)>3δ/2g(t)>3δ/2 for infinitely many t. A real sequence with vanishing increments that lies below δ/2δ/2 and above 3δ/23δ/2 infinitely often must take values in the band [δ/2,3δ/2][δ/2,3δ/2] at arbitrarily large times; in particular, there are times sk→∞s_k→∞ with |g(sk)−δ|→0|g(s_k)-δ|→ 0. By compactness, pass to a convergent subsequence Usk→U⋆U_s_k→ U ; then U⋆∈ΩωU ∈ _ω and d(U⋆,K1)=limkg(sk)=δd(U ,K_1)= _kg(s_k)=δ. But U⋆∈Ωω=K1⊔K2U ∈ _ω=K_1 K_2 forces d(U⋆,K1)=0d(U ,K_1)=0 (if U⋆∈K1U ∈ K_1) or d(U⋆,K1)⩾2δd(U ,K_1) 2δ (if U⋆∈K2U ∈ K_2), contradicting d(U⋆,K1)=δ∈(0,2δ)d(U ,K_1)=δ∈(0,2δ). Hence Ωω _ω is connected. ∎ Proposition C.3 (Connected subsets of countable sets are singletons). A connected subset C of a countable metric space has at most one point. Proof. This is the standard fact that every countable metric space is totally disconnected; see, e.g., Munkres (2000, Sections 23–24). ∎ Lemma C.1 and Propositions C.2 and C.3 imply the following corollary. Corollary C.1. Assume ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is countable. Then there exists Z∞∈~(Φ1|Δ^)Z_∞∈ Z( . -1.2pt _1 | |_ ) such that Zt→Z∞Z_t→ Z_∞. Writing Z∞=(x∞,y∞,x∞,y∞)Z_∞=(x_∞,y_∞,x_∞,y_∞), the payoff Ay∞Ay_∞ is constant on Sx:=supp(x∞)S_x:= *supp(x_∞) and A⊤x∞A x_∞ is constant on Sy:=supp(y∞)S_y:= *supp(y_∞). Proof. By Lemma C.1, Part 3, ‖Zt+1−Zt‖→0\|Z_t+1-Z_t\|→ 0, and Δ is compact, so by Proposition C.2 the ω-limit set Ωω _ω is nonempty, compact, and connected. Note that every point of Ωω _ω is a fixed point of Φ1 _1. If Ztk→Z′Z_t_k→ Z then, using continuity of Φ1 _1 and ‖Ztk+1−Ztk‖→0\|Z_t_k+1-Z_t_k\|→ 0, Z′=limkZtk+1=limkΦ1(Ztk)=Φ1(Z′).Z = _kZ_t_k+1= _k _1(Z_t_k)= _1(Z ). Hence Ωω⊆~(Φ1|Δ^) _ω Z( . -1.2pt _1 | |_ ). Since ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is countable, Ωω _ω is a connected subset of a countable set, so by Proposition C.3, Ωω _ω is a single point, Ωω=Z∞ _ω=\Z_∞\ with Z∞∈~(Φ1|Δ^)Z_∞∈ Z( . -1.2pt _1 | |_ ). Finally, we observe that a sequence in a compact space whose ω-limit set is the single point Z∞Z_∞ converges to Z∞Z_∞. If not, there would exist ε>0 >0 and a subsequence with ‖Ztk−Z∞‖⩾ε\|Z_t_k-Z_∞\| , which by compactness has a further subsequence converging to some Z′∈ΩωZ ∈ _ω with Z′≠Z∞Z ≠ Z_∞, contradicting Ωω=Z∞ _ω=\Z_∞\. Thus Zt→Z∞Z_t→ Z_∞. The stated form and support conditions are Theorem 2.1. ∎ Remark C.1. We only use the total disconnectedness of ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ). Proposition C.3 is applied to the connected set Ωω _ω, and the conclusion |Ωω|⩽1| _ω| 1 holds whenever ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) contains no connected subset of positive diameter. Countability and finiteness imply total disconnectedness. While the converse generally does not hold, it does in our setting since ~(Φ1|Δ^) Z( . -1.2pt _1 | |_ ) is a semialgebraic set. For transparency, we therefore use the strongest assumption, that is, the finiteness of the fixed point set. The following lemma is an essential technical tool to show convergence to a Nash equilibrium. We do this by showing that there is no off-support action with strictly better payoff. Recall the characterization of fixed points from Theorem 2.1 and the example from Remark 2.1. The following lemma rules out exactly these cases. C.2.2 The limit is a Nash equilibrium By Corollary C.1 it remains to show that the limit Z∞Z_∞ corresponds to a Nash equilibrium. Proof of Theorem 3.2. By Corollary C.1, Zt→Z∞Z_t→ Z_∞ with Z∞=(x∞,y∞,x∞,y∞)∈~(Φ1|Δ^)Z_∞=(x_∞,y_∞,x_∞,y_∞)∈ Z( . -1.2pt _1 | |_ ), and Ay∞Ay_∞ is constant on Sx=supp(x∞)S_x= *supp(x_∞) while A⊤x∞A x_∞ is constant on Sy=supp(y∞)S_y= *supp(y_∞). It remains to show (x∞,y∞)(x_∞,y_∞) is a Nash equilibrium. Reduction to a profitable deviation. Let vx:=(Ay∞)iv_x:=(Ay_∞)_i for any i∈Sxi∈ S_x; then x∞⊤Ay∞=vxx_∞ Ay_∞=v_x. Since maxx∈Δdxx⊤Ay∞=maxi(Ay∞)i _x∈ _d_xx Ay_∞= _i(Ay_∞)_i, the strategy x∞x_∞ is a best response to y∞y_∞ iff (Ay∞)i⩽vx(Ay_∞)_i v_x for all i. Symmetrically, with vy:=(A⊤x∞)lv_y:=(A x_∞)_l for l∈Syl∈ S_y (note B=−A⊤B=-A , so the y-player maximizes y⊤Bx=−y⊤A⊤xy Bx=-y A x, equivalently minimizes y⊤A⊤xy A x), y∞y_∞ is a best response to x∞x_∞ iff (A⊤x∞)k⩾vy(A x_∞)_k v_y for all k. Consequently, if (x∞,y∞)(x_∞,y_∞) is not a Nash equilibrium, then at least one of the following holds: (I) there exist ı and j∈Sxj∈ S_x with (Ay∞)ı^>(Ay∞)j=vx(Ay_∞)_ >(Ay_∞)_j=v_x; since (Ay∞)i=vx(Ay_∞)_i=v_x for i∈Sxi∈ S_x, necessarily ı^∉Sx ∉ S_x; (I) there exist ȷ and l∈Syl∈ S_y with (A⊤x∞)ȷ^<(A⊤x∞)l=vy(A x_∞)_ <(A x_∞)_l=v_y; necessarily ȷ^∉Sy ∉ S_y. We only show case (I) since case (I) follows exactly the same argument. Define Rt:=xt,ı^/xt,jR_t:=x_t, /x_t,j. This ratio is well defined and strictly positive for every t by Proposition A.1 and since Z0∈relintΔ^Z_0 by assumption. Since ı^∉Sx ∉ S_x, j∈Sxj∈ S_x, and (Ay∞)ı^>(Ay∞)j(Ay_∞)_ >(Ay_∞)_j, Lemma B.1 provides δ,ϵ,τ>0δ,ε,τ>0 such that, for all t∈ℕt∈ N, ‖Zt−Z∞‖<δ⟹Rt+1⩾eϵRt,\|Z_t-Z_∞\|<δ R_t+1 e^εR_t, (7) and, for all Z=[x,y,x′,y′]Z=[x,y,x ,y ], ‖Z−Z∞‖<δ⟹xı^xj<τ.\|Z-Z_∞\|<δ x_ x_j<τ. (8) By Corollary C.1, Zt→Z∞Z_t→ Z_∞. Thus, there exists T⋆∈ℕT_ ∈ N with ‖Zt−Z∞‖<δfor all t⩾T⋆.\|Z_t-Z_∞\|<δ all t T_ . (9) Convergence of the whole sequence ensures that every iterate with t⩾T⋆t T_ is in Bδ(Z∞)B_δ(Z_∞). Hence (7) applies at every t⩾T⋆t T_ , and by induction Rt⩾eϵ(t−T⋆)RT⋆(t⩾T⋆).R_t\ \ e^ε(t-T_ )\,R_T_ (t T_ ). (10) Since RT⋆>0R_T_ >0 and ϵ>0ε>0, the right-hand side of (10) diverges, so Rt→+∞R_t→+∞. On the other hand, (9) and (8) give the uniform bound Rt=xt,ı^xt,j<τ(t⩾T⋆).R_t= x_t, x_t,j<τ (t T_ ). (11) Inequalities (10) and (11) are incompatible. This excludes Case (I). We conclude that neither deviation can occur, so x∞x_∞ is a best response to y∞y_∞ and y∞y_∞ is a best response to x∞x_∞. With the support-equalization of Theorem 2.1, (x∞,y∞)(x_∞,y_∞) is a Nash equilibrium, i.e. Z∞∈⋆Z_∞∈ Z . By Corollary C.1, Zt→Z∞∈⋆Z_t→ Z_∞∈ Z . ∎ Appendix D Omitted Proofs of Section 4 Our results in this section build on known techniques from discrete dynamical systems theory. See, e.g., Kuznetsov et al. (2026). D.1 The Jacobian We provide some standard computations for the convenience of the reader. Let Z=[z1,z2,z1,z2]Z=[z_1,z_2,z_1,z_2] be a fixed point of Φm _m. First recall that for a fixed point Z∈~(Φm|Δ^)Z∈ Z( . -1.2pt _m | |_ ), Z=[z1,z2,z3,z4]Z=[z_1,z_2,z_3,z_4], 1=Exp(ηx(Az2−vx)),2=Exp(ηy(Bz1−vy)).w_1=Exp ( _x(Az_2-v^x1) ), _2=Exp ( _y(Bz_1-v^y1) )\,. (Recall the definition: vx:=(Az2)iv^x:=(Az_2)_i for any i∈Sxi∈ S_x and vy:=(Bz1)jv^y:=(Bz_1)_j for any j∈Syj∈ S_y.) Lemma D.1. For a game Γ(A,B) (A,B), the Jacobian matrix JΦm(Z)∈ℝ(2(dx+dy))×(2(dx+dy))J_ _m(Z) ^(2(d_x+d_y))×(2(d_x+d_y)) with Z∈~(Φm|Δ^)Z∈ Z( . -1.2pt _m | |_ ) is: JΦm(Z)=[diag(1)−z11⊤(1+m)ηxH(z1)A0−mηxH(z1)A(1+m)ηyH(z2)Bdiag(2)−z22⊤−mηyH(z2)B0Idx0000Idy00].J_ _m(Z)= bmatrixdiag(w_1)-z_1w_1 &(1+m) _xH(z_1)A&0&-m _xH(z_1)A\\ (1+m) _yH(z_2)B&diag(w_2)-z_2w_2 &-m _yH(z_2)B&0\\ I_d_x&0&0&0\\ 0&I_d_y&0&0 bmatrix\,. Proof. Using the block structure of Φm=[(Φm)1,(Φm)2,(Φm)3,(Φm)4] _m=[( _m)_1,( _m)_2,( _m)_3,( _m)_4], where (Φm)k:ℝ2(dx+dy)→ℝdx( _m)_k: R^2(d_x+d_y)→ R^d_x for k=1,3k=1,3 and (Φm)k:ℝ2(dx+dy)→ℝdy( _m)_k: R^2(d_x+d_y)→ R^d_y for k=2,4k=2,4, we compute the Jacobian block-wise J1,1=∂(Φm)1∂z1J_1,1= ∂( _m)_1∂ z_1, J1,2=∂(Φm)1∂z2J_1,2= ∂( _m)_1∂ z_2 and J1,4=∂(Φm)1∂z4J_1,4= ∂( _m)_1∂ z_4. The blocks J2,1,J2,2J_2,1,J_2,2 and J2,3J_2,3 follow analogously. Since for any i,ji,j and for u∈ℝd∖x∈ℝd:⊤x=0u ^d \x∈ R^d:1 x=0\ , we have ∂(Pd)i∂uj=−ui⟨,u⟩2if i≠j1⟨,u⟩−ui⟨,u⟩2if i=j, ∂(P_d)_i∂ u_j= \ split&- u_i 1,u ^2&if i≠ j\\ & 1 1,u - u_i 1,u ^2&if i=j split .\,, the Jacobian for PdP_d is JPd(u)=1⟨,u⟩(Id−Pd(u)⊤) J_P_d(u)= 1 1,u (I_d-P_d(u)1 ) (12) Now let (Φmu)1(z1,z2,z3,z4)=z1⊙Exp(ηxA((1+m)z2−mz4))( ^u_m)_1(z_1,z_2,z_3,z_4)=z_1 ( _xA((1+m)z_2-mz_4)) denote the first component of the unnormalized exponential weight updates. Then, J1,1=∂(Φmu)1∂z1=JPdx((Φmu)1(z1,z2,z3,z4))diag(Exp(ηxA((1+m)z2−mz4))).J_1,1= ∂( ^u_m)_1∂ z_1=J_P_d_x(( ^u_m)_1(z_1,z_2,z_3,z_4))diag (Exp( _xA((1+m)z_2-mz_4)) )\,. As z2=z4z_2=z_4, we have Exp(ηxA((1+m)z2−mz4))=Exp(ηxAz2)Exp( _xA((1+m)z_2-mz_4))=Exp( _xAz_2). Thus, by (12) J1,1 J_1,1 =1⟨z1,Exp(ηxAz2)⟩(Iddx−Pdx(z1⊙Exp(ηxAz2))⊤)diag(Exp(ηxAz2)) = 1 z_1,Exp( _xAz_2) (Id_d_x-P_d_x (z_1 ( _xAz_2) )1 )diag(Exp( _xAz_2)) =(⋆)1⟨z1,Exp(ηxAz2)⟩(Iddx−z1⊤)diag(Exp(ηxAz2)) ( )= 1 z_1,Exp( _xAz_2) (Id_d_x-z_11 )diag(Exp( _xAz_2)) =1⟨z1,Exp(ηxAz2)⟩(diag(Exp(ηxAz2))−z1Exp(ηxAz2)⊤) = 1 z_1,Exp( _xAz_2) (diag(Exp( _xAz_2))-z_1Exp( _xAz_2) ) =diag(Exp(ηx(Az2−vx)))−z1Exp(ηx(Az2−vx))⊤. =diag(Exp( _x(Az_2-v^x1)))-z_1Exp( _x(Az_2-v^x1)) \,. We used the fixed-point equation in the final line 1⟨z1,Exp(ηxAz2)⟩=e−ηxvx, 1 z_1,Exp( _xAz_2) =e^- _xv^x\,, and consequently also Pdx(z1⊙Exp(ηxAz2))=z1P_d_x(z_1 ( _xAz_2))=z_1 in (⋆)( ). The computation of the block J1,2J_1,2 follows similar arguments. We have, J1,2 J_1,2 =JPdx(z1⊙Exp(ηxAz2))diag(z1)diag(Exp(ηxAz2))(1+m)ηxA =J_P_d_x(z_1 ( _xAz_2))diag(z_1)diag(Exp( _xAz_2))(1+m) _xA =1+m⟨z1,Exp(ηxAz2)⟩(Iddx−Pdx(z1⊙Exp(ηxAz2))⊤)diag(z1)diag(Exp(ηxAz2))ηxA = 1+m z_1,Exp( _xAz_2) (Id_d_x-P_d_x(z_1 ( _xAz_2))1 )diag(z_1)diag(Exp( _xAz_2)) _xA =1+m⟨z1,Exp(ηxAz2)⟩(Iddx−z1⊤)diag(z1⊙Exp(ηxAz2))ηxA = 1+m z_1,Exp( _xAz_2) (Id_d_x-z_11 )diag (z_1 ( _xAz_2) ) _xA =(1+m)(Iddx−z1⊤)diag(Pdx(z1⊙Exp(ηxAz2)))ηxA =(1+m) (Id_d_x-z_11 )diag (P_d_x(z_1 ( _xAz_2)) ) _xA =(1+m)(Iddx−z1⊤)diag(z1)ηxA =(1+m) (Id_d_x-z_11 )diag (z_1) _xA =(1+m)(diag(z1)−z1z1⊤)ηxA. =(1+m) (diag (z_1)-z_1z_1 ) _xA\,. The proof is completed by noting that J1,4J_1,4 follows by the same arguments. ∎ D.2 Eigenvalues of the Jacobian and Proof of Theorem 4.2 Notation: Restrictions, Complexification and Eigenvalues Recall that for a real linear map T:E→ET:E→ E we denote the spectrum, the spectrum without multiplicities, and the spectral radius of the complexified restriction by eig(T|V),eig~(T|V)eig (T|_V ), eig (T|_V ) and ρ(T|V)ρ (T|_V ). To make the complexification transparent in this section, we introduce some notation. Thus, let E be a real vector space and denote its complexification by Eℂ:=E⊗ℝℂE_C:=E _ RC. Given a linear map M:E→EM:E→ E we denote by Mℂ:Eℂ→EℂM_C:E_C→ E_C the complex(-linear) extension defined by Mℂ(u+iv)=Mu+iMvM_C(u+iv)=Mu+iMv for all u,v∈Eu,v∈ E. Let V⊂EV⊂ E be a linear subspace such that M(V)⊆VM(V) V. Then M|V . -1.2ptM | |_V induces an endomorphism on V and (M|V)ℂ=(Mℂ)|Vℂ ( . -1.2ptM | |_V )_C= . -1.2pt(M_C) | |_V_C. We denote both by MV,ℂM_V,C. Moreover, the eigenvectors of MV,ℂM_V,C are exactly the eigenvectors z of MℂM_C such that z∈Vℂz∈ V_C. That is, complex eigenvalues of JΦm(Z)|L . -1.2ptJ_ _m(Z) | |_L are complex numbers such that there exists ∈Lℂ(=L+iL)h∈ L_C(=L+iL) for which JΦm(Z)=λJ_ _m(Z)h= . The proof of Theorem 4.2 builds on the following two results. Lemma D.2 (Spectrum of JΦm(Z)|LJ_ _m(Z)|_L). The complex λ∈ℂ⋆λ is an eigenvalue of JΦm(Z)|LJ_ _m(Z)|_L, if and only if one of the following holds λ∈1,i∣i∈1,…,dx∖Sx∪2,j∣j∈1,…,dy∖Syλ∈\w_1,i i∈\1,…,d_x\ S_x\∪\w_2,j j∈\1,…,d_y\ S_y\ or λ≠m+1λ≠ mm+1 and ∃[h1,h2,λ−1h1,λ−1h2]∈Lℂ∖0s.t.ηxH(z1)Ah2=λ(λ−1)(1+m)λ−mh1ηyH(z2)Bh1=λ(λ−1)(1+m)λ−mh2∀i∉Sx,∀j∉Sy,h1,i=h2,j=0. ∃[h_1,h_2,λ^-1h_1,λ^-1h_2]∈ L_C \0\ .t. cases& _xH(z_1)Ah_2= λ(λ-1)(1+m)λ-mh_1\\[10.00002pt] & _yH(z_2)Bh_1= λ(λ-1)(1+m)λ-mh_2\\[10.00002pt] &∀ i∉ S_x,\;∀ j∉ S_y,\;h_1,i=h_2,j=0\,. cases (LS) Proof of Lemma D.2. The complex λ∈ℂ⋆λ is an eigenvalue of JΦm(Z)|LJ_ _m(Z)|_L, if and only if there is some =[h1,h2,h3,h4]∈Lℂh=[h_1,h_2,h_3,h_4]∈ L_C such that JΦm(Z)=λJ_ _m(Z)h= . Assuming λ≠0λ≠ 0, the last two block rows imply h3=λ−1h1h_3=λ^-1h_1 and h4=λ−1h2h_4=λ^-1h_2. Substituting these into the first two rows yields the reduced system: (diag(1)−z11⊤)h1+ηxH(z1)A(1+m−mλ−1)h2 (diag(w_1)-z_1w_1 )h_1+ _xH(z_1)A(1+m-mλ^-1)h_2 =λh1 =λ h_1 (13) (diag(2)−z22⊤)h2+ηyH(z2)B(1+m−mλ−1)h1 (diag(w_2)-z_2w_2 )h_2+ _yH(z_2)B(1+m-mλ^-1)h_1 =λh2 =λ h_2 (14) We then proceed by a case disjunction: Case 1: h1,k≠0h_1,k≠ 0 for some k∉Sxk∉ S_x If there exists k∉Sxk∉ S_x such that h1,k≠0h_1,k≠ 0, then for such k, we have z1,k=0z_1,k=0, so the k-th row of H(z1)H(z_1) is zero, and the k-th row of z11⊤z_1w_1 is zero. Equation (13) for the k-th component becomes: 1,kh1,k+0=λh1,k,w_1,k\,h_1,k+0=λ\,h_1,k\,, therefore λ=1,kλ=w_1,k, since h1,k≠0h_1,k≠ 0. Conversely, for any k∉Sxk∉ S_x, consider the left-eigenvector =(ek,0,0,0)v=(e_k,0,0,0) then ⊤JΦm(Z)=(ek⊤,0,0,0)JΦm(Z)=(1,kek⊤,0,0,0)=1,k⊤.v J_ _m(Z)=(e_k ,0,0,0)J_ _m(Z)=(w_1,ke_k ,0,0,0)=w_1,kv \,. So 1,kw_1,k is a non-zero eigenvalue of JΦm(Z)J_ _m(Z). It remains to show that the corresponding right eigenvector lies in LℂL_ C. If [h1,h2,λ−1h1,λ−1h2][h_1,h_2,λ^-1h_1,λ^-1h_2] is a (right-)eigenvector with eigenvalue 1,k>0w_1,k>0, then necessarily, due to Equation (13), λ⊤h1=⊤(diag(1)−z11⊤)h1+ηx⊤H(z1)A(1+m−mλ−1)h2. 1 h_1=1 (diag(w_1)-z_1w_1 )h_1+ _x1 H(z_1)A(1+m-mλ^-1)h_2\,. Now ⊤(diag(1)−z11⊤)=⊤diag(1)−⊤z11⊤=1⊤−1⊤=0,1 (diag(w_1)-z_1w_1 )=1 diag(w_1)-1 z_1w_1 =w_1 -w_1 =0\,, and similarly ⊤H(z1)=0.1 H(z_1)=0\,. So ⊤h1=01 h_1=0. Symmetrically, we also have ⊤h2=01 h_2=0, so [h1,h2,λ−1h1,λ−1h2]∈Lℂ[h_1,h_2,λ^-1h_1,λ^-1h_2]∈ L_C. Case 2: h2,ℓ≠0h_2, ≠ 0 for some ℓ∉Sy ∉ S_y Similarly, if there exists ℓ∉Sy ∉ S_y such that h2,ℓ≠0h_2, ≠ 0, then necessarily λ=2,ℓλ=w_2, , and conversely these are indeed eigenvalues of JΦm(Z)|LJ_ _m(Z)|_L. Case 3 If neither Case 1 nor Case 2 holds, then h1h_1 is supported on SxS_x and h2h_2 on SyS_y. On the support SxS_x (resp. SyS_y), all coordinates of the vector 1w_1 (resp. 2w_2) are 11. The term (diag(1)−z11⊤)h1(diag(w_1)-z_1w_1 )h_1 becomes (I−z1⊤)h1(I-z_11 )h_1. Since ⊤h1=01 h_1=0, this simplifies to h1h_1. Equations (13) and (14) become: h1+(1+m−mλ−1)ηxH(z1)Ah2 h_1+(1+m-mλ^-1) _xH(z_1)Ah_2 =λh1i.e.(λ−1)h1=(1+m−mλ−1)ηxH(z1)Ah2 =λ h_1 .e. (λ-1)h_1=(1+m-mλ^-1) _xH(z_1)Ah_2 h2+(1+m−mλ−1)ηyH(z2)Bh1 h_2+(1+m-mλ^-1) _yH(z_2)Bh_1 =λh2i.e.(λ−1)h2=(1+m−mλ−1)ηyH(z2)Bh1. =λ h_2 .e. (λ-1)h_2=(1+m-mλ^-1) _yH(z_2)Bh_1\,. To rewrite these in the form (LS), divide by 1+m−mλ−1=((1+m)λ−m)/λ1+m-mλ^-1=((1+m)λ-m)/λ, which is nonzero if λ≠m/(m+1)λ≠ m/(m+1). If instead λ=m/(m+1)λ=m/(m+1), then the equations simplify to (λ−1)h1=0(λ-1)h_1=0, (λ−1)h2=0(λ-1)h_2=0. Since λ=m/(m+1)≠1λ=m/(m+1)≠ 1, this forces h1=h2=0h_1=h_2=0. Hence m/(m+1)m/(m+1) never arises as an eigenvalue through Case 3, and can occur only via Cases 1 or 2, i.e. as an element of W. Conversely, we check that any pair (λ,)∈ℂ⋆×Lℂ∖0(λ,h) × L_C \0\ satisfying these conditions is indeed an eigenvalue-eigenvector pair for JΦm(Z)|LJ_ _m(Z)|_L. Assume first that λ≠m+1λ≠ mm+1 and that (LS) holds. Define :=[h1,h2,λ−1h1,λ−1h2]∈Lℂ.h:= [h_1,h_2,λ^-1h_1,λ^-1h_2 ]∈ L_C\,. Since [h1,h2]≠[0,0][h_1,h_2]≠[0,0], we have ≠0h≠ 0. Moreover, h1,h2h_1,h_2 are supported on Sx,SyS_x,S_y, respectively, and 1=w_1=1 on SxS_x, 2=w_2=1 on SyS_y. Hence, using ⊤h1=⊤h2=01 h_1=1 h_2=0, (diag(1)−z11⊤)h1=h1,(diag(2)−z22⊤)h2=h2. (diag(w_1)-z_1w_1 )h_1=h_1\,, (diag(w_2)-z_2w_2 )h_2=h_2\,. Also, 1+m−mλ−1=(1+m)λ−mλ.1+m-mλ^-1= (1+m)λ-mλ\,. Therefore, by (LS), (1+m−mλ−1)ηxH(z1)Ah2=(λ−1)h1, (1+m-mλ^-1 ) _xH(z_1)Ah_2=(λ-1)h_1\,, and similarly (1+m−mλ−1)ηyH(z2)Bh1=(λ−1)h2. (1+m-mλ^-1 ) _yH(z_2)Bh_1=(λ-1)h_2\,. Substituting these identities into the first two block rows of JΦm(Z)J_ _m(Z)h, and using h3=λ−1h1h_3=λ^-1h_1, h4=λ−1h2h_4=λ^-1h_2 for the last two block rows, gives JΦm(Z)=λ.J_ _m(Z)h= \,. Thus λ∈eig(JΦm(Z)|L)λ (J_ _m(Z)|_L ). It remains to consider the case λ∈Wλ∈ W. This is exactly the off-support case treated above: the corresponding off-support coordinate gives a nonzero eigenvector of JΦm(Z)J_ _m(Z), and the summation argument shows that this eigenvector lies in LℂL_ C. Hence λ∈eig(JΦm(Z)|L).λ (J_ _m(Z)|_L )\,. ∎ Lemma D.3. Suppose nx⩾nyn_x n_y. For any λ∈ℂ⋆∖m/(m+1)λ∈ C \m/(m+1)\, we have the following equivalence ∃[h1,h2,λ−1h1,λ−1h2]∈Lℂ∖0s.t.ηxH(z1)Ah2=λ(λ−1)(1+m)λ−mh1ηyH(z2)Bh1=λ(λ−1)(1+m)λ−mh2∀i∉Sx,∀j∉Sy,h1,i=h2,j=0. ∃[h_1,h_2,λ^-1h_1,λ^-1h_2]∈ L_C \0\ .t. cases& _xH(z_1)Ah_2= λ(λ-1)(1+m)λ-mh_1\\[10.00002pt] & _yH(z_2)Bh_1= λ(λ-1)(1+m)λ-mh_2\\[10.00002pt] &∀ i∉ S_x,\;∀ j∉ S_y,\;h_1,i=h_2,j=0\,. cases (LS) if and only if Qm(λ)∈eig(ηxηyΠSx(H(z1)AH(z2)B)ΠSx⊤|Lx).Q_m(λ) ( _x _y _S_x(H(z_1)AH(z_2)B) _S_x |_L_x )\,. Proof of Lemma D.3. We prove the two implications separately and isolate the case λ=1λ=1. (i)⇒(ii)(i) (i), first assume λ≠1λ≠ 1. Let [h1,h2,λ−1h1,λ−1h2]∈Lℂ∖0[h_1,h_2,λ^-1h_1,λ^-1h_2]∈ L_C \0\ satisfying the condition of the statement. Then since ⊤h1=01 h_1=0, and since h1,i=0h_1,i=0 for all i∉Sxi∉ S_x, we have ∑i∈Sxh1,i=∑i=1dxh1,i=0. _i∈ S_xh_1,i= _i=1^d_xh_1,i=0\,. so ΠSxh1∈Lx,ℂ _S_xh_1∈ L_x,C. Moreover, the eigenvalue equations imply that h1≠0h_1≠ 0, so ΠSxh1≠0 _S_xh_1≠ 0. Finally, since h1h_1 is supported on SxS_x, we have ΠSx⊤ΠSxh1=h1 _S_x _S_xh_1=h_1 so ηxηyΠSx(H(z1)AH(z2)B)ΠSx⊤ΠSxh1=ηxηyΠSx(H(z1)AH(z2)B)h1=ηxΠSxH(z1)A(λ(λ−1)(1+m)λ−mh2)=(λ(λ−1)(1+m)λ−m)2ΠSxh1. _x _y _S_x(H(z_1)AH(z_2)B) _S_x _S_xh_1= _x _y _S_x(H(z_1)AH(z_2)B)h_1\\ = _x _S_xH(z_1)A ( λ(λ-1)(1+m)λ-mh_2 )= ( λ(λ-1)(1+m)λ-m )^2 _S_xh_1\,. Therefore ΠSxh1∈Lx,ℂ _S_xh_1∈ L_x, C is an eigenvector of ηxηyMx(Z)|Lx _x _y . -1.2ptM_x(Z) | |_L_x with eigenvalue Qm(λ)Q_m(λ). (i)⇒(ii)(i) (i), now consider λ=1λ=1. Then μ=0μ=0 and Qm(1)=0Q_m(1)=0. If h1≠0h_1≠ 0, then ΠSxh1∈Lx,ℂ∖0 _S_xh_1∈ L_x, C \0\ and H(z2)Bh1=0,H(z_2)Bh_1=0, so ΠSxH(z1)AH(z2)BΠSx⊤ΠSxh1=0. _S_xH(z_1)AH(z_2)B _S_x _S_xh_1=0. Thus 0=Qm(1)0=Q_m(1) is an eigenvalue of ΠSxH(z1)AH(z2)BΠSx⊤|Lx _S_xH(z_1)AH(z_2)B _S_x |_L_x. Suppose instead that h1=0h_1=0. Since [h1,h2]≠[0,0][h_1,h_2]≠[0,0], we have h2≠0h_2≠ 0. Moreover h2h_2 is supported on SyS_y and belongs to LyL_y, and the first equation gives H(z1)Ah2=0.H(z_1)Ah_2=0. Define T:=ΠSxH(z1)AΠSy⊤:Ly,ℂ→Lx,ℂ.T:= _S_xH(z_1)A _S_y :L_y, C→ L_x, C. Then kerT≠0 T≠\0\, so rankT<dimLy=ny−1. *rankT< L_y=n_y-1. Now write ΠSxH(z1)AH(z2)BΠSx⊤|Lx=T∘R _S_xH(z_1)AH(z_2)B _S_x |_L_x=T R where R:=ΠSyH(z2)BΠSx⊤:Lx,ℂ→Ly,ℂ.R:= _S_yH(z_2)B _S_x :L_x, C→ L_y, C. Hence rank(T∘R)⩽rankT<ny−1. *rank(T R) *rankT<n_y-1. Using the assumption nx⩾nyn_x n_y, we get rank(T∘R)<ny−1⩽nx−1=dimLx. *rank(T R)<n_y-1 n_x-1= L_x. Therefore ΠSxH(z1)AH(z2)BΠSx⊤|Lx _S_xH(z_1)AH(z_2)B _S_x |_L_x is singular, and so 0=Qm(1)0=Q_m(1) is an eigenvalue. (ii)⇒(i)(i) (i), first assume λ≠1λ≠ 1. Let μ=λ(λ−1)(1+m)λ−m≠0,μ= λ(λ-1)(1+m)λ-m≠ 0\,, then the assumption is that there exist v1∈Lx,ℂ∖0v_1∈ L_x,C \0\ such that ηxηyΠSx(H(z1)AH(z2)B)ΠSx⊤v1=μ2v1. _x _y _S_x(H(z_1)AH(z_2)B) _S_x v_1=μ^2v_1\,. Define the vectors h1=ΠSx⊤v1andh2=ηyμH(z2)BΠSx⊤v1h_1= _S_x v_1 h_2= _yμH(z_2)B _S_x v_1 then ηyH(z2)Bh1=μh2 _yH(z_2)Bh_1=μ h_2 and ηxΠSxH(z1)Ah2=ηxηyμΠSxH(z1)AH(z2)BΠSx⊤v1=1μμ2v1=μv1, _x _S_xH(z_1)Ah_2= _x _yμ _S_xH(z_1)AH(z_2)B _S_x v_1= 1μ^2v_1=μ v_1\,, so ηxH(z1)Ah2=ηxΠSx⊤ΠSxH(z1)Ah2=μΠSx⊤v1=μh1. _xH(z_1)Ah_2= _x _S_x _S_xH(z_1)Ah_2=μ _S_x v_1=μ h_1\,. (ii)⇒(i)(i) (i), now consider λ=1λ=1. Since Qm(1)=0Q_m(1)=0, assume that there exists v1∈Lx,ℂ∖0v_1∈ L_x,C \0\ such that ΠSxH(z1)AH(z2)BΠSx⊤v1=0. _S_xH(z_1)AH(z_2)B _S_x v_1=0. Set h^1:=ΠSx⊤v1,r:=H(z2)Bh^1. h_1:= _S_x v_1, r:=H(z_2)B h_1. Then r is supported on SyS_y and satisfies ⊤r=01 r=0, hence r∈Ly,ℂr∈ L_y,C. Moreover, ΠSxH(z1)Ar=ΠSxH(z1)AH(z2)BΠSx⊤v1=0. _S_xH(z_1)Ar= _S_xH(z_1)AH(z_2)B _S_x v_1=0. Since H(z1)ArH(z_1)Ar is supported on SxS_x, this implies H(z1)Ar=0.H(z_1)Ar=0. If r=0r=0, choose h1=h^1,h2=0.h_1= h_1, h_2=0. Then H(z2)Bh1=0,H(z1)Ah2=0.H(z_2)Bh_1=0, H(z_1)Ah_2=0. If r≠0r≠ 0, choose h1=0,h2=r.h_1=0, h_2=r. Then H(z2)Bh1=0,H(z1)Ah2=H(z1)Ar=0.H(z_2)Bh_1=0, H(z_1)Ah_2=H(z_1)Ar=0. In both cases, [h1,h2]≠[0,0][h_1,h_2]≠[0,0], and the vectors have the required support and tangent-space properties. Hence (LS) holds for λ=1λ=1. ∎ We are now ready to prove Theorem 4.2. Proof of Theorem 4.2. From Lemma D.3, for every λ∈ℂ∖0,m+1λ \0, mm+1\, λ∈Qm−1(eig~(ηxηyMx(Z)|Lx))⇔(LS).λ∈ Q_m^-1 ( eig ( _x _y . -1.2ptM_x(Z) | |_L_x ) ) eq:linSys. By Lemma D.2, every λ∈eig(JΦm(Z)|L)∖0,m+1λ (J_ _m(Z)|_L ) \0, mm+1\ either satisfies (LS) or lies in W. It remains to treat λ=m/(m+1)λ=m/(m+1). As the pole of QmQ_m, it is never an element of Qm−1(μ)Q_m^-1(μ) for any finite μ, so it never belongs to the right-hand set; and by the Case 3 analysis above, it is an eigenvalue of JΦm(Z)|LJ_ _m(Z)|_L if and only if m/(m+1)∈Wm/(m+1)∈ W. Thus adjoining or removing λ=m/(m+1)λ=m/(m+1) changes neither side, and eig~(JΦm(Z)|L)∖0=(W∪Qm−1(eig~(ηxηyMx(Z)|Lx)))∖0, eig (J_ _m(Z)|_L ) \0\= (W∪ Q_m^-1 ( eig ( _x _y . -1.2ptM_x(Z) | |_L_x ) ) ) \0\, as claimed. ∎ D.3 Stability It is well known that when a fixed point lies in the interior of the domain, the stability and attraction of the fixed point can be characterized by the spectrum of the Jacobian at the fixed point. In our case, the state space is a product of simplices, and its interior is empty. Our techniques rely on stable subsets with respect to a non-empty relative interior. In the following results, we denote by Bδ(0)B_δ(0) the open ball with radius δ>0δ>0 centered at the origin. Lemma D.4 (Fréchet-Differentials, Jacobians and Restrictions). Let ⊂ℝd O ^d be an open subset and x∈x∈ O. Let f:→ℝdf: O ^d be a 1 C^1 map. Let V⊂ℝdV ^d be a linear subspace and δ>0δ>0. If f(x+(Bδ(0)∩V))⊂x+Vf(x+(B_δ(0)∩ V))⊂ x+V, then Df(x)|V=D(f|∩(x+V))(x).Df(x)|_V=D(f|_ O∩(x+V))(x)\,. In particular, Df(x)V⊂VDf(x)V⊂ V. Proof. We first show that we can assume without loss of generality that x is the origin. Define g(u)=f(x+u)−x,g(u)=f(x+u)-x, for u∈−xu∈ O-x. Then g is 1 C^1, Dg(0)=Df(x)Dg(0)=Df(x), and g((Bδ(0)∩V))⊂Vg ((B_δ(0)∩ V) )⊂ V. Thus, it suffices to prove the claim for x=0x=0. The set ∩V O∩ V is open in V, so f|∩V . -1.2ptf | |_ O∩ V is differentiable as a map defined on V. For any v∈Vv∈ V and any t small enough, we have tv∈∩Vtv∈ O∩ V, hence Df(0)v=limt→0f(tv)−f(0)t=limt→0f|∩V(tv)−f|∩V(0)t=D(f|∩V)(0)v.Df(0)v= _t→ 0 f(tv)-f(0)t= _t→ 0 f|_ O∩ V(tv)-f|_ O∩ V(0)t=D(f|_ O∩ V)(0)v. Moreover, due to the local invariance assumption, for t small enough, both f(tv)f(tv) and f(0)f(0) lie in V, so f(tv)−f(0)t∈V. f(tv)-f(0)t∈ V. Passing to the limit gives Df(0)v∈VDf(0)v∈ V. ∎ D.4 Stability and Instability Recall that we denote by ρ(A)ρ (A ) the spectral radius of the linear map A, i.e., the largest modulus of its complex eigenvalues. The following results will be an essential tool. Many of them are well-known results, which we include for completeness. Proposition D.1 (Stability and Linearization of Maps). Consider a 1 C^1 map g:ℝn→ℝng: R^n→ R^n with g(0)=0g(0)=0. Then 0 is 1. asymptotically stable if ρ(Dg(0))<1ρ (Dg(0) )<1; and 2. unstable if ρ(Dg(0))>1ρ (Dg(0) )>1. For a proof, see, e.g., Theorem 3.2 in Kuznetsov et al. (2026). Theorem D.1. Let V⊂ℝdV ^d be a linear subspace, and O an open subset of ℝdR^d. Let F:→F: O→ O be a 1 C^1 map and x∈x∈ O be a fixed point of F. If there exists δ>0δ>0 such that F(x+(V∩Bδ(0)))⊂x+V,F (x+(V∩ B_δ(0)) )⊂ x+V\,, then x is asymptotically stable relative to x+Vx+V if ρ(DF(x)|V)<1ρ ( . -1.2ptDF(x) | |_V )<1 and unstable relative to x+Vx+V if ρ(DF(x)|V)>1ρ ( . -1.2ptDF(x) | |_V )>1. Remark D.1. The restriction to relative to x+Vx+V is essential. Note that if a fixed point is stable relative to a set A, then it is stable relative to every (forward invariant) subset B⊂AB⊂ A containing the fixed point. Conversely, if it is unstable relative to such a subset B, then it is unstable relative to A. Proof. We assume again without loss of generality that x=0x=0 (otherwise consider G(u)=F(x+u)−xG(u)=F(x+u)-x). We also denote Bδ=Bδ(0)B_δ=B_δ(0). Since F(V∩Bδ)⊂V,F(V∩ B_δ)⊂ V, the restriction f:=F|V∩Bδ:V∩Bδ→Vf:= . -1.2ptF | |_V∩ B_δ:V∩ B_δ→ V is well defined and by Lemma D.4, Df(0)=DF(0)|V.Df(0)= . -1.2ptDF(0) | |_V. Let k=dimVk= V, and let Tc:ℝk→VT_c:R^k→ V be a linear isomorphism. Define F~:=Tc−1∘f∘Tc F:=T_c^-1 f T_c on the open set Tc−1(V∩Bδ)⊂ℝkT_c^-1(V∩ B_δ) ^k. Then F~ F is of class 1 C^1, satisfies F~(0)=0 F(0)=0, and DF~(0)=Tc−1∘Df(0)∘Tc=Tc−1∘DF(0)|V∘Tc.D F(0)=T_c^-1 Df(0) T_c=T_c^-1 . -1.2ptDF(0) | |_V T_c. Hence DF~(0)D F(0) is similar to DF(0)|V . -1.2ptDF(0) | |_V, so they have the same spectrum and therefore the same spectral radius. Since TcT_c is a homeomorphism, Lyapunov stability, attraction, and instability are preserved under this change of coordinates (see, e.g., Section 3 Kuznetsov et al. (2026)). Therefore, by Proposition D.1, the fixed point 0 is asymptotically stable relative to V when ρ(DF(0)|V)<1ρ ( . -1.2ptDF(0) | |_V )<1, and unstable relative to V when ρ(DF(0)|V)>1ρ ( . -1.2ptDF(0) | |_V )>1. ∎ We note that Theorem D.1 does not imply instability in the presence of constraint sets (only instability in x+Vx+V). Since our problem is inherently constrained, instability must be transferred to the constraint set itself. For a fixed point Z∈~(Φm|Δ^)Z∈ Z( . -1.2pt _m | |_ ) with supports Sx,SyS_x,S_y, define the face ℱZ:=[z1,z2,z3,z4]∈Δ^:supp(z1)⊆Sxsupp(z3)⊆Sxsupp(z2)⊆Sysupp(z4)⊆Sy F_Z:= \[z_1,z_2,z_3,z_4]∈ : cases *supp(z_1) S_x\\ *supp(z_3) S_x cases\ cases *supp(z_2) S_y\\ *supp(z_4) S_y cases \ and the face-tangent (lineality) subspace LZ∥:=h=[h1,h2,h3,h4]∈L:hk,i=0for i∉Sx(k=1,3),and j∉Sy(k=2,4).L _Z:=\\,h=[h_1,h_2,h_3,h_4]∈ L:\ h_k,i=0\ for i∉ S_x\,(k=1,3),\ and j∉ S_y\,(k=2,4)\,\\,. Note that Z∈relintℱZ F_Z. Lemma D.5 (Ambient invariance of the face-tangent affine space). There exists a δ>0δ>0 with Z+(LZ∥∩Bδ(0))⊆ΦmZ+(L _Z∩ B_δ(0)) D_ _m and Φm(Z+(LZ∥∩Bδ(0)))⊆Z+LZ∥. _m (Z+(L _Z∩ B_δ(0)) ) Z+L _Z. Consequently JΦm(Z)LZ∥⊆LZ∥J_ _m(Z)\,L _Z L _Z and D(Φm|Z+LZ∥)(Z)=JΦm(Z)|LZ∥D ( . -1.2pt _m | |_Z+L _Z )(Z)= . -1.2ptJ_ _m(Z) | |_L _Z. Proof. Choose δ>0δ>0 small enough that, for every h∈LZ∥∩Bδ(0)h∈L _Z∩ B_δ(0), all on-support coordinates of Z+hZ+h are positive. Since h∈LZ∥h∈L _Z, the off-support coordinates of Z+hZ+h are zero, and the four block sums are still equal to 11. Thus Z+h∈ΦmZ+h∈ D_ _m for δ small enough. Let U:=Z+hU:=Z+h. By Proposition A.1, the first two blocks of Φm(U) _m(U) have no mass outside SxS_x and SyS_y, respectively. The last two blocks of Φm(U) _m(U) are the first two blocks of U, and hence are also supported on SxS_x and SyS_y. Moreover, the first two blocks are normalized by PdxP_d_x and PdyP_d_y, while the last two blocks already have coordinate sum 11. Hence, all four blocks of Φm(U) _m(U) have the same support constraints and affine-sum constraints as Z+LZ∥Z+L _Z. Therefore Φm(Z+(LZ∥∩Bδ(0)))⊆Z+LZ∥. _m (Z+(L _Z∩ B_δ(0)) ) Z+L _Z. The final assertion follows from Lemma D.4 applied with x=Zx=Z, V=LZ∥V=L _Z, and f=Φmf= _m. ∎ Theorem D.2 (Constrained instability of optEW). Let Z∈Δ^Z∈ be a fixed point of Φm _m. If ρ(JΦm(Z)|L)>1ρ (J_ _m(Z)|_L )>1, then Z is not stable for Φm|Δ . -1.2pt _m | |_ . Proof. By Theorem 4.2, the nonzero spectrum of JΦm(Z)|LJ_ _m(Z)|_L is W∪Qm−1(eig(ηxηyMx(Z)|Lx))W∪ Q_m^-1 (eig ( _x _yM_x(Z)|_L_x ) ) if nx⩾nyn_x n_y and by Remark 4.1, we have the analogous identity with My(Z)|LyM_y(Z)|_L_y if ny⩾nxn_y n_x. Since the proof in the second case follows the same argument, we assume without loss of generality that nx⩾nyn_x n_y. In this case, ρ(JΦm(Z)|L)>1ρ (J_ _m(Z)|_L )>1 forces (a) some ∈Ww∈ W with >1w>1, or (b) some μ∈eig(ηxηyMx(Z)|Lx)μ ( _x _yM_x(Z)|_L_x ) with a preimage λ∈Qm−1(μ)λ∈ Q_m^-1(μ), |λ|>1|λ|>1. We treat the two cases separately. (a) Off-support instability. Suppose first that 1,i>1w_1,i>1 for some i∉Sxi∉ S_x. Then (Ay)i>vx=(Ay)jfor every j∈Sx.(Ay)_i>v_x=(Ay)_j every j∈ S_x. Fix such a j∈Sxj∈ S_x. We apply Lemma B.1, case (I), to the fixed point Z=[x,y,x,y].Z=[x,y,x,y]. Now perturb Z by giving the off-support coordinate i a small positive mass. For ε>0 >0, let xε:=(1−ε)x+εeix :=(1- )x+ e_i and define Z0ε:=(xε,y,xε,y).Z _0:=(x ,y,x ,y). Note that this perturbation ensures that [xt]i>0[x_t]_i>0. This allows us to apply Lemma B.1. Hence there exist constants δ>0δ>0, ϵ0>0 _0>0, and τ>0τ>0 such that any orbit satisfying ‖Zt−Z‖<δ\|Z_t-Z\|<δ also satisfies the exponential growth, while every point Z′∈Δ^Z ∈ with ‖Z′−Z‖<δ\|Z -Z\|<δ satisfies the ratio bound. Then Z0ε∈Δ^Z _0∈ , ‖Z0ε−Z‖=O(ε),\|Z _0-Z\|=O( ), and R0=xiεxjε>0.R_0= x _ix _j>0. By Proposition A.1, coordinates i and j remain positive along the orbit, so RtR_t is well defined for all t. Assume for contradiction that the orbit initialized at Z0εZ _0 remains in Bδ(Z)B_δ(Z) for all t⩾0t 0. Then Lemma B.1 gives Rt⩾eϵ0tR0.R_t e _0tR_0\,. Since R0>0R_0>0, this implies Rt→+∞R_t→+∞. On the other hand, since the orbit remains in Bδ(Z)B_δ(Z), the bounded-ratio part of the same lemma gives Rt<τfor all t⩾0,R_t<τ all t 0, a contradiction. Therefore, the orbit initialized at Z0εZ _0 must leave Bδ(Z)B_δ(Z). Since Z0ε→Z _0→ Z as ε↓0 0, we have constructed arbitrarily small perturbations of Z whose orbits leave the fixed neighbourhood Bδ(Z)B_δ(Z). Hence Z is not stable. The case 2,k>1w_2,k>1 for some k∉Syk∉ S_y is identical, using Lemma B.1, case (I). (b) Support (in-face) instability. Here the unstable eigenvector lies in (LZ∥)ℂ(L _Z)_ C (it is supported on Sx,SyS_x,S_y; Lemma D.2, Case 3), and ρ(JΦm(Z)|LZ∥)>1ρ (J_ _m(Z)|_L _Z )>1. By Lemma D.5, Φm _m maps a (ambient) neighbourhood of Z in Z+LZ∥Z+L _Z into Z+LZ∥Z+L _Z and JΦm(Z)|LZ∥ . -1.2ptJ_ _m(Z) | |_L _Z is the corresponding differential, so Theorem D.1 applies with V=LZ∥V=L _Z. Hence, Z is unstable relative to Z+LZ∥Z+L _Z. Because Z∈relintℱZ F_Z, a relative neighbourhood of Z in Z+LZ∥Z+L _Z is contained in ℱZ⊆Δ F_Z ; instability relative to Z+LZ∥Z+L _Z therefore gives instability relative to Δ . ∎ Lemma D.6 (Invariance by Φm _m of the local space). For any fixed point Z, there exists δ>0δ>0 such that Φm(Z+(L∩Bδ(0)))⊆Z+L _m (Z+(L∩ B_δ(0)) ) Z+L. Proof. Let Z=[x,y,x,y]Z=[x,y,x,y] and H=[h1,h2,h3,h4]∈LH=[h_1,h_2,h_3,h_4]∈ L. We use the block structure of the operator Φm=[(Φm)1,(Φm)2,(Φm)3,(Φm)4] _m=[( _m)_1,( _m)_2,( _m)_3,( _m)_4], where (Φm)k:ℝ2(dx+dy)→ℝdx( _m)_k: R^2(d_x+d_y)→ R^d_x for k=1,3k=1,3 and (Φm)k:ℝ2(dx+dy)→ℝdy( _m)_k: R^2(d_x+d_y)→ R^d_y for k=2,4k=2,4. Since (x⊙Exp(ηxAy))⊤>0and(y⊙Exp(ηyBx))⊤>0, (x ( _xAy) ) 1>0 (y ( _yBx) ) 1>0, continuity implies that there exists δ>0δ>0 such that for every H∈L∩Bδ(0)H∈ L∩ B_δ(0) the first two coordinates of Φm(Z+H) _m(Z+H) are well-defined. By definition of the projections PdxP_d_x and PdyP_d_y, we then have (Φm)1(Z+H)⊤=1and(Φm)2(Z+H)⊤=1.( _m)_1(Z+H) 1=1 ( _m)_2(Z+H) 1=1. Moreover, the last two coordinates of Φm _m are just copies of the first two coordinates of the input, so (Φm)3(Z+H)=x+h1and(Φm)4(Z+H)=y+h2.( _m)_3(Z+H)=x+h_1 ( _m)_4(Z+H)=y+h_2. Since H∈LH∈ L, we have h1⊤=h2⊤=0h_1 1=h_2 1=0, hence (Φm)3(Z+H)⊤=(x+h1)⊤=1and(Φm)4(Z+H)⊤=(y+h2)⊤=1.( _m)_3(Z+H) 1=(x+h_1) 1=1 ( _m)_4(Z+H) 1=(y+h_2) 1=1. Therefore all four blocks of Φm(Z+H) _m(Z+H) satisfy the affine constraints defining Z+LZ+L, so Φm(Z+H)∈Z+L _m(Z+H)∈ Z+L for every H∈L∩BδH∈ L∩ B_δ. ∎ We are now ready to prove Theorem 4.1. Proof of Theorem 4.1. By Lemma D.6, there exists δ>0δ>0 such that Φm(Z+(L∩Bδ(0)))⊂Z+L. _m (Z+(L∩ B_δ(0)) )⊂ Z+L. Applying Lemma D.4 with x=Zx=Z, V=LV=L, and f=Φmf= _m, we obtain DΦm(Z)L⊂LandD(Φm|(Z+L)∩Φm)(Z)=DΦm(Z)|L.D _m(Z)L⊂ L D ( _m|_(Z+L)∩ D_ _m )(Z)=D _m(Z)|_L. This proves the first claim. Assume first that ρ(JΦm(Z)|L)<1ρ (J_ _m(Z)|_L )<1. Applying Theorem D.1 with V=LV=L, x=Zx=Z, and F=ΦmF= _m shows that Z is asymptotically stable relative to Z+LZ+L. Since Δ^⊂Z+L ⊂ Z+L, this implies that Z is asymptotically stable for Φm|Δ _m|_ . Assume now that ρ(JΦm(Z)|L)>1ρ (J_ _m(Z)|_L )>1. Applying Theorem D.2 gives the result. ∎ Appendix E Proofs of Section 4.4 E.1 Proof of Corollary 4.1 Proof. For a mixed equilibrium, dim(Lx)⩾1 (L_x) 1, hence eig(Mx(Z)|Lx)≠∅eig ( . -1.2ptM_x(Z) | |_L_x )≠ . Furthermore, since Mx(Z)|Lx . -1.2ptM_x(Z) | |_L_x is non-singular, 0∉eig(Mx(Z)|Lx)0 ( . -1.2ptM_x(Z) | |_L_x ). Hence, there exists a μ∈eig(Mx(Z)|Lx)μ ( . -1.2ptM_x(Z) | |_L_x ) with μ≠0μ≠ 0. Solving Qm(λ)=μQ_m(λ)=μ reduces to finding the roots of the polynomials p+(λ)=λ2−(1+(m+1)s)λ+ms,p−(λ)=λ2−(1−(m+1)s)λ−ms, casesp_+(λ)&=λ^2-(1+(m+1)s)λ+ms\,,\\ p_-(λ)&=λ^2-(1-(m+1)s)λ-ms\,, cases where s2=μs^2=μ. We will show that not all roots can simultaneously lie in the closed unit disk ¯ D. To simplify notation, let a+:=(1+(m+1)s)a_+:=(1+(m+1)s) and b+:=msb_+:=ms, similarly a−:=(1−(m+1)s)a_-:=(1-(m+1)s) and b−:=−msb_-:=-ms. Assume, for contradiction, that all roots lie in ¯ D. By the Schur–Cohn criterion for quadratic polynomials (cf. Lemma E.1), |a+−a¯+b+|⩽1−|b+|2 |a_+- a_+b_+ | 1- |b_+ |^2 and |a−a¯−b−|⩽1−|b−|2 |a_-- a_-b_- | 1- |b_- |^2. Hence |1+s−m(m+1)|s|2|⩽1−m2|s|2,|1−s−m(m+1)|s|2|⩽1−m2|s|2. cases& |1+s-m(m+1) |s |^2 | 1-m^2 |s |^2\,,\\[4.30554pt] & |1-s-m(m+1) |s |^2 | 1-m^2 |s |^2\,. cases Squaring and adding gives |1+s−m(m+1)|s|2|2+|1−s−m(m+1)|s|2|2⩽2(1−m2|s|2)2. |1+s-m(m+1) |s |^2 |^2+ |1-s-m(m+1) |s |^2 |^2 2(1-m^2 |s |^2)^2\,. (15) Note that 1−m(m+1)|s|2∈ℝ1-m(m+1) |s |^2∈ R. Hence, we use that for r∈ℝr∈ R and c∈ℂc , |r+c|2+|r−c|2=2r2+r(c+c¯)−r(c+c¯)+2|c|2 |r+c |^2+ |r-c |^2=2r^2+r(c+ c)-r(c+ c)+2 |c |^2. Thus, (15) is equivalent to 2(1−m(m+1)|s|2)2+2|s|2⩽2(1−m2|s|2)2 2(1-m(m+1) |s |^2)^2+2 |s |^2 2(1-m^2 |s |^2)^2 ⇔ |s|2((1−2m)+m2(2m+1)|s|2)⩽0. |s |^2 ((1-2m)+m^2(2m+1) |s |^2 ) 0\,. However, since |s|2>0 |s |^2>0 and m∈(0,1/2]m∈(0,1/2], we have (1−2m)⩾0(1-2m) 0 and m2(2m+1)|s|2>0m^2(2m+1) |s |^2>0. Thus |s|2((1−2m)+m2(2m+1)|s|2)>0, |s |^2 ((1-2m)+m^2(2m+1) |s |^2 )>0\,, which gives a contradiction. Thus, there exists a λ∈Qm−1(μ)λ∈ Q_m^-1(μ), such that λ∉¯λ ∈ D and therefore |λ|>1 |λ |>1. Hence ρ(JΦm(Z)|L)>1ρ (J_ _m(Z)|_L )>1, and Theorem 4.1 gives the claim. ∎ We provide the (specialized version) of the Schur–Cohn criterion for the convenience of the reader. Lemma E.1 ( Schur–Cohn criterion). Consider a quadratic polynomial p(λ)=λ2−aλ+bp(λ)=λ^2-aλ+b with a,b∈ℂa,b . Then both roots lie in the open unit disk if and only if |b|<1and|a−a¯b|<1−|b|2. |b |<1 |a- ab |<1- |b |^2\,. If both roots lie in the closed unit disk, then |b|⩽1and|a−a¯b|⩽1−|b|2. |b | 1 |a- ab | 1- |b |^2\,. Proof. Denote the two roots by λ+,λ−. _+, _-. Then a=λ++λ−,b=λ+λ−.a= _++ _-, b= _+ _-. We first prove the necessary direction. Assume that both roots lie in the closed unit disk. Then |b|=|λ+λ−|⩽1. |b |= | _+ _- | 1. Moreover, a−a¯b a- ab =λ++λ−(λ¯++λ¯−)λ+λ− = _++ _--( λ_++ λ_-) _+ _- =λ+(1−|λ−|2)+λ−(1−|λ+|2). = _+(1- | _- |^2)+ _-(1- | _+ |^2). Thus, using the triangle inequality, |a−a¯b| |a- ab | ⩽|λ+|(1−|λ−|2)+|λ−|(1−|λ+|2). | _+ |(1- | _- |^2)+ | _- |(1- | _+ |^2). Writing r=|λ+|r= | _+ | and s=|λ−|s= | _- |, we have 1−r2s2−r(1−s2)−s(1−r2)=(1−r)(1−s)(1+r+s+rs)⩾0. 1-r^2s^2-r(1-s^2)-s(1-r^2)=(1-r)(1-s)(1+r+s+rs) 0. Hence |a−a¯b|⩽1−r2s2=1−|b|2. |a- ab | 1-r^2s^2=1- |b |^2. For the sufficient direction, assume |b|<1and|a−a¯b|<1−|b|2. |b |<1 |a- ab |<1- |b |^2. Suppose, for contradiction, that at least one root does not lie in the open unit disk. Without loss of generality, let r=|λ+|⩾1,s=|λ−|.r= | _+ | 1, s= | _- |. Since |b|=rs<1 |b |=rs<1, we have s<1s<1. Using the same identity as above and the reverse triangle inequality, |a−a¯b| |a- ab | =|λ+(1−s2)+λ−(1−r2)| = | _+(1-s^2)+ _-(1-r^2) | ⩾r(1−s2)−s(r2−1) r(1-s^2)-s(r^2-1) =(r+s)(1−rs). =(r+s)(1-rs). Since r⩾1r 1 and s<1s<1, r+s−(1+rs)=(r−1)(1−s)⩾0.r+s-(1+rs)=(r-1)(1-s) 0. Therefore |a−a¯b|⩾(r+s)(1−rs)⩾(1+rs)(1−rs)=1−r2s2=1−|b|2, |a- ab | (r+s)(1-rs) (1+rs)(1-rs)=1-r^2s^2=1- |b |^2, which contradicts the assumed strict inequality. Hence, both roots must lie in the open unit disk. ∎ E.2 Technical Results for the Proofs of Theorem 4.4 and Theorem 4.3 To show Theorem 4.4 and Theorem 4.3, we need the following technical results. For convenience, define σ:=ηxηyρ(Mx(Z)|Lx)σ:= _x _yρ (M_x(Z)|_L_x ), and denote σ⋆(m):=2m−1m2(2m+1)σ (m):= 2m-1m^2(2m+1). Define the polynomial in λ∈ℂ∖m/(m+1)λ \m/(m+1)\ with coefficients σ,m∈ℝσ,m∈ R: Pσ,m(λ):=λ2(1−λ)2+σ((m+1)λ−m)2. P_σ,m(λ):=λ^2(1-λ)^2+σ((m+1)λ-m)^2\,. (16) Note that λ is a root of Pσ,mP_σ,m if and only if Qm(λ)=−σQ_m(λ)=-σ. Using the continuity of the roots of a polynomial with respect to its coefficients, we will show that 1. the roots cross the boundaries of the unit disk at σ=0σ=0 and σ=σ⋆(m)σ=σ (m) (see Lemma E.3); and 2. the roots lie in the unit disk for σ∈(0,σ⋆(m))σ∈(0,σ (m)) and outside or on the boundary otherwise (see Lemma E.4). See Figure 10 for illustration. Figure 10: Illustration of the proof of Lemma E.3 and Lemma E.4. The double roots for σ=0σ=0 are marked with a white circle, and the roots for σ=σ⋆(m)σ=σ (m) with a red star. Technical Details: Lemma E.2. The multi-set of roots λ∈ℂ∖m/(m+1)λ \m/(m+1)\ of Pσ,m(λ)P_σ,m(λ) depends continuously on σ. Proof. This follows from the continuity of a polynomial’s roots with respect to its coefficients. ∎ To understand the existence of a root with modulus strictly less than or greater than 11, i.e., when there exists a λ inside or outside the unit circle, we need to understand when the roots pass through the boundary of the unit circle. Lemma E.3. Let Qm(λ)=−σQ_m(λ)=-σ where σ∈ℝ+σ∈ R_+. Suppose m≠12m≠ 12 and |λ|=1 |λ |=1. Then σ∈σ⋆(m),0σ∈ \σ (m),0 \. Further, if m>12m> 12 and σ=σ⋆(m)σ=σ (m), then there exists a root λ with |λ|=1 |λ |=1. Proof. First note that Qm(λ)Q_m(λ) must be in ℝ R by assumption. Since |λ|=1 |λ |=1 we write λ=eiθλ=e^iθ and for easier notation define cm:=2m+1c_m:=2m+1. By Euler’s identity, eiθ−1=eiθ2(2isin(θ/2))e^iθ-1=e^i θ2(2i (θ/2)) and (m+1)eiθ/2−me−iθ/2=cos(θ/2)+icmsin(θ/2)(m+1)e^iθ/2-me^-iθ/2= (θ/2)+ic_m (θ/2). Hence, using trigonometric identities, we find that Qm(eiθ)Q_m(e^iθ) is equal to −4sin2(θ2)e2iθ(cos(θ2)+icmsin(θ2))2 - 4 ^2 ( θ2 )e^2iθ ( ( θ2 )+ic_m ( θ2 ) )^2 =(1)−4sin2(θ2)cos2(θ2)((1+itan(θ2))21+icmtan(θ2))2 (1)=-4 ^2 ( θ2 ) ^2 ( θ2 ) ( (1+i ( θ2 ) )^21+ic_m ( θ2 ) )^2 =−4sin2(θ2)cos2(θ2)(1−tan2(θ2)+2cmtan2(θ2)1+cm2tan2(θ2)⏟:=ξ+itan(θ2)(cmtan2(θ2)+2−cm)1+cm2tan2(θ2)⏟=:ρ)2. =-4 ^2 ( θ2 ) ^2 ( θ2 ) ( 1- ^2 ( θ2 )+2c_m ^2 ( θ2 )1+c_m^2 ^2 ( θ2 )_:=ξ+i ( θ2 ) (c_m ^2 ( θ2 )+2-c_m )1+c_m^2 ^2 ( θ2 )_=:ρ )^2\,. Since tan(π/2) (π/2) is undefined, the equality in (1)(1) is invalid if θ=πθ=π, that is λ=−1λ=-1. However, we note that Qm(−1)=4(2m+1)2>0Q_m(-1)= 4(2m+1)^2>0, hence, this case is excluded by the assumption that Qm(λ)Q_m(λ) is negative. Since Qm(eiθ)=Qm(λ)Q_m(e^iθ)=Q_m(λ) must be real, ρξρξ must be zero. Since 1−tan2(θ2)+2cmtan2(θ2)=1+(4m+1)tan2(θ2)>0,1- ^2 ( θ2 )+2c_m ^2 ( θ2 )=1+(4m+1) ^2 ( θ2 )>0\,, ρ must be zero. This implies that one of the following conditions must hold: (1)θ=0 or, (2)tan2(θ2)=cm−2cm. (1) θ=0 or, (2) ^2 ( θ2 )= c_m-2c_m\,. In Case (1)(1), Qm(ei0)=0Q_m(e^i0)=0, hence σ=0σ=0, and in Case (2), we simplify Qm(eiθ)=−2m−1m2(2m+1)Q_m(e^iθ)=- 2m-1m^2(2m+1) which implies that σ=σ⋆(m)σ=σ (m). It remains to show that for m>12m> 12, σ=σ⋆(m)σ=σ (m) is attained by a root on the unit circle. Choose θ:=2arctan(cm−2cm),λ:=eiθ.θ:=2 ( c_m-2c_m ), λ:=e^iθ. Due to the assumption m>12m> 12, cm−2cm=2m−12m+1>0 c_m-2c_m= 2m-12m+1>0. Using σ∈ℝσ∈ R, hence ρ=0ρ=0, by the same computations as before, Qm(λ)=−4(cm−2)cm(cm−1)2=−2m−1m2(2m+1)=−σ⋆(m)Q_m(λ)=- 4(c_m-2)c_m(c_m-1)^2=- 2m-1m^2(2m+1)=-σ (m)\, and |λ|=1 |λ |=1. ∎ Lemma E.4. If m>1/2m>1/2 and 1. σ∈(0,σ⋆(m))σ∈ (0,σ (m) ), then every root of Pσ,m(λ)P_σ,m(λ) satisfies that the modulus is bounded as |λ|<1 |λ |<1; 2. σ=σ⋆(m)σ=σ (m), then at least one root of Pσ,m(λ)P_σ,m(λ) lies exactly on the boundary of the unit circle, i.e., |λ|=1 |λ |=1; 3. σ>σ⋆(m)σ>σ (m), then at least one root of Pσ,m(λ)P_σ,m(λ) lies outside the unit circle, i.e., |λ|>1 |λ |>1; If m⩽1/2m 1/2 and σ⩾0σ 0, at least one root of Pσ,m(λ)P_σ,m(λ) has modulus greater than or equal to 11. Note that this technical lemma does not require any assumption on the game. Proof. Let s=σs= σ. If σ=0σ=0, then P0,m(λ)=λ2(1−λ)2,P_0,m(λ)=λ^2(1-λ)^2, so the roots are 0,0,1,10,0,1,1. Assume now that σ>0σ>0. We factor Pσ,m(λ)=∏δ∈−1,1(λ(1−λ)+δis((m+1)λ−m)).P_σ,m(λ)= _δ∈\-1,1\ (λ(1-λ)+δ is((m+1)λ-m) ). Equivalently, Pσ,m(λ)=∏δ∈−1,1pδ(λ),P_σ,m(λ)= _δ∈\-1,1\p_δ(λ), where pδ(λ)=λ2−aδλ+bδ,aδ=1+δi(m+1)s,bδ=δims.p_δ(λ)=λ^2-a_δλ+b_δ, a_δ=1+δ i(m+1)s, b_δ=δ ims. For each δ, |bδ|2=m2σ, |b_δ |^2=m^2σ, and aδ−a¯δbδ=1−m(m+1)σ+δiσ.a_δ- a_δb_δ=1-m(m+1)σ+δ i σ. Hence |aδ−a¯δbδ|2=(1−m(m+1)σ)2+σ, |a_δ- a_δb_δ |^2=(1-m(m+1)σ)^2+σ, and therefore (1−|bδ|2)2−|aδ−a¯δbδ|2=σ((2m−1)−m2(2m+1)σ). (1- |b_δ |^2)^2- |a_δ- a_δb_δ |^2=σ ((2m-1)-m^2(2m+1)σ ). (17) Suppose first that m>1/2m>1/2 and 0<σ<σ⋆(m)=2m−1m2(2m+1).0<σ<σ (m)= 2m-1m^2(2m+1). Then the right-hand side of (17) is positive. Moreover, m2σ<m2σ⋆(m)=2m−12m+1<1.m^2σ<m^2σ (m)= 2m-12m+1<1. Thus, for both δ=±1δ=± 1, |bδ|<1and|aδ−a¯δbδ|<1−|bδ|2. |b_δ |<1 |a_δ- a_δb_δ |<1- |b_δ |^2. By Lemma E.1, both roots of each quadratic factor pδp_δ lie in the open unit disk. Hence every root of Pσ,mP_σ,m satisfies |λ|<1 |λ |<1. Next let m>1/2m>1/2 and σ=σ⋆(m)σ=σ (m). By the unit-circle calculation in Lemma E.3, choosing θ=2arctan2m−12m+1,λ=eiθ,θ=2 2m-12m+1, λ=e^iθ, gives Qm(λ)=−2m−1m2(2m+1)=−σ⋆(m).Q_m(λ)=- 2m-1m^2(2m+1)=-σ (m). Equivalently, Pσ⋆(m),m(λ)=0P_σ (m),m(λ)=0, and by construction |λ|=1 |λ |=1. Thus at least one root lies on the unit circle. Now let m>1/2m>1/2 and σ>σ⋆(m)σ>σ (m). Suppose, for contradiction, that all roots of Pσ,mP_σ,m lie in the closed unit disk. Then the roots of each quadratic factor pδp_δ lie in the closed unit disk. By the necessary part of Lemma E.1, |aδ−a¯δbδ|⩽1−|bδ|2. |a_δ- a_δb_δ | 1- |b_δ |^2. Squaring gives (1−|bδ|2)2−|aδ−a¯δbδ|2⩾0.(1- |b_δ |^2)^2- |a_δ- a_δb_δ |^2 0. This contradicts (17), whose right-hand side is negative when σ>σ⋆(m)σ>σ (m). Hence, at least one root satisfies |λ|>1 |λ |>1. Finally, suppose that m⩽1/2m 1/2. If σ=0σ=0, then λ=1λ=1 is a double root, so the desired conclusion holds. If σ>0σ>0 and all roots lay in the open unit disk, then Lemma E.1 applied to each pδp_δ would imply (1−|bδ|2)2−|aδ−a¯δbδ|2>0.(1- |b_δ |^2)^2- |a_δ- a_δb_δ |^2>0. But by (17), (1−|bδ|2)2−|aδ−a¯δbδ|2=σ((2m−1)−m2(2m+1)σ)<0(1- |b_δ |^2)^2- |a_δ- a_δb_δ |^2=σ ((2m-1)-m^2(2m+1)σ )<0 for every m⩽1/2m 1/2 and every σ>0σ>0. This contradiction shows that not all roots lie in the open unit disk. Therefore, at least one root satisfies |λ|⩾1 |λ | 1. ∎ Lemma E.5. Consider a zero-sum game Γ(A,−A⊤) (A,-A ) and assume the Nash equilibrium is unique and fully mixed. Then Mx(Z⋆)|Lx . -1.2ptM_x(Z ) | |_L_x is non-singular. Proof. Write Z⋆=[x⋆,y⋆,x⋆,y⋆]Z =[x ,y ,x ,y ]. Since the equilibrium is fully mixed, Mx(Z⋆)|Lx=−H(x⋆)AH(y⋆)A⊤. . -1.2ptM_x(Z ) | |_L_x=-H(x )AH(y )A . Write Hx:=H(x⋆)H_x:=H(x ) and Hy:=H(y⋆)H_y:=H(y ). Suppose, for contradiction, that Mx(Z⋆)|Lx . -1.2ptM_x(Z ) | |_L_x is singular. Then there exists 0≠h∈Lx0≠ h∈ L_x such that Mx(Z⋆)h=0⇔HxAHyA⊤h=0.M_x(Z )h=0 H_xAH_yA h=0\,. Thus, AHyA⊤h∈kerHxAH_yA h∈ H_x. But since kerHx=span(dx) H_x=span(1_d_x), there exists c∈ℝc∈ R such that AHyA⊤h=cdx.AH_yA h=c1_d_x. Taking the inner product with h, and using h∈Lxh∈ L_x, gives 0=ch⊤dx=h⊤AHyA⊤h=(A⊤h)⊤Hy(A⊤h).0=c\,h 1_d_x=h AH_yA h=(A h) H_y(A h). Since HyH_y is positive semidefinite with kernel span(dy)span(1_d_y), it follows that A⊤h∈span(dy).A h (1_d_y). Thus, for some c′∈ℝc ∈ R, A⊤h=c′dy.A h=c 1_d_y. Because h∈Lxh∈ L_x, we have dx⊤h=01_d_x h=0. Since x⋆∈relintΔdxx _d_x, for all sufficiently small ϵ≠0ε≠ 0, x(ϵ):=x⋆+ϵhx(ε):=x +ε h still belongs to relintΔdxrelint _d_x, and x(ϵ)≠x⋆x(ε)≠ x . We show that (x(ϵ),y⋆)(x(ε),y ) is again a Nash equilibrium: Since y⋆y is fully mixed at the zero-sum equilibrium, Ay⋆=vdxAy =v1_d_x for some v∈ℝv∈ R. Similarly, since x⋆x is fully mixed at equilibrium, A⊤x⋆=vdy.A x =v1_d_y. Using A⊤h=c′dyA h=c 1_d_y, we obtain A⊤x(ϵ)=A⊤x⋆+ϵA⊤h=(v+ϵc′)dy.A x(ε)=A x +ε A h=(v+ε c )1_d_y\,. Hence, x(ϵ)x(ε) is a best response to y⋆y and vice versa. Consequently (x(ϵ),y⋆)(x(ε),y ) is a fully mixed Nash equilibrium distinct from [x⋆,y⋆][x ,y ], contradicting uniqueness. Therefore, no such nonzero h∈Lxh∈ L_x exists, and Mx(Z⋆)|Lx . -1.2ptM_x(Z ) | |_L_x is non-singular. ∎ E.3 Proof of Theorem 4.3 Proof of Theorem 4.3. We show that the modulus of the eigenvalues of the Jacobian is strictly less than or strictly greater than one. This implies stability under the assumed step size conditions. Let Z⋆Z denote the unique Nash equilibrium and Mx(Z⋆)M_x(Z ) the matrix corresponding to it. We first note that Mx(Z⋆)M_x(Z ) has a real, non-positive spectrum. This is due to H(z1⋆)H(z_1 ) and AH(z2⋆)A⊤AH(z_2 )A being symmetric positive semidefinite, and the non-zero spectrum of H(z1⋆)AH(z2⋆)A⊤H(z_1 )AH(z_2 )A coincides with the non-zero spectrum of the symmetric positive semidefinite matrix H(z1⋆)12AH(z2⋆)A⊤H(z1⋆)12H(z_1 ) 12AH(z_2 )A H(z_1 ) 12. Thus, the spectrum of Mx(Z⋆)=−H(z1⋆)AH(z2⋆)A⊤M_x(Z )=-H(z_1 )AH(z_2 )A is real and non-positive. Furthermore, since Z⋆Z is by assumption full support, Mx(Z⋆)|Lx . -1.2ptM_x(Z ) | |_L_x is non-singular (cf. Lemma E.5). Hence, eig(Mx(Z⋆)|Lx)⊂(−∞,0)eig ( . -1.2ptM_x(Z ) | |_L_x )⊂(-∞,0). Since the entries in Mx(Z⋆)M_x(Z ) are finite, δ:=max(|λ|:λ∈eig(Mx(Z⋆)|Lx))δ:= ( |λ |:λ ( . -1.2ptM_x(Z ) | |_L_x )), is finite and eig(ηxηyMx(Z⋆)|Lx)⊂[−ηxηyδ,0)eig ( _x _y . -1.2ptM_x(Z ) | |_L_x )⊂[- _x _yδ,0). Hence, by Theorem 4.2, the spectrum of JΦm(Z⋆)|LJ_ _m(Z )|_L are either the values in W or the solutions to Qm(λ)=−σ∈(0,ηxηyδ].Q_m(λ)=-σ σ∈(0, _x _yδ]\,. Due to the assumption that the Nash equilibrium has full support, all values in W are strictly less than 11. Hence, we can ignore them for this proof. Under the assumption that m∈(1/2,1]m∈(1/2,1], the claim follows by noting that Qm(λ)=−σQ_m(λ)=-σ if and only if Pσ,m(λ)=0P_σ,m(λ)=0. Combining this with Lemma E.4 implies the claim. The case m∈(0,1/2]m∈(0,1/2], follows from Lemma E.5 and Corollary 4.1. ∎ E.4 Proof of Theorem 4.4 Proof of Theorem 4.4. Since the Nash equilibrium is, by assumption, fully supported, W=∅W= . In the 22-dimensional case, LxL_x is the one-dimensional space of vectors proportional to (−1,1)(-1,1). Moreover, H(x⋆)=p(1−p)[1−1−11],H(y⋆)=q(1−q)[1−1−11]H(x )=p(1-p) bmatrix -1&-1\\ -1& -1 bmatrix, H(y )=q(1-q) bmatrix -1&-1\\ -1& -1 bmatrix Let r=(1,−1)⊤r=(1,-1) . Then H(x⋆)=p(1−p)rr⊤H(x )=p(1-p)r and H(y⋆)=q(1−q)rr⊤H(y )=q(1-q)r . Hence Mx(Z⋆)=H(x⋆)AH(y⋆)B=p(1−p)q(1−q)rr⊤Arr⊤B.M_x(Z )=H(x )AH(y )B=p(1-p)q(1-q)\,r Arr B. Since r⊤Ar=ΔA,r⊤Br=ΔB,r Ar= _A, r Br= _B, we obtain Mx(Z⋆)=p(1−p)q(1−q)ΔA[e−gf−hg−eh−f].M_x(Z )=p(1-p)q(1-q) _A bmatrixe-g& -f-h\\ g-e& -h-f bmatrix. Restricting to Lx=span(−1,1)⊤L_x=span\(-1,1) \, eig(Mx(Z⋆)|Lx)=p(1−p)q(1−q)ΔAΔB.eig (M_x(Z )|_L_x )= \p(1-p)q(1-q) _A _B \. We write this eigenvalue as μ=p(1−p)q(1−q)ΔAΔB.μ=p(1-p)q(1-q) _A _B. Thus, the local criterion becomes Qm(λ)=ηxηyμ.Q_m(λ)= _x _y\,μ. If ΔAΔB>0 _A _B>0, then μ>0μ>0, and by Corollary 4.4, the mixed equilibrium is locally unstable for every ηxηy>0 _x _y>0, and every m. If ΔAΔB<0 _A _B<0 and m⩽12m 12, instability follows from Corollary 4.1. Note that in this case ηxηy>E _x _y>E for all strictly positive step sizes. Thus, assume ΔAΔB<0 _A _B<0 and m>12m> 12, then we have local stability if all solutions to Qm(λ)=−ηxηy|μ|,Q_m(λ)=- _x _y|μ|\,, are of modulus strictly less than 11. Applying Lemma E.4 and Theorem 4.2 gives that the full-support mixed equilibrium is locally asymptotically stable when ηxηy|μ|∈(0,σ⋆(m)). _x _y |μ |∈ (0,σ (m) )\,. When ηxηy|μ|>σ⋆(m) _x _y |μ |>σ (m), by Lemma E.4 (3) it is unstable. The degenerate case ΔAΔB=0 _A _B=0 gives μ=0μ=0 and therefore a unit eigenvalue; in this case, the linear criterion is inconclusive. ∎ E.5 Proof of Theorem 4.5 Proof of Theorem 4.5. We denote the ithi^th row of the matrices A,BA,B by Ai,:A_i,: and Bi,:B_i,:. Define MA=[A1,:−A2,:⋮A1,:−Adx,:⊤],MB=[B1,:−B2,:⋮B1,:−Bdy,:⊤]. M_A= bmatrixA_1,:-A_2,:\\ \\ A_1,:-A_d_x,:\\ 1 \\ bmatrix, M_B= bmatrixB_1,:-B_2,:\\ \\ B_1,:-B_d_y,:\\ 1 \\ bmatrix\,. Furthermore, we denote by MA(i)M_A^(i) (respectively MB(i)M_B^(i)) the matrix MAM_A where the ithi^th column is substituted by edxe_d_x (respectively edye_d_y). We first show the following: 1. det(MA)≠0 (M_A)≠ 0 and det(MB)≠0 (M_B)≠ 0; 2. Under the assumption that the Nash equilibrium is fully mixed and unique the Nash equilibrium is the solutions to the linear equations: MAy=edxM_Ay=e_d_x and MBx=edyM_Bx=e_d_y. Hence yi⋆=det(MA(i))det(MA) and xi⋆=det(MB(i))det(MB).y _i= (M_A^(i)) (M_A) and x _i= (M_B^(i)) (M_B)\,. Due to Theorem 2.1, [Ay⋆]1=[Ay⋆]i[Ay ]_1=[Ay ]_i for i∈2,…,dxi∈\2,…,d_x\ and y⋆∈Δdyy ∈ _d_y Equivalently, [Ay⋆]1−[Ay⋆]i=0 for i∈2,…,dx, and ∑i=1dyyi⋆=1.[Ay ]_1-[Ay ]_i=0 for i∈\2,…,d_x\, and _i=1^d_yy_i =1. By the definition of MAM_A, these equations are exactly MAy⋆=edx.M_Ay =e_d_x. Now, assume for contradiction that MAM_A is singular. Then MAz=0M_Az=0 has a non-zero solution and, due to the last row in MAM_A, ⟨z,⟩=0 z,1 =0. We define y^(α)=y⋆+αz y(α)=y +α z. Then MAy^(α)=MAy⋆+αMAz=edxM_A y(α)=M_Ay +α M_Az=e_d_x and for a sufficiently small α>0α>0, y^(α)∈Δdy y(α)∈ _d_y (recall y⋆∈relintΔdyy _d_y by assumption). Thus, [Ay^(α)]1=[Ay^(α)]i[A y(α)]_1=[A y(α)]_i for all i∈2,…,dxi∈\2,…,d_x\, that is, the payoff is constant. Conversely, Bx⋆Bx is constant by definition of x⋆x . Thus, [x⋆,y^(α)][x , y(α)] is a Nash equilibrium since x⋆∈Δdxx ∈ _d_x is a best response to y^(α) y(α) and vice versa. This contradicts the uniqueness of the Nash equilibrium. Applying Cramer’s rule gives xi⋆x _i and yi⋆y _i as closed-form solutions in the entries of the game matrices, and consequently, the linear operator Mx(Z⋆)|Lx . -1.2ptM_x(Z ) | |_L_x can be expressed in closed-form. So far, we do not require any assumptions on the dimensions besides dx=dyd_x=d_y. The claim follows from Theorem 4.2 combined with the observation that the characteristic polynomial of Mx(Z⋆)|Lx . -1.2ptM_x(Z ) | |_L_x has degree at most 44 and thus roots are expressible by radicals. ∎ Closed Form Spectrum Computation: For illustration of Theorem 4.5, we provide the closed-form formulas for the spectrum. Fix any real linear basis for LxL_x and write d:=dx=dyd:=d_x=d_y. Let N:=ηxηyMx(Z⋆)|Lx∈ℝ(d−1)×(d−1).N:= _x _y\,M_x(Z )|_L_x\ ∈\ R^(d-1)×(d-1)\,. By Theorem 4.2 the nonzero spectrum of JΦm(Z⋆)|LJ_ _m(Z )|_L equals Qm−1(eig(N))Q_m^-1 (eig (N ) ) since W=∅W= at a fully mixed equilibrium. It is convenient to read off eig(N)eig (N ) from the full d×d× d matrix M:=ηxηyH(x⋆)AH(y⋆)B∈ℝd×d.M:= _x _y\,H(x )\,A\,H(y )\,B\ ∈\ R^d× d. Since ⊤H(x⋆)=01 H(x )=0 we have ⊤M=01 M=0 and therefore 0∈eig(M)0 (M ). The remaining d−1d-1 eigenvalues of M are precisely eig(N)=1,…,d−1eig (N )=\ S_1,…, S_d-1\. In particular, the power sums are pj:=Tr(Mj)=∑i=1d−1ij(j⩾1),p_j:=Tr\! (M^j )= _i=1^d-1 S_i^\,j (j 1), and the characteristic polynomial of N is χN()=∏i=1d−1(−i)=∑j=0d−1(−1)jEjd−1−j,E0=1, _N( S)= _i=1^d-1( S- S_i)= _j=0^d-1(-1)^jE_j\, S^\,d-1-j, E_0=1, where, by Newton’s identities, E1= E_1= p1,E2=12(p12−p2),E3=16(p13−3p1p2+2p3), p_1, E_2= 12 (p_1^2-p_2 ), E_3= 16 (p_1^3-3p_1p_2+2p_3 ), E4=124(p14−6p12p2+3p22+8p1p3−6p4), E_4= 124 (p_1^4-6p_1^2p_2+3p_2^2+8p_1p_3-6p_4 ), and Ed−1=detNE_d-1= N. Each pjp_j is a trace of a product of H(x⋆),A,H(y⋆),BH(x ),A,H(y ),B, hence a polynomial in their entries; with the closed forms for x⋆,y⋆x ,y , every EjE_j is an explicit rational function of the entries of A and B. Eigenvalues of N We use that degχN=d−1⩽4 _N=d-1 4, hence the roots can be computed in closed form. • d=2d=2: Here N∈ℝ1×1N∈ R^1× 1. Thus, 1=E1=detN=TrM S_1=E_1= N=TrM. • d=3d=3: Set E2=detN=12((TrM)2−TrM2)E_2= N= 12 ((TrM)^2-TrM^2 ). Then 1,2=E1±E12−4E22 S_1,2= E_1± E_1^2-4E_22 • d=4d=4: We use Cardano’s method. The substitution =t+E13 S=t+ E_13 yields the depressed cubic t3+pt+qt^3+pt+q with p=E2−E123p=E_2- E_1^23, q=−2E1327+E1E23−E3q=- 2E_1^327+ E_1E_23-E_3. Set U3=−q2+q24+p327V3=−q2−q24+p327U^3=- q2+ q^24+ p^327 V^3=- q2- q^24+ p^327\, with UV=−p3UV=- p3. Then for k∈0,1,2k∈\0,1,2\ and ω=e2πi/3ω=e^2π i/3 k=E13+ωkU+ω2kV. S_k= E_13+ω^kU+ω^2kV\,. • d=5d=5: We use Ferrari’s method. Again, the substitution =t+E14 S=t+ E_14 yields the depressed quartic t4+pt2+qt+rt^4+pt^2+qt+r with p=E2−3E128,q=−E3+E1E22−E138,r=E4−E1E34+E12E216−3E14256.p=E_2- 3E_1^28, q=-E_3+ E_1E_22- E_1^38, r=E_4- E_1E_34+ E_1^2E_216- 3E_1^4256. If q=0q=0, the depressed quartic is biquadratic and its roots are t=±(−p±p2−4r)/2t=± (-p± p^2-4r)/2. Otherwise, the resolvent has a nonzero root since its value at 0 is −q2<0-q^2<0. Thus, let u be any non-zero root of the resolvent cubic 8u3+8pu2+(2p2−8r)u−q2=08u^3+8pu^2+(2p^2-8r)u-q^2=0 (solved by the case d=4d=4). Then t4+pt2+qt+rt^4+pt^2+qt+r factors as (t2−2ut+(p2+u+q22u))(t2+2ut+(p2+u−q22u)), (t^2- 2u\,t+ ( p2+u+ q2 2u ) ) (t^2+ 2u\,t+ ( p2+u- q2 2u ) ), and the four roots i=ti+E14 S_i=t_i+ E_14 follow from the quadratic formula. Assembling the Jacobian spectrum. As in the proof of Corollary 4.1, each i S_i contributes the (at most four) eigenvalues λ of JΦm(Z⋆)|LJ_ _m(Z )|_L solving Qm(λ)=iQ_m(λ)= S_i, i.e. the roots of p±(λ)=λ2−(1±(m+1)si)λ±msi,si2=i,p_±(λ)=λ^2- (1±(m+1)s_i )λ± m\,s_i, s_i^2= S_i, namely λ=(1±(m+1)si)±′(1±(m+1)si)2∓4msi2.λ= (1±(m+1)s_i )± (1±(m+1)s_i )^2∓ 4m\,s_i2. With W=∅W= , this gives the full spectrum of JΦm(Z⋆)J_ _m(Z ) in closed form in the entries of A and B. E.6 Details on Related Work Throughout this subsection, we keep the conventions of the main text: Γ(A,B) (A,B) with A∈ℝdx×dyA∈ R^d_x× d_y, B∈ℝdy×dxB∈ R^d_y× d_x, played over the unconstrained strategy spaces ℝdx R^d_x and ℝdy R^d_y. The general-sum bilinear games (x⊤A~y,x⊤B~y)(x Ay,x By), A~,B~∈ℝdx×dy A, B∈ R^d_x× d_y, of De Montbrun and Renault (2025) correspond to Γ(A,B) (A,B) via A~=A A=A and B~=B⊤ B=B ; their matrices B~⊤A~ B A and A~B~⊤ A B are BABA and ABAB in our notation, and their OGDA (Definition 3.1 in De Montbrun and Renault (2025)) is the OGM of Section 4.5 with ηx=ηy=η _x= _y=η. The OGM iteration is linear: writing Zt=(xt,yt,xt−1,yt−1)Z_t=(x_t,y_t,x_t-1,y_t-1), we have Zt+1=ΛA,BZtZ_t+1= _A,BZ_t with ΛA,B=[Idx2ηxA0−ηxA2ηyBIdy−ηyB0Idx0000Idy00]∈ℝ2(dx+dy)×2(dx+dy) _A,B= bmatrixI_d_x&2 _xA&0&- _xA\\ 2 _yB&I_d_y&- _yB&0\\ I_d_x&0&0&0\\ 0&I_d_y&0&0 bmatrix∈ R^2(d_x+d_y)× 2(d_x+d_y) (cf. Section 3.2 in De Montbrun and Renault (2025), where ηx=ηy _x= _y). The fixed points of the dynamics are exactly the lifted Nash equilibria [x,y,x,y][x,y,x,y] with [x,y]∈Ker(B)×Ker(A)[x,y]∈ *Ker(B)× *Ker(A). Let λ∈ℂλ and H=[h1,h2,h3,h4]≠0H=[h_1,h_2,h_3,h_4]≠ 0 with ΛA,BH=λH _A,BH=λ H. The last two block rows give h1=λh3h_1=λ h_3 and h2=λh4h_2=λ h_4; substituting into the first two rows yields λ(λ−1)h3=ηx(2λ−1)Ah4,λ(λ−1)h4=ηy(2λ−1)Bh3. λ(λ-1)\,h_3= _x(2λ-1)Ah_4\,, λ(λ-1)\,h_4= _y(2λ-1)Bh_3\,. (18) For λ=12λ= 12, (18) forces h3=h4=0h_3=h_4=0, hence H=0H=0. Thus, under the assumption that H≠0H≠ 0, 12 12 is never an eigenvalue. Combining these equations gives λ2(1−λ)2h4=(2λ−1)2ηxηyBAh4λ2(1−λ)2h3=(2λ−1)2ηxηyABh3, casesλ^2(1-λ)^2h_4=(2λ-1)^2 _x _y\,BA\,h_4\\ λ^2(1-λ)^2h_3=(2λ-1)^2 _x _y\,AB\,h_3\,, cases with [h3,h4]≠[0,0][h_3,h_4]≠[0,0]. Hence, for λ≠12λ≠ 12, λ2(1−λ)2ηxηy(2λ−1)2 λ^2(1-λ)^2 _x _y(2λ-1)^2 is an eigenvalue of BABA if h4≠0h_4≠ 0 or of ABAB if h3≠0h_3≠ 0. Conversely, following the proof of Proposition 3.7 in De Montbrun and Renault (2025) verbatim, with the only modification that the products ηxηy _x _y replace η2η^2 throughout, every such λ is an eigenvalue of ΛA,B _A,B. This gives eig(ΛA,B)=⋃μ∈eig(AB)∪eig(BA)^⋆(μ),^⋆(μ):=λ∈ℂ:λ2(1−λ)2=μηxηy(1−2λ)2.eig ( _A,B )= _μ \ (AB) \ (BA) S (μ)\,, S (μ):=\λ∈ C:λ^2(1-λ)^2=μ\, _x _y\,(1-2λ)^2\\,. We now prove Corollary 4.5. Since dx=dyd_x=d_y and eig(BA)⊂(−∞,0)eig\ (BA)⊂(-∞,0), the matrix BABA is non-singular, hence Ker(A)=Ker(B)=0 *Ker(A)= *Ker(B)=\0\ and the origin is the unique Nash equilibrium. Moreover, ABAB and BABA share their spectrum, so eig(AB)∪eig(BA)=eig(BA)eig\ (AB) \ (BA)=eig\ (BA). For μ∈eig(BA)μ \ (BA) write μ=−|μ|μ=- |μ |. Then λ∈^⋆(μ)λ∈ S (μ) if and only if Pσ,1(λ)=0P_σ,1(λ)=0 with σ=ηxηy|μ|>0σ= _x _y |μ |>0. If ηxηyρ(−BA)<13=σ⋆(1) _x _yρ (-BA )< 13=σ (1), Lemma E.4 (with m=1m=1) shows that every eigenvalue of ΛA,B _A,B has modulus strictly less than 11; since the dynamics are linear, the fixed point is (globally) asymptotically stable. If ηxηyρ(−BA)>13 _x _yρ (-BA )> 13, applying Lemma E.4 (3) to an eigenvalue μ with |μ|=ρ(BA) |μ |=ρ (BA ) produces λ∈eig(ΛA,B)λ ( _A,B ) with |λ|>1 |λ |>1, and the fixed point is unstable. Finally, we note why dx=dyd_x=d_y cannot be dropped: if, say, dx>dyd_x>d_y and eig(BA)⊂(−∞,0)eig\ (BA)⊂(-∞,0), then AB∈ℝdx×dxAB∈ R^d_x× d_x has rank at most dy<dxd_y<d_x, so 0∈eig(AB)0 \ (AB) and ^⋆(0)=0,1 S (0)=\0,1\ contributes the eigenvalue 11 to eig(ΛA,B)eig ( _A,B ); correspondingly Ker(B)≠0 *Ker(B)≠\0\, the Nash equilibria form a non-trivial subspace, and no single equilibrium is asymptotically stable. In this situation, Theorem 3.8 in De Montbrun and Renault (2025) still yields global exponential convergence to some Nash equilibrium under the assumptions eig(BA)∪eig(AB)⊂(−∞,0]eig\ (BA) \ (AB)⊂(-∞,0], ηxηyρ(−BA)<14 _x _yρ (-BA )< 14, and ΛA,B _A,B diagonalizable or A,BA,B are square matrices and invertible. The modification for ηx≠ηy _x≠ _y is again the substitution η2→ηxηyη^2→ _x _y in the spectral computation. Appendix F Special Games Matching Pennies Define the zero-sum game Γ(A,−A⊤) (A,-A ) with A=[1−1−11].A= bmatrix1&-1\\ -1&1 bmatrix\,. The unique Nash equilibrium is at the uniform distribution for both players. Applying Theorem 4.4 gives that ΔA=−ΔB=4 _A=- _B=4. Hence, the Nash equilibrium is asymptotically stable if ηxηy<2m−1m2(2m+1) _x _y< 2m-1m^2(2m+1). Non-Zero-Sum Matching Pennies Define a non-zero-sum game Γ(A,B) (A,B) with A=[−113−1]andB=[2−1−11].A= bmatrix-1& -1\\ -3&-1 bmatrix B= bmatrix -2&-1\\ -1& -1 bmatrix\,. The unique Nash equilibrium is at x⋆=[2/5,3/5]⊤x =[2/5,3/5] , y⋆=[1/3,2/3]⊤y =[1/3,2/3] . When applying Theorem 4.4 we observe that ΔA=−6 _A=-6 and ΔB=5 _B=5, hence the Nash equilibrium is asymptotically stable if ηxηy<582m−1m2(2m+1) _x _y< 58 2m-1m^2(2m+1). Rock-Paper-Scissors and Variants This is a zero-sum game Γ(A,−A⊤) (A,-A ) with A=[0a−1−101a1−10], A= bmatrix -0& -a&-1\\ -1& -0& - 1a\\ -1&-1& -0 bmatrix\,, and a>0a>0. The equilibrium is at x⋆=12a+1[1,a,a]⊤x = 12a+1[1,a,a] and y⋆=1a+2[1,1,a]⊤y = 1a+2[1,1,a] . A 4×44× 4 Game The following non-zero-sum game has a unique non-fully supported Nash equilibrium. A=[−65−671−1−910−7−7−1610−14−4]B=[7−262173−10−647−79−7−96]. A= bmatrix-6& -5&-6& -7\\ -1&-1&-9&10\\ -7&-7&-1& -6\\ 10&-1& -4&-4 bmatrix B= bmatrix -7&-2& -6& -2\\ -1& -7&3&-10\\ -6& -4& -7&-7\\ -9&-7&-9& -6 bmatrix\,. The Nash equilibrium is at x⋆=[0,4/9,0,5/9]⊤x =[0,4/9,0,5/9] and y⋆=[14/23,0,0,9/23]⊤y =[14/23,0,0,9/23] . References Bailey and Piliouras [2018] James P Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 321–338, 2018. Borkar [1997] Vivek S. Borkar. Stochastic approximation with two time scales. Systems & Control Letters, 29:291–294, 1997. Borkar [2025] Vivek S. Borkar. Stochastic approximation with two time scales: The general case. Stochastic Processes and their Applications, 190:104759, 2025. ISSN 0304-4149. doi: https://doi.org/10.1016/j.spa.2025.104759. Cesa-Bianchi and Lugosi [2006] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. Cheung and Piliouras [2019] Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory, pages 807–834. PMLR, 2019. Chiang et al. [2012] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages 6.1–6.20. JMLR Workshop and Conference Proceedings, 2012. Daskalakis and Panageas [2018] Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Neural Information Processing Systems, 2018. Daskalakis and Panageas [2019] Constantinos Daskalakis and Ioannis Panageas. Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:18, 2019. ISBN 978-3-95977-095-8. De Montbrun and Renault [2025] Etienne De Montbrun and Jerôme Renault. Optimistic gradient descent ascent in general-sum bilinear games. Journal of Dynamics and Games, 12(3):267–301, 2025. Falniowski and Mertikopoulos [2025] Fryderyk Falniowski and Panayotis Mertikopoulos. On the discrete-time origins of the replicator dynamics: from convergence to instability and chaos. International Journal of Game Theory, 54(1):7, Feb 2025. ISSN 1432-1270. doi: 10.1007/s00182-025-00929-3. Fiez and Ratliff [2021] Tanner Fiez and Lillian J Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In International Conference on Learning Representations, 2021. Giannou et al. [2021] Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, and Panayotis Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In Conference on Learning Theory, pages 2147–2148. PMLR, 2021. Hofbauer and Sigmund [1998] Josef Hofbauer and Karl Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998. Hong et al. [2023] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147–180, 2023. doi: 10.1137/20M1387341. Hsieh et al. [2019] Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. Advances in Neural Information Processing Systems, 32, 2019. Korpelevich [1976] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747–756, 1976. Kuznetsov et al. [2026] Yuri Kuznetsov, Odo Diekmann, and Wolf-Jürgen Beyn. Dynamical Systems Essentials: An Application Oriented Introduction to Ideas, Concepts, Examples, Methods, and Results. Springer Nature Switzerland, 2026. ISBN 9783032040831. doi: 10.1007/978-3-032-04083-1. Lei et al. [2021] Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In International Conference on Artificial Intelligence and Statistics, pages 1441–1449. PMLR, 2021. Lin et al. [2025] Tianyi Lin, Chi Jin, and Michael I Jordan. Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization. Journal of Machine Learning Research, 26(11):1–45, 2025. Mertikopoulos and Sandholm [2016] Panayotis Mertikopoulos and William H. Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 41(4):1297–1324, November 2016. ISSN 1526-5471. doi: 10.1287/moor.2016.0778. Mertikopoulos et al. [2018a] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv:1807.02629, 2018a. Mertikopoulos et al. [2018b] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pages 2703–2717. SIAM, 2018b. Munkres [2000] James R. Munkres. Topology. Prentice Hall, 2 edition, 2000. Pangallo et al. [2022] Marco Pangallo, James B.T. Sanders, Tobias Galla, and J. Doyne Farmer. Towards a taxonomy of learning dynamics in 2 × 2 games. Games and Economic Behavior, 132:1–21, March 2022. ISSN 0899-8256. doi: 10.1016/j.geb.2021.11.015. Popov [1980] L. D. Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845–848, Nov 1980. ISSN 1573-8876. doi: 10.1007/BF01141092. Rakhlin and Sridharan [2013] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2, NIPS’13, pages 3066–3074, 2013. Rapoport [1966] Anatol Rapoport. A taxonomy of 2x2 games. General Systems, 11:203–214, 1966. Sandholm [2010] William H. Sandholm. Local stability under evolutionary game dynamics. Theoretical Economics, 5(1):27–50, 2010. doi: https://doi.org/10.3982/TE505. Sayin and Cetiner [2022] Muhammed Sayin and Kemal Cetiner. On the heterogeneity of independent learning dynamics in zero-sum stochastic games. In Roya Firoozi, Negar Mehr, Esen Yel, Rika Antonova, Jeannette Bohg, Mac Schwager, and Mykel Kochenderfer, editors, Proceedings of The 4th Annual Learning for Dynamics and Control Conference, volume 168 of Proceedings of Machine Learning Research, pages 994–1005. PMLR, 23–24 Jun 2022. Syrgkanis et al. [2015] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015. Wei et al. [2021] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. published at ICLR’21, 2021. Weibull [1995] Joergen Weibull. Evolutionary Game Theory. MIT Press, London, UK, 1995. ISBN 0262231816.