On the Interplay between Social Welfare and Tractability of Equilibria
Authors: Ioannis Anagnostides
Tuomas Sandholm
Venue: NeurIPS 2023 poster (2023)
Keywords: learning in games
optimistic gradient descent
Nash equilibrium
price of anarchy
smooth games
social welfare
TL;DR: We establish a new connection between the convergence and welfare of learning algorithms in multi-player games.

Abstract: Computational tractability and social welfare (aka. efficiency) of equilibria are two fundamental but in general orthogonal considerations in algorithmic game theory. Nevertheless, we show that when (approximate) full efficiency can be guaranteed via a smoothness argument a la Roughgarden, Nash equilibria are approachable under a family of no-regret learning algorithms, thereby enabling fast and decentralized computation. We leverage this connection to obtain new convergence results in large games---wherein the number of players $n \gg 1$---under the well-documented property of full efficiency via smoothness in the limit. Surprisingly, our framework unifies equilibrium computation in disparate classes of problems including games with vanishing strategic sensitivity and two-player zero-sum games, illuminating en route an immediate but overlooked equivalence between smoothness and a well-studied condition in the optimization literature known as the Minty property. Finally, we establish that a family of no-regret dynamics attains a welfare bound that improves over the smoothness framework while at the same time guaranteeing convergence to the set of coarse correlated equilibria. We show this by employing the clairvoyant mirror descent algortihm recently introduced by Piliouras et al.

On the Interplay between Social Welfare and Tractability of Equilibria
Ioannis Anagnostides Carnegie Mellon University ianagnos@cs. cmu. edu
Tuomas Sandholm Carnegie Mellon University Strategic Machine, Inc. Strategy Robot, Inc. Optimized Markets, Inc. sandholmêcs. cmu edu
Abstract
Computational tractability and social welfare (aka. efficiency) of equilibria are two fundamental but in general orthogonal considerations in algorithmic game theory. Nevertheless, we show that when (approximate) full efficiency can be guaranteed via smoothness argument à la Roughgarden, Nash equilibria are approachable under family of no-regret learning algorithms, thereby enabling fast and decentral- ized computation. We leverage this connection obtain new convergence results large cames-wheree the number of players n >> 1 1-under the well-documented property of full efficiency via smoothness in the limit. Surprisingly, our framework unifies equilibrium computation in disparate classes of problems including games with vanishing strategic sensitivity and two-player zero-sum games, illuminating route an immediate but overlooked equivalence between smoothness and a well-studied condition in the optimization literature known as the Minty property. Finally, establish that a family of no-regret dynamics attains welfare bound that improves over the smoothness framework while at the same time guaranteeing convergence to the set of coarse correlated equilibria. We show this by employing the clairvoyant mirror descent algortihm recently introduced by Piliouras et al.
Introduction
The Nash equilibrium (NE) [76] formalizes the notion stable outcome a multiagent strategic interaction, and has arguably served as the most influential solution concept in the development of game theory. Indeed, algorithms designed to approximate Nash equilibria in two-player zero- sum games have recently resolved major challenges in AI [7, 10, 81]. Its preseriptive power, however, has been severely undermined in multi-player general-sum games by intrinsic computational barriers [30, 20, 94, 35, 28, 44], limitations which also manifest in the inability of natural learning algorithms to converge [73, 105, 60, 70]. Another well-established but orthogonal critique is the equilibrium selection problem [52]: general-sun game may have multiple Nash equilibria with widely different welfare. As a result, modern research agenda in computational game theory has been identify and characterize natural classes of games that eircumvent those fundamental limitations.
In this paper, we uncover a new natural class of games for which the aforementioned caveats of Nash equilibria can be effectively addressed. In particular, investigation originates from natural question: when are efficient in terms of social welfare-Naa Nash equilibria easy to compute? The answer to this question is, first glance, unsatisfactory: even if Nash equilibria fully efficient, computational hardness still persists given that constant-sum multi-player games are hard. Indeed, efficiency and computational tractability are, in general, two orthogonal considerations. We show,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

however, an interesting twist, an unexpected interplay between efficiency-whiee when viewed from a specific and the behavior of a family of no-regrer learning algorithms.
1.1 Our results
To elucidate the alluded connection that drives much of our results, we first have to recall that the canonical paradigm for establishing the efficiency of equilibria is Roughgarden's celebrated smoothness framework [90] (exposed thoroughly in Section 2). In this context, we observe that if full efficiency of equilibria can be guaranteed via smoothness argument (with bounded parameters), then Nash equilibria are approachable under a family of no-regret learning algorithms. In other words, full efficiency via smoothness implies computational tractability of NE. This is surprising in that Roughgarden's is smoothness framework was developed primarily in order to automatically extend price of anarchy (PoA) bounds to more permissive equilibrium concepts, such as coarse correlated equilibria (CCE); tractability of NE appears at first glance entirely unrelated. In fact, while applying the smoothness framework to playyr) constant-sum games appears to make little sense, given that PoA considerations are trivial in such games (all outcomes attain the same social welfare), it turns out that a certain regime of smoothness in (multi-player) constant-sum games is equivalent to a well-known condition in the optimization literature called the Minty property [36] (Observation 3.4).
The condition described above already captures-somewveee somewhat unexpectedly-wedr sorall--wwll-stddiee settings, such as games that admit a minimax theorem [13]. but we have found that the most fertile and novel ground to apply this theory revolves around large games, that is, games with a large number of players > 1.! The reason we focus on large games is well-documented economic phenomenon: equilibria in large games approach- undrerch-unddr under natural conditions full efficiency as n - +000, a property often es- tablished via smoothness [39, 23] a crucial ingredient in our framework. (One rough intuition for this is that in large games each player's influence on the outcome becomes negligible, making optimal be- havior easier to characterize (39].) To state our first main result, we denote by (A, (1) pair of bounded smoothness parameters of game G; the ratio p(), == __
Itu circumscribes the (in)efficiency of equilibria of G, in that all equilibria will attain at least p fraction of the optimal welfare.
Theorem 1.1 (Informal). Consider sequence of n-player (Ans pmoothh games (Gx)n21 such that Pr. = An
I+p, + with sufficiently fast rate. Then, there are decentralized and computationally efficient no-regret dynamics approaching an (o,, (1), on (1)))weak Nash equilibrium.
A few remarks are in order. First, in Theorems 3.1 and A.2 we give a precise non-asymptotic character- ization that quantifies the number of iterations as well as the approximation error. We also recall that in an (1), on (1))-weak Nash equilibrium almost all players are almost best responding (Defini- tion 2.2); this is well-studied relaxation for which hardness results carry over in general [4, 2, 5, 94]. A limitation of a weak Nash equilibrium is that it can prescribe a strategy profile in which a large num- bers of players-all albeit of vanishing fraction can significantly benefit from deviating; this limitation is inherent in certain regime of Theorem 1.1. Depending on the rate with which Pn approaches full efficiency, Theorem 1.1 can also imply convergence to the usual notion of Nash all players are almost best responding (Corollary A.5). More generally, for broad class of games that includes graphical games with bounded degree, polymatrix games, and games exhibiting small strategic sensitivity, the conclusion of Theorem 1.1 applies without imposing any restrictions on the rate of convergence of pn; those are the most commonly studied classes of games when n >> 1.
setlibrrumm-wheree
There are ample compelling aspects in connecting the convergence of no-regret learning algorithms with Roughgarden's 's smoothness framework. First, there has been a considerable interest in under- standing smoothness, insights that can now be inherited to seemingly entirely different but equally fundamental problem. For example, smoothness naturally extends to Bayesian games [101, 91. 53] (see also [97] for the related class of contextual games), property that we leverage in Theorem 3.8 to expand our scope to mechanisms of incomplete information. Additional extensions based on local smoothness [92, 78] and the refined primal-dum framework of Nadav and Roughgarden [75] are also described in Appendices A.3 and A.4. Finally, our criterion has clear and natural economic interpretation, and is part of an ongoing research effort to identify tractable classes of variational inequalities (VIs) beyond the Minty property [33].
We use the terminology large games here- in accordance with much of the economics literature- to refer to games with large number of players; it should not be confused with another common usage referring to games with a "large" action space.
2

---

As a concrete example, our framework subsumes games wherein each player's effect on the outcome vanishes as n oc; this captures, for example, simple voting settings [57], as well as general auction design problems where establishing that property turns out to be highly non-trivial and quite delicate [39]. More concretely, for games with vanishing sensitivity 6n - 0, in that unilateral deviations can only affect player's utility by an additive 6n (Definition 3.5), we show that the conclusion of Theorem 1.1 applies as long as En S on (1/ /n) (Theorem 3.6). At the same time, the condition that Pn. + 1 goes much deeper than games with vanishing sensitivity, and, earlier, surprisingly applies to two-player zero-sum games as well. We find conceptually appealing that a unifying framework can establish tractability of Nash equilibria in two seemingly disparate classes of problems such as two-player zero-sum games and games with vanishing strategic sensitivity,
explained
Remaining on smooth games, but relaxing the assumption p ~ 1, we next study conditions under which the efficiency guaranteed by the smoothness framework can be improved, while at the same time ensuring the no-regret property, thereby implying convergence to the set of CCE. The smoothness bound is known to be applicable to any outcome of no-regret dynamics, but here we are instead interested in more refined guarantees when specific learning algorithms are in place. Building recent result [I], we show in Theorem 4.1 that the clairvoyant variant of gradient descent, introduced by Piliouras et al. [85], enjoys an improved welfare bound and ensures fast convergence to the set of CCE for the average correlated distribution of play. Crucially, compared to an earlier result [1], the clairvoyant algorithm manages satisfy an appealing notion of per- per-player incentive compatibility, in the form of convergence to CCE. In other words, improving the welfare predicted by smoothness is not at odds with incentive compatibility (Corollary 4.3).
2 Background
Notation We let N {1. be the set of natural numbers. For n E N. we denote by [m] (1,2.....; n). For vector Rd we denote by | its (Euclidean) &2 norm. For convex, compact and nonempty set X, we let (xx(.) represent the Euclidean projection operator with respect X'. We let Dx be the la-diameter of X. To simplify the exposition, we often use the O(-) notation in the main body to suppress the dependence on certain parameters; we also write (.,(-) to indicate the asymptotic growth solely as a function of n, so as to lighten the exposition.
Multilinear games We consider n-playe multilinear games. In multilinear game G each player i [n]] has convex, compact and nonempty set of feasible strategies X; C Rd, for some dimension de E N. Under a joint strategy profile æ = (Z)...... 2n. E II X2 = X, there is continuous utility function uq= ( Fn,) + R such that uz(ar) (æ: .)). for some function u, : æ= + Rd;; here, we used for convenience the standard notation x-; = (æI,..., I; (0....,;;-1,,2 Iz+1, ....,,.......................... ).). This setup readily captures normal- as well as extensive-form games.
Specifically, in a normal-form game every player i E [n]] selects as strategy a probability distribution I; E ((A,) over finite set of available actions A,. There is an arbitrary utility function u; A = I1=, A; + 1] that maps a joint action profile to a utility for Player é; we will be making the standard assumption that the range of each player's 's utilities bounded by an absolute constant, which is in particular independent of the numher of players n. In this setting, the mixed extension of the utility function indeed satisfies the multilinearity condition imposed above: for æ E ((A))
u, (x) == Ea-z in (a)] = (z,, Væ,4; (x)), where we overioaded the notation (-).
Returning to the general setting of multilinear games, we let F'g x
X denote the (x-1,)),... un (x-n)), will often omit the subseript
X, -
underlying operator of the game G, defined as Fgg (#),.... xx,)
where function u, was introduced earlier. For notational simplicity, g when it is clear from the context. We will say that F is L-Lisschitz continuous (w..t. the &g norm) if for any x, x' E II X, it holds that [F(x)= F(x') < L| x'|12
Welfare and the price of anarchy For a joint strategy profile æ E TT' X. we define the social welfure attained under x as (w)) = -n (x(.). The maximum possible social welfare attainable in game G will be denoted by OPT Without any essential loss of generality, it will be assumed that OPTg > O. We say that the game constant-sum if SW(x) = V e Ry for any I[ Xt The price of anarchy (PoA) of game G quantifies the loss in efficiency incurred on
3

---

account of strategic players [61]. Formally, if NEg is the nonempty set of (mixed) Nash equilibria of g (Definition 2.2) [88], we define PoAg == sup N
(W())
OPTs
Smooth games We are now ready to recall the seminal notion of smooth game," 2 conceived in the pioneering work of Roughgarden [90] as technique to (lower) bound the price of anarchy. Definition 2.1 (Smooth game [90]. An n-player game is called (A, pl-smooth, where À > 0 and > -1, if there exists x" E I X3 with (W" = OPTs such that for every æ E I X.
Σ ue(at, a-x) SOPTs ((S(()))
(In the definition above, and throughout this paper, we slightly abuse notation by parsing ut (z x--)) as (3) ...; 1 æt. ,.. Roughgarden [90] observed that in a (A, wi)-mmothh game, in the sense of Definition 2.1, every Nash equilibrium attains least p(),
A_ fraction I+p
of the optimal social welfare OPTg. Importantly, this efficiency guarantee immediately carries over to outcomes of no-regret learning algorithms as well. The robust price of anarchy (rPoAg) the best (i.e., largest) price of anarchy bound provable via a smoothness argument, and can be defined as the solution to the linear program induced by the smoothness constraints given in (1) (see (24) in Appendix A.5). One delicate point here is that the value of rPoAg could be associated with unbounded smoothness parameters, which is pathological and rather trivial manifestation of smoothness (Remark A.10 elaborates on this point). To be clear, when we say a game 9 attains a certain value Pg. we mean that there exists finite pair of legitimate smoothness parameters (X, μ1) With this convention, it might be the case that Pg (A, 11) # rPoAg under any
such that Pc = I+ finite pair of smoothness parameters (A, p1) (Remark 1.) It is also easy that PoAg 2 rPoAg.
X
Nash equilibrium We next recall the concept of a weak Nash equilibrium, a natural generalization of the standard notion which is meaningful in multi-player games.
Definition 2.2 (Weak Nash equilibrium [5]). Let 5 E [o, 1) and Rzo- A joint strategy profile x E I[=-1 X is an (e, 6)-weak Nash equilibrium if at least 1 - 5 fraction of the players are e-best responding. An (c, O)ek Nash equilibrium will be simply referred as e-Nash equilibrium.
In the definition above, we clarify that a player i E [m] is said to be e-best responding if BRGAP,(EI..... vn)) == m (or, (x) - (x,, u, (x= S e. We also define the Nash equilibrium gap as NEGAP(æ) == maxıgisn (Z) It has been shown that hardness results in multi-playe general-sum sumeral-ummmaa games persist under the weak Nash equilibrium concept introduced above, even when and 5 are absolute constants bounded away from 0 [4, 94].
Regret We are operating in the usual online learning setting. At every time t E N player E [n] selects a strategy 2!") E X, and then receives as feedback the linear utility function æ, + (ax, u
where we overload notation so that u, (t) (x)) The regret of player i E [m] under a time horizon T E N is defined as
T
Reg: (T) max
Σ
ui (n an (1)
Σ (x)))
2 EA,
Optimistic gradient descent By now, there are many online algorithms known to guarantee sublinear regret, Reg. = o(T), even if the observed utilitics are selected adversarially [18, 98]. The main no-regret learning algorithm
consider in this paper is optimistic gradient descent (henceforth DCD) [86, 22], which is known to yield improved regret guarantees in the setting of learning in games [103]. For each player i [n]], OGD is defined through the following update rule for L E N.
x; = Px: (e((0) + 1)m
(OGD)
(1+1) = Px (() + mu! (1) ;
3Smoothness in the sense of Definition 2.1 should not be confused with the unrelated notion of smoothness in the optimization nomenclature.

---

(1) Here, 7 0 is the learning rale; m E Rd is the prediction vector; and i; E X, is the initialization. It assumed that the strategy set X; is such that the Euclidean projection Px, (-) can be implemented efficiently. We will let m (!) u (f-1) for any & E N. where u; (0) :- u, a (1)
(t)
-1)
3 Convergence to Nash equilibria via smoothness
In this section, we study the convergence of optimistic gradient descent (DGD) in large games, that is to say, in the regime > 1. In our first main result, stated below Theorem 3.1, we show that when 1om Pn. = 1 with a sufficiently fast rate, not only are Nash equilibria approaching the optimal social welfare, but they can also be computed efficiently in decentralized fashion via OGD.
In the sequel, when considering a sequence of games (gn)m21, with each game 9n being parameter- ized by the number of players we will use subscript with variable to index the rath game in the sequence; that notation will also be used to refer to the other underlying parameters of the game that depend on the number of players.
Theorem 3.1. Consider an n-player (A, -mooohh game Gm such that the game operator Fn, is Lip-hhhhhittz continuous and X (1 (1-6,) (1) +1++ p)) with en + 0. Suppose furteer that all players follow DGD with learning rate in = mmmm) Then, for d E 10 and a sufficiently large number of iterations T On(nIl where In OPTg, Cn. there is time t E [T] such that
(1+
xx11)= = (xr (2") En ) is
(n30n
7n n
.6)
weak Nash equilibrium.
In particular, in On (n (n a E (0, 1), DGD yields an (O,(n (ann+t,,cm
NE.
We remark that if it further holds that 7n o, (1), the above theorem establishes convergence all players are (almost) best responding
to the standard notion of Nash caclibriumm-wheedd (Corollary A.5). Parameter "/n which is proportional to the error term cn, controls both the number of iterations and the approximation guarantee in (2); we refer to Theorem A.2 (in Appendix A) for a more precise non-asymptotic characterization, which bounds the players' cumulative best response gap as a function of the growth of 7n. We also note that Theorem 3.1 can be strengthened so that (2) holds for most iterates of OGD (say 99%), not just a single one (Remark A.4).
Now, to be more concrete regarding the preconditions of Theorem 3.1, we first observe that the growth of the Lipschitz constant Ln depends on the normalization assumptions as well as the structure of the underlying game Gu. In particular, let us assume as is standard- that the range of the utility functions is independent of n, in which case OPTg, = (n). We then show that Ln = (I) in each of the following cases: graphical games with bounded degree (Lemma A.7), games with O,, (1/nt) strategic sensitivity per Definition 3.5 (Lemma A.8), and polymatrix (general-sum) games even with unbounded neighborhoods (Lemma A.9); the first two of the aforementioned classes are the most commonly studied classes in the literature under the regime >> 1. For all of those classes, applying Theorem 3.1 yields an (o,, (1), o (1e)- Nash equilibrium for any en S (1). More generally. the Lipschitz constant Ln, can grow with (Lemma A.6), in which case en must vanish with a faster rate for the conclusion of Theorem 3.1 to kick in. One important limitation of Theorem 3. is that, at least in a certain regime, it prescribes strategy in which many players- albeit vanishing fraction-man have a profitable deviation (in accordance with Definition 2.2); this is admittedly an inherent feature of our framework.
Remark 3.2. In decentralized environment, one question that arises from Theorem 3.1 concerns the identification of a time index t" < [[]] that satisfies (2), which can be viewed as the stopping condition of the algorithm. We suggest two possible approaches. First, we accept that players have access to a common source of randomness, then all players can sample the same index t" uniformly at random from the set [T]. As we point out in Remark A.4, this suffices to provide a guarantee with high probability with only small degradation in the solution quality. The second approach, which does not rest any having common source of randomness, involves a coordinator who can communicate with the players but possesses no information whatsoever about the underlying game. The coordinator sets a target solution quality parameterized by (e, 6) (per Definition 2.2), and after each iteration t elicits from each player i E [n] a single bit, encoding whether (BRGAP, > e). (We note that each player can indeed determine its best response gap with only its local information naammattiionnmmlly......a
5

---

the utility feedback.) The coordinator can then evaluate whether the fraction of the players with at most an e best response gap matches the desired accuracy. While the second approach makes for less decentralized protocol, the communication overhead described above is arguably very limited.
The key precondition of Theorem 3.1 pertains the behavior of the smoothness parameters, to be discussed next after we first sketch the proof of Theorem 3.1, which extends a recent technique [1].
Proof sketch of Theorem 3.1 The proof is based on the fact that the sum of the players' regrets E:=1 Reg.") (T) cannot be too negative, which in turn follows from the assumption that Pn. 1 Cn- The argument then proceeds by bounding the players' cumulative best response gap across the T function of "/n and the time horizon T E N, ultimately leading to the conclusion of Theorem 3.1.
iterations Σ -t ك (BRGAP;(z(1))
Connection with the Minty property While have stated Theorem 3.1 in the regime > under the premise that Pr. is sufficiently close to 1 (as a function of n). its conclusion is in fact interesting beyond that regime. Indeed, important observation is that any two-player constant-sum game G = (A, B), with (x), Aœ²) + (x), Bæ²) = V for any (x), 222 E X1 x X2, satisfies PG = 1. This is indeed a consequence of Von Neumann's minimax theorem: ] f, 25) E X X2 such that "1 ( [2) + uy( (a 21 - V = [ Azz) - (01,AA)) Axz) 2 0 for any 1 x22) E 2 x Xg, in turn implying that 21 (2j, x2) + uy (z5 σ1 2 (1+ 4)PPT WSW(()
V: that is, any two-player
constant-sum game is (1 p. (1) -smooth, thereby making the conclusion of Theorem 3.1 readily appli- cable (by taking p 2 e² for any >> O; see the explicit statement of Theorem A.2). This captures and unifies earlier iteration complexity bounds under OCD and the extra-gradient method [15, 48, 46).
Proposition 3.3. Any two-player constant- sum game G is (1 + μ. p) pm for μ > -1, implying that Pg = 1. Thus, ((1/e²) iterations of OGD suffice obtain an c-Nash equilibrium, for any O.
More broadly, there is a surprisingly overlooked but immediate connection between smooth games (per Definition 2.1 and the Minty property, well-known condition in the literature on variational inequalities (VIs) [36, 66, 71]. More precisely, the Minty property postulates the existence of a strategy profile x² II X; such that (x* x, F(x)) 2 0 for any x E II Ng, where recall that F is the operator of the game. (We caution that the last inequality is typically stated with the opposite sign since the operator F is defined oppositely.) The following connection is thus immediate from the fact that (x", , F(x)) = Ee u, (z=:i)) = Ei= ui( x x-:) and = (W) (by multilinearity).
(a,, F(x)) = Σi= (2;; u1( Observation 3.4. For any (multii (mullti-laayer) constant-sum game G, the Minty property is equivalent to g being (1 + n. pm-smooth for some μ > 1.
Indeed, the Minty property implies that Σi ut (xt, 2 = (1++ (SS((r) (æ), and the converse direction is also immediate. In fact, for (multi-player) zero-sum games, the Minty property is equivalent to G satisfying (1) under some pair (A, n)) E IR2. We stress that even if Pg 1, traditional no-regret learning algorithms such as online mirror descent do not generally enjoy iterate convergence to Nash equilibria [70]. which stands in stark contrast to the behavior of OGD (Proposition 3.3). In light of Observation 3.4, Theorem 3.1 should also be viewed an ongoing effort to establish sufficient conditions of tractability that are more permissive than the Minty property (e.g., [33, 12, 14, 84, I1]. The criterion we furnish herein, based the smoothness framework, has the important benefit of enjoying a natural economic interpretation, as well as having being extensively studied in the literature. Indeed, we will leverage insights from prior work to obtain several interesting extensions in the remainder of this section.
part of
Games with vanishing sensitivity Returning to the regime >> 1, why should we expect A.. -> 1? Indeed, if anything large games are more general than games with a small number of players since one can always incorporate "dummy" players into the game. Yet, the point is that large games oftentimes exhibit a structure that leads to more efficient outcomes. For example, one immediate implication of our framework relates games with a vanishing (strategic) sensitivity (see, e.g., [57, 3, 72, 45]). There are various ways of defining sensitivity; here, we adopt the following standard definition.
Definition 3.5. The strategic sensitivity e E R50 of an n-player game in normal form is defined as
max max max max |ux(de, a) (a))-
Isisn a 15 EA,

---

In words, a unilateral deviation can only impact a player's s utility by an additive Now, as long as the sensitivity decays fast enough, a proof analogous to that of Theorem 3.1 implies the following.
Theorem 3.6. Consider an n-player game In with sensitivity en E R2 Then, T = On(n) tterations of DGD suffice to obtain a (880), On (envn), -weak Nash equilibrium, for 8 E (0,1).
In particular, Theorem 3.6 yields (1), (1)) Nash equilibrium as long as cn, On (v(v)) Further, in the canonical regime where 6n = (n(11/)) Theorem 3.6 circumscribes the best response gap for all but constant number of players (by taking 6 On(1/n)) There are many natural settings where we should expect results such as Theorem 3.6 to be applicable [57, 58, 69]. We find it conceptually compelling that our framework can provide in a unifying way equilibrium guarantees for two seemingly disparate classes of games, namely two-player zero-sum games and games with vanishing strategic sensitivity.
In a similar vein, Feldman et al. [39] showed that pr + with a rate of 1/v/ ni in a general auction design problem (see also [23]) under the relatively mild assumption that each player participates in the market with some constant probability (aka. probabilistic demand), thereby bypassing known barriers regarding the inefficiency of equilibria in general combinatorial domains. Their proof is based on a simultaneous uniform-pric auction format-
the fact that each bidder's 's impact on the prices-unaa becomes asymptotically negligible, in the spirit of Definition 3.5 introduced above. The difficulty that arises in that setting is that the natural representation of the utility functions violates our multilinearity assumption (postulated in Section 2). Instead, one would have resort to some form of discretization before attempting to apply Theorem 3.1, which could be computationally prohibitive; the other prerequisite is that L, = o,, (vn), for which our approach in Lemma A.8 in conjunction with the insights of Feldman et al. [39] could be useful. Understanding whether our techniques can be applied in the combinatorial auction setting of Feldman al. [39] is left as a challenging open question.
Efficiency of equilibria does not suffice for tractability A natural question arising from Theo- rem 3.1 is whether a similar statement applies under the assumption that PoA + 1, that is, assuming that all Nash equilibria of G are (approximately) fully efficient. This is clearly a weaker assumption, but it is unfortunately not sufficient to yield any non-trivial guarantees even in normal-form games:
Proposition 3.7. Even under the promise that Poλg = 1, computing a (ooly(g)--Nasst equilibrium in normal-form games in polynomial time is impossible when n 2 unless PPAD _ P.
This stands in contrast to the class of (1 + pt, -mooohh games, where fully polynomial-time approximation scheme (FPTAS) is implied by Theorem 3.1 3.s-asgu access utility and projection oracle, both of which are available in, for example, most succinet normal-form games. Proposition 3.7 is straightforward consequence of the fact that Nash equilibria are hard to compute even in constant-sum 3-player games [20]. Furthermore, in Example A. we identify a specific 3 3-player game in which OGD fails (unconditionallly to converge to e-Nash equilibria for a constant value of e > O, even though PoA = 1. Our example is based on a variant of Shapley's 's game [99].
Another notable advantage of smoothness as a criterion of convergence is that, at least when the game represented explicitly, it is easy to compute; this is in contrast PoA, whose identification even in two-player games is NP-hard (Proposition A.1
Extensions It turns out that smoothness per Definition 2.1 can be further sharpened using a primal- dual framework [75]. Such refined guarantees can also be translated into our setting (in the context of Theorem 3.1), as we elaborate on in Appendix A.3. The upshot is that the modification of Nadav and (T)
Roughgarden [75] necessitates analyzing the weighted sum of the players' regrets Di=1= 2, Reg, under a dual set of variables {z ) Another interesting extension worth noting relies on the local smoothness framework [92, 78], as we explain in Appendix A.4; the key observation is that local smoothness per Nguyen [78] can be associated with a linearized notion of regret, at which point the analysis of Theorem 3.1 readily carries over. Finally, also expand our scope to Bayesian mechanisms, as we expound in the upcoming subsection.
Before we proceed, it is important to point out that, unsurprisingly, smoothness is not merely enough to guarantee convergence of OGD; see Example A. 13. It instead crucial to additionally ensure that p x 1 in order to obtain interesting guarantees for the behavior of algorithms such as OGD.
7

---

3.1 Bayesian mechanisms
Next, we leverage the connection between smoothness and convergence to Nash equilibria to extend the scope of our framework to Bayesian mechanisms. In particular, analogously to Definition 2. 2. Syrgkanis and Tardos [102] have introduced the notion of a smooth mechanism (Definition A.14); de- tailed background on Bayesian mechanisms and smoothness in that realm is provided in Appendix A.7. In this context, we leverage a reduction of Hartline et al. [53] from an coomplete-ifoomaaiie complete-informatie
to a mechanism to arrive at the following theorem. (The standard notion of a Bayes- Nash equilibrium is analogous to Definition 2.2, and is recalled in Definition A.15 of Appendix A.7.)
Theorem 3.8. Consider a Bayesian mechanism M such that PM 1. Then, for any > 0, T ( iterations of DGD suffice to obtain an e-Bayes-Nash equilibrium of M.
In particular, OGD above executed on the so-called agent-form representation of M (Appendix A.7). Analogously to Theorem 3.1, the above theorem can also be extended in the large n >> under the assumption that P.. - 1. It is worth noting that Theorem 3.1 already can be applied to certain games of incomplete information (such as imperfect-information extensive-form games), but Theorem 3.8 additionally makes connection with the literature on smoothness mechanism design, which facilitates characterizing the smoothness parameters.
4 Improved welfare for no-regret dynamics
Roughgarden's 's seminal work [90] established that no-regret learning algorithms always attain asymp- totically at least rPoA fraction of the optimal social welfare (on average). This guarantee is satisfactory for many classes of games where rPoA is close (emphatically those studied earlier in Section 3), but smoothness is certainly not a universal phenomenon: there are simple games in which the smooth- ness framework only provides vacuous guarantees; one such example is Shapley's s game, discussed in Appendix 10. As result, one important question arising is whether it is possible to improve the efficiency bound predicted by smoothness when specific learning algorithms are in place, while at the same time still guaranteeing convergence to the set of coarse correlated equilibria (CCE). We stress that optimizing over the set of CCE is typically NP-hard suceinct games [79, 6]. making this question interesting also from a theeoric standpoint.
In this section, show that it is indeed possible to obtain improved efficiency bounds der a generic condition, while at the same time guaranteeing the no-regret property for each player. A key ingredient in our improvement is the use of clairvoyant mirror descent, algo- rithm recently introduced by Piliouras et al. [85]. More precisely, we will instantiate that algo- rithm with (squared) Euclidean regularization, which can be defined as follows. Let 1l, (u:) == arg EX; {('', u,) ||,; = be the induced prox operator, where z; X; and uu, E RRd.. Clairvoyant gradient descent (henceforth CGD) at time t E N outputs a(() = T2 (1F(((())))) = (T (- (1721 (w ())) II an (1,, where w(()) is any e1)_
approximate fixed point of the map IT 2 initialization. It turns out that for < I/I., this map is a contraction [37, 85, 19], thereby making approximate fixed points easy to compute. Furthermore, there is also uncoupled implementation of CGD [85], making the algorithm compelling from a decentralized standpoint as well, but we will not dwell on this issue here. We are now ready state the main result of this section.
T ((F)))) and (0) X' is arbitrary
Theorem 4.1. Suppose that all players are updating their strategies using CGD with c(t) < min, Dx, and learning rate = 2T.
1 in a (A, pmmsmooth game G, where L is the Lipschtz-continun parameter
of F. Then, for any 6o > 0 and T 2 61L D* iterations,
cg
1. the average correlated distribution of play is a ALD22 CCE;
2. there is a time t* E [T' such that
(W(al(()) 2 sup min { pg((,,) OPTg + 16(u + 1)ID PoAg. OPTg
2²
-0PT
(3)
20c0
This the first result that establishes simultaneously these properties under a computationally efficient algorithm, improving recent work [1] (see also [42, 67] for related results) that failed to
8

---

guarantee convergence to CCE. In particular, that earlier work was analyzing OGD, and as it turns out, under time-invariant learning rate 7 is not even known whether DGD ensures sublinear per-player regret, let alone constant (as in Corollary 4.3). The basic ingredient to this improvement is new property of CGD, which we explain below. Before we sketch the proof, we note that Item 2 above can be readily strengthened so that the improvement holds for the average welfare of most of the strategies, not just a single one (Remark A.22).
Proof sketch of Theorem 4.1 The key step in the proof is showing (in Corollary A.21) that
CGD satisfies the remarkable per-player regret bound Reg,") (T) I a ? > (BRGAP((a<))) can be made
where > 0 depends on the approximation error of the fixed points of time-invariant with only an Oloo T) per-iteration overhead-and 7 > 0. To do this, we crucially rely on a certain property of the Euclidean regularizer (Lemma A.20), which we use in conjunction with the analysis of Farina et al. [37] who extended the original argument of Piliouras et al. [85] beyond entropic regularization.
It is worth noting that the above per-player regret bound (Corollary A.21) implies that a player with nonnegative regret will be almost always approximately best responding, a rather singular occurrence in the context of learning in games; this has interesting implications and goes well-beyond what is currently known for OCD. In particular, it is an open question whether Theorem 4.1 holds under OGD.
Next, we shall describe a concrete implication of Theorem 4.1 under a generic condition. To do so, let us denote by PoAş the price of anarchy in G with respect to the worst-case e-Nash equilibrium (so that P PoAg).
Condition 4.2. Consider a game G and some game-dependent parameter C = C(g) > 0. There exists an 6g > 0 such that PoAg rPoAg &cC.
Naturally, is always the case that PoAg 2 rPoAg. Further, rPoAg is in general strictly smaller since it measures the worst-case welfare over larger set than PoAg (even broader than outcomes of no- regret learning); Figure in Appendix A.8 further corroborates this premise in a sequence of random normal-form games. Now assuming that PoΛg > rPoAg, Condition 4.2 is met if lim,- PoAg PoAg, a mild continuity condition (see, for example, the discussion by Roughgarden [89]).
Corollary 4.3. Consider a (A, p)--mooth game G that satisfies Condition 4.2 under some Eo > O.
Then, CGD after T 2 641222% iterations and 2τ. satisfies the following:
<
1. the average correlated distribution of play is an O (+)-CCE;
2. there is time t* E [T']] and (g) > 0 such that SW(x Z (p((
A fundamental question that arises from Theorem 4.1 is whether there exists a computationally efficient algorithm that determines CCE with social welfare at least PoA fraction of the optimal welfare. In games where PoA = rPoA this is clearly possible; in contrast, while Theorem 4.1 improves over the smoothness bound, does not always guarantee welfare up PoA. This is central question in light of the intractability of Nash equilibria [30, 20], which has indeed served as primary critique to the literature quantifying the price of anarchy of Nash equilibria [90].
Another promising avenue to improving the welfare predicted by the smoothness framework revolves around eliminating certain strategy profiles by arguing that they are reached with negligible probability. For example, in Appendix 10 we identify an example where iteratively eliminating strictly dominated actions can improve the predictive power of the smoothness framework.
5 Further related work
Large games The study of non-cooperative games with many players (i.e,, large games) has been a classical topic in economic theory [96, 41, 68, 95, 83, 38, 50], most recently revived in the context of mean-field games (e.g., [64, 47, 74, 51, 16, 82, 100, 80, 29, 65]). Indeed, many traditional motivating scenarios in algorithmic game theory, including markets and Internet routing, often feature large number of players in practice. In particular, it has emerged that, under certain conditions, equilibria
'e clarify that Theorem 4.1 could have also been stated as follows: CGD outputs an approximate CCE with social welfare attaining the right-hand side of (3); this evident from the proof in Appendix A.9.

---

in large games exhibit certain remarkable robustness and stability properties; see, for example, the recent survey of Gradwohl and Kalai [49], as well as the older treatment of Kalai [56] on the subject. Furthermore, mechanism design in large games, along with privacy guarantees, is explored in the work of Kearns et al. [58] (see also [57, 59)).
Efficiency in large games Of particular importance to our work, and specifically the precondition of Theorem 3.1, is the line of work uncovering the by now well-documented phenomenon in economics that large games exhibit, under certain relatively mild assumptions, fully efficient equilibria. Our framework additionally requires that the efficiency of equilibria can be derived via smoothness argument, in the sense of Roughgarden [90]; we stress again that efficiency alone is of little use when it comes to equilibrium computation (Proposition 3.7). Fortunately, smoothness has emerged as the canonical paradigm for bounding the price of anarchy (e.g., see the survey of Roughgarden al. [93]. albeit with some notable exceptions [40, 55]. In particular, Feldman al. [39] quantify the price of anarchy in large games via the smoothness framework. They show that in a general combinatorial domain with simultaneous uniform-price auctions, it holds that Pr. + with a rate of 1/ /n as long as there is probabilistic demand, meaning that every buyer abstains from the auction with a constant probability. Several other papers have studied the price of anarchy in large games [63, 23, 24, 26, 25, 17]. In particular, we highlight the work of Cole and Tao [23] which, as Feldman et al. [39], relies on smoothness argument to establish full efficiency in the limit with a rate of 1/ in Walrasian auction, while asymptotic full efficiency is also shown for Fisher markets under the gross substitutes condition. Further, Carmona et al. [17] provide sufficient conditions under which equilibria are fully efficient in class of mean-fiele games; understanding thus whether our framework has new implications in such games is an interesting direction for the future. We finally point out that many other papers have focused on learning in auctions and markets; see [21, 43, 104, 8, 9, 32], and references therein.
Conclusions and future work
In conclusion, we have furnished a new sufficient condition under which a family of no-regret learning algorithms, including optimistic gradient descent (OGD), approaches (weak) Nash equilibria. Our cri- terion has a natural economic interpretation, being intricately connected with Roughgarden's 's smooth- ness framework, and captures other well-studied conditions such as the Minty property. We have also shown that clairvoyant gradient descent attains an improved welfare bound compared to that predicted by the smoothness framework, while ensuring at the same time fast convergence to the set of CCE.
There are many promising directions for future work. First, we have seen that under the condition p there exists an algorithm that computes an e-NE in time poly(1/e), leading to pseudo polynomial-time algorithm (under natural game representations); is there an algorithm that instead runs in time poly(log(1//))
Convergence to Nash equilibria via computational hardness? Another promising approach for showing convergence to Nash equilibria is by harnessing computational hardness results for the underlying welfare maximization problem. To be specific, we consider the following condition.
Condition 6.1. Consider a multi-player (A, pm-smooth game G with pe == Thp from class of games C with the polynomial expectation property [79]. For any & E C, computing a joint strategy profile x E Im= X; such that SW 2 Pc OPT + 1/poly(G) is NP-hard, for any poly(G).
Indeed, smoothness often circumscribes the welfare of polynomial algorithms, such as combinatorial auctions under XOS valuations-in fact, unconditionally under polynomial communication; see [34, Theorem 1.4] and [102, Appendix A.7]. Now, the role of Condition 6. is that (unless P = NP) a syyynommally--oondder algorithm such as OGD-whin wwich is efficiently implementable (for games with a polynomial number of actions) under the polynomial expectation property- will have the property that n Di Reg!") (T) 2 -1 PG), for any g E C and poly( which in turn leads the following. Theorem 6.2. Consider a class satisfying Condition 6.1. For any G E C and e = 1/ppoly(G) there is a polynomial-tine algorithm for computing an c-Nash equilibrium, unless P = NP.
By virtue of Corollary 4.3, the same conclusion applies even under the weaker condition that computing a CCE with welfare improving over the smoothness bound hard; this related to the hardness result of Barman and Ligett [6], discussed in the full version of this paper.
10

---

Acknowledgments and Disclosure of Funding
We are grateful anonymous reviewers and the area chair at NeurIPS for valuable feedback. We also thank Brendan Lucier for helpful pointers to the literature. This material is based on work supported by the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876 National Science Foundation grants RI-2312342 and RI-1901403, ARO award W91 INF2210266, and NIH award A2401085001.
References
[1] I. Anagnostides, I. Panageas, G. Farina, and T. Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 536-581. PMLR, 2022.
[2] I. Arieli and Y. Babichenko. Simple approximate equilibria in games with many players. In ACM Conference Economics and Computation (EC), pages 681-691. ACM, 2017.
[3] Azrieli and E. Shmaya. Lipschitz games. Mathematics of Operation Research, 38(2): 350-357, 2013.
[4] Babichenko and A. Rubinstein. Communication complexity of approximate nash equilibria. Games and Economic Behavior, 134:376-398, 2022.
[5] Babichenko, C. H. Papadimitriou, and A. Rubinstein. Can almost everybody be almost happy? In Conference on Innovations in Theoretical Computer Science (ITCS), pages 1 1-9, ACM, 2016.
[6] S. Barman and K. Ligett. Finding any nontrivial coarse correlated equilibrium is hard. In ACM Conference on Economics and Computation (EC), pages 815-816. ACM, 2015.
[7] M. Bowling, N. Burch, M. Johanson, and O. Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218), Jan. 2015.
[8] S. Brânzei. Exchange markets: proportional response dynamics and beyond. SIGecom Exch., 19(2):37-44 45, 2021.
[9] S. Brânzei, N. R. Devanur, and Y. Rabani. Proportional dynamics in exchange economies. In ACM Conference Economics and Computation (EC), pages 180-201 200-201.22 ACM, 2021.
[10] N. Brown and T. Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374)4418-444, 2018.
[11] Böhm. Solving nonconvex-nonconee min-max problems exhibiting weak minty solutions, 2022.
[12] Y. Cai and W. Zheng, Accelerated single-call methods for constrained min-max optimization. CoRR, abs/2210.03096, 2022.
[13] Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou. Zero-sum polymatrix games: generalization of minmax. Mathematics of Operations Research, 41(2))648 665, 2016.
[14] Y. Cai, A. Oikonomou, and W. Zheng. Accelerated algorithms for monotone inclusions and constrained nonconvex-nonconean min-max optimization. CoRR, abs/2206.05248, 2022.
[15] Y. Cai, A. Oikonomou, and W. Zheng. Finite-time last-iterate convergence for learning in multi-player games. Conference on Neural Information Processing Systems (NeurIPS), 2022.
[16] L. Campi and M. Fischer. Correlated equilibria and mean field games: A simple model. Mathematics of Operations Research, 47(3):2240-2255 2022.
[17] Carmona, Graves, and Tan. Price of anarchy for mean field games. ESAIM: Proceedings and Surveys, 65:349-388 2019.

---

[18] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[19] V. Cevher, G. Piliouras, R. Sim, and S. Skoulakis. Min-max optimization made simple: Approximating the proximal point method via contraction maps. In Symposium on Simplicity in Algorithms (SOSA), pages 192-206. SIAM, 2023.
[20] X. Chen, X. Deng, and S. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 2009.
[21] Y. K. Cheung, S. Leonardos, and G. Piliouras. Learning in markets: Greed leads to chaos but following the price is right. In International Joint Conference on Artificial Intelligence (IJCAI), pages 111717. ojgai.org, 2021.
[22] C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and Zhu. Online optimization with gradual variations. In Conference on Learning Theory (COLT), pages 6-1, 2012.
[23] R. Cole and Y. Tao. Large market games with near optimal efficiency. In ACM Conference on Economics and Computation (EC), pages 791-808. ACM, 2016.
[24] R. Baldii-,a R. Cominetti, P. Mertikopoulos, and M. Scarsini. The asymptotic behavior the price of anarchy. In International Workshop On Internet And Network Economics (WINE), pages 133- 145. Springer, 2017.
[25] R. Colini-Baldeschi, R. Cominetti, and M. Scarsini. Price of anarchy for highly congested routing games in parallel networks. Theory of Computing Systems, 63:90-113, 1130 2019.
[26] R. Colini-Baldeschi R. Cominetti, P. Mertikopoulos, and M. Scarsini. When is selfish routing bad? the price of anarchy in light and heavy traffic. Operations Research, 68(2):41 1-434, 2020.
[27] V. Conitzer and T. Sandholm. Complexity of constructing solutions in the core based on synergies among coalitions. Artificial Intelligence, 170(6-7)60776119 2006. Earlier version in IJCAI-03.
[28] V. Conitzer and T. Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621-641) 2008. Early version in IJCAI-03.
[29] K. Cui and H. Koeppl. Learning graphon mean field games and approximate nash equilibria. In International Conference on Learning Representations (ICLR). OpenReview.net, 2022.
[30] C. Daskalakis, P. Goldberg, and C. Papadimitriou. The complexity of computing a Nash equilibrium. In Symposium on Theory of Computing (STOC), 2006.
[31] J. Deb and E. Kalai. Stability large bayesian games with heterogeneous players. Journal of Economic Theory, 157:1041-1055, 2015.
[32] X. Deng, X. Hu, T. Lin, and W. Zheng. Nash convergence of mean- based learning algorithms in first price auctions. In WWW '22: The ACM Web Conference, pages 141-150. ACM, 2022.
[33] J. Diakonikolas, C. Daskalakis, and M. I. Jordan. Efficient methods for structured nonconvex- nonconcave min-max optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of Proceedings of Machine Learning Research, pages 2746 2754. PMLR, 2021.
[34] S. Dobzinski, N. Nisan, and M. Schapira. Approximation algorithms for combinatorial auctions with complement-free free bidders. Mathematics of Operation Research, 35(1):1-13, 2010.
[35] K. Etessami and M. Yannakakis. On the complexity of Nash equilirria and other fixed points (extended abstract). In Annual Symposium on Foundations of Computer Science (FOCS), pages 113-123, 2007.
[36] F. Facchinei and J.-S. Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.
12

---

[37] G. Farina, C. Kroer, C. Lee, and H. Luo. Clairvoyant regret minimization: Equivalence with nemirovski's conceptual prox method and extension general convex games. CoRR. abs/2208. 1e0088.14991 14891, 2022.
[38] T. Feddersen and W. Pesendorfer. Voting behavior and information aggregation in elections with private information. Econometrica, 65(5):1029- 1058, 1997.
[39] M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, and V. Syrgkanis. The price of anarchy in large games. In Symposium on Theory of Computing (STOC), pages 963-976. ACM, 2016.
[40] M. Feldman, H. Fu, N. Gravin, and B. Lucier. Simultaneous auctions without complements are (almost) efficient. Games and Economic Behavior, 1 123:327-341 2020..
[41] Fudenberg and D. K. Levine. Open-loop and closed-loop equilibria in dynamic games with many players. Journal of Economic Theory, 44(1):1-18 1988.
[42] J. Gaitonde, Y. Li. B. Light, B. Lucier, and A. Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. Innovations in Theoretical Computer Science Conference (ITCS), volume 251 of LIPlcs, pages 52:1-52:1. Schloss Dagstuhl Leibniz- Zentrum für Informatik, 2023.
[43] Y. Gao. New Optimization Models and Methods for Classical, Online Fisher Markets. Columbia University, 2022.
and [44] I. Gilboa and E. Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1,80-93, 1989.
[45] P. W. Goldberg and M. Katzman. Lower bounds for the query complexity of equilibria in lipschitz games. Theoretical Comput. Sci., 962, 2023.
[46] N. Golowich, S. Pattathil, and C. Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. Conference on Neural Information Processing Systems (NeurIPS), 2020.
[47] D. A. Gomes and Saúde. Mean field games models-a brief survey, Dynamic Games and Applications, 4:1 1540154,22000000100011 2014.
[48] E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O(1/K) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pages 366 402. PMLR, 2022.
[49] R. Gradwohl and E. Kalai. Large games: Robustness and stability. Annual Review of Economics, 13:39-56, 2021.
[50] R. Gradwohl and O. Reingold. Fault tolerance in large games. Games and Economic Behavior, 86:438 457, 2014.
[51] Y. Guan, M. Afshari, and P. Tsiotras. Zero-sum games between mean-fiele teams: common information and reachability based analysis. CoRR, 12222333.12233 2023.
[52] J. C. Harsanyi, R. Selten, et al. A general theory of equilibrium selection in games. MIT Press Books, 1, 1988.
[53] J. D. Hartline, V. Syrgkanis, and É. Tardos. No-regret learning in bayesian games. In Conference on Neural Information Processing Systems (NeurlPS), pages 3061-3069, 2015.
[54] W. Hoeffding. Probability inequalities for sums bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
[55] Y. Jin and P. Lu. First price auction is 1/e2 efficient. In Annual Symposium on Foundations of Computer Science (FOCS), pages 179-187. IEEE, 2022.
[56] E. Kalai. Large robust games. Econometrica, 72(6): 1- 2004.
13

---

[57] M. J. Kearns and Y. Mansour. Efficient nash computation in large population games with bounded influence. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 259-266. Morgan Kaufmann, 2002.
[58] M. J. Kearns, M. M. Pai, A. Roth, and J. R. Ullman. Mechanism design in large games: incentives and privacy. In Innovations in Theoretical Computer Science (ITCS), pages 403- 410. ACM, 2014.
[59] M. Kearns, M. M. Pai, R. M. Rogers, A. Roth, and R. Ullman. Robust mediators in large games. CoRR, abs//512.02661 2015.
[60] D. Kim, M. Riemer, M. Liu, J. N. Foerster, M. Everett, C. Sun, G. Tesauro, and J. P. How, Influencing long-term behavior in multiagent reinforcement learning. CoRR, abs/2203.0353, 2022.
[61] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Symposium on Theoretical Aspects in Computer Science (STACS), 1999.
[62] J. Kulkarni and V. S. Mirrokni. Robust price of anarchy bounds via LP and fenchel duality. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1030-1049. SIAM, 2015.
[63] D. Lacker and K. Ramanan. Rare nash equilibria and the price of anarchy in large static games. Mathematics of Operations Research, 44(2):400-427 422. 2019.
[64] J.-M. Lasry and P.-L. Lions. Mean field games. Japanese journal of mathematics, 2(1): 229-260,, 2007.
[65] M. Laurière, S. Perrin, S. Girgin, P. Muller, A. Jain, T. Cabannes, G. Piliouras, J. Pérolat, R. Elie, O. Pietquin, and M. Geist. Scalable deep reinforcement learning algorithms for mean field games. In International Conference Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages
PMLR, 2022.
[66] T. Lin, Z. Zhou, P. Mertikopoulos, and M. I. Jordan. Finite-time last-iterate convergence for multi-agent learning in games. In International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 6161-6171. PMLR, 2020.
[67] B. Lucier, S. Pattathil, A. Slivkins, and M. Zhang. Autobidders with budget and ROI constraints: Efficiency, regret, and pacing dynamics. CoRR, abs/2301.13300 2023.
[68] G. J. Mailath and A. Postlewaite. Asymmetric information bargaining problems with many agents. The Review of Economic Studies, 57(3):351-36) 1990.
[69] F. McSherry and K. Talwar. Mechanism design via differential privacy. In Annual Symposium on Foundations of Computer Science (FOCS), pages 94-103. IEEE Computer Society, 2007.
[70] P. Mertikopoulos, C. H. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2703-2717 SIAM, 2018.
[71] P. Mertikopoulos, B. Lecouat, H. Zenati, Foo, V. Chandrasckhar, and G. Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations (ICLR). OpenReview.net, 2019.
[72] P. Milgrom and R. Weber. Distributional strategies for games with incomplete infromation. Mathematics of Operations Research, 10:619-632, 1985.
[73] J. Milionis, C. H. Papadimitriou, G. Piliouras, and K. Spendlove. Nash, conley, and computa- tion: Impossibility and incompleteness in game dynamics. CoRR, 0ts/2203.111225 2022.
[74] P. Muller, M. Rowland, R. Elie, G. Piliouras, J. Pérolat, M. Laurière, R. Marinier, O. Pietquin, and K. Tuyls. Learning equilibria in mean-field games: Introducing mean-field PSRO. In Autonomous Agents and Multi-Agent Systems, pages 926-934. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022.
14

---

[75] U. Nadav and T. Roughgarden. The limits of smoothness: A primal-dual framework for price of anarchy bounds. In International Workshop On Internet And Network Economics (WINE), volume 6484 of Lecture Notes in Computer Science, pages 319-326. Springer, 2010.
[76] J. Nash. Equilibrium points in n-person games. National Academy of Sciences, 36:48 49, 1950.
[77] A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1), 2004.
[78] K. T. Nguyen. Game efficiency through linear programming duality. In A. Blum, editor, Innovations in Theoretical Computer Science Conference (ITCS), volume 124 of LJPlcs, pages 66:1-66:20. Schloss Dagstuhl Leibniz-7entrrum für Informatik, 2019.
[79] Papadimitriou and Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM,
2008
[80] J. Pérolat, S. Perrin, Elie, M. Laurière, G. Piliouras, M. Geist, K. Tuyls, and O. Pietquin. Scaling mean field games by online mirror descent. In Autonomous Agents and Multi-Agent Systems, pages 0128-107.. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022.
[81] J. Perolat, B. D. Vylder, D. Hennes, E. Tarassov, F. Strub, de Boer, P. Muller, J. T. Connor, N. Burch, T. Anthony, S. McAleer, R. Elie, S. H. Cen, Z. Wang, A. Gruslys, A. Malysheva, M. Khan, S. Ozair, F. Timbers. T. Pohlen, T. Eccles, M. Rowland, M. Lanctot, J.-B. Lespiau, B. Piot, S. Omidshafiei, E. Lockhart, L. Sifre, N. Beauguerlange, R. Munos, D. Silver, S. Singh, D. Hassabis, and K. Tuyls. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623):990 99699999999999999999919999 2022.
[82] S. Perrin, M. Laurière, J. Pérolat, R. Élie, M. Geist, and O. Pietquin. Generalization in mean field games by learning master policies. In AAAI Conference on Artificial Intelligence (AAAI), pages 9413-9421. AAAI Press, 2022.
[83] W. Pesendorfer and M. Swinkels. The loser's curse and information aggregation in common value auctions. Econometrica, 656))1144711281, 1997.
[84] T. Pethick, Latafat, P. Patrinos, O. Fercoq, and Cevher. Escaping limit eycles: Global con- vergence for constrained nonconvex-nonconcave minimax problems. CoRR, abs/2302.09831, 2023.
[85] G. Piliouras, R. Sim, and S. Skoulakis. Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[86] Rakhlin and K. Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, 2013.
[87] S. Rakhlin and Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
[88] J. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica, 33(3):520-534, 1965.
[89] T. Roughgarden. Barriers to near-optimal equilibria. In Annual Symposium on Foundations of Computer Science (FOCS), pages 71-80. IEEE Computer Society, 2014.
[90] T. Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM, 62(5): 32:1-32:42, 2015.
[91] T. Roughgarden. The price of anarchy in games of incomplete information. ACM Trans. Economics and Comput., 3(1::611-6:00, 2015.
15

---

[92] T. Roughgarden and F. Schoppmann. Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 156:317-342, 2015.
[93] T. Roughgarden, V. Syrgkanis. and É. Tardos. The price of anarchy in auctions. Journal of Artificial Intelligence Reseurch, 59:59-101, 2017.
[94] A. Rubinstein. Inapproximability of nash equilibrium. SIAM Journal on Computing, 47(3): 917-959, 2018.
[95] A. Rustichini, M. Satterthwaite, S. Williams. Convergence to efficiency in a simple market with incomplete information. Econometrica, 62:1041-1063, 1994.
[96] D. Schmeidler. Equilibrium points of nonatomic games. Journal of statistical Physics, 7: 295-300, 1973.
[97] P. G. Sessa. I. Bogunovic, Krause, and M. Kamgarpour. Contextual games: Multi agent learning with side information. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
[98] S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2), 2012. ISSN 1935-8237,
[99] L. S. Shapley. Some topics in two-person games. In M. Drescher, L. S. Shapley, and A. W. Tucker, editors, Advances in Game Theory. Princeton University Press, 1964.
[100] S. G. Subramanian, M. E. Taylor, M. Crowley, and P. Poupart. Decentralized mean field games. In AAAI Conference Artificial Intelligence (AAAI), pages 9439-9447. AAAI Press, 2022.
[101] Syrgkanis. Bayesian games and the smoothness framework. CoRR, abs/1203.5155, 2012.
[102] V. Syrgkanis and É. Tardos. Composable and efficient mechanisms. In Symposium on Theory of Computing (STOC), pages 211 211-220. ACM, 2013.
[103] V. Syrgkanis, A. Agarwal, H. Luo, and E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, pages 2989-2997, 2015.
[104] Y. Tao. Market Efficiency and Dynamics. PhD thesis, New York University, 2020.
[105) E. Vlatakis- KHarakki-G L.. Flokas, T. Lianeas, P. Mertikopoulos, and G. Piliouras. No-regret learning and mixed nash equilibria: They do not mix. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020.
16

---

A Omitted proofs
In this section, we provide the proof's and a number of results omitted from the main body.
A.1 Proof of Theorem 3.1
We commence with the proof of Theorem 3.1. Below, we give more detailed version of the statement provided earlier in the main body. We first state an auxiliary lemma which will be useful for the proof, and can be extracted from earlier work [1]
Lemma A.I. Suppose that player E Then, for any time E N.
[n]] updates its strategy using OGD with learning rate n >
Dx + ||au,"/1] (1mz)) a651 12 ||a! a! 11(t1112) 17
(RGAP;(x(.)) S
In the sequel, denote by B; Ry any number such that (x=:))l S Bü, for any E II. X, In the asymptotic notation below, we make the standard assumption that the parameters B, and Dx. do not depend on the number of players
Theorem A.2 (Precise version of Theorem 3.1). Consider n-player (A, -mmoohh game Gn such
that the game operator F, is Ln -ipiscchht continuous and X 2 (1 (1 + μ) (pn. 2 - 6a). Suppose further that all players follow DGD with learning rate 1h ILm and any initialization
(a)) al E II Nr If En 0, then after T 21 iterations there is a time D
t" E [T]] such that
maxigiso D3
BRGAAP,
< 32
max BP)
705 + p)OPTg
(4)
(nm)
1st5n
On (Ln g.
(5)
In particular, for 11.2
:
13, 1* constitutes a
1
On
Ln OPTS
.6) weak Nash equilibrium.
Vo
On the other hand, en then for any T N there is time E [[]]] such that
8 (maxisisa D2
Σ (BRGAP,(2((t))
max B² Isi5n
D2
(n7))
Before we proceed with the proof, we that the underlying assumption μ4 O1) in the asymptotic notation above is consistent with known smoothness bounds in large games [39]; we also refer Remark A.10 for an important point regarding the range of the smoothness parameters.
Proof of Theorem A.2. We will first translate the assumed property p.. 2 6, to a lower bound on the sum of the players' regrets. In particular, have that the sum of the players' regrets Σ Reg,"" (T) for any E N can be expressed as
Σ max 2
uula v (2))
Σ (w() > AOPT - (1 u) Σ sw(x
(6)
by Definition 2.1, where (>, n1) are the assumed smoothness parameter of G.. Now, using the assumption that P.. 2 1 - En, it follows from (6) that Σn == Reg. (7) is in turn lower bounded by
T
(1 (w=
(1 p)) Σ (0) -Ex(1 PPOPT T,
(7)

---

where we used the fact that O., 2 SW(x!") (by definition of the optimal welfare). We next appropriately upper bound the sum of the players' regrets Ei=1 Reg!") Using a slight refinement of the RVU bound [103, 87], it follows that the regret Reg;
(T) can be upper bounded by
T
1 2m/n
D + Tm Σ I
10
Σ
[1 - o + +1100 (t) x; (1(+1) 112
m,
27m
which in turn implies that the sum of the regrets
Σi=1
Regi
(T) is upper bounded by
Σ
Di
Tn Σ |1(00) 10 2nm Σ (|x(1) a |x((0 - 1((+)))))
(8)
2mmn
where we have defined (t) = (uj (1) ..... un!²) and m (1) = (m (1))) ! Moreover, by the
Lipshipsc continuity of the game operator Fg.., it follows that [x(0) m 1 2|2 | (z(10)
Fg.. (x (t- ]]2 S Ln| - x 111 for any t E [T], where we also used the fact that m())
and (0) == (1), Combining with (8), it follows that for any Tn S Alm.
T
Σ Reg S
D3
Σ
=000 + (1x -0100)
111+11113
(9)
2mn 1=1
47mm
As result, combining (7) and (9) we have that
Σ (1Z2)) (1) + 11x =0(+2))133 2 >
D2x + (1 T.
(10)
i=1
Next, applying Lemma A.1 yields that
T
2 (RG (1)
max; D
max B²
Σ
( - 2000 + 11x a0 12)
1=1
max, D3
max B3 (2D + 4m (1) (11)
where the first bound uses the inequality (a 3)2 S 2a + 2,32, while the second bound follows
from (10) by noting that D& > Dic. As result, we conclude that there exists t* E [T]
namely t = arg mini Ei=1 ((()) such that
maxigisa D
( D2 + 4m 4))
(RGAA)(()(())) <4
max BB Isisn
nh
(12)
D3 Now, if 6n # O, taking T 2m (1==(11++PP)1 OPT... guarantee terms of weak Nash equilibria (per Definition 2.2) in (2) can be derived from (4) as follows. We consider parameter 5 E (0, 1) so that 5n |õn] Let also be the minimum among the
(1+a) implies (4). The claimed approximation
21 D3
ôn largest numbers from BRGAP, ((E())((((()))))))) )..(""))... BRGAP, (x)(")) Then, Σ (BRGAP,(E 2
ne2n, and by (12) it follows that
maxisisn D3x
11 + M)PTTs.. max B²) Isis
<
32
V8
nh
n
This implics (2) since (t") ((')) is by definition an (c, -eekk Nash equilibrium. Finally, if ef = 0 the claimed bound follows directly from (12).
We note that the asymptotic notation in (2) and (5) applies in the regime I.,, 2 22 (1); this can be enforced by simply taking L', = 1,
18

---

Remark A.3. One can also introduce a variant of weak Nash equilibria which is instead parameterized by the average over the players' best response gaps n Ex=1 (-GAP, Inequality (4) implies that
the average best response gap of (x(") can be bounded by On (V VL
Ly O.
76
Remark A.4. While Theorem A.2 bounds the (weak) Nash equilibrium gap of a single iterate of the dynamics, (11) implies that at least a 1 y fraction of the iterates of the dynamics constitutes
V0y On LL..o
(V
-weak Nash equilibrium. So, by selecting time index t* E [T]]]
uniformly random we obtain the desired guarantee with high probability, incurring only a small degradation in the solution quality.
In particular, if en approaches to 0 with sufficiently fast rate, Theorem A.2 also implies convergence to the more standard notion of Nash equilibrium (i.e., Definition 2.2 with o = 0). as we state below. In particular, the following corollary can be derived directly from (4).
Corollary A.5. In the setting of Theorem A.2, if it additionally holds that o S on),,, OGD yields on o, (1)-Nash equilibrium after a sufficiently large number of iterations.
On the Lipschitz constant Next, we make some remarks regarding the dependence of the Lipschitz constant L.. on the number of players in the context of general normal-form games. We first note that the Lipschitz constant L. of the underlying game operator can always be bounded as (n))
Lemma A.6 (Lipschitz constant in normal-form games). For any n-player normal-form game g with utilities bounded in [-1, 1], the Lipschitz constant Ln of the game operator satisfies Ln S
n maxigien A.).
Proof. For any player i E [n]] and any joint strategies æ, x' E Ili= A(Ai), we have (x=
[[,(x ur( S v [Aill
uu uz("""))ll
(13)
$ SA
Σ
ailsa-))
II 87
ax [aw] II a [ar]
(14)
a-iEA-i
S AA
Σ
II 8/ti
my (ax)
II ar'e [ay] x
(15)
a i
< V A
|00
S max 1si5n
[A:
| a
(16)
Rig
where (13) uses the equivalence between the & and the foo norm; (14) follows from the definition
of the (expected) utility: u,(a; x) == Ea_.sa_, (a) = Ea_EA_ u((a) II xy,' [azt]. for
any a; E A. (15) uses the triangle inequality along with the assumption that [u; (a)l S 1; and (16)
follows from the well-known fact that the total variation distance between two product distributions can be upper bounded by the sum of the total variation distance of each individual component [54], as well as the equivalence between the ε and the &g norm. As a result, continuing from (16), we have
2
2
[[(()) - F(z')13 =
1u, (x) - u. ux
max 13t5n
(A:1)
Σ
Σ
x lla
2=1
2 |
S n²
max I8iSn
|4il
22'123
where the last inequality used that, by Jensen's 's inequality,
-
5 (n
1) E) 21 < n||æ d'1 This concludes the proof.
Graphical games As byproduct of the proof above, we next point out an important refinement of Lemma A.6 concerning graphical games. In particular, here we assume that the utility of each player i E [n]] only depends on the actions of players belonging to its neighborhood N, S [n]]] \ {i).
19

---

We further assume that [a v A for any player E [n], where A N will be referred to as the degree of the graphical game. To conclude the definition, we also posit that each player i [[x]]] can only affect the utilities of at most A other players: V E [m] : E No S A.
Lemma A.7 (Lipschitz constant in graphical games). For any n-player graphical game with degree E N and utilities bounded in [-1,1] the Lipschitz constant La of the game operator satisfies
Ln A mixisisn [Aa]
Proof. For any player [n]] and any joint strategies x, x' E II A(Ai), we have
(x= u, 1)l S v [A
(x;(x-)) :) - u;(o"";)loo
- Ail
Σ
II
xe [ay]
II
a''s 2ty(ar)
1IveN; Ar AEEN
PEN.
Ai
||000
a'vlli
S max
[A:
|| - x2/y122
1si5n
PEN:
PEEN
where the derivation above is similar to that in Lemma A.6. As a result,
[F(x) - F(z'112 =
Σ
lu,(a= - u. (2'
n 2
max ISaS
D
MEN
n
max 1sisn
[4.1
20 2
iEN:
2 n
max Isis
AA.1
Σ
x
-
E
[m] :ie
i=1
2
S 2
max
M4il)
||
x'
0e112
Isisn
Games with vanishing sensitivity We next focus on different subclass of normal-form games; namely, games with small sensitivity (per Definition 3.5). Taking a step back, in graphical games every player can only be impacted by (and have an impact to) a small number of other players. Instead, here we consider games where player's utility can be impacted by all other players, but only by small amount.
Lemma A.8 (Lipschitz constant in games with vanishing sensitivity). For any n-player normal- form game with sensitivity en E Ry.. the Lipschitz constant Ln of the game operator satisfies L, f maxigisn |A,].
Proof. Let [m]. For 31, a/ E A(Ai) and a E A- (restricting on Player 1 here is without any loss, and only made for the sake of simplicity in the notation), it follows that
u a. u,(2', a-)
Σ
21 a
[l a
Σ
a1E.A1
Σ
(21[ai]- - [aaaaau (01 o (dll))
Σ
(01 - (a(aa))))((( ulah, a))); (17)
20

---

for some of E A1. where we used that (zile'l x = Eoredi Mor - 21(01]) since
11, E A(A)). Continuing from (17), we have
[1, a-1) uu, a-1)
E
[
2 (1 a-1) ui(d], a-1)l
a1EAt\(a)
S
Σ
[1 - [ai]] 6n||ar - - a/ll1;
a1EA)\(a1)
where en is the sensitivity of the game. Similar reasoning yields that (u;(x)) un ui(2 xr-1)
'n 11 - x/ 11, for any x-1 E I (AA)). As a result, we have
(x-1) u1(x''1)ll S (: 22, ................................ In) u1 2.2 23. ................................ .nn
+ | (:: 2/22 U3 ................................ Un) 11 (s+ 222 T'3 3n,
+ ...
+ Juq (-, 2/2, rzg...... ./ 1 un uz 2/2, 2'y ................................ xx,)
$ cn Σ | x1112.
By symmetry, we have shown that [x_;) ui uu loo S en Eeyilla; 2%/111, and the rest of the argument is identical to that of Lemma A.6.
Polymatrix games A careful examination of the proof of Lemma A.8 reveals that its conclusion in fact applies under more relaxed condition compared to what imposed by Definition 3.5; namely, we can define
max maxmax max (u((a) ua(a,, a-))l. ISSa aEA l'ft EA,
(18)
In words, when considering the utility player i E [n]] we only bound deviations by players besides i. It is easy to see that Lemma A.8 in fact applies even if E IR is defined as in (18). This observation enables capturing other interesting classes games under the premise that L,, (1), such polymatrix games. Specifically. a polymatrix game is defined with respect directed graph G = [[n], , E), so that each node of G is uniquely associated with the corresponding player. For every edge (i, d') E E there is matrix A, AA that the utility of Player i is defined as
underlying
(xx)) 1 ET VEN.
(19)
where N₁ := ft' [n]] (1,7) E E}. Unlike the class of graphical games we saw earlier, here we do not restrict the size of the neighborhoods. For this reason, we have normalized each player's utility by a 1/n factor in (19), for otherwise the utilities are not guaranteed to bounded (independent of the number of players n). It is then easy to see that polymatrix games are subject to Lemma A.8 under defined in (18), which here satisfies e = O(1nn) Below, we provide a simpler and sharper argument compared to Lemma A.8.
Lemma A.9. For any n-player polymatrix game, the Lipschitz constant To, of the game operator satisfies L,, maxggae A 2 where || ||2 here denotes the spectral norm.
21

---

Proof. By definition of the utility functions in (19), we have that for any player i E [n] and 2, x E I[:=1 A(A,).
[,,( - (1(22=,))1
Σ PEW.
A - odd)))
Σ
| (x.g
=2/:)112
7 KEN;
Σ
||A 1|2 2//122
n PEN,
(i.))E
| 1l2
|00 22/122
MEN
and the claim follows.
A.2 Games with vanishing sensitivity
We next establish an important implication of our framework concerning the class of games with vanishing strategic sensitivity (per Definition 3.5); the statement of the theorem is recalled below.
Theorem 3.6. Consider an n-player game Gn with sensitivity en. E Ryo. Then, = (n(n) iterations of OGD suffice to obtain ( On (en -weak Nash equilibrium, for 8 (0,
Proof. Let i [n]. Following the proof of Lemma A.8, the definition of sensitivity implies that (,, x--) (x(x)) S 6,1|= æill1 I 2cn, for any æ E IT_ ((A,) and æ E (AA.). The proof now follows that of Theorem A.2. In particular, regrets as follows.
lower bound the sum of the players'
Σ uulat x0 10g
I u (z(t))
Reg.
max (AAA)
Σ t=1
T
lus (2/,,, x ( - us (x(())))
-2I
t=1
As result, following the proof of Theorem A.2, we conclude that for learning rate 7n == 41.,, there exists time t* E [T] such that
Σ (a(1)) 54
maxisign D2
max B
(2Dx
4m
ISisn
T
Thus, setting
D2
2D
T
< 2DD
max
[Ai]
On(n),
ISiST
by Lemma A.8, yields that
Σ (BRGAP((Z(())))
where the asymptotic notation above applies in the regime In 2 (n) The statement thus follows.
We note that the conclusion of Theorem 3.6 also applies under the weaker notion of sensitivity defined in (18), if we additionally assume that there exists xt E II A(A:) such that for any E [T A(A,).
Σ
u
(
x
u;(x) 2 -16p
(20)
i=1
22

---

Condition (20) can be met even in games with large sensitivity (Observation 3.4), which is why we chose to state Theorem 3.6 under a stronger but more interpretable condition.
Next, we point out two interesting extensions of our approach based on developments following the original smoothness framework of Roughgarden [90].
A.3 Refined smoothness
Throughout this paper we have relied on the original smoothness framework [90] to derive much of our results. Nevertheless, it is worth noting that there are certain extensions documented in the literature that can make our predictions sharper. To be more precise, focusing on normal-form games, Nadav and Roughgarden [75] noted that the original smoothness framework is in fact able to provide efficiency bounds for a set of equilibria even more permissive than CCE, which they refer to as average CCE with respect a welfare-maximine
strategy x I (AA)) (ACCE*). In particular, the latter relaxation only requires guarantee for the average regret over the players, 1 Ei= Reg, (xt)).
while CCE instead requires a guarantee for the maximum regret maxisisn Reg, (T) Based on this observation, Nadav and Roughgarden [75] developed primal-dual framework order provide refined guarantees (beyond the original smoothness framework) for CCE*, which boils down to solving the following linear program.
maximize subject to
p Σn 2 (u: a-i) 11--41 ua(a)) 2 of A.,
(21)
2
Here, is assumed that the underlying game is in normal form, with II A being the set of joint action profiles, and a* E II== A, a welfare-maximizing maximizing joint action. (The formulation of Nadav and Roughgarden [75] is based on cost-minimization games, but of course their LP can be cast games in the form of (21).) The above LP a simple transformation
directly for of the fractional- lineaa program corresponding to optimizing p == I+ subject to the smoothness constraints of Definition 2.1, but with the additional flexibility of optimizing over a vector E Ro En. this exactly recovers the LP for computing the robust price of anarchy- given in (24). Nevertheless, Nadav and Roughgarden [75] pointed out that the additional flexibility of (21) can have arbitrarily large impact on the predicted efficiency [75, Remark 1].
A
In particular, when restricting #1 22
The sharper definition of smoothness introduced by Nadav and Roughgarden [75] can be leveraged in our framework as follows. We can define a generalized robust price of anarchy as the solution of the LP (21). If this quantity approaches to 1 with sufficiently fast rate (in terms of the number of players), we can extend Theorem A.2 by analyzing the weighted sum of the players' regrets Ei_ Reg, (T). It is easy to see that the argument of Theorem 3.1 readily carries over under the condition that the ratio z 2zr bounded for any i, i' e [n]], well the assumption that each 2; is bounded away from 0. In contrast, if there exists a pair i, E [n]] for which the ratio zi/2y is unbounded, our current techniques do not appear to applicable; this related to the well-known difficulty of deriving so-called RVU bounds for the maximum of the players' regret, instead of their sum [103]. In other words, our current techniques can sharpen Theorem 3.1 by considering solutions of (21) under the additional (linear) constraint that the variables {z, J have bounded pairwise ratio. Given that the more general framework Nadav and Roughgarden [75] leads to improved bounds, expect that this modification should have applications in setting well. In particular, point out that the 2-player example of Nadav and Roughgarden [75] that separates ACCE* from CCE* indeed satisfies 21 / 22 xe 2.3 [75, Proposition 2], so the separation manifests itself even when the pairwise ratio is bounded by an absolute constant.
We finally refer to the works of Nguyen [78] and Kulkarni and Mirrokni [62] for a different primal- dual take on smoothness.
A.4 Local smoothness
Another interesting extension of our techniques can be obtained using the framework of local smoothness, first introduced by Roughgarden and Schoppmann [92] and recently refined by Nguyen [78] in the context of splittable congestion games. In what follows, we follow the treatment of Nguyen
23

---

[78] as it fits our framework. In this context, Nguyen [78] introduced the notion of (A, -dall smooth differentiable utility function Rzo Rzo with the property that for every vectors
= ( 2n) RS and z' = (zi,...., ......
RR
n
u1(z)
Σ 2(42 2))((=) 2 Xe'u(z') μzu(z))
(22)
where 2 = - and 2' = Di= 2/. We also note that u' above denotes the derivative of u. (Again, (22) has been translated utility- matiity-mximizttiinn games compared to the original formulation of Nguyen [78].) Furthermore, splittable congestion game is called (X, fu)--udlllsmoot smooth [78] if for every resource e E the utility function ue E2 + Rz is (A. -suooooo- in the sense of (22). The importance of Nguyen's 's extension is that it can be applied to coarse correlated equilibria, as opposed to the original definition of Roughgarden and Schoppmann [92] that was applicable to correlated equílibria; this distinction is incidentally important for our framework.
We will connect this concept of local smoothness with the linearization of the players' regrets. In particular, the utility of a player i E [m] under joint strategy æ is defined as (x(x) = Eeen x;
lele.) Then,
0u; = ue Σ
Exilel xvlel
+ tz//elu/
Σ _ollel
[x
As result, for any E N.
Σ (ot x
Va, (x(()))
= Σ
ue (x)eee))a== [e]- -E un (a((e))a))
cEE
EEE
2c [e] (x] x; (xx
EEE
with the understanding that æz(c] == ΣE a. [e] and x
[c] = Σー " for any e E E. Now let (T) (at) It= (x x Va, (z))). Combining the last displayed equality with
us define Rega.
T
local smoothness (22), we get that
Reg (z; 2 Σ x [e]ue (e) (μ + 1) Σ (xlee)
EEE
EEE
= ASS(x*)) - (p (z).
(23)
Consequently, if we define a local smoothness bound, PC == Itu with (A, 1) being subject to (22),
Theorem 3.1 can be readily extended in the regime PC - 1 based on (23).
A.5 Considerations based on PoA
natural to ask if the conclusion of Theorem 3.1 can be relaxed PoA + 1. Here, we point out that such an assumption does not suffice to obtain interesting guarantees. In particular, we next note Proposition 3.7, stated earlier in the main body, which is immediate byproduct of the hardness of computing Nash equilibria in constant-sum games.
Proposition 3.7. Even under the promise that PoΛç = 1, computing a (1/poly(g) (-aassh -Nahh equilibrium in normal-form games in polynomial time is impossible when n. 2 unless PPAD C P.
Proof. Chen al. [20] showed that computing a (1, (maxx |Aas))-Nash equilibrium a general- sum two-player game in normal form is PPAD-hard. As a result, the same applies in constant-sum
3-player games by suitably incorporating an additional player who has no strategic impact on the game. Further, in any constant-sum game G it clearly holds that PoAg 1, concluding the proof. O
Remark 1. The positive result established Theorem A.2 requires that p R 1 under a bounded pair of smoothness parameters (A, u)). One may wonder whether similar conclusions apply even
24

---

when the smoothness parameters are unbounded. In particular, the robust price of anarchy (rPoA) can be defined as the solution to the following linear program.
maximize subject to
P
2
Σ
(2s (4, a-;) u,())) 2 pSW(a") -
Ab,
(24)
2 220.
0.
E ;= A; is a welfare-maximinng action profile, which can be assumed to be unique for the purposes of our discussion here. In this context, can extend the conclusion of Theorem A.2 under the assumption that rPoAg. - 1? In general, that is not possible. Indeed, in any constant-sum sum game can make the LP (24) feasible by taking rPoAg, = for any constant-sum game G. Thus, assuming merely that rPoAg - is not enough to obtain interesting guarantees for computing Nash equilibria (in accordance with Proposition 3.7). In other words, our underlying assumption that the smoothness parameters are bounded is necessary. To further explain this discrepancy, we note that constant-sum game is generally not (1 + μ., p)- smooth (for a finite > -1). for otherwise any constant-sum game would satisfy the Minty property (Proposition 3.3), which would in turn contradict Proposition 3.7. The case where = optimal solution of (24) essentially corresponds to pathological manifestation of smoothness in which the underlying parameters are unbounded. We stress again that throughout this paper, when we say that a game is (A, -mooooh we, of course, posit that those smoothness parameters are finite. Further, when we say that Pg in a game G, we accept that there are finite smoothness parameters associated with Pg. With this convention, we reiterate that there are games in which rPoAg A pg-
Above a² -ai
0 and p 1; that is,
in any
Next, we provide a concrete example based on Shapley's s game [99] in which OCD (unconditionally) fails to converge to an c-Nash equilibrium, for a constant c >> 0.
Example A. We consider a 3-player game G defined as follows. We let
1
2 1
A =
2 1 1
B = 1 1 2
(25)
1 2
2
1 1
Then, we set Un (21, 322 x33) == 21 A U2(21, U2 2z) == 2. Bæy, and uy(01, 22 03) = 3
aT Ax² 2; Bæz. Thus, for any joint strategy (æ1, 22 223) it holds that SW(#), 22, 2:3) = 3.
implying that PoAg 1. Further, G is in normal form. Now, through numerical simulation
draw the following conclusion: Although PoAg = 1, for T > 1 OGD with learning rate vj == 0.01 and initialization (a(") _.a"""')))))))) .)) ((0.5, 0.25, 0.25), (0.25, 0.5, 0.25). .) satisfies NEGAP(x 2 0.1875 for any i [T]. where (zx()) )(21 is the sequence of iterates produced by OGD. We note that here we do not consider the initialization from the uniform distribution simply because that happens to be the unique Nash equilibrium in Shapley's ' game; the conclusion above readily applies for any initialization by suitably modifying the underlying game. We also note that the specific value for the learning rate specified above is used for concreteness, and the conclusion is not tied to that specific value.
We next note another separation between the bound predicted by smoothness and PoA, which gives an additional reason why the smoothness framework more suited as criterion for determining tractability. Below, we make for simplicity the assumption that the game has a unique welfare- maximizing action profile, which can always be enforced by incorporating an arbitrarily small noise in the players' utilities.
Proposition A.12. Determining whether a game is (h, -)ssmhoth can be done in polynomial time in explicitly represented normal-form games. In contrast, even in two two-player games, determining PoA is NP-hard.
Proof. First of all, the welfare-maximizee action profile a" E [T=_, A, can be trivially computed in polynomial time (in the size of the input) since the game is explicitly represented. For a legitimate p) pair, determining whether the game is (A, (4) -moohh can be phrased as a feasibility linear program, with a number of constraints equal to the number of possible joint action profiles, each corresponding to a separate constraint (1); namely, Σn= u.(a?, a-:) 2 XOPT - / Σm (a). As a result, the number of constraints is polynomial in the description of the game (since it is assumed that the game is explicitly represented). Furthermore, one can optimize over the smoothness parameters by considering the LP (of polynomial size) given in (24), which determines the robust price
25

---

of anarchy (rPoA). In accordance with Theorem A.2 (see Remark A.10), one can also incorporate
the constraint 2 2 1/poly(g). Regarding the second claim, hardness of determining PoA even in two-player games follows directly from the reduction of Conitzer and Sandholm [27, Theorem 1]. In partieular, an algorithm computing PoA would enable determining the satisfiability of a SAT formula.
L
One important question is whether smoothness can be identified in polynomial time even in succinctly represented games [79]. Indeed, the obvious algorithm for identifying smoothness described above requires a number of constraints that scales exponentially with the number of players, which is especially problematic in the regime of large games focus on in Section 3.
We need to clarify, however, that knowing the smoothness parameters is certainly not a prerequisite for applying our approach. In detail, one can first of all apply Theorem 3.1 in classes of games where there are available analytical bounds for Prx as a function of n. obviating the need to determine whether Prr is close to 1. Besides this point, and more importantly, one can always execute the algorithm prescribed by Theorem 3. -.whic does not require any knowledge regarding the smoothness parameters- and then efficiently evaluate the solution quality (per Definition 2.2). If the desired accuracy has been reached, then this is precisely the initial goal; otherwise, we can safely assume that the preconditons of Theorem 3.1 are not met.
A.6 Smoothness does not suffice for convergence
Next, we provide for completeness an example of a smooth game where OGD fails to converge to Nash equilibria. This shows that, as expected, it is not merely enough to know that o 0 to obtain interesting guarantees.
Example A.13, This example is based on a bimatrix game in normal form described with the payoff matrices
0.2
0.8
0.9
0.3
00.4
0.2
0
0.17
0.2
0.8
0.2
0.3
0.5
0
0.2
0.8
A
B
(26)
0.9
0.2
0.4
0.4
0.7
0.8
0
0.4
0.6
0.9
0.3
0.1
[0
0.1
0.4]
We first claim that this bimatrix game satisfies Pg 2 0.125. Indeed, we first that the welfare-
maximizing profile of (26) reads (æj, = ((0, (,,,0, (1, 0)), We also claim that for any pair of actions dj E Ai and a2 Ag it holds that
2
4, (,] a-;) 2 0.125 -1125-015 OPPS.
where 0PTg = 1.6. As a result, it follows that for any æ1 E A(A)) and æ2 E A(A2) it holds that
02>~2 02 12 x un u,( (.))) > 0.125 OPT in turn implying that > uz( x_.) > 0.125 - OPTg. This means that G is (0.125, -mmoohh. Furthermore, through numerical simu- lation we draw the following conclusion: for T >> 1, OGD with learning rate 7) == 0.01 satisfies (t)
NEGAP(2 (t) (2) 2 0.046 for any t E [7]], where (a 22 )e21 is the sequence of iterates pro- duced by DGD. Once again, it is worth noting that this conclusion is not tied to the specific choice of learning rate we chose above, which is only used for concreteness.
(t)
A.7 Bayesian mechanisms
In this subsection, we consider the standard independent private value model of Bayesian mechanisms. In particular, each player e [n] has a type U, drawn from a distribution F. over a finite set of types V; without any loss, we may assume that J; is the uniform distribution over V, It is further assumed that players' types are pairwise independent. After each player i E [m] draws a type e; F, selects an action (2:)) E Ag, which is a function of its type Us Now consider a fixed profile of types V1 x V/2 ... V,, The (expected) utility of Player i under joint strategy profile =(v) is denoted by u;(:;; v;) == Ea-æ
E V
[a [a; v; }. There is also a principal agent who does not take an action in the game, and whose utility under ar is given by R(x)) == Eg-= R(a)). Accordingly, the social welfare is defined as SW(2, v) == - (=; vz) + R(x). while OPT OPTM(( (v) represents the optimal social welfare of mechanism M as a function of the joint type v E V. We will make the assumption that the utility functions assign solely nonnegative values.
n
26

---

Smooth mechanisms Analogously to the notion of smooth game (Definition 2.1), Syrgkanis and Tardos [102] introduced the notion of smooth mechanism, formally recalled below.
Definition A.14 (Smooth mechanism [102]). A mechanism M is (A, p--smooth, where X, 2 0, if there exists an strategy profile (v) I ((A)), for every type profile V, such that for any action profile a E A and type profile a = (C1,... Un) E V.
Σ (v). a- 2 (OPT jR((a).
(27)
As it turns out, many important mechanisms satisfy the above definition under various parameters (A, [102]. For (A, w))smooth mechanism M, we define PM max
Definition A.15. Let x; Vi + ((A)) be the strategy of each player i E [m]. A joint strategy
profile is Bayes-Nash equilibrium (BNE) if for any player i [[]] any type Us V, and deviation af E A..
Eu_,-__ (x()); 2 E._,,r_, (a (v;(v=)); wz)].
(28)
This definition coincides with the standard notion of Nash equilibrium saw in Definition 2.2 when each distribution F; is a point mass. We also note that an e-BNE incorporates an e 2 0 additive slackness in (28).
Population interpretation of Bayesian games In the agent-form representation of a Bayesian game [53], it is assumed that there are finite subpopulations of players, each corresponding to
player E [n]] Each player belonging to population corresponds to a type v; E V,, which is distinct in each population and across populations. In this induced population game, nature first draws one player from each population, and then each player is selects an action a, (e;);; the game is then played under those selected actions. In symbols, the utility of Player v, from population reads
AG (a) (a()) m:)1 (v:)):
(29)
where by [ above we denote the event that type is selected by nature among the population corresponding to Player i. The importance of the population interpretation of the Bayesian game is that it induces a mechanism of complete information, which will be denoted by MM = MG (MG.
The following characterization highlights an important connection between MAG and M.
Theorem A.16 ([53)). If mechanism M is (>, p)-smooth, then the complete information mechanism MAG (M)) is also (X, -mmoohh.
We now proceed with the proof of Theorem 3.8. To keep the exposition self-contained, we will not make explicit use of Theorem A.16.
Theorem 3,8. Consider a Bayesian mechanism M such that PM 1. Then, for any e T = ((1/²)) iterations of DGD suffice to obtain an e-Bayes-Nash equilibrium of M.
Proof. Under the assumption that PM 1, it follows that there exists pair (A, p)) E R2 such that M is (A, (m)-mmohh with x max (1, p... Further, by definition holds that (M))(()) > En uz(a; 0;) + R(a), for any action profile E A. Combining with (27), we have that there exists a strategy profile x= (v) E II A(A:) such that for every type profile u E V and action profile A,
Σ us (o a.) 2 Σ us (a; + XR(a) - -R((a) 2 ua(a; Us),
since x = max [1, n and utilities are nonnegative. As result, for any x(v) E I. A(A)).
E (v), x ()=:): [Rn>((u(((()::u:)))
(30)
1=1
Further, by definition of the agent-form utilities (29) and the law of total expectation, (30) can be equivalently cast as
AG Ug (2 x (i.we)
2 (x),
AG
1= MEE.
i=
27

---

where we used the notation Zi,e, == =.))). This implies that the sum of the players' regrets in the agent-form representation is nonnegative. The proof of Theorem 3.8 then follows from the correspondence between Nash equilibria in the agent-form representation of M and Bayes-Nash equilibria in the original incomplete-information mechanism M.
A.8 PoA vs robust PoA
In this subsection, provide some additional justification for the condition rPoA & PoA required in Corollary 4.3. particular, we conduct experiments on a set random normal-form games. Some illustrative results for 10 random games demonstrated in Figure Overall, observe that not only rPoA # PoA, but in fact the gap between the two quantities is typically substantial. This have already stressed, rPoA quantifies the worst-case welfare
discrepancy is expected since, over a (typically) much broader set of equilibria.
Fraction of optimal welfare
PoA
0.8
rPoA
0.6
0.4
0.2
0.0
Game
Figure 1: PoA versus rPoA in random normal-fome games.
A.9 Proof of Theorem 4.1
In this subsection, provide the proof of Theorem 4.1. For completeness, we also include the proofs of certain results known from prior work [37, 85, 77].
To this end, we first recall that the prox operator associated with the (squared) Euclidean regularizer flll 112 is defined as
IT (u:) arg max x E.t
(x), u.) 2 la.; 21113
(31)
under some utility vector u, E Rd Accordingly, we let II (w) = (Ig, (u1)... II, (u,)), where = (u1,... U.)) With this definition in mind, note the following property of the prox operator.
Lemma A.17 77)). The prox operator I1 (-) is 1-Lipschitz continuous with respect to ||2 for any æ E
1I_,, X,
Proof. Let E [n]. For any u. ui E 4 and æ; X,
|10m (u:) 1I, (ul)ll2 Pxx (z; u:) - Px, (x. + u/)ll2 llu u// 2|,
where we used the fact that the projection operator is non-expansive with respect to || 1| and that
I (u:) arg max E'E,;
(a//,
1 |
2 2111
arg max ExE:
22l12 + (arh, un + as))
= arg min E
{||ør (u, + xx))1
= Pxx (æ; + =u)).
This implies that [u) (T())) ||ue 11u-uui w'll. where u (u),... U. and ri' (ul,
28

---

Using this lemma, key observation for the analysis of clairvoyant mirror descent is the following contraction property [85, 37].
Proposition A.18 ([85, 37D). Suppose that F is L-Lipschitz continuous. For any x' T[T== X₂ the function
Y
x I (n)(ww)
Il
(32)
-iisscitt continuous, As result, function (32) is contraction mapping long ll +
This follows directly from Lemma A.17: ||l (nFF())))) - - (n S (ilF(())F((u) )|l z L =w'12.
Proposition A.18 reassures us that fixed points of the contraction mapping (32) not only exist, but c-approximate fixed points can also be computed in time proportional to log(1/c) [85]. In this context, if (0)
I &r is an arbitrary point, we consider the update rule defined for E N via
(1)) (I (n)(w(()))
(33)
where (())) E [T==1 X; is any point such that (1 II m(t (m)(()))) {0) It important to note that this sequence (x!")) )621 is not uniquely defined, but with a slight abuse we refer to any sequence satisfying (33) as clairvoyant gradient descent (CGD). CGD satisfies the following remarkable regret bound.
Theorem A.19 (185, 37J). For any T N, the regret of player E [n]] under CGD satisfies
Reg:
(T)
D3
1
x
11-1)
Dx. Li (
(34)
2m
21
t=1
1=1
where Li Rso is the Lipschitz constant of u, with respect || 2--
(1) 1I a 1 (m7e (w))). the first-order optimality condition implies that for Proof. Given that x;
any at X, and E [T].
x (t)
x mui (w ( (x) x 11(1)))) 2 0.
(35)
We further have that
(t- 1)
1 (1) |
|| x
x
11-1)112
1 |
x
(1 1)
112
2
thereby implying through a telescopic summation that
T
T
Σ
[ x;
(t) xx!
(()
x
1111); S 2
D
(t)
x
(1-1)
(1
2
t=1
Combining with (35),
Σ - (0 uw ()))
D2
1
x
(1)
x3
(t
(t-1)
11.
2n
2n
1=1
The claim thus follows from the fact that
T
T
Σ ( ax (. (2() 2
|
11211111, (eellee((00 (2) - ue (2=
1=1
1=1
>
Dx x
Li
(t)
t=1
29

---

Unlike prior work, here we will make crucial use of the negative term in (34). The important lemma below will enable us to express the regret bound (34) in terms of i's best response gap; it is analogous to Lemma A. we stated earlier for OGD.
Lemma A.20. Fix any 1 E N and les x(l)) = 11 11 (n)x-)))) where w point such that (1=(() - TT 1y (n ))1l S c0) Then,
E II X, is any
Dx: (1)
(Z)))) & (x (1) - u. a=""\ll2 +
" | x; (0(11)122
Proof. By the first-order optimality condition, it follows that for any m; E X,
aq (...7u; (2 (xx) x 1) 2 0,
in turn implying that
(ar 19) w/j us u:((o
1
(
(e) (2)
xt! (1- 1))
(36)
17
Furthermore,
(x) u( (0/)) =(x]() z un (2 [})} + {xx
(t)
x u. (, (x:
I (a) (1) x. u. ui( ( + ||ا!
(1) a 1ellllu ( - un (x
S (2) - xi u (x + Dx [w (1)) us (x: (1)
(37)
Combining (36) and (37) yields that
(x)") (x (1a) max (at ux(x=()) 2 Dxx (1,)) u,(a=")122
Dx (10! xt!" 10(-~112 2
m EX;
concluding the proof.
Corollary A.21. For any T N, the regret of player E [n]] under CGD be bounded as
D3
T
T
T
Reg,
(T) (T)) <
2n
4D X.
Σ
(B(G))((E("))
+Z,Dx
(t)
17
uu:(w (1) - =2, (1.
El
In particular, if = 2L and (
Dr. S
S for any L E [T].
T
Reg (T) S3LD3
(BRGAP((Z()))
uu (w (1) u.
+
2" t=1
8LD X
Proof. By Lemma A.20, it follows that for any E [T]].
1
|
x
11
4D% (BRGAP((a())) 2
7)
nllu:(w=)) - u. (a.
27
Summing over all E [T] and combining with Theorem A.19 implies the statement since Dx Exn (0) < L Dx Σ + < 2LD
We now ready prove Theorem 4.1, which is recalled below.
Theorem 4.1. Suppose that all players are updating their strategies using CGD with (()) < min, Dx, and learning rate 1 in (X, m))smooth game G, where L is the Lipschte-continuity parameter 21.
12
of F. Then, for any > 0 and T > GAL2
iterations,
1. the average correlated distribution of play is a T CCE:
4L.D2
2. there is a time t* E [T] such that
(W(ar(()) 2 sup min { p)(), OPTs
6²
PoAg. OPT (3)
16(p + 1)LD
<0co
30

---

Proof. First, by Corollary A.21,
T
Reg: (T)
3T.
D
BRGAP,((x!))
1
[u,(ur (2)
2., (xx_
SLD
2
i=1
X
i=1
t=1
t= i=1
T
=3LD
(BGGAP(E(
2
22"
+
1
Σ
|I((w())
F=x(()))
S {=1
33LD3
(BGAAI((E
+
+2
(+)
x
8LD X
T
<3LD>
Σ
(R (1)
+ 22
Σ
(c
8LD
== t=1
1=1
S 4LD
ΣΣ
(RG)A
(38)
8LD'
where we used the fact that ( S D& D < 2Dx and = 27: As result, Item 1 follows directly from (38) by invoking the well-known fact that the CCE gap bounded by
1
maxigign Reg."" (T)
For Item 2, let us fix any c < co. Suppose that at every time t E [T] it holds that (RGAP((::.)) > for some player i [n]. Then, by (38) we conclude that
Reg. ()) < <ALDx
2T
èT.
SLD
16LD
641.2t 0
641 D As result, by (A, smooohhesss it follows that
since T
T
Σ
Reg, (T))
AOPTST (1 + Σ sW("
in turn implying that
sw(= po(A.)) OPTg 1 " Σ Reg. (T) 2 pp()..p) OPTg
22 16(μ + D)
As result, there is time E [T] such that SW(x po( (1) OPT + 16(x-1)LD3 In the contrary case, if there is a time E [T] such that (x S e for any player E [m]] follows that (W))((") 2 PoAg OPTg (by definition). This concludes the proof.
2
In particular, note that Corollary 4.3 stated earlier in the main body is immediate consequence of Theorem 4.1 under Condition 4.2 since rPoAg 2 Pg. is also worth noting that for the special case of normal-form games, can state Theorem 4.1 so that the first term in the right-hand hand side of (3) reads Pg (A) OPTg + 32(=+1)z thus, for broad class of games (see Lemmas A.7 to A.9), the improvement over the smoothness bound is an absolute constant when e and j are also bounded by absolute constants. Relatedly,
should note that Theorem 6.2 applics in the regime where is polynomially bounded (we are not aware of any application of smoothness where this is not the case).
Remark A.22. It is direct to see that Item 2 of Theorem 4.1 can be refined so that there is a set S S [T]. with [S] 2 (1 TT, so that
SW Sw(x (9) sup min { | P 16( + I)LD3 POAG OPT
762
OPT, +
S
200
Remark A.23. Theorem 4.1 can also be refined using the primal-dual framework of Nadav and Roughgarden [75] discussed in Appendix A.3, with the caveat that the variables {2) need to
31

---

again have bounded pairwise ratio. It is interesting to note, however, that using CGD enables making non-trivial conclusions even when subset of the variables {2:) are zero an optimal solution. In particular, when the quantity Σ Zi=1- 2, Reg, (T)
is nonnegative, we can readily draw the non-trivial conclusion that all players the set {i E [n] 2, + 0} are eventually best responding (by virtue of Corollary A.21). It is not at all clear if such conclusions apply OGD as well. In other words, using CGD one can essentially replace PoAg. Theorem 4.1 by the price of anarchy with respect to solution concept in which a particular subser of players are best responding. Shedding light to this type of guarantee necessitates understanding the implications variables {2, ) being zero in an optimal solution of the LP (21). Relatedly, even if we constraint Zn = 2, can we characterize the games for which & R 0? We explained earlier in Remark A.10 that such pathologies (typically) occur in constant-sum games, for which questions concerning social welfare are trivial.
having some of the
21 = 22
A.10 Beyond smoothness
In this subsection, we discuss example in which the welfare predicted by the smoothness framework far from the welfare obtained by learning algorithms such as OGD. We then suggest natural direction that enables obtaining sharper predictions; we have already seen refined guarantees beyond the standard smoothness framework Appendices A.3 and A.4, but here we explore different direction.
Our example is again based on Shapley's game, a bimatrix game in normal form defined with the matrices
0
0
0
A
0
0
B
0 1
(39)
0
1 0 0
Claim A.24. Let be the bimatrix game defined (39). Then, rPoAg = 0.
(0, 0)) be a welfare- maximiiini joint action. By symmetry, the following argument will apply to any welfare-max maffiiiiaaiiiizin joint action. Consider (æ1, 022) 1,0, (0, 0)). Then, we have that ii (æj x22 + u2 (2,, (æi) Ax + æ Bæg 0 0+ As result, the smoothness constraint corresponding to (æ), (22) necessitates that 0 2 X, which is incompatible with the constraint that
Proof. Let (xi. =
(Definition 2.
In spite of the fact that rPoAg = O, we see in Figure 2 (left) that OGD approaches close to the optimal social welfare This be explained by the fact that certain joint actions-in particular, those in the diagonal-are played with small probability under OGD (right-side of Figure 2). This motivates introducing a more refined notion of smoothness in which the smoothness constraints are only enforced on the joint actions that are visited with non- nog-neglig probability.
Probability bad state
0.3
Average social welfare
0.2
0.8
0.1
0.7
0.0
0
500
1000
1500
2000
0
500
1000
1500
2000
Iteration
Iteration
Figure 2: The behavior of OGD in the bimatix game (39) with 7 0.01. On the left, plot the average social welfare of the dynamics. On the right, we plot the probability of playing a joint action in the diagonal.
32

---

One class of games in which one can easily make such refinements concerns games solvable under iterated elimination of strictly dominated actions. As a concrete example, let
0
B 0 1
(40)
Observation A.25. Let G be the game defined in (40). Then, rPoAg- - 1. Furthermore, i' is the game" resulting from iterative removal of strictly dominated actions, then rPoAg. = 1.
"Under elimination of strictly dominated actions, this is always uniquely defined.
33


Reviews:
[{"review_id": "mkVtzOCLrl", "reviewer": "Reviewer_Q8mF", "summary": "This work studies the connection between efficiency and computation tractability of equilibrium in smooth games. Its major finding is that optimistic mirror descent reaches a weak Nash equilibrium for large games satisfying the property that asymptotically smoothness can guarantee efficiency of equilibria. This result establishes the connection between smoothness arguments and the approachability of no-regret learning algorithms to Nash equilibria.\n", "questions": "What are some natural examples where the conditions in Thm 3.1 are satisfied and non-trivial rates are obtained?\n\nIs there direct generalization to mean-field games?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work draws new insights on an interesting angle connecting two fundamental subjects in algorithmic game theory. Robust price of anarchy characterizes the fraction of optimal social welfare that smoothness argument can guarantee for every Nash equilibria. It turns out from this paper that robust PoA $\\to 1$ also ensures the convergence of no-regret dynamics, which is non-trivial. The results also recover existing theories of the covergence of OMD in two-player zero-sum games. \n", "weaknesses": "The rates (e.g. $n^{-\\alpha/3}$) are dependent on the number of players instead of the number of iterations, which is different from what we commonly see/expect. I am not sure how useful the rates are, for example, in large games, still a $n^{2/3}$ number of players may yield bad responses.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback.\n\n*“What are some natural examples where the conditions in Thm 3.1 are satisfied and non-trivial rates are obtained?”*\n\nThe most simple example is when $rPoA = 1$, in which case Thm 3.1 (in particular see the more general version of Theorem A.2) yields a $1/\\sqrt{T}$-Nash equilibrium after $O(T)$ repetitions. As we point out in Observation 3.3, this already captures the well-studied Minty property, which is satisfied, for example, in two-player zero-sum games.\n\nFurthermore, in the regime where $rPoA \\to 1$, Corollary 3.4 shows that the conditions of Thm 3.1 are satisfied in the natural class of games with bounded influence, which includes voting games; see reference [51] for further applications.\n\n\n*“In large games, still a $n^{2/3}$  number of players may yield bad responses.”*\n\nThis is true for a certain regime of $\\gamma^n$, but as we show in Corollary A.3 our approach can also establish convergence to a Nash equilibrium--a point where *all* players are best responding. \n\n*“Is there direct generalization to mean-field games?”*\n\nThis is an interesting question. To apply our results in the mean-field regime the key difficulty seems to be showing that the robust price of anarchy ($rPoA$) approaches $1$. There is some work in the literature that identifies natural classes of mean-field games for which $PoA \\to 1$ (e.g., see Carmona et al. (Price of Anarchy for Mean Field Games)), so it is plausible that the same applies to $rPoA$ as well, but formalizing this would require further work."}, {"review_id": "wurbLEuiu1", "reviewer": "Reviewer_9HSU", "summary": "This work studies the connections between the efficiency of Nash equilibria, as measured for example by social welfare, and tractability of computing these equilibria through efficient no regret learning algorithms. The authors provide the key insight that the smoothness framework introduced by Roughgarden, that is typically used to analyze price of anarchy, can be also leveraged to analyze the efficient convergence of optimistic gradient descent (OGD) to Nash equilibria. They use this insight to prove that if as the number of players increases, the robust price of anarchy goes to 1 without increasing the games Lipschitz constant too quickly, then OGD converges to weak Nash equilibria. This finding unifies previous findings on zero sum games and is connected to existing work on the Minty property. Even beyond OGD, the authors study the connections between convergence to CCE and social welfare for clairvoyant GD (CGD). They show for the first time that convergence to CCE and outperforming restricted price of anarchy can be combined through an efficient algorithm.", "questions": "See above for a question/suggestion.", "limitations": "No limitations applicable.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Overall I believe that the paper makes a very strong and original contribution. To the best of my knowledge, connections between efficiency of equilibria and tractability have not received a lot of attention. This is evidenced by the fact that relatively simple observations like 3.3 are commonly overlooked. In addition to the novelty of this works topic, the technical results are very extensive and non trivial. ", "weaknesses": "The paragraph from 179 to 190 could benefit from expansion. In the common setting where we analyze a fixed game, one can always normalize the utilities to get a Lipschitz constant of 1. I have a sense that such a normalization would affect the value of $\\epsilon$ in the general case thus we cannot always get $\\gamma$ to be small for free. I am not sure though. Adding more intuition would help. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback.\n\n  \n*“The paragraph from 179 to 190 could benefit from expansion.  In the common setting where we analyze a fixed game, one can always normalize the utilities to get a Lipschitz constant of 1”*\n\nIt is indeed the case that we can appropriately normalize the utilities so that the Lipschitz constant is 1, but here we operate in the usual setting where a bound on the utilities is imposed on the $\\ell_\\infty$ norm; this is why the Lipschitz constant with respect to the $\\ell_2$ norm can be as large as $\\Theta(\\sqrt{n})$. We will clarify this in the revised version. \n"}, {"review_id": "ElV25GC2WI", "reviewer": "Reviewer_SmPo", "summary": "This paper discusses the convergence and welfare of learning algorithms in smooth games. The authors show that when approximate full efficiency can be guaranteed via a smoothness argument, Nash equilibria are approachable under a family of no-regret learning algorithms, thereby guaranteeing fast and decentralized computation. They also leverage this connection to obtain new convergence results in large games, as well as extensions to Bayesian mechanisms. The paper unifies recent works in two-player zero-sum games, illuminating an equivalence between smoothness and a well-studied condition in the optimization literature known as the Minty property. Finally, the authors establish that a family of no-regret learning dynamics outperforms the welfare predicted by the smoothness framework under a generic condition, while at the same time guaranteeing convergence to the set of coarse correlated equilibria.", "questions": "1. Is there any counterexample that if rPOG does not converge to 1, then the decentralized algorithm (OGD) provided in this paper does not converge to Nash Equilibrium? or If Condition 4.1 does not hold, then still thm 4.2.1 hold?\n2. What is the indication of Condition 4.1? Are there some examples that condition 4.1 holds? \n\n\n", "limitations": "The authors adequately addressed the limitation and potential negative societal impact on their work.\n\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength of this paper lies in its contribution to the understanding of the convergence and welfare of learning algorithms in smooth games. The authors provide new insights into the relationship between efficiency and the behavior of a family of no-regret learning algorithms, and they also unify recent works in two-player zero-sum games.", "weaknesses": "The paper does have quite a few notations, but it's understandable. I've got a few questions, which might also point out some areas in the paper that could be improved. I've put these questions and potential weaknesses together in the question section for easy reference. But, I think this is an overall well-written paper. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback.\n\n*“Is there any counterexample that if $rPoA$ does not converge to 1, then the decentralized algorithm (OGD) provided in this paper does not converge to Nash Equilibrium?”*\n\nYes. As we point out in Lines 272-274, there is a bimatrix game (see Proposition A.10 in Appendix A.3) in which $rPoA = 0.125$ and OGD does not converge to a Nash equilibrium.\n\n“Is there any counterexample…If Condition 4.1 does not hold, then still thm 4.2.1 hold”\n\nWe do not know of an example where Condition 4.1 does not hold but the conclusion of Thm 4.2 applies, but we imagine that it should be the case that such examples exist. \n\n“Are there some examples that condition 4.1 holds?”\n\nCondition 4.1 is quite generic, so we expect it to hold in general. More specifically, as we explain in the paper, there are two sufficient assumptions to satisfy Condition 4.1. The first one is that $PoA > rPoA$; given that $PoA$ gives the worst-case quality over a smaller set compared to $rPoA$, we expect this condition to hold. More concretely, Figure 1 in Appendix A.5 shows that such is the case in random normal-form games, while in the revised version we will also highlight that the condition $PoA > rPoA$ is satisfied for all benchmark extensive-form games studied in the literature. The second assumption is a mild continuity condition regarding the behavior of $PoA$ under approximate Nash equilibria; as noted by Roughgarden [81], this is standard in this line of work for otherwise the entire analysis of $PoA$ becomes problematic (in that the conclusions of the theory are not robust to arbitrarily small perturbations). So Condition 4.1 is very generic. We finally point out that Theorem A.18 provides a more general result that does not rely on Condition 4.1.\n"}, {"review_id": "L7M07frOlO", "reviewer": "Reviewer_vrCA", "summary": "This paper studies the convergence properties of no-regret dynamics in $(\\lambda,\\mu)$-smooth games. More precisely the authors show that for any $(\\lambda,\\mu)$-smooth game at which the bound of $\\frac{\\lambda}{1+\\mu}$ converges to $1$ as the number of agents grows, the resulting Online Gradient Descent dynamics converges in polynomial time to an $(\\epsilon,\\delta)$-weak Nash Equilibrium. In an $(\\epsilon,\\delta)$-weak NE, $(1-\\delta)$-fraction of the agents cannot increase their payoff by more that $\\epsilon$ by deviating to another mixed strategy. The latter implies that if $\\frac{\\lambda}{1-\\mu} = 1$ then the resulting OGD dynamics converges to an $\\epsilon$-MNE in $O(1/\\epsilon^2)$ steps. The latter reveals an interesting phase transition on the computational complexity of equilibrium computation of general multi-player games with PoA = 1 and the smaller class of $(\\lambda,\\mu)$-smooth games with $\\frac{\\lambda}{1-\\mu} = 1$ (this naturally implies PoA = 1). \n\nMotivated by the work of Roughgarden et al. establishing that no-regret dynamics in $(\\lambda,\\mu)$-smooth games guarantees $\\frac{\\lambda}{1-\\mu}$ fraction of the optimal payoff, the authors show that the latter result can be improved for a specific class of $(\\lambda,\\mu)$-smooth satisfying an additional condition (Condition 4). More precisely, the authors show that if all agents adopt Clairvoyant Gradient Descent then the time-average joint probability distribution converges to a CCE while there exists an iteration at which the respective mixed strategy profile attains strictly more than $\\frac{\\lambda}{1+\\mu}$ fraction of the optimal payoff.", "questions": "Your second results refers to the $best-iterate$ while the result of Roughgarden et al. refets to the time-average payoff. Could you elaborate more on how the two results compare?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe that the convergence results to an $(\\epsilon,\\delta)$-weak NE in $(\\lambda,\\mu)$-smooth games is a solid contribution. I also find surprising the phase transition on the computational complexity of equilibrium computation of games with PoA = 1 (that are PPAD hard) and the respective complexity of $(\\lambda,\\mu)$-smooth games with $\\frac{\\lambda}{1+\\mu} = 1$. Also I find the second presented result, improving upon the $\\frac{\\lambda}{1+\\mu}$ fraction of the optimal social welfare, interesting. I overall believe that this is a good paper aligned with the interest of the online learning/game theory audience of NeuRIPS.", "weaknesses": "In my opinion the only weakness of the paper concerns the comparison of the second result with the respective previous result of Roughgarden et al. As far as I understand, Roughgarden et al. show that the time-average payoff attained by any no-regret dynamics (in an $(\\lambda,\\mu)$-smooth game) is at least $\\frac{\\lambda}{1+ \\mu}$ fraction of the optimal social welfare. However Theorem~4.2 guarantees social welfare strictly more than $\\frac{\\lambda}{1+ \\mu}$ fraction the optimal one only at a specific iteration. \n\nThat being said I still consider the result interesting. However in case I am not missing something, an additionally discussion is needed so as to fairly compare the two results. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback.\n\n*“Theorem 4.2 guarantees social welfare strictly more than $\\frac{\\lambda}{1 + \\mu}$  fraction the optimal one only at a specific iteration.”*\n\nWhile we stated Item 2 of Theorem 4.2 for a single iteration, it is direct to extend our proof so that the improvement in fact holds for almost all iterates (say 99% of them), not just a single one. More precisely, we can state Item 2 of Theorem 4.2 so that a $1- \\delta$ fraction of the iterations has an average social welfare strictly better than rPoA by an additive factor of $\\delta \\cdot \\epsilon_0^2 C(\\mathcal{G})$. We will highlight this stronger result in the revised version. \n"}, {"review_id": "TDJeaEkhZB", "reviewer": "Reviewer_Qpnv", "summary": "This paper considers a specific type of smooth game first introduced in [Roughgarden 2015]. The main result of this paper is that when the game has robust PoA lower bounded by 1-$\\epsilon$ (defined by the concept of smoothness of the game) and all the players apply optimistic gradient descent algorithm (OGD), the best iterate over the learning process will achieve $(\\sqrt{\\epsilon}/\\sqrt{\\delta n}, \\delta)$ weak Nash-equilibrium, meaning that there are $\\delta$ fraction of the players having low NE gap. The authors also show that under certain condition of the game, CGD, a variant of OGD, performs better social welfare guarantees.", "questions": "- Can the authors explain more on the class of game with $rPoA\\geq 1-\\epsilon$? Is there a certain class of previously studied games or real applications that satisfy this condition?\n- The obtained results for good NE gap strategy is with respect to the best-iterate. I wonder whether the results may also extend to the average-iterate case, which may lead to less computational complexity to derive the output strategy?\n", "limitations": "See weakness and questions for details.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper considers a certain type of game with good rPoA guarantee and shows that classic OGD algorithm performs good results with provable guarantees.\n- The general idea of the proof is intuitive and clear to me. The analysis also looks correct to me in general.\n", "weaknesses": "- One issue is the motivation of the study and the novelty of the proposed analysis. Specifically, it is less clear why the class of game with $rPoA\\geq 1-\\epsilon$ is an interesting class of games. It seems to me that this is more about a technical assumption that makes the proof work. More concretely, with respect to the first result showing the convergence to Nash, the analysis follows the recent line of works about last-iterate convergence and constant individual regret bound in general-sum games using OGD/OFTRL, which show that lower bounded sum-of-regret leads to stability of the dynamic, which furthre leads to low NE gap guarantees. The rPoA condition basically guarantees that the sum-of-regret is lower bounded according to the smoothness condition of the game.\n- Another related issue is the trackability of rPoA. As mentioned mentioned by the authors, while rPoA can be calculated within polynomial time if the game is explicitly represented, meaning that the game representation already takes exponential space with respect to the number of players, which may not be the case when the utility function for each player is define by certain concrete functions. Therefore, deciding whether rPoA is lower bounded or not is also computationally intractable when the number of players is large.\n- The description of Observation 3.3 does not look very clear. Specifically, the equivalence should define a certain choice of $(\\lambda, \\mu)$ in the definition of smooth game and I do not find a proof for this observation.\n- The notations used in this paper are not very clear. \n    - In section 3, many notations are with superscript $n$, which would be better if they are replaced by $*^{(n)}$ in order to distinguish with the exponent notation. Specifically, in line 194, $rPoA\\geq 1-\\epsilon^n$ is very misleading.\n    - In line 302, should $rPoA_G^{\\epsilon}$ be replaced by $PoA_G^{\\epsilon}$, since $rPoA$ is not defined with respect to NE.\n    - In line 324, the guarantee should be $rPoA_G\\cdot OPT$. Specifically, in line below line 926, the RHS should also include $OPT$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback. Below we address the concerns.\n\n*“Specifically, it is less clear why the class of game with $rPoA≥1−\\epsilon$  is an interesting class of games. [...] Is there a certain class of previously studied games or real applications that satisfy this condition?”*\n \nWe believe that the main application of this condition is on large games. Indeed, two rather recent papers [37,22] show that $rPoA \\to 1$ as $n \\to \\infty$ under very broad conditions, encompassing Walrasian auctions and Fisher markets, as well as general combinatorial auctions under probabilistic demand. Those are some of the most well-studied settings in algorithmic game theory, so the class of games in which $rPoA \\geq 1 - \\epsilon$ certainly contains previously studied games in the literature. Another application of this condition we provide in our paper is on games with bounded influence (see Corollary 3.4), which is another class of games with rich history and real applications.\n\nFurthermore, beyond large games and games with bounded influence, another class that satisfies this property are zero-sum games for which the Minty property holds (Observation 3.3), which is a classical condition in optimization. We believe that this connection is interesting as it connects two separate lines of work, and it allows us to use insights from the line of work on smoothness to better understand the Minty property, and vice versa; several such implications are highlighted in Lines 70-85.\n\n*“Another related issue is the trackability of rPoA. As mentioned mentioned by the authors, while rPoA can be calculated within polynomial time if the game is explicitly represented, meaning that the game representation already takes exponential space with respect to the number of players, which may not be the case when the utility function for each player is define by certain concrete functions. Therefore, deciding whether rPoA is lower bounded or not is also computationally intractable when the number of players is large.”*\n\nFirst, as we explained in our response above, there are many interesting classes of games where we know that $rPoA \\to 1$, without requiring one to exactly compute rPoA. \n\nSecond, and more importantly, the tractability of $rPoA$ is by no means necessary to our approach. Indeed, notice that executing the algorithm—which is of course computationally efficient even in multi-player games with a succinct representation—gives itself a sufficient and computationally efficient condition, without having to compute $rPoA$. Specifically, by running the algorithm and computing the (minimum) best response gap (which can be computed easily), there are two possibilities: \n\ni) if the best response gap is large, then our theory implies that $rPoA$ must be far from 1, in which case our theory is not applicable;\n\nii) if the best response gap is small, we are close to Nash equilibrium, which is precisely what we were looking for in the first place.\n\nSo computing $rPoA$ is not needed at all for our approach.\n\n*“The description of Observation 3.3 does not look very clear. Specifically, the equivalence should define a certain choice of $(\\lambda,\\mu)$ in the definition of smooth game “*\n\nThis observation follows directly from the definitions, which is why a proof has not been included. Notice that a game being smooth by definition means that there exists a legitimate pair of finite parameters $(\\lambda, \\mu)$ that satisfies the smoothness property, which is why defining such a pair in Observation 3.3 is not needed. Indeed, the existence of any such pair suffices for the claimed equivalence. \n\n*“In section 3, many notations are with superscript $n$. which would be better if they are replaced by...”*\n\nWe thank the reviewer for the suggestion. We will follow the reviewer’s recommendation in the revised version, as we see how our current notation can cause confusion. \n\n*“In line 302, should $rPoA_\\mathcal{G}^\\epsilon$ be replaced with $PoA_\\mathcal{G}^\\epsilon$ ?”*\n\nIndeed, this is a typo, thank you for pointing it out. \n\n*“In line 324, the guarantee should be [...]”*\n\nWe stated Theorem 4.2 under the (normalizing) assumption that $OPT_{\\mathcal{G}} = 1$ (as noted in Line 915), but we will follow the reviewer’s suggestion as we see how our current choice causes confusion. \n\n*“The obtained results for good NE gap strategy is with respect to the best-iterate. I wonder whether the results may also extend to the average-iterate case, which may lead to less computational complexity to derive the output strategy?”*\n\nIndeed, our main result can be extended to apply for an average iterate, not just the best iterate. Specifically, by selecting an iterate at random, there is a high probability that it will have a small equilibrium gap. We will make sure to point this out in the revised version.\n\n"}]

Author rebuttal:

Meta-review: This paper treats the problem of equilibrium convergence in large games whose price of anarchy goes to $1$ as the number of players grows to infinity. The authors assume that players have access to perfect payoff gradients and study the convergence of the optimistic gradient descent (OGD) algorithm. The paper's main result is that, if OGD is run by the players for a sufficiently large number of iterations, the history of play will be concentrated on states where most players have a minimal incentive to deviate. In addition, the authors study the players' social welfare and estimate its rate of convergence as a function of the game's robust price of anarchy.

For the most part, the reviewers appreciated the paper's technical contributions, the authors' rebuttal answered most of the committee's concerns, and there were no major objections to an "accept" decision. After my own discussion with the authors and the reviewers, I concur with this assessment, subject to the following clarifications / revisions for the camera-ready phase:
1. The statement of Theorems 3.1 and 4.2 (though mostly Theorem 3.1) should be made precise. The authors already included an informal version of their results in the introduction, so they should replace the current version of Theorems 3.1/4.2 with the statements A.2/A.18 from the appendix and avoid vague statements like "OGD reaches [some state]" .
2. The authors should clarify that, in addition to a perfect gradient oracle, the guarantees they provide for OGD require back-and-forth communication with a central coordinator to terminate the process. I would also recommend providing a more thorough description of how the algorithm is to be implemented in a decentralized setting, but I leave the details of this to the authors.
3. As pointed out by one of the reviewers, if the price of anarchy decreases at a moderate rate, a significant number of players could be playing a bad response at the end of the learning process. While this guarantee can be improved in certain cases, this is a limitation that the authors should discuss in more detail.

Subject to the above modifications (which amount to a minor revision of the paper), I am happy to recommend acceptance.
Decision: Accept (poster)