First-order (coarse) correlated equilibria in non-concave games

Given our motivations, we seek notions of equilibrium that are tractably computable given access to payoff gradients independent of concavity assumptions on the payoffs, and that contain (coarse) correlated equilibria of normal form games as special cases. Towards this end, we build upon the recent work of [18], who considered a local variant of $\Phi$ regret traditionally considered in literature (cf. [39]), and showed two such families of local strategy modifications are tractably computable via online gradient ascent. Our key insight is that the $\delta$-strategy modifications contained in their work are generated by gradient fields of a suitable family of functions.

To provide intuition for our arguments, consider a smooth game with a set of players $N$, compact and convex action sets $X_{i}$ for each player $i$ (with their product denoted $X$), and smooth utility functions $u_{i}$ for each player $i$. Suppose all players implement online gradient ascent with the same adaptive step sizes $\eta_{t}$ at time $t$. That is, if player $i$ chooses action $x_{i}^{t}$ at time $t$, they will fix

To impose a correlated distribution $\sigma$ of play as an equilibrium concept, let each $x^{t}$ is drawn with probability proportional to $\eta_{t}$. Now consider a “local” deviation for player $i$, in which they consider deviating in their strategies along the gradient of a function $h_{i}$. That is, for $\delta>0$, they consider $x_{i}^{t}\mapsto\Pi_{X_{i}}\left[x_{i}^{t}+\delta\nabla_{i}h_{i}(x_{i}^{t})\right]$.

What is the possible change in payoffs by such a local deviation? Consider for simplicity the case when no projections are ever required for the purposes of local deviations and during online gradient ascent, i.e. both $\Pi_{X_{i}}\left[x_{i}^{t}+\delta\nabla_{i}h_{i}(x_{i}^{t})\right]=x_{i}^{t}+\delta\nabla_{i}h_{i}(x_{i}^{t})$ and $\Pi_{X_{i}}\left[x_{i}^{t}+\eta_{t}\nabla_{i}u_{i}(x^{t})\right]=x_{i}^{t}+\eta_{t}\nabla_{i}u_{i}(x^{t})$. In this case, the change in utility is given, after $T$ time steps and ignoring terms of order $\delta^{2}$,

The second equality here is by considering a Taylor expansion of $u_{i}(x_{i}+\delta\nabla_{i}h_{i}(x_{i}),x_{-i})$, and the fourth inequality follows from a Taylor expansion of $h_{i}(x^{t}_{i}+\delta\nabla_{i}u_{i}(x^{t}))$. As a consequence, if the function $h_{i}$ which generates these local deviations are bounded, under suitable assumptions for the step sizes, the regret against $h_{i}$ of order $O(\delta)$ would vanish with time. Dividing both sides by $\delta$ and letting $\delta\rightarrow 0$, we see that the expectation of $\left\langle\nabla_{i}h_{i}(x_{i}^{t}),\nabla_{i}u_{i}(x^{t})\right\rangle$, the “first-order local regret”, would vanish also.

However, when projections are involved, we would need to bound losses we obtain due to terms of the form $\left\langle x^{t+1}_{i}-x_{i}^{t}+\delta\nabla_{i}h_{i}(x_{i}^{t}),\nabla_{i}u_{i}(x^{t})\right\rangle$, $\left\langle x^{t+1}_{i}-x_{i}^{t}+\eta_{t}\nabla_{i}u_{i}(x^{t}),\nabla_{i}h_{i}(x_{i}^{t})\right\rangle$. This turns out to be a non-trivial task. Yet, when we consider the continuous motion induced by the game dynamics, defined via the differential equation $\dot{x}(\tau)=\Pi_{\mathcal{TC}_{X_{i}}\left(x_{i}(\tau)\right)}\left[\nabla_{i}u_{i}(x(\tau))\right]$, no such loss occurs and we observe a declining regret bound through very straightforward differential arguments (cf. Section 3). This is via an argument on stationarity of the resulting distribution. Namely, given a smooth function $h:X\rightarrow\mathbb{R}$, each action profile $x\in X$ assigns a rate of change to $h$ via the projected gradient dynamics of the game; given $x(\tau)$,

and the expectation of this quantity over a time period $[0,\overline{\tau}]$ is simply equal to $(h(\overline{\tau})-h(0))/\overline{\tau}$, which converges to zero. Intuitively, the longer we let the curve trace out, the closer it becomes to forming a distribution invariant under time translation. Exchanging which vector is projected onto the tangent cone, we observe that

except for a set of measure zero on the curve traced by the projected gradient dynamics of the game. This motivates our two first-order notions of equilibrium, one based on local deviation, the other based on stationarity.

In particular, since our high level argument hints that projected gradient descent minimises regret with respect to the gradient field of any such function $h$, we identify the notion of coarseness to be so. Meanwhile, for more general correlated equilibria, we allow deviations generated by arbitrary set $F$ of vector fields on $X$.

As mentioned, the main technical barrier is in dealing with projections. Our chief technical innovation is thus in Section 3.1, where we wriggle our hands free of dealing with them directly, by constructing an appropriate continuous (and almost everywhere differentiable) curve over which regret analysis is simple. We essentially convert the sequence of play $x^{1},x^{2},\dots$ to a continuous curve $x(\tau)$, “connecting the dots” by projecting a partial gradient step, scaled by some factors $\mu_{t}$ which allows us to modify the probability distribution we consider over $x^{t}$. For instance, suppose that the initial strategies are $x^{0}$, and each player $i$ fixes $x_{i}^{1}=\Pi_{X_{i}}\left[x_{i}^{0}+\eta_{0}\cdot\nabla_{i}u_{i}(x^{0})\right]$. We interpret this step as having been taken “over time $\mu_{t}\eta_{t}$”, i.e. we let $x(0)=x_{i}^{0}$ and $x(\mu_{0}\eta_{0})=x_{i}^{1}$. To extend to $x(\tau)$ continuously, we then let $x_{i}(\tau)=\Pi_{X_{i}}\left[x_{i}^{0}+(\tau/\mu_{0})\cdot\nabla_{i}u_{i}(x^{0})\right]$ for each player $i$. This extension is continuous on $[0,\mu_{0}\eta_{0}]$, and more desirably, is differentiable almost everywhere with respect to the Lebesgue measure on the interval. Moreover, the choice $\mu_{t}=1$ corresponds to a simulation of the gradient dynamics of the game, whereas $\mu_{t}=1/\eta_{t}$ roughly corresponds to a uniform distribution over $x^{t}$.

Bounding the regret then amounts of bounding the difference between $\dot{x}(\tau)$, the velocity along the curve given by our “approximate” gradient dynamics for the game, and $\Pi_{\mathcal{TC}_{X_{i}}\left(x_{i}(\tau)\right)}\left[\nabla_{i}u_{i}(x(\tau))\right]$, the actual velocity prescribed by the dynamics of the game. When the boundary of the action sets are regular hypersurfaces in Euclidean space, the difference turns out to be small, whereas if the actions sets are polyhedra satisfying a positivity condition (Definition 10), the difference only depends on the Lipschitz moduli of the utilities. We remark that the sufficient conditions we identify for the actions sets are satisfied by many settings of interest – it includes e.g. the sphere, the hypercube or the simplex. Consequently, we obtain proof that projected gradient ascent with equal step sizes has a universal approximation property.

That aggregate regret over the players against first-order deviations generated by any such function $h:X\rightarrow\mathbb{R}$ depends crucially on the fact that when all players use the same step sizes, the time sequence $(x^{t})$ simulates the underlying continuous projected gradient dynamics of the game. Intuitively, zero regret in the first-order against any such deviation provides a convex description of solutions to the projected gradient dynamics, once the time-ordering information on the curve is erased. Thus, with potentially different step sizes which might have different asymptotic rates of decrease, or when some players can be adversarial, our methods fail to guarantee coarse regret bounds in such generality. However, first-order regret is still vanishing, when the deviations are restricted to vary only on players who do use the same step size. The result depends on a similarly defined curve $x:[0,T]\rightarrow X$, which interpolates the gradient steps of relevant players.

In Section 4, we turn our attention to first-order correlated equilibria. Here, we observe that the usual methods for $\Phi$-regret minimisation work for computing both stationary and local equilibria; the latter if the vector fields satisfy a tangency condition.

The question is whether there exists an interesting setting in which fixed-point computation can be performed tractably. We identify one setting; when each vector field is affine-linear, each fixed point computation reduces to minimising a quadratic function. Example 1 shows that a careful selection of such vector fields results in last iterate convergence to the equilibrium in the matching pennies game. This suggests that a centralised learning algorithm might not require optimism [32] or explicit second-order corrections to the utility gradients [52] to obtain last iterate convergence to equilibrium in games.

In Section 5, we focus on equilibrium analysis. Our goal here is to determine how equilibrium can be reasoned about. Towards this end, we adapt in Section 5.1 the usual primal-dual framework for equilibrium analysis, bounding the expectation of a quantity defined over the set of outcomes (e.g. welfare, distance to an equilibrium) for our equilibrium concepts. Our observation is that for a primal problem which seeks a best or worst-case correlated equilibrium, a dual solution provides information on the gradient dynamics of the game. In particular, if the primal problem maximizes expected worst-case distance to an equilibrium and there exists a dual solution of value $0$, the solution is a Lyapunov function by its usual definition. For correlated equilibrium, the dual problem is instead that of a vector field fit problem, searching for a linear or conical combination of vector fields in $F$ which are well-aligned with the utility gradients.

Finally, in Section 5.2 we look at how first-order local equilibria look like for continuous extensions of normal form games. Here, we find an interesting equivalence result.

The equivalence here is in terms of equilibrium constraints on the resulting distributions of action profiles; a first-order correlated equilibrium defined with respect to an appropriate set $F$ of vector fields induces a distribution on action profiles that correspond to the one of the above equilibrium concepts. Moreover, the converse statement is also true. It is in this sense that the usual methods for primal-dual analysis of price of anarchy are given an interpretation as “Lyapunov function estimation problems”. The equivalence also shows that our equilibrium notions may be considered true refinements and extensions of the usual notions of (coarse) correlated equilibria to the richer setting of non-concave games. Finally, we remark that as desired, the set of vector fields corresponding to the incentive constraints for (average) coarse correlated equilibrium satisfy also our notion of coarseness for first-order correlated equilibria, justifying our nomenclature.

Game theoretic analysis of multi-agent systems is often based on first the assertion of a concept of equilibrium as an expected outcome, followed by an investigation of its properties. The classical assumption is that with self-interested agents, the outcome of the game should be a Nash equilibrium, which exists for finite normal-form games [62], or more generally, concave games [70].

Diverging from classical equilibrium theory for convex markets, the outcome of a game need not be socially optimal. The algorithmic game theory perspective has then been to interpret the class of equilibria in question from the lens of approximation algorithms. First proposed by [51], the price of anarchy measures the worst-case ratio between the outcome of a Nash equilibrium and the socially optimal one. A related concept measuring the performance of the best-case equilibrium outcome, the price of stability was first employed by [78] and named so in [3]. Since then, a wealth of results have followed, proving constant welfare approximation bounds for e.g. selfish-routing [71], facility location [80], a variety of auction settings including single-item [49] and simultaneous [21] first-price auctions, simultaneous second-price auctions [20], hinting at good performance of the associated mechanisms in practice. Meanwhile, deteriorating price of anarchy bounds, such as those for sequential first-price auctions [56], are interpreted as arguments against the use of such mechanisms.

However, the assertion that the outcome of a game should be a Nash equilibrium is problematic for several reasons, despite the guarantee that it exists in concave games. It is often the case that multiple equilibria exists in a game, in which case we are faced with an equilibrium selection problem [47]. Moreover, Nash equilibrium computation is computationally hard in general, even in the setting of concave games where its existence is guaranteed. In general determining whether a pure strategy NE exists in a normal-form game is NP-complete [27], and even for two player normal form games finding an exact or approximate mixed Nash equilibrium is PPAD-complete [17, 30, 28]. Similar results extend to auction settings; for instance, (1) finding a Bayes-Nash equilibrium in a simultaneous second-price auction is PP-hard [23], even when buyers’ valuations are restricted to be either additive or unit-demand, and (2) with subjective priors computing an approximate equilibrium of a single-item first-price auction is PPAD-hard [38], a result that holds also with common priors when tie-breaking rule is also part of the input [26].

Some answers to this problem come from learning theory. First, for special classes of games, when each agent employs a specific learning algorithm in repeated instances of the game, the outcome converges in average play to Nash equilibria. This is true for fictitious play [15] for the empirical distribution of players’ actions in a variety of classes of games, including zero-sum games [69], $2\times n$ non-degenerate normal form games [8], or potential games [59]. For the case of zero-sum games, the same is true for a more general class of no-(internal [16] or external [81]) regret learning algorithms, while for general normal-form games they respectively converge to correlated or coarse correlated equilibria – convex generalisations of the set of Nash equilibria of a normal form game. The price of anarchy / stability approach can then be extended to such coarse notions of equilibria, with the smoothness framework of [72] for robust price of anarchy bounds being a prime example.

