Convergence is Not Enough: Average-Case Performance of No-Regret Learning Dynamics
Authors: Iosif Sakos
Stefanos Leonardos
William Overman
Stelios Andrew Stavroulakis
Ioannis Panageas
Georgios Piliouras
Venue: Submitted to ICLR 2023 (2023)
Keywords: q-replicator dynamics
potential games
average price of anarchy
learning

Abstract: Learning in games involves two main challenges, even in settings in which agents seek to coordinate: convergence to equilibria and selection of good equilibria. Unfortunately, solving the issue of convergence, which is the focus of state-of-the-art models, conveys little information about the quality of the equilibria that are eventually reached, often none at all. In this paper, we study a class of games in which q-replicator (QRD), a widely-studied class of no-regret learning dynamics that include gradient descent, “standard” replicator, and log-barrier dynamics as special cases, can be shown to converge pointwise to Nash equilibria. This is the starting point for our main task, which is the mathematically challenging problem of performance. In our main contribution, we quantify both conceptually and experimentally the outcome of optimal learning dynamics via average performance metrics, i.e., metrics that couple the regions of attraction with the quality of each attracting point. We provide an exhaustive comparison between gradient descent and “standard” replicator in a class of games with severe equilibrium selection problems and empirically extend our results to all dynamics in the QRD class. Our results combine tools from machine learning, game theory, and dynamical systems and provide a framework to initiate the systematic comparison of different optimal learning dynamics in arbitrary games.

Under review as a conference paper at ICLR 2023
CONVERGENCE IS NOT ENOUGH: AVERAGE-CASE PER- FORMANCE OF NO-REGRET LEARNING DYNAMICS
Anonymous authors Paper under double-blind review
ABSTRACT
Learning in games involves two main challenges, even in settings in which agents seek coordinate: convergence to equilibria and selection of good equilibria. Un- fortunately, solving the issue of convergence, which is the focus of state-of-the-we models, conveys little information about the quality of the equilibria that are even- tually reached, often none at all. In this paper, we study a class of arbitrary-size games in which g-replicator (QRD), a widely-studied class of no-regret learning dynamics that include gradient descent (GD), standard replicator dynamics (RD), and log- barrier dynamics as special cases, can be shown to converge pointwise to Nash equilibria. Turning to our main task, we provide both theoretical and experi- mental results on the average case performance of different learning dynamics in games. For example, in the case of GD, show tight average Price of Anarchy bound of 2, for a class of symmetric 2 x 2 potential games with unbounded Price of Anarchy (PoA). Furthermore, in the same class, we provide necessary and sufficient conditions so that GD outperforms RD in an average case analysis giving novel insights about two of the most widely applied dynamics in game theory. Finally, our experiments suggest that unbounded gaps between average case performance and PoA analysis are common, indicating a fertile area for future work.
INTRODUCTION
Multi-agent coordination often involves the solution of complex optimization problems. What makes these problems so hard, even when agents have common (Bard et al.) 2020) or aligned interests (Dafoe et al.) 2020 Dafoe et al. 2021). that learning occurs on highly non-convex landscapes; thus, even if the learning dynamics equilibrate, their fixed points may include unnatural saddle points or even local minima of very poor performance (Dauphin et al. 2014). To address this issue, a large stream of recent work has focused the convergence of optimization-drivenn (e.g., no-regret) learning dynamics to good limit points. Notable results include avoidance of saddle points and convergence of first order methods, e.g., gradient descent, to local optima (Ge et al., 2013 Lee et al.) 2019
Mertikopoulos et al. 2019), point-wise or last-iterate convergence of various learning dynamics to (proper notions of) equilibria in zero-sum (competitive) games (Daskalakis & Panageas 2019: Bailey
& Piliouras 2019 Cai et al. 2022) and convergence of no-regret learning to stable points in potential (cooperative) games (HHciouCM17.PPPP) D1PP11,,BLPPouuuiii
Even though these results seem to provide a sufficient starting point to reason about the quality of the collective learning outcome, unfortunately, this is far from being true. Non-trivial game settings routinely possess attracting points of vastly different performance, and this remains true, even if one able to restrict attention to refined and highly robust notions of equilibria (Flokas al. 2020).
Nevertheless, and despite the intense interest of the machine learning community to address the problem of equilibrium selection, there a remarkable seareity of work in this direction. To make matters worse, static, game-theorete approaches to the problem (Harsanyi] 1973] Harsanyi & Selten 1988: van Damme 1987). offer little insight, often none at all, from a dynamic/lerning perspective. In this case, the challenge is to show approximately optimal performance not for (almost) all initial conditions (which is not possible), but in expectation, i.c., for uniformly random chosen initial conditions (worst-case versus average-cass analysis). This is fundamentally hard problem since one has to couple the performance of equilibria to the relative size of their regions of attraction. However, regions of attraction complex geometric manifolds that quickly become mathematically

---

Under review as a conference paper at ICLR 2023
intractable even in oow-dimensional settings. Importantly, their analysis requires the combination of tools from machine learning, game theory, non-convex optimization and dynamical systems.
In terms of average case analysis of game theoretic dynamics in coordination/common interest games, the only other references that we know of are Zhang & Hotbauer (2015); Panageas & Piliouras (2016). In fact, Panageas & Piliouras (2066) is the key precursor to our work. Critically, whereas Panageas & Piliouras (201) (2016) focuses exclusively on a single dynamics, i.e., replicator dynamics and bounding its average price of anarchy (APoA) in restricted instances of games such as Stag Hunt, we show how these techniques can be applied much more broadly by addressing novel challenges:
Can formally define the notion of Average Price of Anarchy for large classes of dynamics and games?
Axiomatic challenge:
Analytical challenge: Even if the definitions be made robust how do we analyze these nonlinear
dynamical systems given random imitial conditions in the presence of multiple attractors? Exxeerimenta/viiualiaattt
challenge: Can we develop novel custom visualization techniques as well as showcase that our experimental results have predictive power even in complex high dimensional settings?
Model and Contributions. To make progress in addressing these challenges, we study the q-replicator dynamics (QRD), one of the most fundamental and widely-studied classes of multi-agent learning dynamics that include gradient descent, replicator and log-barrd log-barrier dynamics special cases (A. Gian nou 202I). We start with our first motivating question which answer affirmatively by proving pointwise convergence of all QRD dynamics to Nash equilibria (NEs) in almost all finite potential games. Potential games include multi-agent interac- tions in which coordination is desirable, congestion games and games of identical interests as important and widely-studied
subclasses (Wang & Sandholm, 2002 Panait & Luke 2005 Dafoe et
Carroll al. 2019
2020
The proof of wise convergence to NEs combines recent advances (Swenson et al. 2020 I with standard convergence techniques in the study of potential games, e.g.. Palaiopanos ct al. (2017b). Such techniques have been used to either es- tablish convergence of QRD to NEs under the assumption of point-wise convergence (Mertikopoulos & Sandholm, 2016) prove convergence limit cycles of (restricted) equilib- rium points (Mertikopoulos & Sandholm, (0118). However, whereas in previous works such results are the main focus, in our case they are only the starting point as they clearly not suffice to explain the disparity between the regularity of QRD in theory (bounded regret, convergence to Nash equilibria) and their conflicting performance in practice (agents' utilities after learning).
Figure Vector fields of gradient descent (top) and replicator dynam- ies (bottom) for a game with payoff- and risk disk-ntminant equilibrium at the bottom-lefi corner. The trajectories in the region of attraction of the good (bad) equilibrium are shown gray (red). The black solid and dashed lines show the stable and un- stable manifolds, respectively. In this case, gradient descent outper- forms replicator dynamic.
We then turn to our second question and the fundamental prob- lem of equilibrium quality. While different QRD dynamics may reach the same asymptotically stable equilibria, this is only minimal and definitely not sufficient condition to com- pare their performance. In particular, the regions of attraction of these common attracting equilibria, i.c., the sets of conver- gent initial conditions, can be very different for different QRD dynamics.
SSpecifically, Swenson et al. (2200) shows that all NEs in almost all potential games are regular in the sense rohust[Harsanyi of Harsanyi, i.c., they isolated and highly robust Harsanyi (1973): van Damme ( (1987). Almost all refers to
set whose complement closed set with Lehesgue measure zero.
2

---

Under review as a conference paper at ICLR 2023
In our main technical contribution, we tackle this task by providing geometric insights into the shapes and sizes of the regions of attractions of different QRD dynamics. We show that in a class of two- agent potential games, gradient descent reaches the payoff- wooff-ddmmiaatttt (socially optimal) equilibrium more often than standard replicator whenever this equilibrium is also risk-dominant (less risky), see study class of games in which the Price of Anarchy is unbounded, I..., in which the worst-case equilibrium can be arbitrarily worse than the socially optimal outcome Panageas & Piliouras 2016), and derive a (tight) upper bound of 2 for the Average Price of Anarchy for the gradient descent dynamics and all instances of the class in which the risk- and payoff- payoff-dominant equilibria coincide. This is the first such tight result of its kind.
Figure 1] As an implication,
Conceptually, our methods provide a systematic approach to explore the design and hyperparameter space of learning dynamics and extend recent advances towards a taxonomy of learning dynamics in low-dimensional or general potential games (Panageas & Piliouras) 2016 Pangallo et al. (022). More importantly, they signify the expressiveness in this task of performance measures that couple the likelihood of convergence to certain outcome (region of attraction) with the performance of an algorithm at this outcome. From a practical perspective our findings admit a dual interperation. On the one hand, they provide concrete recommendations about the optimality of different QRD dynamics based on the features of the underlying game. On the other hand, they suggest, that even in the simplest possible classes of games, there not a single optimal QRD dynamic to beat them all.
Intriguingly, the above results hinge on two interconnected, yet fundamentally different, theories. The first part (convergence), relies on the theory of Lyapunov analysis and the properties of dissipative systems, i.e., systems that lose momentum over time till they converge to a steady state. By contrast, the second part, i.e., the qualitative analysis of the different parametrizations of the QRD dynamics, relies on the existence of invariant functions that characterize stable and unstable areas in the state space of such systems (Palaiopanos et al., 2217aa Nagarajan et al.) 2020). The existence of invariant functions, however, is a feature most often studied in conservative systems, fundamentally orthogonal principle to the one of dissipation.
PRELIMINARIES: THME-THEREETIC AND BEHAVIORAL MODELS
Game-theoretic model. A multi-agent finite potential game r = (N, (Au; us uR)EEN }) denotes the interaction between a set N == [l.....n} of agents. Each agent ts E N has a finite set of actions, Ak. with size [Atl. and a reward function ug A -> R where A == -ITEN - As is the set of all pure action profiles of Г. Agents may use mixed actions or choice distributions, Th = (# E Xx. where Ikaz is the probability with which agent k uses their action as E Au and Xx= = {ar E BlAal Eate, Tkay = 1, Tkay 2 0} is the (|Axl ---ddmmeniion simplex. Given any mixed-action I& E Ne. we will write supp(xx) = {ax E As Ikaz > 0} to denote the support of the action 24. i.e., the set of all pure actions as Ar that are selected with a positive probability at dg. Using conventional notation, we write s = ($k, $-k) E A and (22,, E X == IIxE Xx to denote the joint pure and mixed action profiles of I, where s s_k and Hー are the vectors of pure and mixed actions, respectively, of all agents other than k. When time is relevant, we will use the index / for all the above, e.g., we will write xx(() for agent k's choice distribution at time f. 2 0. The function
A + R is called a potential functioo of (ss) (s s).). for all k e N and all s, s' E A. The agents' reward functions and the potential function extend naturally to mixed action profiles with ug (z) Eg (s)) and (xx) = E, (s))]
I and satisties (s) u s
Regular Nash and restricted equilibria. A Nash equilibrium (NE) of I is an action profile x" E X ). for all K E N and for all x E X. By linearity of expectation, the
such that un (xxx) 2 above definition is equivalent to:
(1) where us (a x"x)) denotes the reward of agent & when they play the pure action ag. versus the mixed strategies xix for the rest of the agents. Let NE(T) denote the set of all NE of r. A NE is called symmetric if rf
ug (x²) 2 un ug x² x), for all ag E Ar. and all l E N,
= I and is called fielly mixed if supp(r*) = supp((t) A. AE called regular if it satisfies the following definition.
Definition 2.1 (Regular Nash equilibria (Harsanyi 1973, Swenson et al. 2020 ). A Nash equilbrium. x² E NE(T), ), is called regular if it is (i) quasi-strict, i.e., if for each player k E N, at assigns positive
3

---

Under review as a conference paper at ICLR 2023
probability to all best responses of player k against bast $ eontaiied in- and (ii) second-order non-degenerate, i.e., if the Hessian, H(x"), taken with respect to supp(x") is non-singular.
best best respenses each player K-E to
Finally, a restriction of I' is a game I" = {N, (Ak. u'e ue) where A C As and ui A' + R is the restriction of u. to A' := ITEN A'e for all E N. An action-profile x E X' is called a restricted equilibrium of I if it is a Nash equilibrium of a restriction of r, cf. Mertikopoulos & Sandholm (0018). It is easy to see that all restrictions of a potential game I = [V.((A, ut)neN Φ) are potential games, whose potential functions are restrictions & to the respective subspaces of A.
Behavioral-leariing model. The evolution of the agents' choice distributions (or mixed actions) in the joint action space X' is governed by the q-replicator dynamics (QRD) which are the parametric dynamics described by the system of differential equations (equations of motions) d = VT),,), where
Vg X |a is given by:
uk ux(a xb Enyedr Thin un uu(a, = for all & E N, as E A (QRD)
Kaa = x akas
EajeAe Kka,
for any q 2 Special cases of the above dynamics are the projection or gradient descent (GD)
dynamics, for 9 = O, the the standard replicator (RD) dynamics. for 1, and the log- -arrier or
inverse update dynamics, for q = 2 (Mertikopoulos Sandholm 2018 A. Giannou 2021).
3 POINTWISE CONVERGENCE OF QRD TO NASH EQUILIBRIA
Our results consist of two parts. In the first part, which is the subject of this section, we show convergence of QRD to Nash equilibria in a class potential games, which we term perfectly-regular potential games, whose definition follows.
Definition 3.1 (Perfectly-regular potential games). A potential game I is called regular if it has only regular Nash equilibria. A regular potential game is called perfectly-regular potential game (PRPG) if all its restrictions are regular potential games, i.e., if they only possess regular Nash equilibria.
Almost all potential games are PRPGs; this is a generalization of Swenson et al. 2020) who prove that almost all potential games are regular. Furthermore the PRPG class contains other important subclasses of games, e.g., congestion games, as well as games with identical reward functions, which are currently widely studied in the context of cooperative artificial intelligence (Wang & Sandholm
2002, Panait & Luke 2005 Carroll et al. 2019: Dafoe et al. (0200). The convergence result is stated formally Theorem 3.2] its complete proof may be found in ??.
Theorem 3.2 (pointwise convergence of QRD to NE in PRPGs). Given any perfectlyrregular potential game (PRPG), I, and any interior initial condition z²0) E int X, the q-replicator dynamics, defined as in equation (RD) converge pointwise to a Nash equilibrium x. Tf for any parameter q 2 O. Furthermore, the set ((int X) == Uzoeint x {x" E X lim x(f) = x", x(0) zo), i.e. the set of all limit points of interior initial conditions, is finite.
proceeds in two steps, which utilize the properties that (i) PRPGs have finite number of regular equilibria, and (ii) the probability of optimal actions near an equilibrium point is increasing in time with respect to the QRD. In the first step, we prove that for any initial condition, the sequence of joint action profiles z z(t) that is generated by QRD for any q 2 0 converges to restricted equilibrium of a PRPG, r. This relies on the fact that the set of cluster (limit) points of the trajectory- also called the w-limit set-is a finite, and fact, as we show, singleton (a single element set) for any PRPG. In turn, this follows from the fact that PRPG provably contains only a finite number of restricted equilibria.
Sketch of the proof. The proof of Theorem 3.2
Having established convergence to restricted equilibria, in the second step, it remains to show that, in fact, any such limit point has to be a NE of T, i.e., we need to exclude convergence to restricted equilibria that not NE T. To establish this, couple the structure of PRPGs, which ensures that there is finite number of (regular) restricted equilibria, with the nature of QRD which guarantees that in the vicinity of limit point, optimal actions, i.e., best responses, need to be played with
4

---

Under review as a conference paper at ICLR 2023
increasingly higher probability. Thus, all actions in the support of the limit choice distribution of each agent must be best responses against the actions of all other agents, which implies that all points that can be reached by QRD are NE of
In other words, Theorem 3.2 says that for almost all potentials games and almost all initial conditions, QRD converge to a NE of the game.An important implication of Theoree 3.2 that, when one is reasoning about the quality of the collective learning outcome in cooperative multi-agent settings (as captured by PRPGs), they can restrict their attention to NE. However, reverting to off-the-shelf, static performance measures that compare the quality of different NE, we only obtain results that are meaningless, if not misleading, from a dynamic/lcarning perspective. The reason is that certain bad (or sometimes even good) NE may be reachable only from a very small set of initial conditions. Thus, we need to develop and argue about average performance measures that couple the outcome of the learning process (NE of an PRPG), with the likelihood that such outcome is reached by the given learning dynamic (region of attraction of this NE). This is the subject of the next section.
4 QUALITY OF THE COLLECTIVE LEARNING OUTCOME
When static performance metries fail. Having established that in the landscape of potential games, QRD converge almost surely to Nash equilibria, we next turn attention the main challenge of quantifying the quality of the collective learning outcome. In order to do that, one would first have to establish appropriate performance metries. In static regime,
rely in variety of meaningful metrics, e.g.. the Price of Anarchy (PoA) (Koutsoupias & Papadimitriou 1999. Christodoulou & Koutsoupias 2005 Roughgardeen 2015), which is defined as the ratio between the socially worst NE of the game and the socially optimal outcome, where the social-optimality of an outcome x E X measured with respect to the social welfare SW(x) the agents. The PoA is a natural static metric that one may consider in PRPG setup. After all, coordination is the essence of potential games, which typically model multi-agent settings where this is a desirable property. However, it is not difficult to find PRPGs where the PoA fails to provide any meaningful information about the game. Let us consider the following example:
ΣLEN uy (z), i.e., the total reward of
Example 4.1 (A simple example of unbounded performance loss). Consider the parametric 2 x 2- PRPG, I Tw. i.e., a 2-player 2-actions PRPG, with payoff functions Un, (81, 82) = Unn,2 (82, 81) = (s1,182)) where the matrix An E 2x2 is given by:
An 000 ww) 4
A Am =
15w. w.
The games, Iww are already expressive enough to capture the aforementioned problem. In order to this, observe that the NE that corresponds to (1,0) and 22 = (1, has social welfare equal to SW (x) = 1 + = 2 but the NE that corresponds to x = (0, and x'2 = (0. 1) has SW(z') =
2w. Since w can take any value larger than 1, the difference in performance can
be arbitrary large with respect to the PoA. Specifically, PoA(I'w) SW(Z) w 00 as w
SW(z))
4.1 REGIONS OF ATTRACTION AND AVERAGE PERFORMANCE MEASURES
While useful in static environments, the PoA metric fails to capture the dynamic nature of multi-agent learning. In particular, it does not provide an answer to the question:
How likely is it for the agents reach good bad outcome given that the multi-agent system converges?
To answer this question and argue about the collective performance of the game dynamics, we need to quantify the likelihood of each outcome when we the initial conditions of the system are randomly sampled. A region of attraction of given outcome formalizes this notion.
2 2-game, one usually abuses notation and writes x, y E [0, 1] (instead of (x, 1 - æ)) and (y. 1 - 8)) to denote the mixed choice distributions of players 1 and 2, respectively. Then, all notions that we presented in Section mayy be viewed as functions of x, y. For example, we could have written SW11, 1) to denote the social welfare of the NE that corresponds
NNote about notation:
y 1. In this section we going to interchange between the notations, but our choice always going be clear by the context.
5

---

Under review as a conference paper at ICLR 2023
Definition 4.2 (Regions of attraction). Let I be any game and assume that its joint action profile, I E X. is evolving according to the equations of motion è = f(r). Then for any x² E X, the set goA")((x)) == {Io X lim4- z(t) = x², z00) zo is called the region of attraction (RoA) of x² with respect to the dynamics f.
In other words, the RoA of point x' E X' the set of all initial conditions in X' for which the dynamics asymptotically converge to x". Note that RoAs do not intersect. If we can determine the regions of attraction of some game dynamics, then given a certain static performance metric, e.g., the social welfare, we can define corresponding tveerag--peformanne possible outcomes, in the sense of limit points, according to their likelihood of occurring with respect to the given dynamics. In order for this average be meaningful, minimum requirement, is that the dynamics converge for almost all, i.e., all but a measure zero, initial conditions. Formally, an average performance metric is defined as follows
metric that weighs-in all
Definition 4.3 Avvrrag--erffrmaat
metric). Let I be malti-agent game and assume that its joint action profile, x E X, is evolving according to the equations of motion i = f(x). Let Ng S X be set of initial conditions such that the set of convergence points ((Xg) is finite. Then, given performance metric g : X - TR ofT, the average-perfont seeage-peefformncce of the dynamics governed by f in with respect to the performance metric g and the set of initial condition Ng, is given by
APM No (f,1)= = Σ (((AA))((z") g(x"),
(APM)
xx' s'EQ(X))
where μ is a probability measure on Xo.
In other words, an APM is the expected optimality of random initialization of the dynamics in No S X' with respect to some metric g. For instance, if the performance metric is the social welfare, then the average-performan system for any random initialization in Ng. The average-pent prrage-performanc metric that we are going to use in the remainder of this section is the Average Price of Anarchy (APoA). The APoA is an APM with respect to the social welfare, re-normalised such that the APoA is greater than equal to 1, with equality only if (almost) all the initial conditions converge to the socially optimal outcome of the system. Formally, given multi-agent game I, equations of motion å fz) that describe the evolution of the agents actions in I, and a set of initial conditions No S X that consists of almost all X, the APoA is given by the formula:
metric with respect to g measures the expected social welfare of the
m SW(x)
APOA(S.T)
(APoA)
APMsw, (S.T)
Here, is important to note Definition 4.3 does not ensure that an APM is always meaningful metric for the system. However, as long as one can prove that (i) the dynamics converge pointwise to some x² E Q(X) C NE(T) for almost all initial condition zi E X, and (ii) the set of limit points, Q(X), is finite two conditions that are satisfied by any PRPG that evolves with respect to some QRD (cf. [Thoormm 3.2) the APoA has an intuitive interprentation. Specifically, in this setup, the APoA is always bounded between the PoA and the Price of Stability (PoS) of the game, i.c., the ratio between the socially optimal outcome and the socially optimal NE.
4.2 THE TAXONOMY OF QRD IN 2 2 PRPGS
To systematically evaluate and compare the performance of different QRD in perfectly-regular finite potential games, we address the case of symmetric 2 x coordination games, i.e., games in which one can change the identities of the players without changing the payoff to the actions. Such games constitute one of the current frontiers current.rontiers in terms of classification of game-dynamics (Zhang & Hofbauer) 2015; Pangallo et al.] (022). Such games are trivially potential games and include games of identical payofts as special cases. Omitted definitions and proofs of this section may be found ??.
Representation of symmetric 2 x PRPGs. Recall that NE, x², of symmetric potential I is called payoff-dominant if un (x*) 2 un (x') for all x' E NE(T), and it is called risk-dominant if x= is
For this definition, recall that probability measure / compact space X' is r-additive function from the powerset of X' R2, such that /(²² = and )x(²") 2 0 for all X' C X.

---

Under review as a conference paper at ICLR 2023
unilaterally optimal against the uniform distribution of the rest of the agents. All symmetric 2 x 2 PRPGs can be conveniently represented by the parametric class of games I w.., with payoff functions 8, (81, #2) = U,,,,,2 81) = Aw. where the matrix A E R222 given by:
1 B
Aw,a
B515w.
The game I w. has the same NE as the original game, retains the payoff- and risk-dominance properties of its equilibrium points, and preserves the limiting behavior of any QRD (see ??). Each game I 8 has three NE, two pure at x = y = 0 and x = y = 1, with social welfare (W, 0) = 2w and (1, 1) 2, respectively, as well as one fully-mixed NE at:
w
x²
(4)
w 1
For convenience, we are going to refer to the first pure-NE as Tw. Note that Tu is payoff-domine for any parametrization I w. and it is also dos-nnmmnaant whenever w 11 B, or equivalently. whenever >> 0.5. The first result of this section states that whenever the risk- and payoff-dominani equilibria of w..3 coincide, i.e., a 2 0.5, then the gradient descent dynamics, i.e., the 0-replicator dynamics, perform better (or equally in the generic case = 0.5) on average than the standard replicator dynamics with respect to the social welfare of their outcomes, i.c., they yield a smaller APoA. In any other instance of these games, i.e., for a 0.5, the RD perform better than GD with respect to the same metric.
Theorem 4.4 (Performance of QRD in symmetric 2 2 PRPG). Given any 2 symmetric PRPG, which, without any loss of generality, can be represented as an instance I w.w.B it holds that
(5) if and only if whenever the payoff-dominant equilibrium is also risk-dominant, with equality only when if and only if a 0.5, i.e., = = 3. where Vo. V1 are the equations of motion of the O-replicator and 1-replicator dynamics, respectively equation QRD
APMsW int x I 2 APMsw int x (V1,Tw...) w.
Interpretation of Theorem 4.4, The proof of Theorem 4.4 proceeds with first order analysis of the manifolds that separate the regions of attractions of the two pure equilibria for the different dynamics (cf. Figures 2) and 3. When comparing the gradient descent (GD) dynamics and the replicator dynamics (RD), the main implication of this theorem is that the expected social welfare is optimized by GD whenever risk and payoff-dominant equilibria coincide and is optimized by RD when risk and payoff- payoff-dominant equilibria differ. More generally, this result may be interpreted in two ways. On the one hand, provides a concrete recommendation on the optimal behavior of the agents (GD versus RD) based solely on the properties of the underlying game. On the other hand, it suggests that even in the low-dimensional setting of 2 x 2 potential games, there not a uniform recommendation, and the optimal behavior largely depends on the features of the underlying game. As it turns out, in this case, the decisive feature is the riskiness of the payoff-dominan equilibrium.
Generalization to all QRD. Technically, the proof of Theorem 4.4 uses tools that orthogonal to the Lyapunov analysis, and the theory of dissipation of dynamical systems, that we used to prove convergence to NE in /section 3] It leverages the constants of motion or invariant functions (Nagarajan) ett al. 2020), i.e., quantities that remain constant along the trajectories of the learning dynamics. The rationale is that if one could identify such a function, then, by finding its value at the unique mixed equilibrium a of the game, they can determine all initial conditions that asymptotically converge to it: these will be all points the same level set of the invariant function. The manifold. i.e., the geometric locus, of all the points that converge to the equilibrium, i.e., the stable manifold of a, is the one that separates the regions of attractions of the two pure NE of the game. Because of this property, we may also refer to the stable manifold of the mixed NE as the separatrix (Panageas & Piliouras 2016). Note that, since the dynamics are also mockward-invarian Mettikopoos & Sandholm 2018), their level-set will also contain a set of initial conditions that converge to it when moving backward in time. This points constitute the unstable manifold of a. In the following lemma identify such an invariant for all QRD.
(Panageas & Piliouras
Lemma 4.5 (Invariant functions of QRD in 2 x 2 symmetric PRPGs). Given a 2 x 2 symmetric PRPG, I Sw whose agents evolve with respect to the q-replicator dynamics, the separable function V, (0, 1)2 -> IK with gg(,,, y) = (xx) Vy(y),, where 1hr (0, - R. is given by:
7

---

Under review as a conference paper at ICLR 2023
43
44
Figure 2: The invariant function, (2 y). for x,y y E [0, 1]2 in the game T.. for w = 2, B 0, and various values of q: q 0 (gradient descent), q 1 (standard replicator), 9 2 (log-barrier), and q = 20. The invariant function becomes very steep at the boundary as increases, taking both arbitrarily large negative (dark) and positive (light) values in the vicinity of the NE.
x--9 + (1 xr)
1 +
1 axr-9 - (1 - -a)(11 - x)1-1
q 9 1,2,
2 2-9
1 q
(x))
(ll(())) + +11 a)) In(1 - xx).
9=1,
(6)
In(x) + In(1 - x) + a +
1-a
q= 2,
1-x'
remains constant along any trajectory (I((), (())((()))))))) 120 of the system. The function V Vo((x) is continuous
with respect to the parameter q at, both, q = 1 and = 2, since limg-1 V (x) = VV((x) and l
2 V (z) = (2(x)ftr for all x E (0. 1).
In Figure we visualize the invariant function, V (c. y). for x. y E (0, 1)2 for various values of q E [0, 20). From the panels of Figure 2| it is also evident that V (x y) acts as a handy tool to visualize the regions of attraction of the two pure NE of the game. Namely, at the unique mixed NE, i.c., x = y a, the invariant function. Lg is equal to 0. The same holds for any point (x, E (0, 1)² with = Thus, we can factor- ize (o(z, y) as Vo(2, (z, y) = V S.,Stable (z, y) (x y) where V Vg.Stable (I. y) = 0 is precisely the geomet- ric locus of all points (s, E (0, 1)2 such that lim xr()= a, and y is the geometric locus of all points such lim x(t) = a. These two manifolds constitute the stable and unstable mani- folds, respectively, of the g-replicator dynamics.
68
x=
488
6.7
4,5
Stable mansfold Ge e ( 10)
6.4
0.3
6.1
Figure 4: Stable manifold (separatrix) for all different values of q E [0, 10] (from blue to brown) in the ww.. game for w 2 and 8 = O. The manifolds for q = 0, = 1, and = 2 are shown in shades of black for reference (cf. FFiuure 3). The region of attraction of the payoff-dominant equilibrium (bottom-left corner) shrinks as q increases.
Since the invariant function (z y) takes the value 0 only at the stable and unstable manifolds, we can visualize the separatrix for different values of q by plotting the 0-level set of the invariant functions in Fiiuree These are depicted in FFigure 3] As sanity check, also see from Figure 3 that the region of attraction of the payoff-dominant equilibrium for q = 0 (GD dynamics) is larger than the region of attraction for = (RD).
Empirical evidence for the monotonicity of the APM with respect to q. If we stack the stable manifolds (solid blue lines) in the panels of Figure 3] it becomes evident that the region of attraction of the payoff-dominant and risk-dominan equilibrium grows as decreases Figure for all values of q E [0. 10) (the progression of the surface remains essentially unchanged for larger q). Analogous plots (but with the results reversed as predicted by Theorem 4.4) can be generated for instances of I w.. in which the risk-dominant equilibrium is different from the payoff-dominant one, as well as, for 2 x generic PRPGs (cf. section 4p. In general, putting together Theorem 4.4 have both theoretical and empirical evidence that the
This depicted in
and the aforementioned visualizations, region of attraction of the payoff-dominan equilibrium in I w. is decreasing (increasing) in q for q 2 0 whenever this equilibrium is (is not) rimk-ntm Formal verification of the monotonicity of
8

---

Under review as a conference paper at ICLR 2023
04
340
02
32-
Figure 3: The stable manifolds, 10 Stabble y) = 0, (solid blue lines) for the same values of q and the same instance of T s as in Figure 2) in which the payoff- and risk- dominant NE is at the bottom left cornr. For all q. the separatrix goes through the mixed NE at the intersection of the x² (dashed red) and y" (dashed black) coordinates. All panels also include the unstable manifold defined by y = 0 (dashed blue line). The region of attraction of the payoff-domine NE is larger for all values of q; however, this is because this NE also risk-dominant, cf. [Theorem 4.4
tte manifolds the regions of attractions with respect to q in the QRD parametrization remains open.
Application: APoA in 2 x 2 PRPGs. We conclude this section by providing concrete result regarding the evaluation of the APoA wverage-performane measure in the class of 2 x 2 symmetric PRPGs, which show- cases the practical importance Theorem and the invariant function approach.
15
Theorem 4.6. The APoA of GD dynamics in all 2 x 2 symmetric PRPGs, Tw.g. is bounded by 2, i.e., APoA (V, a) < 2. Furthermore, this bound is tight.
800
1900
-00
-300
200
The bound also holds for 3 == ----,, but in this case, there exists no risk-dominant equilibrium. The proof of Theorem 4.6 essentially proceeds by first order analysis of the function depicted in Figure 3 which, in turn, de- pends on the invariant function of the gradient descent dynamic. One way to see that this bound is tight, is to set 3 = 1 w + é, for a small > 0 and let increase (cf. Figure 5). In combination Theorem 4.4 and Theorem 4.6 imply that the APoA of the RD (QRD with g = 1), not upper bounded by whenever < 0.5, i.c., whenever the risk- and payoff-dominam equilibria are different. However, for the case a > 0.5, the separatrices for all q 2 as visualized in in(Figure 4| (empirically) imply that simulations of q-replicator dynamics which
Figure 5: APoA of a 2 x 2 symmetric PRPG for the gradient descent dynamics and various values of 3 and w. The APoA is upper bounded by (dark to light val- ues) as shown in Theorem 4.6
similar bounds hold for all values of [ In ??, provide evidence that the statement of Theorem and the bound of Theorem 4.6 co6)cnne to hold in PRPGs of higher dimensions, i.e., beyond the 2 x setting.
5 CONCLUSIONS
In this paper, we studied the class of q-replicator dynamics (QRD), and showed that all QRD converge pointwise to Nash equilibria perfectly-regular potential games, a class of games that encompasses almost all potential games, i.c., the standard models of multi-agent coordination. The convergence of QRD in these settings is remarkably robust, occurring regardless of the number of agents or actions and for all possible parametrizations of QRD. From the perspective of equilibrium selection and quality, however, convergence provides little information, often none at all. Turning to this challenging problem, we provided geometric insights into the reasons why different dynamics exhibit fundamentally different performance despite their convergence to the very same set of attracting points. Our techniques leverage two intertwined, yet orthogonal each other elements of dynamical systems theory: dissipation (Lyapunov theory) and conservation (invariant functions).
"To avoid confusion, in Figure 4 we visualize the stable manifolds for the case in which GD are the dynamics with the largest region of attraction, i.e., has the lowest APoA. The case < 0.5, in which the manifolds are simply mirrored the y 1 diagonal, is in ??

---

Under review as a conference paper at ICLR 2023
REFERENCES
P. Mertikopoulos A. Giannou, E.-V. Viatakis-Ckkragkkunii. On the Rate of Convergence of Regularized Learning in Games: From Bandits and Uncertainty to Optimism and Be- yond. Part of Advances in Neural Information Processing Systems 34 pre-proceedings (NeurIPS 2021), 2021. URL Ittps://proceecingg.eeell wwwpaaiiss.ccppppppeeee cc/paper/pp//11// /ttp://ppceeeaaurr.e.eroooo////r
html
J. Bailey and G. Piliouras. Fast and Furious Learning in Zero-Sum Games:
Vanishing Regret with Non-Vanishing Step Sizes. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL
neurips cC wttpppppeeop.p//.L..... pdf
N. Bard. J. N. Foerster, S, Chandar, N. Burch, M. Lanctot, H. F. Song, E. Parisotto, V. Dumoulin, S. Moitra, E. Hughes, Dunning, S. Mourad, H. Larochelle, M. G. Bellemare, and M. Bowling. The Hanabi challenge: A new frontier for Al research. Artificial Intelligence, 280: 103216, 2020.
ISSN 0004-3702. doi: 10. 10.1066j.artitt22133 103216..
Y. Cai, A. Oikonomou, and W. Zheng. Tight Iust-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities, CoRR, abs/2204.09228, 2022. URL https
//doi org/ /00 48550/a a rxiv. 2204 09228
M. Carroll, R. Shah, M. K. Ho, T. Griffiths, S. Seshia, Abbeel, and A. Dragan. On the Utility of Learning about Humans for Human-Al Coordination. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, 2019.
G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the Thirty-Sevente Annual ACM Symposium on Theory of Computing. STOC '05. pp. 67-73, New York, NY, USA, 2005, Association for Computing Machinery. doi: 10. 145111600909.0.. 1a000005900000066600 1060600.
A. Dafoe, E. Hughes, Y. Bachrach, T. Collins, K. R. McKee, J. Z. Leibo, K. Larson, and T. Graepel. Open Problems in Cooperative AI. arXiv e-prints, December 2020.
A. Dafoe, Y. Bachrach, G. Hadfield, F. Horvitz, K. Larson, and T, Graepel. Cooperative AI: machines must learn to find common ground. Nature, 7857:33-36, 2021. doi: (0388/41186-0222 170-0.
C. Daskalakis and I. Panageas. Itst-Iterate Convergence: Bero-Sum Games and Constrained Min- Max Optimization. In Avrim Blum (ed.), 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12 2019, San Diego California, USA, 2019.
Y. N. Dauphin, R. Pascanu, Ç. Gülçehre, K. H. Cho, S. Ganguli, and Y. Bengio. Identifying and attacking the saddle point problem in nigh-dimensional non-convex optimization. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 2933-2941, 2014.
L. Flokas, E. V. Vlatakis Vlatakis-Gkaragkkonn Gkaragkounis, T. Lianeas, P. Mertikopoulos, and G. Piliouras. No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping From Saddle Points Online Stochastic Gradient for Tensor Decomposition. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pp. 797-842. JMLR. 2015.
J. C. Harsanyi. Oddness of the number of equilibrium points: A new proof. International Journal of Game Theory, 211) Dec 1973. ISSN 1432-1270. doi: 10.1007/BF011337572 URL
kttps:://e
J. C. Harsanyi and R. Selten. A General Theory of Equilibrium Selection in Games. Cambridge: MIT Press., 1988.
10

---

Under review as a conference paper at ICLR 2023
E. Koutsoupias and C. Papadimitriou. Worst-Case Equilibria. In Christoph Meinel and Sophie Tison (eds.), STACS 99, pp. 404-413, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. doi: 10.1007/3-540-491 4001--9411113--61 38.
J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. Jordan, and B. Recht. First-order methods almost always avoid strict saddle points. Math. Program., 176(1-2)3311333 2019.
P. Mertikopoulos and W. H. Sandholm. Learning in Games via Reinforcement and Regularization. Mathematics of Operations Research, 41 1497:1227,1332, 2016. doi: 10.1287/moor:2016.000
Mertikopoulos and H. Sandholm. Riemannian game dynamics. Journal of Economic Theory, jet.6jj..............
177:315-364 2018. ISSN 0022-0531. doi:
Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
S. G. Nagarajan, D. Balduzzi, and G. Piliouras. From chaos order: Symmetry and conservation laws in game dynamics. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 7186-7196. PMLR, 13-18 Jul 2020. URL https: http::///occeeeeeeeeeeee
p .mw.eeedinnnn.........mmm mlr. wtt.sems..rpreeeeeeeeeeee
nagara jagarajan20a. html
G. Palaiopanos, I. Panageas, and G. Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5872-5882, 2017a.
G. Palaiopanos, I. Panageas, and G. Piliouras. Multiplicative weights update with con- stant step-size in congestion games: Convergence, limit cycles and chaos. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017b. URL htLLttts////pccceciiggg wewriss...rppp.pp wttpc/pppppppppp...p..... e93028bdci
.ddf
I. Panageas and G. Piliouras. Average performance of replicator dynamics in potential games via computing regions of attraction. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC 16. pp. 703-720, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450339360. doi: 10. 10.1145/2940716.229
L. Panait and S. Luke. Cooperative Multi-Agent Learning: The State of the Art. Autonomous Agents and Multi-Agent Systems, 113):3877434, Nov 2005. doi: 10. 10.10077/114588-05--66611
M. Pangallo, J. B.T. Sanders, T. Galla, and J. D. Farmer. Towards a taxonomy of learning dynamics
in games. Games and Economic Behavior, 132:1-21, 2022. ISSN 0899-8256. doi:
10.1016/j 10.1016/j.geb.202111 geb...2....221101155..
Roughgarden. Intrinsic Robustness of the Price of Anarchy. ACM, 62(5), nov 2015. ISSN 0004-5411. doi: 10.1 10.1145/280688.
B. Swenson, R. Murray, and S. Kar. Regular potential games. Games and Economic Behavior, 124: gcb.2020.090005
432-453, 2020. ISSN 0899-8256. doi:
E. van Damme. Stability and Perfection of Nash Equilibria. Peringer-Verlag Berlin, Heidelberg, 1987. ISBN 0387171010.
X. Wang and T. Sandholm. Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games. In Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS'02, pp. 1603-1610, Cambridge, MA, USA, 2002. MIT Press.
B. Zhang and J. Hofbauer. Equilibrium selection via replicator dynamics in 2 x 2 coordination games. International Journal of Game Theory, 44(2):433 -48, May 2015. ISSN 1432-1276 doi: 10.10777400082--0444447777
11


Reviews:
[{"review_id": "qkDvI_VYaA", "reviewer": "Reviewer_S7pu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper motivates the study of the relative sizes of regions of attraction of different equilibria, then tackles the case of symmetric, 2x2 coordination games. For this class of games, some partial/preliminary results are given.", "summary_of_the_review": "The problem is relevant and the empirical/visual approach is promising. This can make a fine contribution if the formal results are expanded to have more formal proofs or a more complete treatment of the 2x2 symmetric games case.", "strength_and_weaknesses": "I found the paper to be well written and easy to read. It is certainly convincing in terms of motivation, the problem is interesting and challenging.\n\nMy main concern is that the paper asks interesting questions, but makes little progress in terms of answering them. The paper sets out to compare the average performance of q-replicator dynamics for the class of symmetric 2x2 coordination games. Even in this 2-dimensional case, the results presented in the paper are very partial and feel preliminary in nature:\n- Theorem 4.4 compares average performance between q=0 and q=1, when $\\alpha \\geq 0.5$. Nothing is said about other values of $q$.\n- An invariant function is given in Lemma 4.5, which gives empirical evidence (through plots) that the regions of attraction are monotonic in q, but no formal proof is given. This left me with the impression that there is no treatment of the general case that was promised in the introduction (i.e. general q) except a conjecture at this point.\n- It is also unclear if/how this geometric approach would generalize to other game classes, especially in higher dimensions. It would be great if the authors could argue why this approach can generalize and can be useful beyond the two dimensional case.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "c3FJGRNhcYJ", "reviewer": "Reviewer_jma7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves pointwise convergence of q-replicator dynamics to NE and corresponding bounds on average price of anarchy, generalizing previous works.", "summary_of_the_review": "I tend to reject due to lack of comparison with PP16 and seemingly incremental results.\n\nAfter discussion with other reviewers, I'm satisfied with added discussion with PP16 and will raise the score accordingly.", "strength_and_weaknesses": "Strengths:\n\nThe results are solid. The motivation and proof ideas are well explained. \n\nWeaknesses:\n\nI'm not familiar with this specific topic studied in this paper, however I found it's a follow-up of (and resembles) the EC paper \"Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction\" (PP16) which this paper doesn't seem to give enough credit to. The studies of convergence of RD to NE, region of attraction and average price of anarchy already appeared in PP16, yet this paper doesn't have enough discussion on PP16 at all. PP16 were only mentioned and cited a few places in this paper just like other much less relevant papers, which might cause misleading judgement on the novelty of the results.\n\nThe significance of results seems questionable. Theorem 3.2 is a generalization of PP16 to QRD whose proof idea seems similar. The applications Theorems 4.4/4.6 are limited to the 2X2 case.\n\nSome terms are not defined rigorously. For example, $x_k^*$ is a point in simplex in Definition 2.1, what do you mean by a best response is contained in a point?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Mogpu3NL1zp", "reviewer": "Reviewer_jh9A", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors consider the problem of finding dynamics that not only converge to Nash Equilibria but also converge to \"good\" equilibria according to some objective function, e.g., the social-welfare. The main results are the following:\n  1. The social welfare of the 0-replicator dynamics is higher than the social welfare of the 1-replicator dynamics.\n  2. For the special case of symmetric two player game with two strategies (2-by-2 games) the price-of-anarchy, i.e., the ratio of the optimal social welfate divided with the social welfare of the equilibrium given by the dynamics, is bounded by 2.", "summary_of_the_review": "  Based on my comments above I recommend acceptance.", "strength_and_weaknesses": "Strengths\n======================\n  - The problem that the authors consider is very important and difficult and even the results for the special case of 2-by-2 games are very important.\n\n  - The paper is well-written and the algorithms, techniques, and results are well-explained.\n\nWeaknesses - Comments\n========================\n\n  1. 2-by-2 games is a rather restricted case, it would be nice if the authors can explain why their techniques cannot be extended to more general games. Do we have lower bounds for more general games.\n\nPost-Rebuttal\n========================\nI thank the authors for the response! After discussion with other reviewers, I agree in the following weaknesses of the paper:\na. The contribution of the paper should be expressed more clearly. In particular, it should be clear from the abstract that this is not the first work that explores the average case performance of no-regret algorithms in games. Also, I believe the authors should highlight more, even in the abstract, that the class of games that they consider captures games for which the worst-case PoA is unbounded.\nb. The number of people that would be interested in this result is smaller compared to other conferences, e.g., EC, which are a better fit for this paper.\nI still recommend acceptance but I would reduce my score to 7 instead of 8 if there was such an option.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject