No-regret learning and mixed Nash equilibria: They do not mix

Introduction

Regret minimization is one of the most fundamental requirements for online learning and decision-making in the presence of uncertainty and unpredictability . Defined as the difference between the cumulative performance of an adaptive policy and that of the best fixed action in hindsight, the regret of an agent provides a concise and meaningful benchmark for quantifying the ability of an online algorithm to adapt to an otherwise unknown and unpredictable environment.

Arguably, the most widely studied class of no-regret algorithms is the general algorithmic scheme known as follow the regularized leader (FTRL) . This umbrella learning framework includes as special cases the multiplicative weights update (MWU) and online gradient descent (OGD) algorithms , both of which achieve a min-max optimal $\operatorname{\mathcal{O}}(T^{1/2})$ regret guarantee. For obvious reasons, the ability of FTRL to adapt optimally to an unpredictable environment makes them ideal for applying them in multi-agent environments – i.e., games. In this case, if all agents adhere to a no-regret learning process based on FTRL (or one of its variants), as the sequence of play becomes more predictable, stronger regret guarantees are achievable, possibly down to constant regret, see e.g., and references therein. As such, several crucial questions arise:

What are the game-theoretic implications of the no-regret guarantees of FTRL? Do the dynamics of FTRL converge to an equilibrium of the underlying game?

A folk answer to this question is that “no-regret learning converges to equilibrium in all games” , suggesting in this way that no-regret dynamics inherently gravitate towards game-theoretically meaningful states. However, at this level of abstraction, both the type of convergence as well as the specific notion of equilibrium that go in this statement are not as strong as one would have hoped for. Formally, the only precise conclusion that can be drawn is as follows: under a no-regret learning procedure, the empirical frequency of play converges to the game’s set of coarse correlated equilibria .

This leads to an important disconnect with standard game-theoretic solution concepts on several grounds. First, even in $2$-player games, coarse correlated equilibria may be exclusively supported on strictly dominated strategies , so they fail even the most basic requirements of rationalizability . Second, the archetypal game-theoretic solution concept is that of Nash equilibrium (NE), and convergence to a Nash equilibrium is a much more tenuous affair: since no-regret dynamics are, by construction, uncoupled (in the sense that a player’s update rule does not explicitly depend on the payoffs of other players), the impossibility result of Hart & Mas-Colell precludes the convergence of no-regret learning to Nash equilibrium in all games. This is consistent with the numerous negative complexity results for finding a Nash equilibrium : an incremental method like FTRL simply cannot have enough power to overcome PPAD completeness and converge to Nash equilibrium given adversarially chosen initial conditions.

In view of the above, a natural test of whether the dynamics of FTRL favor convergence to a Nash equilibrium is to see whether they eventually stabilize and converge to it when initialized nearby. In more precise language, are Nash equilibria asymptotically stable in the dynamics of FTRL? And, perhaps more importantly, are all Nash equilibria created equal in this regard?

We establish a stark and robust dichotomy between how the dynamics of FTRL treat Nash equilibria in mixed (i.e., randomized) vs. pure strategies. For the case of mixed Nash equilibria we establish a sweeping negative result to the effect that the notion of mixed Nash equilibrium is antithetical to no-regret learning. More precisely, we show that any Nash equilibrium which is not strict (in the sense that every player has a unique best response) cannot be stable and attracting under the dynamics of FTRL. Schematically:

Informal Theorem: Asymptotically stable point for FTRL $\implies$ Pure Nash equilibrium

Equivalently: Mixed Nash equilibrium $\implies$ Not asymptotically stable under FTRL

The linchpin of our analysis is the following striking property of the FTRL dynamics: when viewed in the space of “payoffs” (their natural state space), they preserve volume irrespective of the underlying game. More precisely, the Lebesgue measure of any open set of initial conditions in the space of payoffs remains invariant as it is carried along the flow of the FTRL dynamics (cf. Fig. 2). Importantly, this result is not true in the problem’s “primal” space, i.e., the space of the player’s mixed strategies: here, sets of initial conditions can expand or contract indefinitely under the standard Euclidean volume form.

This duality between payoffs and strategies is the leitmotif of our approach and has a number of important consequences. First, exploiting the volume-preservation property of FTRL, we show that no interior Nash equilibrium (and, furthermore, no closed set in the interior of the strategy space) can be asymptotically stable under the dynamics of FTRL, as this effectively would necessitate volume contraction in the interior of the space (Theorem 1).

To move beyond this result and disqualify all non-strict Nash equilibria (not just interior ones) more intricate arguments are required. In this case, a fundamental distinction arises between classes of dynamics that may attain the boundary of the players’ strategy space in finite time versus those that do not. The first case concerns FTRL dynamics with an everywhere-differentiable regularizer, like the Euclidean regularizer that gives rise to OGD and the associated projection dynamics. The second concerns dynamics where the regularizer becomes steep at the boundary of the strategy simplex, e.g., like the Shannon-Gibbs entropy that gives rise to the multiplicative weights update (MWU) algorithm and the replicator dynamics. While the interior of the strategy simplex is invariant for the second class of dynamics, this is not the case for the former: in Euclidean-like cases, the support of the mixed strategy of an agent may change over time. This leads to an essential dichotomy in the boundary behavior of different classes of FTRL dynamics. Nonetheless, despite the qualitatively distinct long-run behavior of the dynamics, a unified message emerges: under the dynamics of FTRL, only strict Nash equilibria survive (Theorem 2).

Finally, for the case of steep, entropy-like regularizers we prove that not only their asymptotically stable points but much more generally any asypmptotically stable set must contain at least one pure strategy profile (Theorem 3).

Related work

The regret properties of FTRL have given rise to a vast corpus of literature which we cannot hope to review here; for an appetizer, we refer the reader to and references therein. On the other hand, the long-run behavior of FTRL in games (even finite ones) is nowhere near as well understood. A notable exception to this is the case of the replicator dynamics which have been studied extensively due to their origins and connection with evolutionary game theory, cf. for a review. For the replicator dynamics, a special instance of the volume preservation principle was first discovered by Akin and ultimately gave rise to the so-called “folk theorem” of evolutionary game theory:Interestingly, Akin’s result was established under a special non-Euclidean volume form on the game’s strategy space, a fact which made any attempts at generalization particularly elusive. in population games, the notions of strict Nash equilibrium and asymptotic stability coincide . This instability of mixed Nash equilibria plays a major role in the theory of population games as it shows that even the weakest form of mixing cannot be stable in an evolutionary sense. The volume preservation result that we establish here can be seen as a much more general “learning analogue” of this biological principle and provides an important link between population dynamics and the theory of online learning in games.

Recent work has examined the non-convergence of FTRL dynamics in more specialized settings. Coucheney et al. established a version of the folk theorem of evolutionary game theory for a subclass of “decomposable”, steep FTRL dynamics. By contrast, Mertikopoulos et al. focused on two-player zero-sum games (and networked versions thereof), and showed that almost all trajectories of FTRL orbit interior equilibria at a fixed distance without ever converging to equilibrium, generalizing the previous analysis for replicator dynamics by Piliouras & Shamma . This is an interior equilibrium avoidance result, but one that uniquely concerns zero-sum games. Although the above results apply for continuous-time dynamics, in discrete-time non-convergence results only become stronger. Bailey & Piliouras proved that discrete-time FTRL diverges away from the Nash equilibrium in zero-sum games, whereas Cheung & Piliouras established Lyapunov chaos (volume-expansion, butterfly effects). Understanding the detailed geometry of non-equilibrating FTRL dynamics, e.g., periodicity/chaos, is an interesting direction where volume analysis has found application . Non-convergence, recurrence results have recently been established for FTRL dynamics via volume analysis even outside normal form games, e.g., in non-convex non-concave min-max differential games and imperfect information zero-sum games . Finally, such instability, non-convergence results have inspired new, dynamics-based, solution concepts for games that generalize strict Nash while allowing cyclic, recurrent behavior .

In the converse direction, a complementary research thread has shown strict Nash equilibria are asymptotically stable under several incarnations of the FTRL dynamics . Our paper establishes the converse to this stability result, thus leading to the the following overarching principle (which covers all generic $N$-player games):

Asymptotic stability under FTRL $\iff$ Strict Nash equilibrium

This result has significant implications for predicting the outcome of a learning process as it shows unequivocally that its pointwise stable outcomes are precisely the strict (and hence, pure) Nash equilibria of the underlying game.

Preliminaries

The game

Given a mixed profile $x\in\mathcal{X}$, the corresponding expected payoff of player $i$ will be

To keep track of the payoffs of each individual action, we will also write

where, in standard notation, $\langle v,x\rangle=v^{\top}x$ denotes the ordinary pairing between $v$ and $x$.

In terms of solutions, the most widely used concept in game theory is that of a Nash equilibrium (NE), i.e., a state $x^{\ast}\in\mathcal{X}$ such that

Writing $\operatorname{supp}(x^{\ast}_{i})=\{\alpha_{i}\in\mathcal{A}_{i}:x^{\ast}_{i\alpha_{i}}>0\}$ for the support of $x^{\ast}_{i}$, Nash equilibria can be equivalently characterized via the variational inequality

In turn, this characterization leads to the following taxonomy:

$x^{\ast}$ is called pure if $\operatorname{supp}(x^{\ast})=\prod_{i}\operatorname{supp}(x^{\ast}_{i})$ is a singleton.

If $x^{\ast}$ is not pure, we say that it is mixed; and if $\operatorname{supp}(x^{\ast})=\mathcal{A}$, we say that it is fully mixed.

By definition, pure Nash equilibria are themselves pure strategies and correspond to vertices of $\mathcal{X}$; at the other end of the spectrum, fully mixed equilibria belong to the relative interior $\operatorname{ri}(\mathcal{X})$ of $\mathcal{X}$, so they are often referred to as interior equilibria.

Another key distinction between Nash equilibria concerns the defining inequality (NE): if this inequality is strict for all $x_{i}\neq x^{\ast}_{i}$, $i\in\mathcal{N}$, $x^{\ast}$ is called itself strict. Strict Nash equilibria are pure a fortiori, and they play a key role in game theory because any unilateral deviation incurs a strict loss to the deviating player; put differently, if $x^{\ast}$ is strict, every player has a unique best response. Taking this idea further, $x^{\ast}$ is called quasi-strict if (4) is strict for all $\alpha_{i}\in\mathcal{A}_{i}\setminus\operatorname{supp}(x^{\ast}_{i})$, i.e., if all best responses of player $i$ are contained in $\operatorname{supp}(x^{\ast}_{i})$. By a deep result of Ritzberger , all Nash equilibria are quasi-strict in almost all games;Specifically, on a set which is open and dense (and hence of full measure) in the space of all games. in view of this, we will tacitly assume in the sequel that all equilibria considered are quasi-strict, a property known as “genericity” .

We should stress here that quasi-strict equilibria need not be pure: they could be partially or even fully mixed, e.g., as in the case of Stag Hunt, Rock-Paper-Scissors, Matching Pennies, the Battle of the Sexes, etc. We provide a series of illustrative examples in the supplement.

Regret

A key requirement in online learning is the minimization of the players’ regret, i.e., the cumulative payoff difference between a player’s mixed strategy at a given time and the player’s best possible strategy in hindsight. In more detail, assuming that play evolves in continuous time $t\geq 0$, the (external) regret of a player $i\in\mathcal{N}$ relative to a sequence of play $x(t)\in\mathcal{X}$ is defined as

and we say that player $i$ has no regret under $x(t)$ if $\operatorname{Reg}_{i}(T)=o(T)$.

No-regret learning via regularization

The most widely used method to achieve no-regret is the class of policies known as follow the regularized leader (FTRL) . Heuristically, at each $t\geq 0$, FTRL prescribes a mixed strategy that maximizes the players’ cumulative payoff up to time $t$ minus a regularization penalty which incentivizes exploration. Formally, this is represented by the dynamics

In the above, each $y_{i\alpha_{i}}$ plays the role of an auxiliary “score variable” which measures the aggregate performance of the pure strategy $\alpha_{i}\in\mathcal{A}_{i}$ over time. These scores are subsequently tranformed to mixed strategies by means of a player-specific choice map $y_{i}\mapsto x_{i}=Q_{i}(y_{i})$ which is defined as

One of the most widely used regularizers in online learning is the (negative) Gibbs-Shannon entropy $h_{i}(x_{i})=\sum_{\alpha_{i}}x_{i\alpha_{i}}\log x_{i\alpha_{i}}$. A standard calculation then yields the so-called logit choice map, written in vectorized form as $\operatorname{\Lambda}_{i}(y_{i})={\exp(y_{i})}/{\sum_{\alpha_{i}\in\mathcal{A}_{i}}\exp(y_{i\alpha_{i}})}$. In turn, this leads to the exponential weights dynamics:

The system (EW) describes the mean dynamics of the so-called multiplicative weights update (MWU) algorithm (or “Hedge”); for an (incomplete) account of its long history, see and references therein.

Another popular choice of regularizer is the quadratic penalty $h_{i}(x_{i})=(1/2)\lVert x_{i}\rVert^{2}$. In this case, the associated choice map is the Euclidean projector on the simplex, $\operatorname{\Pi}_{i}(y_{i})=\operatorname*{arg\,min}_{x_{i}\in\mathcal{X}_{i}}\lVert y_{i}-x_{i}\rVert$, which gives rise to the Euclidean regularization dynamics

Beyond the two prototypical examples discussed above, the origin of the dynamics (FTRL) can be traced to Shalev-Shwartz & Singer , Nesterov , and, via their link to online mirror descent (OMD), all the way back to Nemirovski & Yudin . Describing the history and literature surrounding these dynamics would take us too far afield, so we do not attempt it.

The fundamental dichotomy of FTRL dynamics

To connect the long-run behavior of (FTRL) to the Nash equilibria of the underlying game, we must first understand how the players’ mixed strategies evolve under (FTRL). Our goal in this section is to provide some background to this question as a precursor to our analysis in Section 4. To lighten notation, we will drop in what follows the player index $i$, writing for example $x_{\alpha}$ instead of the more cumbersome $x_{i\alpha_{i}}$; we will only reinstate the index $i$ if absolutely necessary to avoid confusion.

To begin, we note that (FTRL) exhibits a unique duality: on the one hand, the variables of interest are the players’ mixed strategies $x(t)\in\mathcal{X}$; on the other, the dynamics (FTRL) evolve in the space $\mathcal{Y}$ of the players’ score variables $y(t)$. Mixed strategies are determined by the corresponding scores via the players’ choice maps $y\mapsto x=Q(y)$, but this is not a two-way street: as we explain below, the map $Q\colon\mathcal{Y}\to\mathcal{X}$ is not invertible, so obtaining an autonomous dynamical system on the strategy space $\mathcal{X}$ is a delicate affair. In the general case, invoking standard arguments from convex analysis we have $y(t)\in\nabla h(x(t))+\operatorname{PC}(x(t))$, where

denotes the polar cone to $\mathcal{X}$ at $x$.In particular, for all $y\in\operatorname{PC}(x)$, we have $y_{\alpha}=y_{\beta}$ whenever $\alpha,\beta\in\operatorname{supp}(x)$. The similarity of this condition to the characterization (4) of Nash equilibria is not a coincidence: $x^{\ast}$ is a Nash equilibrium of $\Gamma$ if and only if $v(x^{\ast})\in\operatorname{PC}(x^{\ast})$ .

On the other hand, in the Euclidean framework of Example 2.2, the choice map $Q=\operatorname{\Pi}$ can also return non-fully mixed strategies. Both Equation 7 and Fig. 1 show that on the boundary $\operatorname{PC}(x)$ is strictly larger compared to the interior. Thus $\operatorname{\Pi}$ is surjective but not injective, even modulo a subspace of $\mathcal{Y}$.

The key obstacle to mapping the dynamics (FTRL) to $\mathcal{X}$ is the lack of injectivity of $Q$. In turn, this allows us to make two key observations: (\edefnit\selectfonti ) there is an important split in behavior between boundary and interior states; and (\edefnit\selectfonti ) this split is linked to whether the underlying choice map is surjective or not. We elaborate on this below.

2. The steep/non-steep dichotomy

The lack of injectivity of $\operatorname{\Lambda}$ on $\operatorname{ri}(\mathcal{X})$ is a technical artifact of the sum-to-one constraints of the strategy probabilities: knowing all but one of the strategy probabilities we can easily recover the remaining one. Thus the $\mathcal{Y}$ space, having the same number of coordinates as the $\mathcal{X}$ space, also contains redundant information. With an appropriate projection we can remove this redundancy and restore injectivity in the interior, deriving the dynamics of $x(t)$ on $\mathcal{X}$. Making this argument precise for the entropic case of Example 2.1, we obtain the replicator dynamics:

On the other hand, this is not enough for the Euclidean framework of Example 2.2. When trajectories approach $\operatorname{bd}(\mathcal{X})$, the positivity constraints $x_{i}\geq 0$ kick in finite time. Unlike the sum-to-one constraints of the previous case, these cannot be resolved with a dimensionality reduction so we cannot obtain a well-posed dynamical system on $\mathcal{X}$ as above. This problem can only be temporarily avoided for time intervals where $\operatorname{supp}(x(t))$ remains constant. For these intervals $x(t)$ can be shown to satisfy the projection dynamics

In contrast to the replicator dynamics, different trajectories of (PD) can merge or split any number of times, and they may transit from one face of $\mathcal{X}$ to another in finite time .

The two cases above are not just conveniently chosen examples, but archetypes of the fundamentally different behaviors that can be observed under (FTRL) for different regularizers. As we discuss in the supplement, this polar split is intimately tied to the behavior of the derivatives of $h$ at the boundary of $\mathcal{X}$. To formalize this, we say that $h$ is steep if $\lVert\nabla h(x)\rVert\to\infty$ whenever $x\to\operatorname{bd}(\mathcal{X})$; by contrast, if $\sup_{x\in\mathcal{X}}\lVert\nabla h(x)\rVert<\infty$, we say that $h$ is non-steep. Thus, in terms of our examples, the negentropy function of Example 2.1 is the archetype for steep regularizers, while the $L^{2}$ penalty of Example 2.2 is the non-steep one. The split between steep and non-steep dynamics may then be stated as follows:

If $h$ is steep, the mixed-strategy trajectories $x(t)=Q(y(t))$ carry all the information required to predict the evolution of the system; in particular, $x(0)$ fully determines $x(t)$ for all $t\geq 0$, and $x(0)$ remains fully mixed for all time.

If $h$ is non-steep, the trajectories $x(t)=Q(y(t))$ do not fully capture the state of the system: $x(0)$ does not determine $x(t)$ for all $t\geq 0$, and even the times when $x(t)$ changes support cannot be anticipated by knowing $x(0)$ alone. For concision, we defer the precise statement and proof of this dichotomy to the paper’s supplement.

Convergence analysis and results

We now turn to the equilibrium convergence properties of (FTRL). The central question that we seek to address here is the following: Which Nash equilibria can be stable and attracting under (FTRL)? Are all equilibria created equal in that regard?

At a high level, a point is (\edefnit\selectfonta\edefnn) stablewhen every trajectory that starts nearby remains nearby; and (\edefnit\selectfonta\edefnn) attractingwhen it attracts all trajectories that start close enough. Already, this heuristic shows that defining these notions for (FTRL) is not straightforward: the target points are strategy profiles in $\mathcal{X}$, while the dynamics (FTRL) evolve in the dual space $\mathcal{Y}$. When $h$ is steep, we can define an equivalent presentation of (FTRL) on $\mathcal{X}$, so this problem can be circumvented by working solely with mixed strategies; however, when $h$ is non-steep, this is no longer possible and we need to navigate carefully between $\mathcal{X}$ and $\mathcal{Y}$. In view of this, we have the following definitions:

$x^{\ast}\in\mathcal{X}$ is stable if, for every neighborhood $U$ of $x^{\ast}$ in $\mathcal{X}$, there exists a neighborhood $U^{\prime}$ of $x^{\ast}$ such that $x(t)=Q(y(t))\in U$ for all $t\geq 0$ whenever $x(0)=Q(y(0))\in U^{\prime}$.

$x^{\ast}\in\mathcal{X}$ is attracting if there exists a neighborhood $U$ of $x^{\ast}$ in $\mathcal{X}$ such that $x(t)=Q(y(t))\to x^{\ast}$ whenever $x(0)=Q(y(0))\in U$.

$x^{\ast}\in\mathcal{X}$ is asymptotically stable if it is both stable and attracting.

For obvious reasons, asymptotic stability is the “gold standard” for questions pertaining to equilibrium convergence and it will be our litmus test for the appropriateness of an equilibrium $x^{\ast}\in\mathcal{X}$ as an outcome of play. Specifically, if a Nash equilibrium is not asymptotically stable under (FTRL), it is not reasonable to expect a no-regret learner to converge to it, meaning in turn that it cannot be justified as an end-state of the players’ learning process. We expound on this below.

2. Volume preservation

A key observation regarding asymptotic stability is that neighborhoods of initial conditions near an asymptotically stable point should “contract” over time, eventually shrinking down to the point in question. Our first result below provides an apparent contradiction to this principle: it shows that volume is preserved under (FTRL), irrespective of the underlying game.

Let $\mathcal{R}_{0}\subseteq\mathcal{Y}$ be a set of initial conditions for (FTRL) and let $\mathcal{R}_{t}=\{y(t):y(0)\in\mathcal{R}_{0}\}$ denote its evolution under (FTRL) after time $t\geq 0$. Then, $\operatorname{vol}(\mathcal{R}_{t})=\operatorname{vol}(\mathcal{R}_{0})$.

Proposition 1 (which we prove in the supplement through an application of Liouville’s formula) is surprising in its universality as it holds for all games and all instances of (FTRL). As such, it provides a blanket generalization of the well-known volume-preserving property for the replicator dynamics established by Akin , as well as subsequent results for zero-sum games .

3. Instability of fully mixed equilibria

As stated above, the volume-preserving property of (FTRL) would seem to suggest that no strategy can be asymptotically stable. However, this is a figment of the duality between strategy and score variables: a mixed strategy orbit $x(t)=Q(y(t))$ could converge in $\mathcal{X}$, even though the corresponding dual orbit $y(t)$ diverges in $\mathcal{Y}$ (for an illustration, see Fig. 2 above). This again brings into sharp contrast the behavior of (FTRL) at the boundary of $\mathcal{X}$ versus its behavior at the interior. Our first instability result below shows that the volume-preserving property of (FTRL) rules out the stability of any fully mixed equilibrium, in any game:

A fully mixed Nash equilibrium cannot be asymptotically stable under (FTRL).

The main idea of the proof of Theorem 1 relies on a tandem application of Proposition 1 together with the dimensionality reduction idea we discussed for the entropic case in Section 3. In the resulting quotient space, the inverse image of an interior point $x^{\ast}\in\operatorname{ri}(\mathcal{X})$ is a single point and the induced dynamics remain volume-preserving. If $x^{\ast}$ is asymptotically stable, a limit point argument rules out the possibility of a trajectory entering and exiting a small neighborhood of its preimage infinitely many times. At the same time, Lyapunov stability and volume preservation imply that the dynamics are locally recurrent. This contradicts the transient property established above and proves that $x^{\ast}$ cannot be asymptotically stable; the details involved in making these arguments precise are fairly intricate, so we defer the proof of Theorem 1 to the supplement.

This universal instability result has significant implications as it provides a dynamic justification of the fragility of fully mixed Nash equilibria. Theorem 1 illustrates this principle through the lens of regret minimization: any deviation from a fully mixed equilibrium invariably creates an opportunity that can be exploited by a no-regret learner. When every player adheres to such a policy, this creates a vicious cycle which destroys any chance of stability for fully mixed equlibria.

4. The case of partially mixed equilibria

Taking this premise to its logical extreme, a natural question that arises is whether this instability persists as long as even a single player employs a mixed strategy at equilibrium. In the previous case, after the dimensionality reduction argument we described in Section 3, neighborhoods of fully mixed equilibria in the space of strategies ($\mathcal{X}$) correspond to sets of finite volume in the space of payoffs ($\mathcal{Y}$). On the contrary, the case of partially mixed equilibria is much more complex because neighborhoods of points on the boundary of $\mathcal{X}$ correspond to sets of infinite volume in the space of payoffs – and this, even after dimensionality reduction (cf. Fig. 1). Because of this, volume preservation arguments cannot rule out asymptotic stability of Nash equilibria lying at the boundary of the strategy space: indeed, pure Nash equilibria also lie on the boundary but they can be asymptotically stable .

In view of the above, it is not a priori clear whether partially mixed equilibria would behave more like pure or fully mixed ones – or if no conclusion can be drawn whatsoever. Our next result shows that the dynamics of FTRL represent a very sharp selection mechanism in this regard:

Only strict Nash equilibria can be asymptotically stable under (FTRL).

If $x^{\ast}$ is partially mixed, it cannot be asymptotically stable under (FTRL).

Viewed in isolation, Theorem 1 would seem to be subsumed by Theorem 2, but this is not so: the former plays an integral role in the proof of the latter, so it cannot be viewed as a special case. In more detail, the proof of Theorem 2 builds on Theorem 1 along two separate axes, depending on whether the underlying regularizer is steep or not:

In the steep case, as we discussed in Section 3 there is a well-posed dynamical system on $\mathcal{X}$. As we show in the supplement, each face of $\mathcal{X}$ is forward-invariant in this system, so $x^{\ast}$ must also be asymptotically stable when constrained to the face $\mathcal{X}^{\ast}$ of $\mathcal{X}$ spanned by $\operatorname{supp}(x^{\ast})$. The conclusion of Theorem 2 then follows by noting that $x^{\ast}$ is interior in $\mathcal{X}^{\ast}$ and applying Theorem 1 to the restriction of the underlying game to $\mathcal{X}^{\ast}$.

The non-steep case is considerably more difficult because (FTRL) no longer induces a well-posed system on $\mathcal{X}$. In lieu of this, by examining the finer structure of the inverse image of $x^{\ast}$, it is possible to show the following: for every small enough compact neighborhood $\mathcal{K}$ of $x^{\ast}$ in $\mathcal{X}$, there exists a finite time $\tau_{\mathcal{K}}\geq 0$ such that $\operatorname{supp}(x(t))=\operatorname{supp}(x^{\ast})$ for all $t\geq\tau_{\mathcal{K}}$ whenever $x(0)\in\mathcal{K}$. As it turns out, the dynamics after $t\geq\tau_{\mathcal{K}}$ locally coincide with the mixed strategy dynamics of (FTRL) applied to the restriction of the underlying game to the face $\mathcal{X}^{\ast}$ of $\mathcal{X}$ spanned by $x^{\ast}$. Since $x^{\ast}$ is a fully mixed equilibrium in this restricted game, it cannot be asymptotically stable.

5. Stable limit sets

We conclude our analysis with a result concerning more general behaviors whereby the dynamics of FTRL do not converge to a point, but to a more general invariant set – such as a chain of stationary points interconnected by solution orbits, a structure known as a heteroclinic cycle [see e.g., 29, 59, and references therein]. As an example, in the case of two-player zero-sum games with a fully mixed equilibrium, it is known that the trajectories of (FTRL) form periodic orbits (cycles). However, these orbits are not asymptotically stable: if the initialization of the FTRL dynamics is slightly perturbed, the resulting trajectory will be a different periodic orbit, which does not converge to the first (in the language of dynamical systems, the cycles observed in zero-sum games are not limit cycles). We are thus led to the following natural question:

What type of invariant structures can arise as stable limits of (FTRL)?

To state this question formally, we will require the setwise version of asymptotic stability: a set $\mathcal{S}$ is called asymptotically stable under (FTRL) if \edefnit\selectfonta\edefnn) all orbits $x(t)=Q(y(t))$ of (FTRL) that start sufficiently close to $\mathcal{S}$ remain close; and \edefnit\selectfonta\edefnn) all orbits that start nearby eventually converge to $\mathcal{S}$. Then, focusing on the case of steep dynamics to avoid more complicated statements, we have:

Every asymptotically stable set of steep (FTRL) contains a pure strategy.

The proof of Theorem 3 relies on an “infinite descent” argument whereby the faces of $\mathcal{X}$ that intersect with $\mathcal{S}$ are eliminated one-by-one, until only pure strategies remain as candidate elements of $\mathcal{S}$ with minimal support; we provide the details in the supplement.

The importance of Theorem 3 lies in that it provides a succinct criterion for identifying possible attracting sets of (FTRL). Indeed, by Conley’s decomposition theorem (also known as the “fundamental theorem of dynamical systems”) , the flow of (FTRL) in an arbitrary game decomposes into a chain recurrent part and an attracting part (see for several examples/discussion in the case of replicator dynamics). The recurrent part is exemplified by the periodic orbits that arise in zero-sum games with an interior equilibrium (there are no attractors in this case) . Theorem 3 goes a long way to showing that the attracting part of (FTRL) always intersects the extremes of the game’s strategy space – i.e., the players’ set of pure strategies. A special case of Theorem 3, in the case of replicator dynamics, was employed in as a step in the definition of new, dynamics/decomposition-based solution concepts. Formalizing the exact form of this decomposition in arbitrary games is an open direction for future research with far-reaching implications for the theory of online learning in games.

Concluding remarks

The well known universal existence theorem for (mixed) Nash equilibria in general games has been very influential not only from a mathematics perspective but also from a public policy one as it seems to suggest that there is no inherent tension in any societal setting between the single-minded pursuit of individual profits and societal stability. Nash equilibria satisfy both desiderata simultaneously. Thus, there is in principle no need for centralized intervention and guidance as market forces will converge upon such a solution.

Our results present an argument in the opposite direction. Unless the game has a pure Nash equilibrium, which is definitely not satisfied in numerous strategic interactions, then societal systems do not self-stabilize, even if they are driven by our most effective payoff seeking dynamics, i.e., gradient learning and its follow-the-regularizer-leader variants. Exploring the tradeoffs between individual optimality and societal stability is thus a much more subtle issue than it first meets the eye, and we hope that we inspire follow-up work that can elucidate these questions further.

Acknowledgments

This research was partially supported by the COST Action CA16228 “European Network for Game Theory” (GAMENET), the French National Research Agency (ANR) under grant ALIAS, and the Onassis Foundation undr Scholarship ID: F ZN 010-1/2017-2018.

E.V. Vlatakis-Gkaragkounis is grateful to be supported by NSF grants CCF-1703925, CCF-1763970, CCF-1814873, CCF-1563155, and by the Simons Collaboration on Algorithms and Geometry.

T. Lianeas is supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant”, project BALSAM, HFRI-FM17-1424.

P. Mertikopoulos is grateful for financial support by the French National Research Agency (ANR) in the framework of the “Investissements d’avenir” program (ANR-15-IDEX-02), the LabEx PERSYVAL (ANR-11-LABX-0025-01), and MIAI@Grenoble Alpes (ANR-19-P3IA-0003).

G. Piliouras gratefully acknowledges AcRF Tier-2 grant (Ministry of Education – Singapore) 2016-T2-1-170, grant PIE-SGP-AI-2018-01, NRF2019-NRF-ANR095 ALIAS grant and NRF 2018 Fellowship NRF-NRFF2018-07 (National Research Foundation Singapore).

Appendix A An ontology of Nash equilibria: representative examples

In the archetypal game of Prisoner’s Dilemma (left), it is easy to check that the unique Nash equilibrium is the mutual betrayal which is strict (and hence pure). On the other hand, Matching Pennies (right) is an example of a zero-sum game whose unique Nash equilibrium is fully mixed but still quasi-strict (since all strategies present in its support are unilateral best responses to it). We mention the above to clarify that quasi-strict does not mean pure equilibria and includes also the fully mixed Nash equilibrium; the terminology is, perhaps, unfortunate, but otherwise deeply entrenched in the game-theoretic literature .

Appendix B Basic properties of the FTRL dynamics

In this appendix, we provide some general preliminaries from general topology and the theory of dynamical systems that we will use freely in the sequel.

A key notion in our analysis is that of (Poincaré) recurrence. Intuitively, a dynamical system is recurrent if, after a sufficiently long (but finite) time, almost every state returns arbitrarily close to the system’s initial state.Here, “almost” means that the set of such states has full Lebesgue measure. More formally, given a dynamical system on $\mathcal{X}$ that is defined by means of a semiflow $\Phi\colon\mathcal{X}\times[0,\infty)\to\mathcal{X}$, we have:A smooth map $\Phi\colon\mathcal{X}\times[0,\infty)\to\mathcal{X}$ is called a semiflow if $\Phi_{0}(x)=x$ and $\Phi_{t+s}(x)=\Phi_{s}(\Phi_{t}(x))$ for all $x\in\mathcal{X}$ and all $t,s\geq 0$. Heuristically, $\Phi_{t}(x)\equiv\Phi_{t}(x)$ describes the trajectory of the dynamical system starting at $x$.

A point $x\in\mathcal{X}$ is said to be recurrent under $\Phi$ if, for every neighborhood $U$ of $x$ in $\mathcal{X}$, there exists an increasing sequence of times $t_{n}\uparrow\infty$ such that $\Phi_{t_{n}}(x)\in U$ for all $n$. Moreover, the flow $\Phi$ is called (Poincaré) recurrent if, for every measurable subset $A$ of $\mathcal{X}$, the set of recurrent points in $A$ has full measure.

The above definition directly implies that the flow $\Phi_{t}(x)$ from a recurrent point $x$ cannot converge to any $x^{\prime}\neq x$. Poincaré’s recurrence theorem gives sufficient condition for the existence of such points.

If a flow $\Phi$ preserves volume and its orbits are bounded, then almost every point is recurrent under $\Phi$.

The key notion in the above formulation of the theorem is that of volume preservation: formally, a flow $\Phi$ is volume-preserving if $\operatorname{vol}(\Phi_{t}(\mathcal{R}))=\operatorname{vol}(\mathcal{R})$ for any set of initial conditions $\mathcal{R}\subseteq\mathcal{X}$. A useful condition to establish this property is via Liouville’s formula, as stated below:

Let $\Phi$ be the flow of a dynamical system with infinitesimal generator $V$, i.e., $\Phi_{t}(x)$ is the solution trajectory of the ordinary differential equation

with initial condition $x(0)=x$. Then, letting $\mathcal{R}_{t}=\Phi_{t}(\mathcal{R})$ for an arbitrary measurable set $\mathcal{R}$, we have

B.2. Structural properties of the FTRL dynamics: the steep/non-steep dichotomy

The result follows by applying the Karush–Kuhn–Tucker (KKT) conditions to this optimization problem and noting that, since the constraints are affine, the KKT conditions are sufficient for optimality. Our Langragian is

where the set of constraints (i) of the statement of the lemma are the stationarity constraints, which in our case are $\nabla\mathcal{L}(x,\mu,\nu)=0\Leftrightarrow\nabla(\sum_{\alpha\in\mathcal{A}}y_{\alpha}x_{\alpha}-h(x))=\mu\nabla(\sum_{\alpha\in\mathcal{A}}x_{\alpha}-1)-\sum_{\alpha\in\mathcal{A}}\nu_{\alpha}\nabla x_{\alpha}$ , while the set of constraints (ii) of the statement of the lemmas are the complementary slackness constraints. Note that complementary slackness implies that whenever $\nu_{\alpha}>0$ whenever $\alpha\notin\operatorname{supp}(x)$. Finally, if $h$ is steep, we have $\lvert\partial_{\alpha}h(x)\rvert\to\infty$ as $x\to\operatorname{bd}(\mathcal{X})$, which implies that the KKT conditions admit a solution with $\nu_{\alpha}=0$. ∎

where $H_{\alpha}(x)=\left[\sum_{\beta,\beta^{\prime}\in\operatorname{supp}(x)}H_{\beta\beta^{\prime}}(x)\right]^{-1/2}\sum_{\beta\in\operatorname{supp}(x)}H_{\alpha\beta}(x)$. In particular, we have the following dichotomy:

If $h$ is steep, the dynamics (FTRL-s) are well-posed, i.e., they admit unique global solutions from any initial condition $x\in\mathcal{X}$ (including the boundary). Moreover, the faces of $\mathcal{X}$ are forward-invariant under (FTRL-s): the support of $x(t)$ remains constant for all $t\geq 0$.

If $h$ is non-steep, the dynamics (FTRL-s) are not well-posed: solutions $x(t)$ to (FTRL-s) exist only up to a finite time, after which the support of $x(t)$ may change.

For the first part of the lemma, we follow a line of reasoning due to . Specifically, letting $g_{\alpha}(x)=\partial_{\alpha}h(x)$, Lemma B.1 yields

Since $y_{\alpha}$ and $g_{\alpha}$ are both smooth, so is $\mu(t)$. Thus, differentiating with respect to $t$ we get

since for all $t\in I$ and $\beta\in\mathcal{A}\setminus\mathcal{A}^{*}$, $x_{\beta}(t)=0$, and thus $\dot{x}_{\alpha}(t)=0$. Multiplying with the inverse of the Hessian, and omitting $t$ for brevity, we get

By the definition of the dynamics, $\dot{y}_{\beta}=v_{\beta}$ and since the support remains constant $\sum_{\alpha\in\mathcal{A}^{*}}\dot{x}_{\alpha}=0$. Summing up Equation B.4 for $\alpha\in\mathcal{A}^{*}$ we get

where $G=\sum_{\beta,\beta^{\prime}\in\operatorname{supp}(x)}H_{\beta\beta^{\prime}}(x)$. Substituting the latter and $\dot{y}_{\beta}=v_{\beta}$ to Equation B.4 we get the desired result.

B.3. Volume preservation in 𝒴𝒴\mathcal{Y} and ri⁡(𝒳)ri𝒳\operatorname{ri}(\mathcal{X})

After restating it, we proceed to show Proposition 1 by simply applying Liouville’s formula (Theorem B.2). See 1

We have to show that the dynamics of (FTRL) (i.e., $\dot{y}(t)=v(Q(y(t)))$) are incompressible. For any player $i$ and any $\alpha\in\mathcal{A}_{i}$ we have

because $v_{i}$ does not depend on $x_{i}$. We thus obtain $\operatorname{div}_{y}v(y)=0$, i.e., the dynamics (FTRL) are incompressible. The result then follows from Liouville’s formula ∎

In the following lemma, we show that the flow defined by FTRL in the interior $\operatorname{ri}(\mathcal{X})$ of $\mathcal{X}$ is incompressible under a suitably defined measure. For that, using Liouville’s formula, we first show that in the so-called $z$-space, i.e., a “slice” of the payoff space, the respective flow is incompressible. Using that, we can easily get a diffeomorphism from $\operatorname{ri}(\mathcal{X})$ to the $z$-space, we define the volume of a set in $\operatorname{ri}(\mathcal{X})$ to be the volume of the corresponding set in the $z$-space, and thus incompresssibility in the interior comes for free. Lemma B.2. There exists a measure $\mu_{x}$ for which the flow in the interior of $\mathcal{X}$ is incompressible, i.e., for any subset $U\subset\operatorname{ri}(\mathcal{X})$ of initial conditions, and any $t_{0}\geq 0$ so that for any $0\leq t\leq t_{0}$: $\Phi(U,t)\subset\operatorname{ri}(\mathcal{X})$, it is $\mu_{x}(U)=\mu_{x}(\Phi(U,t))$.

First we go on to define the $z$-space. The intuition for defining and using the $z$-space can be based on Lemma B.1 which implies that for any $x\in\operatorname{ri}(\mathcal{X})$, any two corresponding points $y,y^{\prime}$ in the $y$-space differ by a constant, since for all $i$ and $\alpha_{j}\in\mathcal{A}_{i}$, $y_{i\alpha_{j}}=\frac{\partial h}{\partial x_{i\alpha_{j}}}+\mu_{i}$ and $y^{\prime}_{i\alpha_{j}}=\frac{\partial h}{\partial x_{i\alpha_{j}}}+\mu_{i}^{\prime}$ for some $\mu_{i}$ and $\mu_{i}^{\prime}$ (recall $x\in\operatorname{ri}(\mathcal{X})$ implies $\nu_{i\alpha_{j}}=0$). Thus, all $y$’s that correspond to an $x\in\operatorname{ri}(\mathcal{X})$ form an equivalent class. For each class, we pick as representative the $y$ in the class that has in some specific coordinate $\hat{\alpha}_{i}$, for every player $i$. The set of representatives form the $z$-space and there is a a one to one correspondence of points of $\operatorname{ri}(\mathcal{X})$ to points in the $z$-space which moreover can be used to define an incompressible flow in $\operatorname{ri}(\mathcal{X})$.

So, for a benchmark strategy $\hat{\alpha}_{i}\in\mathcal{A}_{i}$ for every player $i\in\mathcal{N}$ and for all $\alpha\in\mathcal{A}_{i}\mathopen{}\setminus\{\hat{\alpha}_{i}\}\equiv\hat{\mathcal{A}}_{i}$ consider the corresponding score differences

Now, under FTRL, the score differences (B.7) evolve as

Our first step below is to show that (B.8) constitutes a well-defined dynamical system on $z$ as long as the correpsonding $x$’s remain in $\operatorname{ri}(\mathcal{X})$.

where we used the fact that $\sum_{\alpha\in\mathcal{A}_{i}}x_{i\alpha}=1$. The above shows that $Q_{i}(y_{i}^{\prime})=Q_{i}(y_{i})$ if and only if $\Pi_{i}(y_{i})=\Pi_{i}(y_{i}^{\prime})$, so $\hat{Q}_{i}$ is well-defined. Letting $\hat{Q}\equiv(\hat{Q}_{1},\dotsc,\hat{Q}_{N})$ denote the aggregation of the players’ individual mirror maps $\hat{Q}_{i}$, it follows immediately that $Q(y)=\hat{Q}(\Pi(y))=\hat{Q}(z)$ by construction.

Hence, the dynamics (B.8) may be written as

These dynamics obviously constitute an autonomous system.

Next, we show incompressibiity of the $z$-space. Indeed, for all $\alpha\in\mathcal{A}$ we have

because $v_{i}$ does not depend on $x_{i}$. We thus obtain $\nabla_{z}\cdot V(z)=0$, i.e., the dynamics (B.11) are incompressible.

For the last step, for a set $A\subset\operatorname{ri}(\mathcal{X})$ define $\mu_{x}(A):=\mu_{z}(Q^{-1}(A))$, where $\mu_{z}$ is the Lebesgue measure in the $z$-space. Then for any $U\subset\operatorname{ri}(\mathcal{X})$, as long as $\Phi(U,t)$ remains in $\operatorname{ri}(\mathcal{X})$, it is

Appendix C Proof of Theorem 1

Below we show that there are no asymptotically stable sets (or points) in $\operatorname{ri}(\mathcal{X})$. Indeed, if this were the case, there would be a full-measure set of initial conditions outside the asymptotically stable set $A^{*}$ that converges to $A^{*}$, while at the same time its trajectories are bounded (by stability). This contradicts Poincaré’s recurrence theorem, because the flow in $\operatorname{ri}(\mathcal{X})$ is volume-preserving by Lemma B.2. Theorem C.1. Let $A^{*}$ be a closed set of $\operatorname{ri}(\mathcal{X})$. Then $A^{*}$ is not asymptotically stable under FTRL.

To reach a contradiction, let $A^{*}$ be an asymptotically stable set, i.e., attracting and Lyapunov stable, belonging in $\operatorname{ri}(\mathcal{X})$. Since $A^{*}$ is attracting, there exists a neighborhood $U$ of $A^{*}$ all points of which converge to $A^{*}$. Without loss of generality, since $A^{*}$ is closed, we may assume that $U$ lies in $\operatorname{ri}(\mathcal{X})$, and its closure is disjoint from the boundary of $\mathcal{X}$.

Now, since $A^{*}$ is Lyapunov stable, there exists some neighborhood $U_{0}$ of $A^{*}$ so that whenever $x(0)\in U_{0}$, $x(t)\in U$. Pick some $x_{0}\in U_{0}\setminus A^{*}$. Since $A^{*}$ is closed and $U_{0}$ is open, there is a small enough neighborhood $E$ of $x_{0}$ so that all points of $E$ lie inside $U_{0}\setminus A^{*}$. By Lyapunov stability, for all $t\geq 0$, $\Phi(E,t)\subseteq U$. But then the set $E_{\infty}=\cup_{t\geq 0}\Phi(E,t)$ is bounded, having positive measure that does not change over time (Lemma B.2). Therefore it is a Poincaré recurrent set. But this means that all but a measure zero set of initializations in $E$ lead to recurrent trajectories that return infinitely often to $E$. Picking $E$ to be bounded away from $A^{*}$ (which is a closed set) we conclude that there are points in $E$ (and thus $U$) that do not converge to $A^{*}$, a contradiction. ∎

Now, given that any singleton set $\{x\}$, $x\in\mathcal{X}$, is closed, the above yields:

There are no asymptotically stable points in $\operatorname{ri}(\mathcal{X})$

Theorem 1 (restated below) then follows as a corollary.

Appendix D Proof of Theorem 2: the non-steep case

Our goal in this appendix is to provide the proof of Theorem 2, which we restate below for convenience:

Because of the fundamental dichotomy between steep and non-steep FTRL dynamics, we will break the proof in two cases, treating here the non-steep regime; the steep case will be proved in Appendix E as a consequence of a more general result. The fundamental distinction between the two cases is that, in the non-steep regime, the mixed-strategy dynamics of (FTRL) could change support infinitely many times, which means that the type of volume-preservation arguments employed in the previous section cannot work (because the corresponding preimages in the $z$-space could have infinite volume; see below for a graphical illustration). However, as we show below, this “change of support” is a blessing in disguise: if $x^{\ast}$ is asymptotically stable, nearby trajectories will end up employing only those strategies present in $x^{\ast}$ in finite time.

The following lemma shows that, for generic games, if the underlying regularizer is non-steep, all trajectories starting near an asymptotically stable point $x^{\ast}$ attain the face of $x^{\ast}$ in some uniform, finite time. The intuition for this is that, generically, for any player $i$, the coordinates of $y_{i}$ that correspond to the support of $x^{\ast}_{i}$ increase with a “speed” that is uniformly higher than those strategies not supported in $x^{\ast}$. The regularizer of player $i$ could possibly act in favor of the coordinates that do not belong to the support, but in a bounded way, since it is non-steep. Thus, there is a time after which the coordinates of $y_{i}$ corresponding to the support are bigger enough than the other coordinates, so that the mirror map $Q_{i}$ keeps returning a point with support equal to the support of $x^{\ast}_{i}$. Lemma D.1. Let $x^{\ast}$ be an asymptotically stable equilirium of a generic finite game $\Gamma$, with the regularizers used, being non-steep. For any neighborhood $U$ of $x^{\ast}$, there exists a neighborhood $U_{0}$ of $x^{\ast}$ and a finite time $T_{0}$ such that if $x(t)=Q(y(t))$ is an orbit of FTRL starting at $x(0)\in U_{0}$, then $\operatorname{supp}(x(t))=\operatorname{supp}(x^{\ast})$ for all $t\geq T_{0}$.

By the genericity assumption, all Nash equilibria are quasi-strict. Clearly we have that for any player $i$, $u_{i\alpha}(x^{\ast})>u_{i\beta}(x^{\ast})$ for all $\alpha\in\operatorname{supp}(x^{\ast}_{i})\equiv\mathcal{A}^{*}_{i}$ and $\beta_{i}\notin\operatorname{supp}(x^{\ast}_{i})$. Thus, by continuity there exists some neighborhood $U$ of $x^{\ast}$ and a $c>0$ so that for any $x\in U$ and any player $i$, $u_{i\alpha}(x)>u_{i\beta}(x)+c$ for all $\alpha\in\mathcal{A}^{*}_{i},\beta\in\mathcal{A}_{i}\setminus\mathcal{A}^{*}_{i}$. Additionally, we can choose $U$ small enough so that for all $x\in U$, $\operatorname{supp}(x^{\ast})\subseteq\operatorname{supp}(x)$. Since $x^{\ast}$ is asymptotically stable there exists a neighborhood $U_{0}$ of $x^{\ast}$ so that $x(t)\in U$ for all $t$ whenever $x(0)\in U_{0}$, and $\lim_{t\to\infty}x(t)=x^{\ast}$.

By Lemma B.1, for any $t\geq 0$ there exist a $\mu(t)$ and non negative $v_{\alpha}(t)$’s so that

since, by complementary slackness, $v_{\alpha}(t)=0$, whenever $x_{\alpha}(t)>0$. Subtracting we get

with the inequality following, for some constant $G$, by $h$ being non-steep.

On the other hand by the definition of the dynamics, using Equation D.1 and that $u_{\alpha}(x(t))>u_{\beta}(x(t))+c$, for all $t$ (since $x(0)\in U_{0}$), we get

with the last inequality following again by $h$ being non-steep. Combining the latter with Equation D.1, and since $v_{\beta}(0)\geq 0$, we get

which implies that for $t\geq\frac{2G}{c}$ it is $v_{\beta}(t)>0$. This in turn, by complementary slackness, yields $x_{\beta}(t)=0$ for all $t\geq\frac{2G}{c}$, implying $\operatorname{supp}(x(t))\subseteq\operatorname{supp}(x^{\ast})$. By the choice of $U$ and since $\forall t:x(t)\in U$ we have $\operatorname{supp}(x(t))\supseteq\operatorname{supp}(x^{\ast})$ and thus setting $T_{0}=\frac{2G}{c}$ proves the claim, since the above holds for any player $i$. ∎

The main result of this section is the following theorem that covers the non-steep case, stating that for generic games at an asymptotically stable point under non-steep regularizers, every player plays a pure strategy. The proof combines results presented above. It reaches a contradiction by showing that points in a small enough neighborhood of the asymptotically stable point $x^{\ast}$, instead of converging to it as they ought to, they follow recurrent trajectories. In a first step it finds points that after a finite time $T_{0}$ reach and stay forever at the simplex formed by the support of $x^{\ast}$ (using Lemma D.1), which moreover have non-zero volume in that simplex. But then, these points follow FTRL trajectories in the restricted simplex (Proposition B.1) and $x^{\ast}$ belongs in the interior of this simplex. However, we already know this cannot be the case in the interior (Theorem C.2) and we follow a similar reasoning. Theorem D.1. If $x^{\ast}\in\mathcal{X}$ is an asymptotically stable point under non-steep regularizers of a generic game $\Gamma$, then it consists of only pure strategies.

Let $x^{\ast}\in\mathcal{X}$ be asymptotically stable, $\mathcal{A}^{*}=\operatorname{supp}(x^{\ast})$, with $|\mathcal{A}_{i}^{*}|=|\operatorname{supp}(x_{i}^{*})|\geq 2$ for some player $i$, and $\mathcal{X}^{*}$ be its respective simplex. Since $x^{\ast}$ is attracting, there exists some (bounded) neighborhood $U$ of $x^{\ast}$ for which if $x(0)\in U$, then $\lim_{t\to\infty}x(t)=x^{\ast}$. By Lemma D.1, there exists a neighborhood $U_{0}$ of $x^{\ast}$ and a finite time $T_{0}$ such that if $x(t)=Q(y(t))$ is an orbit of FTRL starting at $x(0)\in U$, then $\operatorname{supp}(x(t))=\mathcal{A}^{*}$ for all $t\geq T_{0}$.

By Proposition B.1, for $t\geq T_{0}$ all trajectories satisfy Equation FTRL-s and these trajectories coincide with the trajectories of a generic game $\Gamma^{\prime}$ played on $\mathcal{A}^{*}$, with the restricted simplex being $\mathcal{X}^{*}$. At the same time, similar to the proof of Theorem C.1, $\Phi(U_{0},T_{0})$ is a bounded (as a subset of $U\operatorname*{\bigcap}\mathcal{X}^{*}$), positive measure for $\mathcal{X}^{*}$ (as the evolution of an open set after a finite time (recall $|\mathcal{A}_{i}^{*}|\geq 2$ for some $i$)), and invariant (Lemma B.2) set of $\mathcal{X}^{*}$ and, therefore, it is also Poincaré recurrent, contradicting that for $x(0)\in\Phi(U_{0},T_{0})\subseteq U$, $\lim_{t\to\infty}x(t)=x^{\ast}$, as implied by the asymptotic stability of $x^{\ast}$. Thus, if $x^{\ast}\in\mathcal{X}$ is asymptotically stable then $|\operatorname{supp}(x_{i}^{*})|=1$ for all $i$. ∎

As we stated in the beginning of this appendix, the steep case of Theorem 2 comes as a corollary (Corollary 3) of a more general result on asymptotically stable sets that we prove in the next section (Theorem 3).

Appendix E Proof of Theorem 3 and Theorem 2: the steep case

The following theorem shows that any asymptotically stable set $A$ cannot be contained in the interior of any non-singleton face $\mathcal{X}^{\prime}$. This comes as a consequence of Theorem C.1. When the regularizers are steep, any point starting in $\operatorname{ri}(\mathcal{X}^{\prime})$ stays in $\operatorname{ri}(\mathcal{X}^{\prime})$ over time and $A$ being asymptotically stable implies that $A\operatorname*{\bigcap}\mathcal{X}^{\prime}$ is an asymptotically stable set under the FTRL dynamics of the restricted game played on $\mathcal{X}^{\prime}$. But for the restricted game Theorem C.1 applies excluding the possibility of $A\operatorname*{\bigcap}\mathcal{X}^{\prime}$ being an asymptotically stable set inside $\operatorname{ri}(\mathcal{X}^{\prime})$. Theorem E.1. Let $A\subseteq\mathcal{X}$ be an asymptotically stable set intersecting a non-singleton face $\mathcal{X}^{\prime}$ of $\mathcal{X}$. Then, $A\operatorname*{\bigcap}\mathcal{X}^{\prime}$ cannot be contained in the relative interior of $\mathcal{X}^{\prime}$.

To reach a contradiction let $A$ intersect a non-singleton face $\mathcal{X}^{\prime}$ of $\mathcal{X}$ and $A^{\prime}=A\operatorname*{\bigcap}\mathcal{X}^{\prime}$ be a subset of the relative interior of $\mathcal{X}^{\prime}$. We will show that if this is the case then $A^{\prime}$ is an asymptotically stable set under the dynamics of FTRL restricted to $\mathcal{X}^{\prime}$, that lies in the relative interior of $\mathcal{X}^{\prime}$. This contradicts Theorem C.1.

To reach the contradiction, we go on to prove that $A^{\prime}$ is an asymptotically stable set under FTRL dynamics in $\mathcal{X}^{\prime}$. We will crucially use that with steep regularizers for any $x(0)\in\operatorname{ri}(\mathcal{X}^{\prime})$, $x(t)\in\operatorname{ri}(\mathcal{X}^{\prime})$, for all $t\geq 0$, i.e., $\mathcal{X}^{\prime}$ is forward invariant under FTRL (Proposition B.1).

To show Lyapunov stability of $A^{\prime}$ in $\mathcal{X}^{\prime}$ pick any neighborhood $U^{\prime}$ of $A^{\prime}$ in $\mathcal{X}^{\prime}$. It can be written as $U^{\prime}=U\operatorname*{\bigcap}\mathcal{X}^{\prime}$ for some neighborhood $U$ of $A$ in $\mathcal{X}$. Since $A$ is Lyapunov stable, there exists a neighborhood $U_{0}$ of $A$ in $\mathcal{X}$ such that for any $x(0)\in U_{0}$, it is $x(t)\in U$ for all $t\geq 0$. Let $U^{\prime}_{0}=U_{0}\operatorname*{\bigcap}\mathcal{X}^{\prime}$. Using that $\mathcal{X}^{\prime}$ is forward invariant, the latter implies that for any $x(0)\in U^{\prime}_{0}=U_{0}\operatorname*{\bigcap}\mathcal{X}^{\prime}$, it is $x(t)\in U\operatorname*{\bigcap}\mathcal{X}^{\prime}=U^{\prime}$ for all $t\geq 0$, as needed.

We use similar ideas to show that $A^{\prime}$ is attracting in $\mathcal{X}^{\prime}$. Since $A$ is attracting in $\mathcal{X}$ there exist a neighborhood $U$ of $A$ in $\mathcal{X}$ such that for any $x(0)\in U$, $x(t)\to A$. Let $U^{\prime}=U\operatorname*{\bigcap}\mathcal{X}^{\prime}$. The latter combined with the forward invariance of $\mathcal{X}^{\prime}$ implies that for any $x(0)\in U\operatorname*{\bigcap}\mathcal{X}^{\prime}=U^{\prime}$, $x(t)\to A\operatorname*{\bigcap}\mathcal{X}^{\prime}=A^{\prime}$, as needed. ∎

As a corollary of the above theorem we may get Theorem 3, restated below. Whenever an asymptotically stable set intersects a non-singleton face it must intersect its respective boundary, and thus a face of smaller dimension. Consequently, “in the long run”, it must intersect a singleton face. Put differently, it should contain a point consisting of only pure strategies. See 3

Let $A$ be asymptotically stable and $\mathcal{X}_{min}$ be a face of minimal dimension intersected by $A$ which is not a singleton. By Theorem E.1, $A$ cannot be contained in the relative interior of $\mathcal{X}_{min}$, so it must intersect the boundary of $\mathcal{X}_{min}$. However, this means that $A$ intersects a face of dimension strictly smaller than that of $\mathcal{X}_{min}$, a contradiction. Thus, $\mathcal{X}_{min}$ is a singleton and $A$ must contain a vertex of $\mathcal{X}$. ∎

If $x$ is an asymptotically stable point, then it consists of only pure strategies.

References