Unfortunately, this perspective falls short of a complete picture for several reasons. First, learning dynamics can exhibit arbitrarily high complexity. Commonly considered learning dynamics may cycle about equilibria, as is the case for fictitious play [74] or for multiplicative weights update [14]. Worse, learning dynamics can exhibit formally chaotic behaviour [68, 25], bimatrix games may approximate arbitrary dynamical systems [4]. In fact, replicator dynamics on matrix games is Turing complete [5], and reachability problems for the dynamics is in general undecideable.

In the converse direction, the usual notion of no-regret learning can be too weak to capture learnable behaviour. In this case, the associated price of anarchy bounds may misrepresent the efficiency of actual learned outcomes. One motivating example here is that of auctions. For first-price single item auctions, in the complete information setting there may exist coarse correlated equilibria with suboptimal welfare, even though the unique equilibrium of the auction is welfare optimal [36]. Meanwhile, in the incomplete information setting with symmetric priors, whether coarse correlated equilibria coincide with the unique equilibrium depends on informational assumptions on the equilibrium structure itself [7] and on convexity of the priors [1]. This is in apparent contradiction with recent empirical work which suggest the equilibria of an even wider class of auctions are learnable when agents implement deep-learning or (with full feedback) gradient based no-regret learning algorithms [9, 10, 60].

This motivates the necessity of a more general notion of equilibrium analysis, stronger than coarse correlated equilibria for normal-form games and weaker than Nash equilibria, which nevertheless captures the guarantees of the above-mentioned settings and is tractable to approximate or reason about. For the case of auctions, one recent proposal has been that of mean-based learning algorithms [13], but even in that case convergence results of [31, 35] are conditional.

There are two approaches towards the resolution of this question which, while not totally divorced in methodology, can be considered distinct in their philosophy. One approach has been to consider “game dynamics as the meaning of a game” [67], inspecting the existence of dynamics which converge to Nash equilibria, and extending price of anarchy analysis to include whether an equilibrium is reached with high probability. The work on the former has demonstrated impossibility results; there are games such that any gradient dynamics have starting points which do not converge to a Nash equilibrium, and for a set of games of positive measure no game dynamics may guarantee convergence to $\epsilon$-Nash equilibria [11, 58]. Meanwhile, [66, 77] proposed the average price of anarchy as a refined performance metric accounting for the game dynamics. The average price of anarchy is defined as the expectation over the set of initial conditions for the welfare of reached Nash equilibria, for a fixed gradient-based learning dynamics for the game.

Another approach has been to establish the computational complexity of local notions of equilibria. This has attracted attention especially in the setting non-concave games, where the existence of Nash equilibria is no longer guaranteed, due to the success of recent practical advances in machine learning via embracing non-convexity [29]. However, approximate minmax optimisation is yet again PPAD-complete [34]. As a consequence, unless PPAD $\subseteq$ FP, a tractably approximable local equilibrium concept for non-concave games with compact & convex action sets must necessarily be coarser. Towards this end, [48, 46] define a notion of regret that is based on a sliding average of players’ payoff functions. Meanwhile, a recent proposal by [18] has been to define a local correlated equilibrium, a distribution over action profiles and a set of local deviations such that, approximately, no player may significantly improve their payoffs when they deviate locally pointwise in the support of the distribution. They are then able to show for two classes of local deviations, such an approximate local correlated equilibrium is tractably computable.

Our goal in this paper is then to address the question of an equilibrium concept which is (1) also valid for non-concave games, (2) is stronger than coarse correlated equilibria for normal form games, (3) is tractable to approximate, and (4) admits a suitable extension of the usual primal-dual framework for bounding the expectation of quantities over the set of coarse correlated equilibria. The latter necessitates not only a distribution of play, but also incentive constraints which are specified only depending on the resulting distribution and not its time-ordered history. We remark that framework of [48] falls short in the latter aspect when the cyclic behaviour of projected gradient ascent results in a non-vanishing regret bound. We thus turn our attention to generalising the work of [18] on a local notion of $\Phi$-equilibrium [40].

Strikingly, in doing so, we demonstrate the intrinsic link between such local notions of coarse equilibria and the dynamical systems perspective on learning in games. In particular, the two local notions of $\Phi$-equilibria defined in [18] are subclasses of what we dub local coarse correlated equilibria, distribution of plays such that agents in aggregate do not have any strict incentive for infinitesimal changes of the support of the distribution along any gradient field over the set of action profiles. The history of play induced by online (projected) gradient ascent then approximates such an equilibrium, by virtue that it approximates a time-invariant distribution for the game’s gradient dynamics. Extending the usual primal-dual scheme for price of anarchy bounds then reveals that any dual proof of performance bounds is necessarily of the form of a “generalised” Lyapunov function for the quantity whose expectation is to be bounded. The usual LP framework for coarse correlated equilibria is in fact contained in this approach, its dual optimal solutions corresponding to a “best-fit” quadratic Lyapunov function.

Our approach in proving our results combines insights previously explored in two previous works. The existence and uniqueness of solutions to projected dynamical systems over polyhedral sets is due to [33], and in our approximation proofs we also define a history over a continuous time interval. However, our analysis differs as we are not interested in approximating the continuous time projected dynamical system itself over the entire time interval; an approach that would doom our endeavour for tractable approximations in the presence of chaotic behaviour, which is not ruled out under our assumptions [25, 4]. Instead, we are interested in showing the approximate stationarity of expectations of quantities. Therefore, for projected gradient ascent, we suitably extrapolate the history of play into a piecewise differentiable curve, in the fashion of the projections curve studied by [57]. We then identify settings in which this curve moves approximately along the payoff gradients at each point in time via consideration of the properties of the boundary of the action sets in question.

Meanwhile, whereas Lyapunov-function based arguments is not new in analysis of convergence to equilibria in economic settings (e.g. [65]), in evolutionary game theory (c.f. [73] for an in-depth discussion), and in learning in games (e.g. [61, 82]), our perspective in bounding expectations of quantities appears to be relatively unexplored. Most Lyapunov-function based arguments in literature are concerned with pointwise (local) convergence to a unique Nash equilibrium, and work under the assumption of monotonicity or variational stability, or the existence of a potential function. The former two conditions imply the existence of a quadratic Lyapunov function for the game’s projected gradient dynamics, from which Lyapunov functions for alternate learning processes may be constructed. One exception is [43], which deals explicitly with the problem of bounding expectations of stable distributions of Markov processes. Moreover, it is there that the dual solution of the LP bounding the expectation of some function is dubbed a “Lyapunov function”. The continuous time gradient dynamics we study is of course a Markov process, and a rather “boring” one in the sense that it is fully deterministic; this motivates us to denote any of our dual solutions as a generalised Lyapunov function. However, the results of [43] do not include approximations of the Markov process and how Lyapunov-function based dual proofs extend to such approximations. Moreover, it is unclear how their results apply to projected gradient ascent, with polyhedral action sets. We are able to provide positive answers on both fronts.

In turn, our analysis of local correlated equilibria depends on the more established framework of $\Phi$-regret minimisation. Our techniques here are essentially those used in [41, 39]. One key difference is our vector field formulation; usual swap-regret minimisation [76, 39, 41] considers mappings of the action space onto itself, while we measure regret against its differential generators. The consequences are reminiscent of the result of [44] on the equivalence of no regret learning and fixed point computation, in that we require access to a fixed-point oracle for the linear (or conical) combinations of vector fields in question to implement our regret minimisation algorithms. On the other hand, our vector field formulation allows us to refine the notion of correlated equilibria to a family of vector fields for which fixed-point computation is tractable; we are unaware of any similar observation.

These argument presented in Section 3 form the basis of our proofs of tractable approximability of local or stationary CCE. In particular, we shall see that after proving the approximability of a stationary CCE, that a local CCE itself is also approximable will then follow, by arguing that the zero-measure property above is maintained for the analogue of (7).

There is yet a hiccup though; most learning algorithms in practice take discrete steps. Whereas [33] (Theorem 3) implies that a discrete analogue of (5) would approximate the continuous dynamics uniformly over an interval $[0,T]$ for sufficiently small step sizes, their result does not come with approximation guarantees. And besides, our formulation of the gradient dynamics of a game is general enough that we cannot yet rule out chaotic behaviour (as in e.g. [68]).

Thus we want to avoid any attempts at an uniform approximation of a solution of (5). Instead, we shall consider the case when each player uses projected gradient ascent with equal, adaptive learning rates as their learning algorithm. We shall then extend this to a piecewise-defined continuous curve as an approximation of the underlying projected gradient dynamics. This parametrised curve might actually diverge from actual solutions of (5), and would significantly do so in the presence of chaos. But we shall in the following subsections that this does not end up mattering for the purposes of vanishing regret bounds. Moreover, our discussion in Section 5 will show that, for the purposes of bounding expectations of quantities, regret bounds for the continuous curve are “as-if” they were for the corresponding weighted average distribution of play. All in all, our discrete-time learning algorithm and the resulting continuous curve of interest are defined: