Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games

Introduction

Von Neumann’s seminal work on zero-sum games set the formal foundations of game theory, the mathematical theory of coupled strategic behavior. The crowning jewel of his theory is the celebrated minimax theorem that states that in zero-sum competitions each agent can in isolation compute a safety strategy, the one that guarantees her, her maxmin payoff and moreover no possible improvement over this minimal guarantee is possible given that the other agent also plays such a defensive, safety minded strategy.

A cornerstone of economic theory, arguably its most resolute thesis, is that this prescribed solution is indeed the only meaningful behavior in such a setting. Any rational self-interested learning/adaptive behavior is bound to gravitate to this benign, static behavioral snapshot with both agents being deadlocked at their maxmin strategies, or, minimally even if the system does not equilibrate all of the necessary information needed to understand the system is represented by these efficiently computable, effectively unique, system states.

The number of research threads that follow this kind of reasoning is too numerous to enumerate here, but they effectively span all disciplines that study the subject, be it economics, (algorithmic) game theory, online optimization, multi-agent systems, etc. In fact, the whole sub-field of studying learning dynamics in games started with the work of and on fictitious play in zero-sum games, which showed that the time-average of the agent behavior converges to their maxmin equilibria. Ever since that first result a stream of followup works argue convergence of the time-average behavior (strategies/payoffs) of online (e.g., regret-minimizing) learning dynamics in zero-sum games . This line of results represents the main frontier of our understanding of the effects of rational, self-interested behavior in strictly competitive settings (see e.g., recent books ).

As such, the time-average notion has been widely adopted from an algorithmic perspective. Focusing on time-averages alone, however, can be rather misleading from a behavioral perspective. For example, in a two-political-party competition, while the time-average of the political attitude might be moderate which is widely interpreted as good, at different times it might swing between extremes of the political spectrum which are all often interpreted as bad. In this context, where such competition can be modelled as zero-sum game, the theoretical results in suggest that online learning are non-equilibrating, and pushing parties’ political attitude towards extremes. Instability of equilibrium is also a major issue for Generative Adversarial Networks (GANs) , a key application of zero-sum games in AI (see Related Work). These examples illuminate the importance of developing a better understanding of the actual behavior of game dynamics, instead of the time-averaged ones. As we shall see, our results showcase the possibility of a more unpleasant phenomenon: online learning in games can be chaotic, impossible to predict, at the polar opposite of the picture suggested by the celebrated minimax theorem.

Methodology — Volume Analysis. Our approach is a new methodology in the study of learning in games: we analyze the volume changes of the learning algorithm. More precisely, given a set of starting points with positive volume (Lebesgue measure), we analyze the change of the volume as the set is evolved according to the learning algorithm. In Figure 1 we plot how a small neighbourhood around the Nash Equilibrium (NE) (left figure) and one around a non-NE (right figure) are evolved over time by the MWU algorithm; see Appendix A for more details on how the plots are produced.

We show in Sections 3 and 4 that the volume in the dual (payoff) space increases exponentially, and as a result in the primal space (probability distributions over strategies) are moving away from Nash and towards the boundary. Intuitively, let’s assume that an observer asks the agents playing Matching-Pennies whether they prefer Heads or Tails (and by how much in terms of aggregate payoff so far). The range of possible answers consistent with any arbitrary small set of initial conditions blows up exponentially with time everywhere in the payoff space (Figure 1). Since the diameter of a set is polynomially lower-bounded by its volume, our result formally implies Lyapunov chaos, a classical notion to measure how chaotic a system is. It is measured by Lyapunov time, which can be informally defined as: when the starting point is perturbed by a distance of tiny amount of $\delta$, for how long will the trajectories of the two starting points remain within a distance of at most $2\delta$. Clearly, the shorter the Lyapunov time, the more chaotic the system is. We show that the Lyapunov time of MWU in zero-sum game is $\mathcal{O}(1/\epsilon^{2})$, where $\epsilon$ is the step-size of the learning algorithm.

This result is robust both algorithmically as well as game theoretically:

Algorithmic robustness: Chaos is robust to agents using any of a general sub-family of Follow-the-Regularized-Leader (FTRL) algorithms, the well known regret-minimizing dynamics, even when agents mix-and-match dynamics, use different or slowly decreasing step-sizes (Section 5).

Game theoretic robustness: Chaos is robust to all affine network variants of zero-sum games with arbitrary large number of agents (Section 6), and even to competitive settings beyond these (Generalized Rock-Paper-Scissors (RPS) games in Section 7, and general $2\times 2$ bimatrix game in Section 8).

A Note About Human Behavior in Zero-sum Games. Our results are in stark contrast with the standard interpretation of the behavior of regret minimizing dynamics in zero-sum games, which is typically referred to as “converging to equilibrium”. Naturally, we cannot without careful behavioral studies make a claim that human agents in practice adapt their beliefs according to MWU, gradient descent, FTRL, or any other classic first-order optimization method. However, we can confidently deduce a statement in the inverse direction. If as economic theory postulates (and Aumann’s quote neatly summarizes) Nash equilibria in zero-sum games are indeed stable and moreover experimentally verifiable, then this implies that human agents in practice must deviate robustly from the axiomatic perspective of purely optimization driven dynamics as captured by gradient descent and variants and apply carefully tailored equilibrium-seeking behavioral dynamics. Moreover, this is a cross-cultural behavioral universal.

Related Work. Eshel and Akin were the first to point out that replicator dynamics are volume-preserving after a transformation. In this paper, we will mostly use a slightly different transformation, except for general $2\times 2$ bimatrix games we use their transformation. Recent work on continuous time dynamics in (variants of) zero-sum games has established that such dynamics exhibit recurrent, cycle-like behavior, e.g., replicator in network zero-sum games , periodic orbits in team zero-sum games and finally recurrence for all FTRL dynamics in affine variants of network zero-sum games . Progress in discrete-time dynamics has been much slower but recently based on the above results, Bailey and Piliouras and Cheung independently developed non-equilibration analysis for all FTRL dynamics and MWU dynamics respectively in zero-sum games.

The two prior work showed that in a zero-sum game, MWU dynamic diverges from any fully-mixed NE; more precisely, they showed that the KL-divergence between the current point and the fully-mixed NE strictly increases. Consequently, the $\omega$-set for any starting point which is not NE must be a subset of the boundary of the strategy space. The main concern of the prior work is instability of the dynamics, while our current work focuses on chaos and unpredictability — these provide an entirely new, rather intuitive and convincing argument against not only Nash equilibria but the misconception that zero-sum games are “easy”. “Predictability” is a general target in any branch of science, and particularly so in dynamical systems. To clarify that “unpredictability” is conceptually different from instability, we use the classical example of weather forecast. It is common sense that weather changes day-to-day, so saying it is unstable is nothing but a tautology. What is more surprising is its unpredictability (butterfly effect), namely a small change in initial conditions and environmental factors can lead to significant difference in the outcomes. Our work is able to spot out and utilise the (geometric) volume measure, which can be viewed as a summary measure on capturing the effects of perturbation in all dimensions. In contrast, the analyses in can be viewed as focusing on an one-dimensional projection (the KL-divergence) of the dynamics, and clearly had not exploited the richer geometric structures of the dynamics.

By showing that the volumes increase exponentially, a result similar to the $\omega$-set-inside-boundary result in can be derived. One advantage of our approach is it does not need to distinguish between cases on whether a fully-mixed NE exists or not; however, the statement we can make here will be slightly weakerThe statement is: in every open subset in the primal space, there exists a starting point which will eventually get close to the boundary. See Corollaries 5 and 6.. A more compelling advantage is that this approach leads to a global instability result of NE in RPS games (see Theorem 12).

There have been work reporting observations of chaos even in simple games. Sato et al. focused on a class of RPS games which contains some zero-sum games; the two players employ the continuous-time replicator dynamics. They ran numerical simulations to find that for those zero-sum games, the dynamics are chaotic with finite Lyapunov time. Galla and Farmer focused on random two-player games where the payoffs to the two players can be positively or negatively correlated; zero-sum games belong to the negatively correlated regime. They considered a spectrum of discrete reinforcement learning dynamics, which includes MWU. Their simulations suggest experimentally that for negatively correlated games MWU exhibit chaos. We provide a theoretical underpinning for these phenomena for a wide spectrum of dynamics and games. Palaiopanos et al. and Chotibut et al. studied MWU and its variant in congestion games. While MWU with very small constant step-size converges to equilibrium in such games, they showed if we increase the step-size MWU becomes chaotic in a notion first defined by Li and Yorke . Hence chaotic behavior may be provably verifiable even outside strictly competitive games.

A stream of recent papers proves positive results about convergence to equilibria in (mostly bilinear, unconstrained) zero-sum games for suitably adapted variants of first-order methods and then apply these techniques to Generative Adversarial Networks (GANs), showing improved performance. One such adapted dynamics are extra-gradient lookahead “optimistic” methods . Constrained zero-sum game optimization (e.g. simplex constrained strategies, normal form games) are much harder to address theoretically and only recent work has addressed even the special case of optimistic MWU . exploit conservation laws of learning dynamics in zero-sum games (e.g., ) to develop new algorithms for training GANs that add a new component to the dynamic that aims at minimising this energy function. Different energy shrinking techniques for convergence even in non-convex saddle point problems exploit connections to variational inequalities and employ mirror descent techniques with an extra gradient step . Time-averaging seems to work well in practice for a wide range of architectures, although without necessarily leading to convergence . Finally, provide negative momentum adapted dynamics that add friction to the dynamics. To re-quote Aumann , determined efforts are being made once again to make zero-sum games fit their historically prescribed roles as equilibrium generators, however, zero-sum games are fighting back. For example, optimistic gradient methods as they pressure the system towards stability can end up stabilising even points that are not local min-max solutions, i.e., non-Nash solutions . Our paper showing universal chaos for first order methods in bilinear zero-sum games should be seen as a cautionary tale about the true unpredictability and hardness of training GANs. Not only do we have a long road ahead of us before we have a correct understanding of the behavior of training algorithms for GANs but more distressingly a thorough understanding might be downright impossible due to emergence of chaos.

Preliminary

Given a measurable set $S$ and a system of differential equations, the flow of $S$ at time $t$ is the collection of the flows of all starting points in $S$ at time $t$; when the underlying dynamical system is clear from context, we denote it by $S(t)$. Let $\mathsf{volume}(S)$ denote the Lebesgue volume of a measurable set $S$. In the rest of this paper, all sets $S$ are assumed to be measurable and bounded.

The Jacobian of the system is a $d\times d$-matrix, with the entry in the $i$-th row and $j$-th column be $\frac{\partial F_{i}}{\partial z_{j}}$.

Lyapunov Chaos. In the study of dynamical systems, Lyapunov chaos refer generally to following phenomenon in some systems: a tiny difference in the starting points can yield widely diverging outcomes quickly. A classical measure of chaos is Lyapunov time, which can be defined as: when the starting point is perturbed by a distance of tiny $\delta$, for how long will the trajectories of the two starting points remain within a distance of at most $2\delta$.

Replicator Dynamics. In game setting, Replicator Dynamic (RD) is a continuous-time update rule on a probability distribution over strategies. Such distribution can be naturally denoted by a strategy vector. Briefly speaking, in RD, the relative change of a probability density in a strategy vector is same as the payoff from that strategy minus the average payoff at the current probability distribution.

In two-person bimatrix game setting, where the payoffs of the two players are given by matrices $\mathbf{A},\mathbf{B}$ respectively, let the strategy set of Players 1 and 2 be $J$ and $K$ respectively, and let $n=|J|$, $m=|K|$. We denote a strategy vector of Players 1 and 2 be $\mathbf{x}\in\Delta^{n}$ and $\mathbf{y}\in\Delta^{m}$ respectively.

Then RD is governed by the following system of differential equations:

We follow convention by assuming that every entry in $\mathbf{A},\mathbf{B}$ is within the interval $\pm 1$.

Next, we discuss a crucial transformation of RD system (1). This transformation is motivated by the standard implementation of the discrete analogue of RD, the MWU algorithm.

For Player 2, the strategy vector $\mathbf{y}^{t}$ is defined similarly.

After each round, the weight of each strategy $j$ is updated by incrementing the value of the payoff to strategy $j$ in that round. In two-player bimatrix game setting, the update rule is

Observe that $(W^{T}_{j}-W^{\circ}_{j})$ is the cumulative payoff of Player 1 if she were to choose strategy $j$ with certainty in the first $t$ time steps, while Player 2 were assumed to stick with the choices $\{\mathbf{y}^{t}\}_{t=1\cdots T}$. The weights of Player 2 are updated similarly.

Now we are ready to describe the transformation. The resulting space has dimension $n+m$, which we call the dual space or the cumulative payoff space. The space before transformation will be called the primal space. Let $p_{j}$ for $j\in[n]$, and let $q_{k}$ for $k\in[m]$ be the variables in the dual space; $\mathbf{p}$ and $\mathbf{q}$ are analogous to the weight vectors of Players 1 and 2 in the MWU algorithm respectively. We will write $\mathbf{r}=(\mathbf{p},\mathbf{q})$.

The transformation from the dual space to the primal space is done via the map

Observe that $G$ is not one-to-one, but it is easy to see that $G(\mathbf{p}_{1},\mathbf{q}_{1})=G(\mathbf{p}_{2},\mathbf{q}_{2})$ if and only if $\mathbf{p}_{1}-\mathbf{p}_{2}=c_{1}\cdot\mathbf{1}$ and $\mathbf{q}_{1}-\mathbf{q}_{2}=c_{2}\cdot\mathbf{1}$ for some real numbers $c_{1},c_{2}$.

We note the similarity between the above system and the MWU update rule (2). It is easy to show that system (3) is equivalent to the system (1), as stated precisely in the following proposition.

The system (3) is useful since all diagonal entries in its Jacobian are always zero, a property that leads to volume preservation, which we discuss next.

2 Liouville’s Formula and Volume Preservation

Determinant. Given a $d\times d$ squared-matrix $\mathbf{M}$, its determinant is given by the Leibniz formula $\det(\mathbf{M})~{}=~{}\sum_{\sigma\in\mathsf{Perm}([d])}\mathsf{sgn}(\sigma)\cdot\prod_{s=1}^{d}M_{s,\sigma(s)},$ where $\mathsf{Perm}([d])$ is the collection of all permutations on $[d]$, and $\mathsf{sgn}(\sigma)$ is the sign of the permutation $\sigma$. Recall from college calculus that determinant computes the signed volume of the parallelepiped spanned by its $d$ column vectors.

The following fact, which follows easily from the Leibniz formula, will be useful. Suppose that the rows and columns of $\mathbf{M}$ are indexed by union of two sets $J,K$, and $\mathbf{M}$ can be written as

we note that the coefficient of any odd power of $\epsilon$ is zero.

Liouville’s Formula. Here, we discuss the necessary ingredient for this paper about Liouville’s Formula, and refer readers to for a more elaborate discussion. Any dynamical system with sum of diagonal entries in its Jacobian always zero is called a divergence-free system.

We will need some elements in a proof of Theorem 2 to proceed. The proof uses integration for substitution for multi-variables and Taylor expansion. To apply the former, we need to make sure that for discrete updates, the flow from $S(t)$ to $S(t+1)$ is injectiveThis holds automatically for continuous updates for the flow from $S(t)$ to $S(t+\Delta t)$ for a sufficiently small $\Delta t$, when $E$ is continuously differentiable and $S(t)$ is bounded.. In Appendix B, we prove that $\epsilon<1/4$ suffices to guarantee this for MWU in two-person general-sum game; indeed, the proof covers graphical polymatrix games too, with a smaller upper bound on $\epsilon$. The proof uses an appropriate variant of the inverse function theorem.

At time , the solution to the system of ODEs can be locally written as

while volume at time $t$ can be computed by

in which $\mathbf{I}$ is the identity matrix. By expanding the determinant in the RHS, we have

Dividing both sides by $t$, and taking the appropriate limit as $t\searrow 0$ completes the proof.

Exponentially Increasing Volume. Here we focus on MWU discrete-time updates with step-size $\epsilon$. We may view a MWU update as equivalent to a continuous-time dynamic in the time interval $[0,\epsilon]$, with the function value $E$ unchanged during the updates within this time interval. Consequently, the $\mathcal{O}(t^{2})$ term in (5), which was to account for the changes in $E$, disappears. By following the above computations, given a measurable set $S$, and let $S^{\prime}$ be the flow of $S$ after one time step, we have

If one can show that there exists a $\delta>0$ such that for all $s\in S$, the integrand is at least $1+\delta$, then we have $\mathsf{volume}(S^{\prime})\geq(1+\delta)\cdot\mathsf{volume}(S)$. If this holds in every time step, then the volume increases exponentially at a rate of at least $(1+\delta)^{t}$.

Volume Change of Discrete Multiplicative Weights Updates

Next, we consider the discrete analogue of the system (3), which is exactly the MWU algorithm with step-size $\epsilon$. Our calculations in this section are for two-person general-sum games, where $\mathbf{A},\mathbf{B}$ can be arbitrary.

Following the notation in Theorem 2, we rewrite the system (3) as $\dot{\mathbf{r}}=E(\mathbf{r})$, where $\mathbf{r}=(\mathbf{p},\mathbf{q})$. MWU algorithm is then equivalent to the vector-form update rule $\phi(\mathbf{r})~{}=~{}\mathbf{r}+\epsilon\cdot E(\mathbf{r})$. By (6), we are interested in the determinant of the following matrix:

Observe that $\frac{\partial E}{\partial\mathbf{r}}$ has the properties of the matrix $\mathbf{Z}$ appeared in Section 2.2. Thus, $\det(\mathbf{M})$, which is the integrand in (6), is of the form $1+C(\mathbf{r})\cdot\epsilon^{2}+\mathcal{O}(\epsilon^{4})$, where $C(\mathbf{r})$ can be computed using (4). Hence, when $\epsilon$ is sufficiently small, the value of $C(\mathbf{r})$ will be decisive for volume change. Clearly, $C(\mathbf{r})$ is a function of $\mathbf{r}$, but we shall see that it is actually a function of $G(\mathbf{r})$, the corresponding primal variables.

Next, we compute $C(\mathbf{r})$ explicitly for two-person general-sum games. Recall that $\mathbf{M}$ is a $(J\cup K)\times(J\cup K)$ squared matrix. Let $(\mathbf{x},\mathbf{y})=G(\mathbf{r})$. Due to the structure of $\frac{\partial E}{\partial\mathbf{r}}$, all diagonal entries of $\mathbf{M}$ are $1$. For any distinct $j_{1},j_{2}\in J$ and distinct $k_{1},k_{2}\in K$, $M_{j_{1}j_{2}},M_{k_{1},k_{2}}=0$. For $j\in J$ and $k\in K$, we have

Analogously, $M_{kj}~{}=~{}\epsilon x_{j}\cdot(B_{jk}-[\mathbf{B}^{\mathsf{T}}\mathbf{x}]_{k})$. By (4),

As promised, $C(\mathbf{r})$ eventually depends on $(\mathbf{x},\mathbf{y})=G(\mathbf{r})$ only, but not explicitly on $\mathbf{r}=(\mathbf{p},\mathbf{q})$. Expanding the RHS yields:

Exponentially Increasing Volume in Two-Person Zero-sum Games

In any two-person zero-sum game $(\mathbf{A},-\mathbf{A})$, at any point $\mathbf{r}$ in which each entry is a finite number, $C(\mathbf{r})\geq 0$. Furthermore, the equality holds if and only if the game matrix $\mathbf{A}$ can be written in the following form for some real numbers $a_{1},a_{2},\cdots,a_{n},b_{1},b_{2},\cdots,b_{m}$:

Before proving the lemma, we point out that a zero-sum game with matrix (9) is “trivial”, since both players have a dominant strategy: for Player 1, the dominant strategy is $\operatorname*{arg\,max}_{j\in J}a_{j}$, while the dominant strategy of Player 2 is $\operatorname*{arg\,max}_{k\in K}b_{k}$. In this case, the limit behaviour of MWU is easy to derive: eventually, each player will play exclusively on her own dominant strategy.

For a two-person zero-sum game, $B_{jk}=-A_{jk}$. By (8),

We consider an underlying probability distribution where the tuple $(j,k)$ is chosen with probability $x_{j}y_{k}$. Then we can write

Next, we simplify the last three terms in the RHS.

Since the underlying distribution is the product distribution induced by $\mathbf{x}$ and $\mathbf{y}$, we also have

completing the proof of the first part of the lemma.

To prove the second part of the lemma, first note that since the entries in $\mathbf{r}$ are all finite numbers, $(\mathbf{x},\mathbf{y})=G(\mathbf{r})$ are fully-mixed. Thus, in the application of the Cauchy-Schwarz inequality above, it is tight if and only if $A_{jk}-[\mathbf{A}\mathbf{y}]_{j}+[\mathbf{B}^{\mathsf{T}}\mathbf{x}]_{k}$ are identical for all $j\in J$ and $k\in K$. Next, we prove that the latter condition holds if and only if $\mathbf{A}$ has the form of (9):

$(\Rightarrow)$ Suppose that at some $\mathbf{r}$ we have $A_{jk}-[\mathbf{A}\mathbf{y}]_{j}+[\mathbf{B}^{\mathsf{T}}\mathbf{x}]_{k}=d$ for all $j\in J,k\in K$. Then each $A_{jk}$ can be written as $d+[\mathbf{A}\mathbf{y}]_{j}-[\mathbf{B}^{\mathsf{T}}\mathbf{x}]_{k}$. We are done by setting $a_{j}=d+[\mathbf{A}\mathbf{y}]_{j}$ and $b_{k}=[\mathbf{B}^{\mathsf{T}}\mathbf{x}]_{k}$ in (9). ∎

Our next target is to show that the second-order coefficient $C(\mathbf{r})$ is bounded away from zero under suitable conditions. To begin, we first let

Observe that for any $\mathbf{r}\in R(\delta)$, $(\mathbf{x},\mathbf{y})=G(\mathbf{r})$ are fully-mixed, and every product $x_{j}y_{k}\geq\delta^{2}$.

Recall that $C(\mathbf{r})$ can be zero only when the underlying zero-sum game is trivial. Thus, naturally, a lower bound on $C(\mathbf{r})$ will depend on the distance between the game matrix $\mathbf{A}$ and the family of those trivial matrices. Accordingly, we consider the parameter

Thus, by the definition of $c(\mathbf{A})$, in $R(\delta)$, the gap is at least $\delta^{2}\cdot(c(\mathbf{A})/2)^{2}=\delta^{2}\cdot c(\mathbf{A})^{2}/4$.

After having a concrete lower bound on $C(\mathbf{r})$, we will still need to bound the higher order terms. Recall that $\det(\mathbf{M})$ can be written in the form $1+C\epsilon^{2}+\mathcal{O}(\epsilon^{4})$. We need a more explicit expansion using the Leibniz formula to bound the higher-order terms.

For each $\min\{n,m\}\geq i\geq 2$, there are at most $\binom{n}{i}\cdot\binom{m}{i}\cdot(i!)^{2}$ terms in the summation of the Leibniz formula with factor $\epsilon^{2i}$. Each of such terms is a product of $2i$ off-diagonal entries of $\mathbf{M}$, while the absolute value of each such entry of $\mathbf{M}$ can be bounded by $2\epsilon$. Overall, the sum of all terms with factor $\epsilon^{2i}$ is bounded by $\binom{n}{i}\cdot\binom{m}{i}\cdot(i!)^{2}\cdot(2\epsilon)^{2i}~{}\leq~{}(2\epsilon\sqrt{nm})^{2i}.$ Thus,

When $\epsilon\leq 1/(32n^{2}m^{2})$, we have $(2\sqrt{nm})^{4}\epsilon+(2\sqrt{nm})^{6}\epsilon^{3}+\cdots\leq 1$. Consequently, when $\epsilon\leq\min\{1/(32n^{2}m^{2})~{},~{}\delta^{2}\cdot c(\mathbf{A})^{2}/8\}$, we have $\det(\mathbf{M})~{}\geq~{}1+\frac{\delta^{2}\cdot c(\mathbf{A})^{2}}{8}\cdot\epsilon^{2}.$

Let $\overline{T}$ be a time such that for all $t\in\{0\}\cup[\overline{T}-1]$, $S(t)\subset R(\delta)$. Then for any $t\in[\overline{T}]$,

Consequently, the Lyapunov time of the system before reaching $R(\delta)$ is at most $\mathcal{O}(1/(\delta^{2}\epsilon^{2}))$, where the hidden constant depends on the game matrix $\mathbf{A}$ only.

The interpretation of the above theorem is: as long as the MWU algorithm with some sufficiently small step-size remains in some strict interior of the primal space, the volume of the flow of MWU in the dual space increases exponentially with a rate of at least $(1+\Theta(\epsilon^{2}))^{t}$.

2 Reaching Boundary: Exponential Lower Bound vs. Polynomial Upper Bound on Volume

Theorem 4 leaves one question: for how long will $S(t)$ stay within $R(\delta)$. To answer this question, a key observation is that in the dual space, in every time step of the MWU flow, each entry of $\mathbf{p},\mathbf{q}$ will change within the interval $\pm\epsilon$. Hence, unconditionally (not only for zero-sum games, but also for general-sum games), $S(t)$ must be a subset of the following rectangular hyper-box:

Consequently, the volume of $S(t)$ is unconditionally upper bounded by $\mathcal{O}((\epsilon t)^{m+n})$; note that this bound is $\mathcal{O}(\textsf{poly}(t))$ by viewing $m,n,\epsilon$ as fixed parameters.

However, the volume lower bound in Theorem 4 is exponential in $t$. Thus, the upper and lower bounds are incompatible when $t$ gets large, implying that $S(t)$ can only stay within $R(\delta)$ for at most the first positive root $t$ of the following equation:

Note that when $t=0$, the LHS is strictly less than the RHS, since $S$ is strictly contained in a hypercube of side length $\gamma$. Also, when $t\nearrow\infty$, the LHS is asymptotically larger than the RHS. Thus, a positive root of the equation must exist.

Indeed, the same argument holds so long as the volume lower bound on the LHS of (10) is $\omega(t^{m+n})$. This allows us to generalize to MWU algorithm with diminishing step-sizes. We present the analogous corollary here, and defer the details to Appendix C.1.

Then there exists a starting point in $S$ such that its flow will eventually reach the outside of $R(\delta)$; consequently, there is a dense set of starting points which their flows will eventually reach the outside of $R(\delta)$.

The conditions on $\{\epsilon_{t}\}$ can be satisfied by a step-size sequence which is asymptotically like those used in regret minimization: $\epsilon_{t}=\min\left\{\frac{1}{4+\kappa_{1}}~{},~{}\frac{4\sqrt{m+n+\kappa_{2}}}{\delta\cdot c(\mathbf{A})}\cdot\frac{1}{\sqrt{t}}\right\}=\Theta\left(\frac{1}{\sqrt{t}}\right),$ where $\kappa_{1},\kappa_{2}>0$.

We note that while Theorem 4 is a novel type of result, Corollaries 5 and 6 are weaker than the main results in . However, the proofs presented here avoids the need to distinguish between games with fully-mixed NE or not. Corollary 5 also provides an explicit time bound (the first positive root of (10)) for reaching the boundary. More importantly, in Section 7, we will see that the technique (exponential lower bound vs. polynomial upper bound) used for proving the two corollaries can be generalized to prove some novel and interesting results about some Rock-Paper-Scissors games (for eager readers, please see Theorem 12).

Generalization to the Follow-The-Regularized-Leader Algorithm

Using this more general update rule, the results presented in this section can extend to settings where

players use MWU with different step-sizes: we just need to scale up or down the players’ regularizer functions by constant factors;

different players using different diminishing-step-sizes, since our volume analysis can actually permit the regularizer functions be changed over time (so long as they do not violate the requirements we will impose soon); recall that Bailey and Piliouras imposed a requirement on the step-size sequences used by different players;

different players mix-and-match dynamics, i.e., the players can use entirely different types of regularizers.

In zero-sum games, we want to reproduce an analysis for general FTRL as in Section 4. In full generality it is rather clumsy. Thus, we focus on the special cases when

$h_{i}(\mathbf{x}_{i})=\sum_{j\in S_{i}}h_{ij}(x_{ij})$ is separable and second-continuously-differentiable in the relative interior of the primal space;

for all $x_{ij}>0$, $h_{ij}^{\prime\prime}(x_{ij})$ is strictly positive, i.e., $h_{ij}$ is strictly convex; and

the corresponding FTRL dynamic guarantees $\mathbf{x}_{i}$ stays full-mixed.This condition holds if $\lim_{x_{ij}\searrow 0}h^{\prime}_{ij}(x_{ij})=-\infty$ for all $i,j$.

Next, we explain how the previous analyses in this paper can be generalized to FTRL algorithm in two-person zero-sum games.

Two-person Zero-sum Game. Again, we focus on showing $C(\mathbf{r})\geq 0$, and defer all other details and result statements to Appendix D. Recall the system (3), which we rewrite here:

Keep in mind that here $\mathbf{x}$ is a function of $\mathbf{p}$ while $\mathbf{y}$ is a function of $\mathbf{q}$, which we do not write out explicitly for two reasons: first, the explicit formula might be complicated, and second, for the need of computing the Jacobian of the system, knowing (11) suffices. As in Section 3, in the matrix $\mathbf{M}$, the diagonal entries are all $1$, and $M_{j_{1}j_{2}}=M_{k_{1}k_{2}}=0$ for any distinct $j_{1},j_{2}\in J$ and distinct $k_{1},k_{2}\in K$. For $j\in J,k\in K$, by (11),

To proceed, we consider $C(\mathbf{r})\left/\left[\left(\sum_{j\in J}\bar{x}_{j}\right)\left(\sum_{k\in K}\bar{y}_{k}\right)\right]\right..$ This quantity is identical to the one given in (8), except that each $x_{j}$ is replaced by $\bar{x}_{j}/\left(\sum_{j\in J}\bar{x}_{j}\right)$ and each $y_{k}$ is replaced by $\bar{y}_{k}/\left(\sum_{k\in K}\bar{y}_{k}\right)$. Note that coincidentally, the replaced values form two probability distributions over $J$ and $K$ respectively, which we call them the shadow distributions of their corresponding FTRL update rule (see formal definition below). Therefore, all the arithmetic using expectations that leads to Lemma 3 carries through smoothly to prove that $C(\mathbf{r})\left/\left[\left(\sum_{j\in J}\bar{x}_{j}\right)\left(\sum_{k\in K}\bar{y}_{k}\right)\right]\right.\geq 0$ and hence $C(\mathbf{r})\geq 0$, while equality holds if and only if $\mathbf{A}$ has the form (9).

Given a FTRL update rule with $h_{i}(\mathbf{x}_{i})=\sum_{j\in S_{i}}h_{ij}(x_{ij})$ are separable and second-differentiable in the relative interior of the primal space, such that the update guarantees $\mathbf{x}_{i}$ stays full-mixed. The shadow distribution of the FTRL update rule at $\mathbf{x}_{i}$ is the distribution in which each $j\in S_{i}$ is realized with probability

The remaining analyses are spiritually identical to those presented in Sections 4.1 and 4.2, although some details (e.g., conditions for guaranteeing that a FTRL algorithm is injective) are different. We defer them to Appendix D but present the results here. Let

Also, let $\Delta(\delta)$ denote the minimum possible value in the shadow distributions of any $(\mathbf{x},\mathbf{y})=G(\mathbf{r})$, where $\mathbf{r}\in R(\delta)$. We note that $\Delta(\delta)$ is strictly positive for any $\delta$.

Let $\overline{T}$ be a time such that for all $t\in\{0\}\cup[\overline{T}-1]$, $S(t)\subset R(\delta)$. Then for any $t\in[\overline{T}]$,

Consequently, the Lyapunov time of the system before reaching $R(\delta)$ is at most $\mathcal{O}(1/(\Delta(\delta)^{2}\cdot\epsilon^{2}))$, where the hidden constant depends on the game matrix $\mathbf{A}$ only.

constant step-size satisfying the bound in Theorem 8; or

diminishing step-sizes satisfying $\lim_{t\rightarrow\infty}\epsilon_{t}=0$ and

Then there exists a starting point in $S$ such that its flow will eventually reach the outside of $R(\delta)$; consequently, there is a dense set of starting points which their flows will eventually reach the outside of $R(\delta)$.

Generalization to Graphical Constant-sum Games

Graphical Constant-sum Games. Next, we consider a striking generalization of two-person zero-sum game, in which there can be many players. We use $i$ or $i_{\bullet}$ to denote a player, and $j$ or $j_{\bullet}$ to denote a strategy. In a game with $m$ players, we number the players by $1,2,\cdots,m$, and let $S_{i}$ denote the strategy set of Player $i$, and $n_{i}:=|S_{i}|$. All variables in the primal space are now denoted by $x_{ij}$, and hence we denote the concatenation of all variables by $\mathbf{x}$. Again, we denote the variables in the dual space by $\mathbf{r}$.

A game with $m$ players is a graphical polymatrix game if the game is defined as follows: on an undirected graph $H=([m],E_{H})$, each edge $(i_{1},i_{2})\in E_{H}$ corresponds to a bimatrix game between Players $i_{1}$ and $i_{2}$ with strategy sets $S_{i_{1}}$ and $S_{i_{2}}$ respectively. It is worth noting that the strategy set of a Player $i$ in different bimatrix games is the same, and every time she plays the game, she must choose the same mixed strategy for all these bimatrix games. The payoff of a Player $i$ is the sum of payoffs she received from the bimatrix games she involves. Such a game is a graphical constant-sum game if the bimatrix game corresponded by every edge $(i_{1},i_{2})\in E$ is a two-person constant-sum game (different bimatrix games may have different constants). WLOG, we assume that each bimatrix game is indeed zero-sum.

Analysis. As we have already seen in Section 4, the key is to show that the value of second-order coefficient $C(\mathbf{r})$ is above zero. The rest of the analysis amounts to bounding $\epsilon$ to make sure that the effects of higher order terms are insignificant and $\det(\mathbf{M})$ is strictly positive.

For each zero-sum game corresponding to edge $(i_{1},i_{2})$, let $\mathbf{M}_{i_{1},i_{2}}$ denote the $\mathbf{M}$-matrix as if there were only these two players playing this zero-sum game. A crucial observation is:

the sum of all her payoffs in the bimatrix games which she involves,

if we focus on the sub-squared-matrix of $\mathbf{M}$ corresponding to Players $i_{1}$ and $i_{2}$,

By (4), the above observation leads to the following:

the second-order coefficient in $\det(\mathbf{M})$ is

exactly equal to the second-order coefficient in $\sum_{(i_{1},i_{2})\in E_{H}}\det(\mathbf{M}_{i_{1}i_{2}})$.

Recall that in Lemma 3, we have already shown that the second-order coefficient in each $\det(\mathbf{M}_{i_{1}i_{2}})$ is non-negative. Thus, we have proved that $C(\mathbf{r})\geq 0$, while equality holds if and only if every edge corresponds to a trivial zero-sum game of the form (9).

Accordingly, we say a graphical constant-sum game is non-trivial if at least one of the two-person constant-sum games corresponded by an edge is non-trivial.

We can define $R(\delta)$ in a similar manner as in Section 4.1. Same as in Section 4.1, a strictly positive lower bound on $C(\mathbf{r})$ in $R(\delta)$ can be derived for non-trivial game. For simplicity, we denote this lower bound by $\bar{C}(\delta)$.

However, unlike in a two-person zero-sum game, the coefficients of $\epsilon^{3}$ and other odd powers of $\epsilon$ in $\det(\mathbf{M})$ can be non-zero. So we need to derive a new bound on higher-order terms. Let $n=\sum_{i=1}^{m}n_{i}$. By expanding the determinant using the Leibniz formula, we have

When $\epsilon\leq 1/(64n^{6})$, we have $(2n)^{3}\epsilon^{0.5}+(2n)^{4}\epsilon^{1.5}+(2n)^{5}\epsilon^{2.5}+\cdots\leq\sqrt{2}$. Consequently, when $\epsilon\leq\min\{1/(64n^{6})~{},~{}\bar{C}(\delta)^{2}/8\}$, we have $\det(\mathbf{M})~{}\geq~{}1+\frac{\bar{C}(\delta)}{2}\cdot\epsilon^{2}.$

The analysis for diminishing step-sizes can also be extended easily. Indeed, the only modification needed is to replace the upper bound $1/4$ on $\epsilon$ to $1/(4\bar{d})$, where $\bar{d}$ is the maximum degree of the graph underlying the game, so as to guarantee that MWU is injective and $\mathbf{M}$ is strictly diagonally dominant (see Appendices B and C.1).

Suppose that MWU are used by all players with step-size satisfying

Let $\overline{T}$ be a time such that for all $t\in\{0\}\cup[\overline{T}-1]$, $S(t)\subset R(\delta)$. Then for any $t\in[\overline{T}]$,

constant step-size $\epsilon\leq\min\{1/(64n^{6})~{},~{}\bar{C}(\delta)^{2}/8\}$; or

where $\bar{d}$ is the maximum degree of the graph $H$.

Then there exists a starting point in $S$ such that before some finite time, its flow reaches the outside of $R(\delta)$. Consequently, there is a dense set of starting points in $R(\delta)$ which their flows will eventually reach the outside of $R(\delta)$.

Non-Zero-Sum Games: Generalized Rock-Paper-Scissors Games

Consider the Rock-Paper-Scissors (RPS) game with payoff matrices $(\mathbf{A},\mathbf{A}^{\mathsf{T}})$, where

This family of games are neither zero-sum nor strictly competitive when $P\neq Q$.To see why, assume $P<Q$. Suppose $\mathbf{x}=\mathbf{y}=(1/3,1/3,1/3)$, then the expected payoffs of both players are $(P-Q)/3$. However, if both players switch to $(1-2\kappa,\kappa,\kappa)$ for some tiny $\kappa$, the expected payoffs of both players will be $(4\kappa-2\kappa^{2})(P-Q)$, which is strictly larger than $(P-Q)/3$ when $\kappa$ is sufficiently small. The case $P>Q$ is symmetric.

Suppose both players employ MWU to play the game. Since the dimension is small, computing $\det(\mathbf{M})$ explicitly is easy (say, by using math software). Let $C_{1}:=2P^{2}+2Q^{2}+5PQ$ and $C_{2}:=(P-Q)^{2}$. Let $a=e^{{}^{p_{1}}}$, $b=e^{{}^{p_{2}}}$, $c=e^{{}^{p_{3}}}$, $d=e^{{}^{q_{1}}}$, $e=e^{{}^{q_{2}}}$ and $f=e^{{}^{q_{3}}}$. We have

Recall that after transformation $G$, $x_{1}=a/(a+b+c)$, $y_{1}=d/(d+e+f)$, and other $x_{j}$ and $y_{k}$ can be computed similarly. Thus, we can rewrite the second-order coefficient $C(\mathbf{r})$ in two different forms:

A necessary (but not sufficient) condition for $C(\mathbf{r})\leq 0$ is both of the followings hold:

one of $\frac{x_{1}}{x_{2}},\frac{x_{2}}{x_{3}},\frac{x_{3}}{x_{1}}$ or their reciprocals is less than $\frac{C_{2}}{2C_{1}}=\frac{(1-r)^{2}}{4+10r+4r^{2}}$, where $r:=Q/P$;

one of $\frac{y_{1}}{y_{2}},\frac{y_{2}}{y_{3}},\frac{y_{3}}{y_{1}}$ or their reciprocals is less than $\frac{C_{2}}{2C_{1}}$.

Accordingly, let $W$ denote the collection of all points $(\mathbf{p},\mathbf{q})$ in the dual space such that the corresponding $(\mathbf{x},\mathbf{y})$ satisfy the negations of both (A) and (B).Some readers might feel uncomfortable that we require the negations of both (A) and (B) to hold, since this seems stronger than needed. Our choice is conscious, as we will need both conditions for giving a good lower bound on $C(\mathbf{r})$. Then $x_{1}\geq 1/(1+4C_{1}/C_{2})$;This follows from $x_{1}+\frac{2C_{1}}{C_{2}}x_{1}+\frac{2C_{1}}{C_{2}}x_{1}~{}\geq~{}x_{1}+x_{2}+x_{3}~{}=~{}1$. the same lower bound holds for other $x_{j},y_{k}$ too. Thus, in $W$, we can lower bound $C$ by the AM-GM inequality:

Note that this bound is strictly positive as $6C_{1}>3C_{2}$ always.

By observing that outside $W$, at least one of $x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}$ must be strictly less than $\frac{C_{2}}{2C_{1}+C_{2}}$,For instance, say $x_{1}/x_{2}<\frac{C_{2}}{2C_{1}}$, then we have $x_{1}/(1-x_{1})<\frac{C_{2}}{2C_{1}}$, which leads to $x_{1}<\frac{C_{2}}{2C_{1}+C_{2}}$. and by bounding the higher order terms in $\det(\mathbf{M})$ appropriately, we can use the proof technique behind Corollaries 5 and 6 to derive the theorem below.

Suppose two players employ MWU to play RPS game (12). Let $w$ be an interior point in $W$, let $N(w)\subset W$ be a neighbourhood around $w$ with positive volume. If both players use either

constant step-size $\epsilon$ satisfying $\epsilon\leq\min\left\{\frac{1}{2592}~{},~{}\frac{6C_{1}-3C_{2}}{2(1+4C_{1}/C_{2})^{4}}\right\}$; or

a sequence of diminishing step-sizes $\{\epsilon_{t}\}$ satisfying

then there exists a finite time $T$ such that the flow of $N(w)$ at time $T$ does not lie entirely within $W$.

Consequently, there is a dense subset of starting points in $W$, such that the flow of each of them will eventually reach a point such that one of $x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}$ is strictly less than $\frac{C_{2}}{2C_{1}+C_{2}}$.

We discuss an interpretation of Theorem 12. Take $w$ be the NE. The table below lists some concrete values of $\frac{C_{2}}{2C_{1}+C_{2}}=\frac{(1-r)^{2}}{5+8r+5r^{2}}$ for different values of $r=Q/P$. Note that all the values are significantly below $\frac{1}{3}\approx 0.333$, the value in all entries of the NE. Theorem 12 implies that the flow of a dense set of starting points in any open neighbourhood of the NE will eventually get quite far away from the NE. This is a global instability result, in contrast with the classical local instability analysis which linearise the dynamic near the NE locally and compute the unstable and stable manifolds.

We present a slightly stronger version of the above theorem in Appendix E, which states that for diminishing step-sizes, the conclusion can actually be improved to: for any $\kappa>0$, two of $x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}$ are strictly less than $\frac{C_{2}}{2C_{1}+C_{2}}+\kappa$.

Non-Zero-Sum Games: 𝟐×𝟐22\mathbf{2\times 2} Bimatrix Games

We consider general $2\times 2$ bimatrix game here. It is well-known that after a reduction of game matrices, we can consider the following games only:

In this case, it is more convenient to use a transformation of RD by , as it will eliminate all $\mathcal{O}(\epsilon^{3})$ terms. We describe this transformation for two-person general-sum games.

Number the strategies of Player 1 by $\{1,2\cdots,n\}$ and those of Player 2 by $\{1,2,\cdots,m\}$, where $n,m\geq 2$. Let $f_{j}:=\ln x_{j}-\ln x_{n}$ for $j\in[n-1]$, and let $g_{k}=\ln y_{k}-\ln y_{m}$ for $k\in[m-1]$. Let $\mathbf{f}=(f_{1},f_{2},\cdots,f_{n-1})$ and $\mathbf{g}=(g_{1},g_{2},\cdots,g_{m-1})$ denote the dual variables. The dimension of the dual space is $n+m-2$. We also let $f_{n},g_{m}\equiv 0$, but keep in mind that they are not variables in the dual space. Note that the variables $\mathbf{x},\mathbf{y}$ before transformation can be recovered from $\mathbf{f},\mathbf{g}$ as follows:

The Jacobian of the system is an $(n+m-2)\times(n+m-2)$-squared matrix with all diagonal entries zero.

Back to $2\times 2$ bimatrix game. The Jacobian is a $2\times 2$ matrix for which we can compute its determinant directly:

In other words, the volume is globally strictly increasing if and only if $(R_{1}+R_{2})(R_{3}+R_{4})<0$. When $R_{1}=-R_{2}$ or $R_{3}=-R_{4}$, the volume is preserved even with the discrete updates.

One should note that, however, while globally strictly increasing volume implies reaching boundary, globally strictly decreasing volume does not imply the opposite. When $R_{1}>-R_{2}>0$, and $R_{3}+R_{4}>0$, the volume is decreasing, but since the first strategy of Player 1 is a strictly dominating strategy of her, it follows that $f_{1}\nearrow\infty$.

The only scenarios when the game has a unique NE which is fully mixed is when $R_{1},R_{2}$ have the same sign, $R_{3},R_{4}$ have the same sign, and $R_{1},R_{3}$ have different signs. In this case, volume is globally strictly increasing, indicating the fully mixed NE is globally unstable.

Acknowledgements

Yun Kuen Cheung and Georgios Piliouras acknowledge SUTD grant SRG ESD 2015 097, MOE AcRF Tier 2 Grant 2016-T2-1-170, grant PIE-SGP-AI-2018-01 and NRF 2018 Fellowship NRF-NRFF2018-07.

References

Appendix A Figure 1

The game used is a classical zero-sum game called Matching-Pennies. The payoff matrix for Player 1 is

We use the transformation of ; see Section 8.

In both cases, we use MWU algorithm with step-size $\epsilon=0.1$. The evolved sets are coloured dark-green, orange, purple, lime, pink, blue and red in chronological order. In the left figure, the evolved sets are captured at times $0,500,1000,1500,2000,2500,3000$ respectively. In the right figure, the evolved sets are captured at times $0,300,600,900,1200,1500,1800$ respectively.

In the left figure, an outer region strictly contains an inner region, so it shows that the volume expands. Also, as time goes, the shape of the region goes from square-like to tornado like.

In the right figure, the regions move in clockwise direction around the origin. Their shapes get thinner, while their diameters grow quickly, indicating that chaos are occurring.

Appendix B MWU Algorithm is Injective in Graphical Polymatrix Games

Recall that $\bar{d}$ is the maximum degree of the graph underlying the graphical polymatrix game. For two-person general-sum game, $\bar{d}=1$.

Suppose the contrary that there are two points $\mathbf{r}_{1}$ and $\mathbf{r}_{2}$ such that they map to the same point $\mathbf{r}^{\prime}$ after one round of MWU. Since the payoff received by each player is within the interval of $\pm\bar{d}$, we have $\|\mathbf{r}_{1}-\mathbf{r}^{\prime}\|,\|\mathbf{r}_{2}-\mathbf{r}^{\prime}\|\leq\bar{d}\epsilon$, and hence $\|\mathbf{r}_{1}-\mathbf{r}_{2}\|\leq 2\bar{d}\epsilon$. Our target is then to derive a contradiction by showing that within the ball $\overline{B}(\frac{\mathbf{r}_{1}+\mathbf{r}_{2}}{2},\bar{d}\epsilon)$, MWU is injective; observe that this ball includes both $\mathbf{r}_{1},\mathbf{r}_{2}$. We will use the following version of inverse function theorem [16, Theorem 3.1]:

Let $\mathbf{X},\mathbf{Y}$ be Banach spaces equipped with norms $\|\cdot\|_{\mathbf{X}},\|\cdot\|_{\mathbf{Y}}$ respectively. Let $\overline{B}(x_{0},r_{0})$ be a closed ball in $\mathbf{X}$. Let $f:\overline{B}(x_{0},r_{0})\rightarrow\mathbf{Y}$ be a function so that for some invertible linear map $L:\mathbf{X}\rightarrow\mathbf{Y}$ and some $\rho<1$,

Then $f$ is injective on $\overline{B}(x_{0},r_{0})$.

Suppose that $\|\mathbf{r}_{a}-\mathbf{r}_{b}\|=\kappa$. Then observe that when mapped back to the primal space, every entry in $\mathbf{x}(\mathbf{r}_{a})$ will be within a multiplicative factor of $e^{2\kappa}$ of the corresponding entry in $\mathbf{x}(\mathbf{r}_{b})$. Thus, when we focus on the entry of $E$ that corresponds to Player $i$ and her strategy $j$, we have

where the final inequality holds when we assume $\bar{d}\epsilon<1/4$, so that $2\kappa\leq 4\bar{d}\epsilon<1$ and hence $e^{2\kappa}-1\leq 4\kappa$.

Consequently, $\epsilon\|E(\mathbf{r}_{b})-E(\mathbf{r}_{a})\|\leq 4\bar{d}\epsilon\kappa$. For the condition required in the above theorem to hold, it suffices to restrict that $4\bar{d}\epsilon<1$, i.e., $\epsilon<1/(4\bar{d})$.

Appendix C Two-person Zero-sum Games

Here, we consider the case when the step-sizes used by both players are not constants. For simplicity, we here assume that both players use the same diminishing step-sizes $\{\epsilon_{t}\}$. Also, we assume that $\epsilon_{1}<1/4$ and $\lim_{t\rightarrow\infty}\epsilon_{t}=0$. Let $t_{0}$ be the first time such that $\epsilon_{t}\leq\bar{\epsilon}(\delta)$. Then the inequality in Theorem 4 can be replaced by: for any $t\geq t_{0}$,

To proceed, we need to argue that if $\mathsf{volume}(S(0))$ is strictly positive, then $\mathsf{volume}(S(t_{0}))$ is also strictly positive. In Appendix C.2, we will prove that when $\epsilon<1/4$, the matrix $\mathbf{M}$ is strictly diagonally dominant; then by a use of Levy-Desplanques theorem, we can show that $\det(\mathbf{M})$ is strictly positive. Thus, when $S(0)$ has positive measure, $\mathsf{volume}(S(1))=\int_{S(0)}\det(\mathbf{M})\,\mathsf{d}V$ remains strictly positive. Inductively, we arrive at the conclusion that $\mathsf{volume}(S(t_{0}))$ remains strictly positive for any finite $t_{0}$.

If the summation is $\omega(\log t)$, then $\mathsf{volume}(S(t))=\omega(\textsf{poly}(t))$. By the logic identical to that in Section 4.2, the conclusion in Corollary 5 applies when the step-sizes are diminishing gently. The next theorem describes the precise conditions required on $\{\epsilon_{t}\}$.

C.2 𝐌𝐌\mathbf{M} is Strictly Diagonally Dominant

For each $j\in J$, $M_{jj}=1$, for any $j^{\prime}\in J$ and $j^{\prime}\neq j$, $M_{jj^{\prime}}=0$, and

Consequently, when $\epsilon<1/4$, the matrix $\mathbf{M}$ is strictly diagonally dominant.

By Levy-Desplanques theorem, $\mathbf{M}=\mathbf{M}(\epsilon)$ is non-singular for any $\epsilon\in[0,1/4)$. Thus, $\det(\mathbf{M}(\epsilon))$ is non-zero for any $\epsilon\in[0,1/4)$.

Now, suppose the contrary that $\det(\mathbf{M}(\epsilon^{\prime}))\leq 0$ for some $\epsilon^{\prime}\in[0,1/4)$. Since $\det(\mathbf{M}(\epsilon))$ is a continuous function w.r.t. $\epsilon$, by the intermediate value theorem, there exists an $\epsilon^{\prime\prime}\in[0,\epsilon^{\prime}]$ such that $\det(\mathbf{M}(\epsilon^{\prime\prime}))=0$, a contradiction.

Appendix D Follow-The-Regularized-Leader Dynamics

D.2 FTRL Algorithm is Injective in Two-Person General-Sum Games

As was done in Appendix B, to show that the algorithm is injective, it suffices to show that FTRL algorithm is injective inside the ball we introduced in Appendix B. Here $\bar{d}=1$. Recall that notation $\mathbf{r}=(\mathbf{p},\mathbf{q})$ for two-person general-sum games.

Suppose that $\|\mathbf{r}^{b}-\mathbf{r}^{a}\|=\kappa$. To bound the term in RHS, we consider the line segment from $\mathbf{r}^{a}$ to $\mathbf{r}^{b}$, which is parametrized by $$. Recall the matrix$\mathbf{M}$which we computed in Section 5. For any$j\in J$,$k\in K$,$M_{jk}$is actually$\epsilon\cdot\frac{\partial E_{j}}{\partial q_{k}}$. Then we have

Thus, by setting $u$ to be the inverse of the maximum value of $\sum_{k\in K}\bar{y}_{k}$ in the ball, we have

Then by restricting $\epsilon\leq u/4$, we have

Thus, we can set the parameter $\rho$ in Theorem 13 to be $1-u/2$.

We still need to provide a concrete value of $u$. Towards this, for any $\delta>0$, we define

Suppose that $\mathbf{r}^{a},\mathbf{r}^{b}\in R(\delta)$. It is actually possible that the line segment between $\mathbf{r}^{a}$ and $\mathbf{r}^{b}$ does not fully lie within $R(\delta)$, i.e., $R(\delta)$ is not convex. Therefore, $u$ might need to be strictly smaller than $1/\overline{H}(\delta)$.

the above inequality guarantees that all points in $\mathcal{L}$ has $x_{ij}$ value at least $\delta/2$.

By assumptions on $h$, the upper bound on $\epsilon$ is strictly positive, yet it can be arbitrarily close to zero, since there is nothing to prohibit that $h_{ij}^{\prime\prime}(z)$ being tiny (but positive) for a particular $z\geq\delta/2$. For instance, one may construct a regularizer $h_{ij}$ such that $h_{ij}^{\prime\prime}(z)\approx 0$ for all $z\geq\alpha$, but when $z<\alpha$ the value $h_{ij}^{\prime\prime}(z)$ gets much larger so that $\lim_{z\searrow 0}h^{\prime}_{ij}(z)=-\infty$. Then all three conditions on $h$ which we stated in Section 5 hold.

Of course, the above constructed regularizer is quite unnatural, so one should be able to improve our bounds for a more natural regularizer. Our key concern here, however, is just to provide a strictly positive upper bound on $\epsilon$, for any $\delta>0$. (The upper bound can depend on $\delta$.)

Anyway, by having the restriction on $\epsilon$, we can set $u$ to be $\overline{H}(\delta/2)$. In sum, we need the restriction

D.3 Analysis for Two-person Zero-sum Games

Again, we need to bound the higher order terms. As in Section 4.1, for each $\min\{n,m\}\geq i\geq 2$, there are at most $\binom{n}{i}\cdot\binom{m}{i}\cdot(i!)^{2}$ terms in the summation of the Leibniz formula with factor $\epsilon^{2i}$. Each of such terms is a product of $2i$ off-diagonal entries of $\mathbf{M}$, and its absolute value can be bounded as

Note that all $j_{a}$’s are distinct, while all $k_{b}$’s are also distinct.

By the AM-GM inequality, the RHS of the above inequality can be bounded by

Overall, the sum of all terms with factor $\epsilon^{2i}$ is bounded by

Following the calculations in Section 4.1, we impose an upper bound of

We will also need the following quantity to bound the gap when applied the Cauchy-Schwarz inequality. Let $\Delta(\delta)$ denote the minimum possible value in the shadow distributions of any $(\mathbf{x},\mathbf{y})=G(\mathbf{r})$, where $\mathbf{r}\in R(\delta)$. We note that $\Delta(\delta)$ is strictly positive for any $\delta$. Then in $R(\delta)$, we have

Thus, Theorem 4 holds for FTRL too, after replacing the upper bound on $\epsilon$ appropriately. This yields Theorem 8.

In Appendix C.1, we concern MWU with diminishing step-sizes. For FTRL with diminishing step-sizes, the analysis is essentially the same, except that we need a slightly different argument to show that $\mathsf{volume}(S(t_{0}))$ is strictly positive.

So for showing that $\det(\mathbf{M})$ is strictly positive, it suffices to show that $\det(\mathbf{M}^{\prime})$ is strictly positive.

The advantage of using $\mathbf{M}^{\prime}$ is that it allows us to reuse the calculations in Appendix C.2 (by appropriately replacing $\mathbf{x},\mathbf{y}$ with $\bar{x},\bar{y}$) to show that when $\epsilon<1/(4\cdot\overline{H}(\delta))$, $\mathbf{M}^{\prime}$ is strictly diagonally dominant and hence $\det(\mathbf{M}^{\prime}),\det(\mathbf{M})$ are both strictly positive. Thus, Corollary 6 holds for FTRL too, by replacing the upper bound on $\epsilon_{1}$ with appropriately, yielding Corollary 9.

Appendix E A Stronger Theorem for the Generalized Rock-Paper-Scissors Games

We can derive a slightly stronger theorem than Theorem 12. Here, we only present the result for diminishing step-sizes.

For any $\kappa,\delta>0$, let $W_{\kappa,\delta}$ denote the collection of all points $(\mathbf{p},\mathbf{q})$ in the dual space such that the corresponding $(\mathbf{x},\mathbf{y})$ satisfy either of the following two conditions:

all of $\frac{x_{1}}{x_{2}},\frac{x_{2}}{x_{3}},\frac{x_{3}}{x_{1}}$ and their reciprocals are larger than or equal to $\frac{C_{2}}{2C_{1}}+\kappa$, and at least two of the three entries in $\mathbf{y}$ are larger than or equal to $\delta$; or

all of $\frac{y_{1}}{y_{2}},\frac{y_{2}}{y_{3}},\frac{y_{3}}{y_{1}}$ and their reciprocals are larger than or equal to $\frac{C_{2}}{2C_{1}}+\kappa$, and at least two of the three entries in $\mathbf{x}$ are larger than or equal to $\delta$.

To understand why $W_{\kappa,\delta}$ is defined as above, we suppose the first condition above holds. WLOG, assume $y_{1},y_{2}\geq\delta$. Then in the first form of $C$, the second and third terms are non-negative, while the first term satisfies

Thus, the RHS of the above inequality can serve as a lower bound for $C$. Similarly, the same lower bound for $C$ holds if the second condition holds. Therefore, whenever one of the two conditions hold, we have a strictly positive lower bound for $C$. Following the logic behind Theorem 12, we have the following theorem.

Suppose two players employ MWU to play the RPS game (12). For any $\kappa,\delta>0$, let $w$ be an interior point in $W_{\kappa,\delta}$, let $N(w)\subset W_{\kappa,\delta}$ be a neighbourhood around $w$ with strictly positive volume. If both players use a sequence of diminishing step-sizes $\{\epsilon_{t}\}$ satisfying

then there exists a finite time $T$ such that the flow of $N(w)$ at time $T$ does not lie entirely within $W_{\kappa,\delta}$. Consequently, there is a dense subset of starting points in $W_{\kappa,\delta}$, such that the flow of each of them will eventually reach a point such that one of the following holds:

one of $x_{1},x_{2},x_{3}$ is strictly less than $\frac{C_{2}}{2C_{1}+C_{2}}+\kappa$, and one of $y_{1},y_{2},y_{3}$ is strictly less than $\frac{C_{2}}{2C_{1}+C_{2}}+\kappa$; or

two of $x_{1},x_{2},x_{3}$ are strictly less than $\delta$; or