Beating Price of Anarchy and Gradient Descent without Regret in Potential Games
Authors: Iosif Sakos
Stefanos Leonardos
Stelios Andrew Stavroulakis
William Overman
Ioannis Panageas
Georgios Piliouras
Venue: ICLR 2024 poster (2024)
Keywords: q-replicator dynamics
potential games
average price of anarchy
learning
Primary area: learning theory
TL;DR: Despite being almost optimal on average in a class of $2\times2$ potential games with unbounded Price of Anarchy, gradient descent is not always the optimal choice even in this restricted setting. These findings extend experimentally in larger games.

Abstract: Arguably one of the thorniest problems in game theory is that of equilibrium selection. Specifically, in the presence of multiple equilibria do self-interested learning dynamics typically select the socially optimal ones? We study a rich class of continuous-time no-regret dynamics in potential games (PGs). Our class of dynamics, *Q-Replicator Dynamics* (QRD), include gradient descent (GD), log-barrier and replicator dynamics (RD) as special cases. We start by establishing *pointwise convergence* of all QRD to Nash equilibria in almost all PGs. In the case of GD, we show a tight average case performance within a factor of two of optimal, for a class of symmetric $2\times2$ potential games with unbounded Price of Anarchy (PoA). Despite this positive result, we show that GD is not always the optimal choice even in this restricted setting. Specifically, GD outperforms RD, if and only if *risk-* and *payoff-dominance* equilibria coincide. Finally, we experimentally show how these insights extend to all QRD dynamics and that unbounded gaps between average case performance and PoA analysis are common even in larger settings.

Published as a conference paper at ICLR 2024
BEATING PRICE OF ANARCHY AND GRADIENT DE- SCENT WITHOUT REGRET IN POTENTIAL GAMES
Iosif Sakos
Stefanos Leonardos
Singapore University of Technology and Design sesif_sskos@myeee sutd. sg
King's College London
stefanos. leres..oonaann leonardos@kkl .ac. uk
Stelios Andrew Stavroulakis
William Overman
UC Irvine
Graduate School of Business, Stanford University wpo@stanford.co
sstavroueuci.ed
Toannis Panageas
Georgios Piliouras
UC Irvine
Singapore University of Technology and Design georgios@sutd.
ipanagea&ics.uci. uul.c...uciee..
ABSTRACT
Arguably one of the thorniest problems in game theory is that of equilibrium selection. Specifically, in the presence of multiple equilibria do self-interested learning dynamics typically select the socially optimal ones? We study rich class of continuous-tine no-regret dynamics in potential games (PGs). Our class of dynamics, Q-Replicator Dynamics (QRD), include gradient descent (GD), log- barrier and replicator dynamies (RD) special cases. We start by establishing pointwise convergence of all QRD to Nash equilibria in almost all PGs. In the case of GD. we show a tight average case performance within a factor of two of optimal, for class of symmetric 2 2 potential games with unbounded Price of Anarchy (PoA). Despite this positive result, we show that GD not always the optimal choice even in this restricted setting. Specifically, GD outperforms RD, if and only if risk- and payoff-dominance equilibria coincide. Finally, we experimentally show how these insights extend to all QRD dynamics and that unbounded gaps between average case performance and PoA analysis are common even in larger settings.
INTRODUCTION
Multi-agent learning often occurs on highly non-convex landscapes even when agents have perfectly aligned or common interests (Bard et al., 2020 Dafoe et al.) 2020: 2021). Thus, even if learning dynamics equilibrate, their fixed points may include saddle points or local optima of poor performance (Dauphin et al. 2014). large stream of recent work has made considerable progress in showing convergence of optimization driven learning dynamics to locally attracting points (Ge al. 2015
Lee et al. 2019 Mertikopoulos et al.] 2019) or equilibria in cooperative games (Cohen et al. 2017
Palaiopanos et al.) 2017 Anagnostides et al. 2022 Leonardos & Piliouras 2222 However,
trivial games routinely possess attracting points of vastly different performance, and this remains true, even if restricts attention refined and highly robust notions of equilibria, such as pure/strict
Nash equilibria (NE) (Kleinberg et al., 2009 Flokas et al. 2020). Accordingly, these convergence results are enough to reason about the quality of the learning outcomes.
This challenge, known as the equilibrium selection problem, is arguably one of the thorniest problems on the intersection of game theory and learning theory with multiple practical manifestation ML systems (Daloe et al. (2020). Standard game-theoretic approaches (Harsanyi) 1973 Harsanyi & Selten
1988 van Dammel 1987) or worst-case metries, such as the Price of Anarchy (PoA) Koutsoupias & Papadimitriou
1999); Christodoulou & Koutsoupias (2005); [Rouhhgarden (001)). offer little
For convergence equilibria in competitive games also (Daskalakis & Panageas 2018 Bailey & Piliurra 2019 Cai
2022

---

Published as a conference paper at ICLR 2024
insight, often none at all, from a dynamic//earning perspective. The reason is that certain NE may be reachable only from very small sets of initial conditions. Thus, instead of seeking approximately optimal performance for (almost) all initial conditions, which is generally impractical, we need to develop and argue about average performance measures that couple the limit point of the learning process with the likelihood that such an outcome is reached by the given learning dynamics.
Based on the above, our focus is to study 1) under which conditions can we reliably compare the performance of standard learning dynamics, such as replicator and gradient descent, in games and 2) under which conditions can they be shown to be approximately optimal under random initialization even when the performance gap between different equilibria, i.e., the PoA, is unbounded.
Model and Contributions. To make progress in these directions, we study Q-replicator dynamics (QRD) in general potential games (PGs). QRD are one of the most general classes of continuous time, multi-agent learning dynamics that include gradient descent (GD), replicator (RD) and log- barrier dynamics as special cases (Giannou et al., (02T). On the other hand, PGs are the standard model of multi-agent coordination and include congestion and identical interests games as important sub-classes (Wang & Sandholm 2002 Panait & Luke 2005 Carroll et al. 2019 Dafoe et al. 2020).
To analyze the average- and cumparative-performaat establish their convergence to equilibrium points. In our first result, we answer this question affirma- tively by proving pointwise convergence of all QRD to NE in almost all finite PGs (Theorem 3.2).
of QRD in PGs, an essential first step is to
Our proof combines recent results from Swenson et al. (2020 2 with standard convergence techniques in the study of PGs, e.g.. Palaiopanos al. (2017) 7); Mertikopoulos & Sandholm 2016 2018).
In Section 4 we turn to our main focus of equilibrium selection, we restrict our attention for analytical tractability class of 2-agent, 2-action (2 2) PGs. Despite its simple representation, this class retains all complexities of multi-agent learning that we aim to study. Specifically, as we show, there exist games in this class which have arbitrarily large PОλ, i.e., for which the worst-case equilibrium can be arbitrarily worse than the socially optimal outcome, but for which the Average Price of Anarchy (APoA) under GD admits a (tight) upper bound of (Theorem 4.8p. Despite this positive news for GD, we also show that, even in this restricied class of games, GD is not always optimal. Specifically, GD reaches the payoff-dominan RD, if and only if. this equilibrium is also risk-dominant (less risky) (Theorem 4.6). To the best of our knowledge, this provides the first comparison in the performance between two optimal no-regret dynamics and adds new dimension the long literature on the important interplay between risk- and payoff- payoff-dominance in game-theoretic dynamics (Kim 1996; Scchmidt et al. 2003 Sato et al.)
i.e., socially optimal, equilibrium more often than
2005 Kaisers& & Tuyls 2011: Kianercy & Galstyan 2012 Leonardos & Piliouras] 2022 Pangallo
ct al. 2022).
Finally, in section we present experiments in larger PGs for which risk- and nayoff-dominance can be properly generalized (diagonal payoff matrices). Such games are, in fact, designed to be as hard as possible from the perspective of average case performance due to their exponentially large number of NE and unbounded PoA. However, as our experimental results rather surprisingly indicate, increasing the size of the game seems to have little no effect on average-case or relative performance and the analogues of Theorem 4.6) i.e., comparative performance of RD and GD, and Theorem 4.8 i.e., bounded APoA (in fact typically around 1.2), continue to hold.
Related Work The literature average-case performance is scarce. As exhibited by Panageas & Piliouras 2016); Zhang & Hofbauer (005)); Pangallo et al. (2022) one of the main reasons is that regions of attraction complex geometric manifolds that become mathematically intractable even in low-dimensional settings. Average performance metrics are first introduced in Panaagess & Piliouras (2016) who is the main precursor our work. [aanageas & Piliouras (2016) focus exclusively on replicator dynamics and prove pointwise convergence to NE only for the special cases of congestion games with linear cost functions and network coordination games. Their bounds on APoA only apply in restricted instances of common interest games (Stag Hunt), Critically, prior to our work it was not known whether a rigorous comparison between RD and GD possible in any single game setting.
Swenson et al. 2020) shows that all NEs in almost all, i.e., in all but closed set with Lebesgue measure zero, PGis are regular in the sense of Harsanyi 1973) i.c., they are isolated and highly robust.
2

---

Published as a conference paper at ICLR 2024
Regarding the technical tools, our approach makes use of two connected, yet fundamentally different, theories. The first part, i.c., convergence, relies on the theory of Lyapunov analysis and the properties of dissipative systems, i.c., systems that lose momentum over time till they converge steady state
(Haddad & Chellaboina 2008). This in itself is standard staple of analyzing learning in potential games (Kleinberg et al.] 2009 Cohen al. 2017 Anagnostides et al.] 2022). By contrast, the second part, i... performance, relies on the existence of invariant functions, a feature most often studied in conservative systems, that characterize stable and unstable areas in the state space of such systems (Palaiopanos et al., 2017 Nagarajan et al. 2020). is important to note that this proof technique is scalable to higher dimensional settings. The key idea is to identify one or more (in more complex games) invariants of motion for QRD or other game dynamics. This is arguably a challenging task, but several recent works showcase that this is viable proof strategy rather general settings Balduzzi et al. 2018); Mertikopoulos et al. (0:T8) Piliouras & Wang (2021) Paik & Griffnn (2023)
functioos
2 PRELIMINARIES: GAME-THEORE
AND BEHAVIORAL MODELS
Game-theoretic model. A multi-agent finite potential game r = (N, (As, uk) })} denotes the interaction between a set of N == (1..... .2} agents. Each agent A E N has a finite set of actions, Ak. with size |Axl. and reward function ug A - R where A == -ITEN As is the set of all pure action profiles of r. Agents may use mixed actions or choice distributions, Ta (osk.o))LE.Al
E Xx. where FR,0g is the probability with which agent uses their action aş E As and X3- = {I* RlAul Ea.es, Ik.oz = 1, Tk,oz 2 0} is the (IAg) (all-1--dimnnt -)-dimensional simplex. Given any mixed-action I& E Xr, we write supp(æ*) == fax E AA Fh > -} to denote the support of action T4. i.e., the set of all pure actions 0g E AA. that are selected with positive probability at Tg. Using conventional notation, we also write 8 = (8k,8-)) )) E A and = (+=) X' IIKEN X to denote the joint pure and mixed action profiles of T, where 8-A and - are the vectors of pure and mixed actions, respectively, of all agents other than k. When time is relevant, we will use the index t for all the above, c.g., we will write zx(t) for agent k's choice distribution at time 2 O. Finally, a function $ A-> R is called a potential function of T if it satisfies u4 (s) ue g. s=*) (ss) $(5,, 8-1), for all k E N and all s' E A. The agents' reward functions and the potential function extend naturally to mixed action profiles with un (x) Ee [u>r[ux((s) [s)] and (xx) E.~z (s)).
Regular Nash and restricted equilibria. A Nash equilibrium (NE) of I' is an action profile x' e X x",)) (xx.x"x)) for all & E N and for all X. By linearity of expectation, the above definition is equivalent to: un (x*) ) 2 us ux(a,,=",)) for all ag E Ass and all k N, where uy (ak, x²xx) is the reward of agent l for playing pure action ag against mixed strategies z"* by the remaining agents. Let NE(T') denote the set of all NE of I. A NE is called symmetric if oi = = xx and is called fully mixed if supp(=*) = ILE supp (xt) = A. A NE called regular if it satisfies the following definition.
such that un (x(x) 2 uy (3x,
2020).. A Nash equilibrium, xx E NE(L"), is called regular if it is (i) quasi-strict, i.e., for each player k E N, æt assigns positive probability to all best responses of player k against x= and (ii) second-order non-degenerate, i.e. if the Hessian, Hxx") of the potential function D. taken with respect to supp(x*) is non-singular.
Definition 2.1 (Regular Nash equilibria (Harsanyi 1973 Swenson et al.)
Finally, a restriction, I' = {N, (Aps "N)e))) of T, is game where A As and u/g : A' R is the restriction of uy A' == TKE for all k E W. We write Rr denote the set of all restrictions of T. An action-profile x E X is called a restricted equilibrium of I if it is a Nash cquilibrium of a restriction of I,, cf. Mertikopoulos & Sandholm (2018). It is easy to see that all restrictions of a potential game I' = [N,(An, (A,, uk uk)Rev. / are also potential games, whose potential functions are restrictions of & to the respective subspace of A.
lebaaiiorll-earrinn model. The evolution of agents' choice distributions in the joint action space. X' is governed by the differential equations (equations of motions) = Vz(x), where V, : X R A4l is given by
q- gereplicator dynamics (QRD) which are described by the parametric system of
tk.a k = 2h.a (un(as, x-x) Eo,eA, L,,, ux(ag,
for all k E N, ax E As, (QRD)
EajeAn A "haj
3

---

Published as a conference paper at ICLR 2024
for any q 2 0. Special cases of the above dynamics are the projection gradient descent (GD)
dynamics, for = O, the (standard) replicator (RD) dynamics, for q = 1. and the log bog-barrier or
inverse update dynamics, for q = 2 (Mertikopoulos & Sandholm 2018 Giannou al. 202I
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 subclass of potential games we dub Perfectly-egualar Potential Games (PRPG) that contains almost all finite potential games.
Definition 3.1 (Perfectly-regee
potential games). A potential game I' is called regular if it has only regular Nash equilibria. A regular potential game is called arfectty-reguilee potential game (PRPG) if all its restrictions are regular potential games, i.e., if they only possess regular Nash equilibria.
As we show in Lemma B.2 B.2 in the Appendix, almost all finite potential games are PRPGs; this is a direct generalization of Swenson et al.) (2020) who prove that almost all potential games are regular. The PRPG class contains many widely-studice subclasses of games, e.g., congestion games, or games with identical reward functions (Wang& & Sandholm/ 2002]
& Luke| 2005; Carroll et al.) 2019) Dafoe et al.) 2020). Examples of non-PRPG games are degenerate games with equal payoff's e.g., two-player game with actions A₁ = A = {ar, a2) and payoff's un (a;, a,) = 1 for all j E A& and k 2, The convergence result of QRD in this class is stated formally in Theorem 3.2
|aanait |
Theorem 3.2 (Pointwise convergence of QRD to NE in PRPGs). Given any perfectly-regular potential game (PRPG), r, and any interior initial condition x00) E int X. the q-replicator dynamics, defined as in equation QRD) converge pointwise to Nash equilibrium x² of for any parameter q 2 O. Furthermore, the set 2(int.X) = U x (x" E X llim,-so x(1) = x², xx0) = ro ) i.e.
the set of all limit points of interior initial conditions, is finite.
states that QRD converge some NE for almost all initial conditions in almost all potentials games. A direct implication is that when reasoning about the quality of the collective learning outcome in cooperative multi-agent settings, as captured by PRPGs, we can restrict our attention to NE. This is the subject of the next section. Before proceeding with this, we provide a sketch of the proof of of[hherem 3.2 (cf. (Apenddix for the formal proof).
Importantly, Theorem 3.2
The proof of Theorem 3.2 proceeds in two steps, which utilize 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 QRD. In the first step, we prove that for any initial condition, the sequence of joint action profiles, ar())22,. that is generated by QRD for any q 2 converges to restricted equilibrium of PRPG, P. This relies on the fact that the set of cluster (limit) points of the trajectory- also called the wimit set-is a finite, and in fact, as we show, a single element set for any PRPG. In turn, this holds because any PRPG provably contains only a finite number of restricted equilibria. In the second step, we show that any such limit point has to be a NE of r. To establish this, we exclude convergence to restricted equilibria that are not NE of I by coupling the structure of PRPGs, which ensures that there a 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 increasingly higher probability. As a result, 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 r.
4 PERFORMANCE OF THE COLLECTIVE LEARNING OUTCOME
Beyond static performance metrics. We next turn our attention to the main challenge of quan- tifying the quality of the collective learning outcome. To do that, we need to derive appropriate performance metrics. In static regimes, we can rely on a variety of meaningful metries, e.g., the Price of Anarchy (PoA) (Koutsoupias & Papadimitriou 1999 Christodoulou & Koutsoupias 2005 Roughgarden 2015). which is defined as the ratio between the socially worst NE of the game and the socially optimal outcome (in terms of the agents' sum of rewards). However, despite the useful insights that PoA provides in general games, it is not difficult to find PRPGs in which the PoA fails to provide any meaningful information about the game. Let us consider the following example:
4

---

Published as a conference paper at ICLR 2024
Example 4.1 (A simple example of unbounded performance loss). Consider a parametric x PRPG. Tw, i.e., a 2-player 2-actions PRPG with identical payoff functions Uw 1 ($1, 82) = Uu (82, $1) (s1, $2), where matrix Aw E _2x2 is given by A,, = diag (1, w), with I w The game Iw has two pure NE, one that corresponds to 21 = (1,0) and 22 = (1, 0) with social welfare (W(x) = ++++11 = 2, and one that corresponds to x = (0, 1) and x/2 = (0. with social welfare 2w. Since w can take any value larger than 1, the difference in performance can be arbitrary large with respect to the PoA. Specifically, (TA = SW(=') (W()) w + 00 as w - 00.
SW (a') =
While useful in static environments, the PoA metrie does not 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 to reach good or bad outcome given that the mulli-agent system converges?
4.1 REGIONS ATTRACTION AND AVERAGE PERFORMANCE METRICS
To answer the above question and argue about the collective performance of the game dynamics, we need to quantify the likelihood of each outcome when the initial conditions of the system are randomly sampled. A region of altruction of given outcome formalizes this notion.
Definition 4.2 (Regions of attraction). Let I be any game and assume that its joint action profile, I X. is evolving according to the equations of motion è f(x). Then for any x² X. the set fr((") == {Io E X lim,->oo x(t) = x², z00) = _o is called the region of attraction (RoA) of with respect to the dynamics f.
In other words, the RoA of point x" X' is 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 a corresponding average- seerage-performacce metric that weighs-in all 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 to be meaningful, a minimum requirement, is that the dynamics converge for almost all, i.e., all but a measure zero, initial conditions. An Average Performance Metric (APM), refined from (Panageas & Piliouras, 2016), is defined as follow?
metric). Let I be multi- agent game and assume that its joint action profile, z E X, is evolving according to the equations of motion à f(x). Let Xo S X be a set of initial conditions such that the set of convergence points ((Kx) is finite. Then, given performance metric g : TR ofT, the overage-perfommen
Definition 4.3 Avverage-prffrmaate
of the dynamics governed by f with respect to the performance metric 9 and the set of initial condition Xu, is given by
APM, No (f,1)= = >E [m(ROA(r((z)) g(x"),
(APM)
xx" x'EQ(X))
where y is probability measure on Xo-
In other words, APM is the expected optimality of a random initialization of the dynamics in Xo S X with respect to some metric g. For instance, if the performance metric g is the social welfare, then the wverage-performann
metric with respect g measures the expected social welfare of the system for any random initialization in Xg. The wwerage-performen remainder of this section is the Average Price of Anarchy (APoA) (Panageas & Piliouras) 2016). The APoA is an APM with respect to the social welfare, re-normalised such that the APoA is greater than or equal to 1, with equality only if (almost) all the initial conditions converge to the socially optimal outcome of the system. Formally, given a multi-agent game T, equations of motion à = f(x) that describe the evolution of the agents actions in I', and set of initial conditions Xo S X that consists of almost all points in X, the APoA is given by
metric that we are going to use in the
APOA(J,T) = maX x SW(x)
(APoA)
APMsw. (f.T)
P Heee, diag(a1, 02) denotes matrix with 01 22 on the diagonal and zeros otherwise. Also, we write both xr. y E J0, 1] to denote the mixed choice distributions, (z. 1 - 2), (v, 1 - y), of players I and 2, respectively. 'Recall that probability measure μ on compact space X' is countably-additive function from the powerset of X' to R4 such that p(X'= 1 and ((0)= = 0.
5

---

Published as a conference paper at ICLR 2024
Notice that a large APoA, like large PoA, is negative trait that depends on the game r, but, in contrast to PoA, it also depends on the game dynamics f. In other words, a lower APoA is an indication of better performance of f in I compared to some other dynamics with larger APoA.
Remark 4.4. As we mentioned above, 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 2(x) C NE(T) for almost all initial condition Io E XX, and (ū) the set of limit points, ((X), is finite two conditions that are satisfied by any PRPG that evolves with respect to some QRD (cf. Theorem
the APoA has an intuitive interpretation. Specifically, in this setup, the APoA is always bounded between the PoA and the Price of Stability (PoS) of the game, i.e., the ratio between the socially optimal outcome and the socially optimal NE (Roughgarden 2015
4.2 THE TAXONOMY OF QRD IN 2 x PRPGS
Having established appropriate performance measures and that PRPGs are appropriate class in which standard learning dynamics, like QRD, can be compared in terms of performance, in this section, we perform complete theoretical analysis of our two motivating questions in the subclass of symmetric 2 x 2 PRPGs. The main takeaway of this analysis is that if the payoff-dominant NE requires relatively low risk for the players compared to the other NE of the game, i.e., if it is risk-dominant, then GD performs better than RD, and vice versa, if the payoff- game fails to be the risk-dominant one, RD performs better than GD. To the best of our knowledge, this is the first rigorous analysis on the relative performance between GD and RD. Concerming our second question, we establish that if the payoff- and iisk-dmminant equilibria coincide, the APoA of GD is upper bounded by 2. It is important to note that the class of symmetric 2 x 2 PRPGs is non-trivial regime for the comparison of the two dynamics, since PoA is provably unbounded in this setup, cf. Example 4.1 Omitted materials may be found in Appendix C
NE of the
Representation of symmetric 2 x PRPGs. We begin this section by showing that any 2 x symmetric PRPG is equivalent to game I' w, as defined in Lemma 4.5 The only non -eneerie games that are excluded from this reformulation are dominance-solvable games whose analysis is trivial and, therefore, outside of our scope. To proceed with the formal statement of Lemma 4.5 recall that NE, x², of a symmetric potential game, I, is called for all x' E NE(T'), and it is called risk-dominant, if zt is unilaterally optimal against the uniform distribution of the rest of the agents (Harsanyi & Selten 1988).
if ux(x') ) 2 uy ux'x')
Lemma 4.5. Any 2 x 2 symmetric PRPG, I, with payoff functions in (1(81 s2) = u2(52, can be equivalently represented by a game I w with payoff functions uw B (81, $2) ,,, (52, $1)
A.,3.51.22 where the matrix A E 12x2 is given by Au,3 = [ w for B 1 w. The game
T has the same NE as the original game, 1, retains its payoff- and disk-dominance properties, and preserves the limiting behavior of any QRD I. Accordingly, each game I T has three NE, two pure at = y O) and x y 1, with social welfare SW SW 0) = 2w and SW(1 = 2, respectively, as well as one fully-mixed NE at x² = 3² a w/ (w
3).
We are going to refer to the first pure-NE of T w as Tw- Note that zu is payoff-dominant for any Tw.,. and it is also risk-dominant whenever w >> 1 B, or equivalently, whenever a > 0.5.
Replicator dynamics (RD) versus gradient descent (GD). The first result of this section is that whenever the risk- and payoff-dominant equilibria of I was coincide, i.e., > 0.5, then the gradient descent (GD) dynamics, i.e., the 0-replicator dynamics, perform better (or equally in the generic case 0.5) average than the standard replicator dynamics (RD) with respect to the social welfare of their outcomes, i.e., they yield a smaller APoA. In any other instance of these games, i.e., for < 0.5, the RD perform better than GD with respect the same metric.
Theorem 4.6( ( Comparative Performance of RD and GD in 2 x 2 PRPGs). Consider an arbitrary 2 x 2 symmetric PRPG, which, without any loss of generality, can be represented an instance I w. and let Vo, V12 denote the equations of motion of the O-replicator, i.e., gradient descent dynamics, and 1 1-replicator, i.e., replicator dynamics, respectively, cf. equation QRD Then, it holds that
APMsw iut x (Vo, I ww,3) 2 APMsw iut x (Vi,
(1)
if and only if the payoff-dominan dominant equilibrium is also dominnat. Equality obtains only when 0.5, ie., when w = B.

---

Published as a conference paper at ICLR 2024
2
04.
113
40
454
Figure 1: The invariant function, (2, y), for all x; y E |0, 1]2 (cf. Lemma 4.7 in the game I. for w = 2. 9 = 0, and 0 (gradient descent), 9 = (standard replicator), = (olog-barrier), and q 20. The invariant function becomes steep at the boundary as increases, taking both arbitrarily large negative (dark) and positive (light) values in the vicinity of the NE, The contour lines zero, highlighted as solid blue and dashed red lines on the surfaces, correspond to the stable, Va.Stable y) = 0, and unstable, - y = O manifolds, respectively.
Theorem 4.6 demonstrates that the riskiness of the socially optimal equilibrium is decisive in characterising the relative performance of the GD and RD. In particular, as stated in Theorem 4.6 the expected social welfare is optimized by GD whenever risk and payoff-dominant equilibria coincide and is optimized by RD when risk and payoff-domine Theorem 4.6 provides a concrete recommendation on the optimal behavior of the agents (GD versus RD) based solely on the properties of the underlying game. However, it also suggests that even in low-dimensional. 2 x potential games, there is 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 the riskiness of the payoff-dominant dofinatt equilibrium (see also Appendix C).
equilibria differ. From a practical perspective,
Invariant functions. Technically, the proof of Theorem 4.6 (see Appendix C proceeds with first order analysis of the manifolds that separate the regions of attractions of the two pure equilibria for the different dynamics. This approach leverages the constants of motion invariant functions (Nagarajan et al., 2020), i.e., quantities that remain constant along the trajectories of the learning dynamics. The rationale is that if we can identify such function, then, by finding its value at the unique mixed equilibrium a of the game, we can determine all initial conditions that asymptotically converge to it: these will be all points at the same level set of the invariant function. The manifold, i.e., the geometric locus of all the points that converge to the equilibrium, formally, 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 sepuratrix (Panageas & Piliouras| 2016). Note that, since the dynamics are also back backward-inve -ard-invaaiinnt (Panageas & Piliouras) & Sandholm 2018), their level-set will also contain a set of initial conditions that converge to it when moving backward in time. These points constitute the unstable manifold of a. In Lemma 4.7 we identify such invariant for all QRD.
Lemma 4.7 (Invariant functions of QRD in 2 x 2 symmetric PRPGs), Given a 2 x 2 symmetric PRPG, I Tw.& whose agents evolve with respect to the q-replicator dynamics, QRD the separable function Va : 1) + IR, with 4 (I, == vh (④) vy(y),, and bhy (0,1) + R given by
x2-9 9 (1 2-22- +
axl-9 (1 aa x)) 1-1
q + 1,2,
2-
1 --6 q
(x)
a (2x)))) (1 a) In(1 x))
q = 1,
(2)
In(x) + In(1 x) + a +
1-a
q=2,
x
1-x'
remains constant along any trajectory (x(t), y(t)(( (:zo of the system. The The function Ug(x) is continuous with respect to the parameter q at, both, 9 = 1 and = 2, since lim 1 V (z(x) = 1z(x) and
lim (z(x) = 22((x)) (e) for all x E (0, 1).
Monotonicity of RoAs for all QRD. A rigorous extension of Theorem 4.6 to all QRD is prevented by the difficulty to obtain an analytical form of the separatrix for all E (0, 1). However, by visualizing the RoAs for all QRD in this range, obtain empirical evidence that the RoA is monotonically increasing in 4.
In Figure 1. we visualize the invariant function, v. (z y). for x. y 1) defined in Lemma 4.7
for varrous values of & E [0, 20]. From the panels of Figure I 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, the unique
7

---

Published as a conference paper at ICLR 2024
mixed NE, i... at y a, the invariant function, gg is equal to 0. The same holds for any point (sr, v) E (0, 1)2 with x = y. Thus, we can factorize (2 y) as V (T, = V St,atabl y) (x y) where 4taStablo (z, y) = 0 is precisely the geometric locus of all points (I, y) E (0,1) such that lim; s(t) a, and y = x is the geometric locus of all points such - z(t) a. These two manifolds constitute the stable and unstable manifolds of the g-replicator dynamics.
If we stack the stable manifolds (solid blue lines in Figure 1. it becomes evident that the region of attraction of the payoff-dominant and risk- dominant equilibrium grows as q decreases to This is depicted in Figure for all values of q E [0, 10). In this case, the unstable manifolds are always equal to the diagonal, x = y and thus, omitted. The progression of the surface of the stable manifolds continuous for larger values of q. Analogous plots, but with the results reversed as predicted by Theorem 4.6, can be generated for instances of T. g. in which the risk-dominant cquilibrium is different from the payoff-dominant one, as well as, for 2 2 generic PRPGs. In gen- eral, putting togetherTheoormm Theorem 4.d the current visualizations, we have both theoretical and em- pirical evidence that the region of attraction of the payoff-dominant equilibrium in I w. is de- creasing (increasing) in q for q 0 whenever this equilibrium is (is not) disk-dominant.
e-Replicator
0.9
9=1
0.7
0.5
Stable manifold for q j0, 10]
0.4
0.5
0.2
0.1
Figure 2: Stable manifold (separatrix) for all different values of q E [0. 10] (from blue to brown) in the I a game for w = 2 and g = 0. The manifolds for q = 0.
1, and = 2 are shown in shades of black for reference (cf. Figure 5). The region of attraction of the payoff-dominane equilibrium (bottom-Jett corner) shrinks as g increases.
Application: APoA in 2 x 2 PRPGs. To show-
case the practical importance of Theorem 4.6land the invariant function approach, conclude this section with a concrete evaluation of the APoA weraae-perforranee measure in the class of 2 x 2 symmetric PRPGs. For this result, focus symmetrie 2 x 2 PRPGs such that payoff and risk-dominant equilibria coincide; one can prove tight bounds on APoA as shown in Theorem 4.8
Theorem 4.8. The APoA of GD dynamics in all symmetric PRPGs, Tw,,, in which the payoff- and risk-dominant NE coincide is bounded by 2, i.e., APoA(Vo, Tw,,) S 2, for all Twys with >>> w. This bound is fight.
The proof of Theorem 4.8 proceeds by first order analysis of the function depicted in FFiuure 3 which, in turn, depends on the invariant function of the gradient descent dynamic, see Appendix C Note that the bound of Theorem 4.8 also holds for 5 1- w. but in this case. there exists no risk-dominant equilibrium. Moreover, one way to check that this bound is tight, is to set / = w+, for a small > and let w increase (cf. FFiurre 3). In combination Theorem 4.6 and Theorem 4.8 imply that the APoA of the RD (QRD with == 1), is not upper bounded by 2 whenever a < 0.5. i.e., whenever the risk- and payoff-dominan equilibria are different. However, for the case a 0.5, the separatrices for all q as visualized in Figure 2 (empirically) imply that
14
APMs Die
14
200
430
110
Figure 3: APoA of 2 x 2 symmetric PRPG for the gradient descent dynamies and various values of 9 and w. The APoA is upper bounded by 2 (dark to light values) as shown in Theorem 4.8 similar bounds hold for all values of q
visualize the stable manifolds when GD have the largest region of attraction, i.c., the lowest APoA. The case < 0.5, in which the manifolds mirrored on the y xr diagonal, is in Appendix C
$In Figure 2
8

---

Published as a conference paper at ICLR 2024
13
Alboks
APoA Sslurce
Midar Misae
APoA - std (Max APoA)
Hulliflla Bshal
RD
GD
12
4.3
3
1.16
+ .05(1.23)
1.12 + .04(1.1))
3.2
5
1.19
+ .06(1.3)
1.14 + .04(1.22)
10
1.22
- .05(1.38)
1.13 + .0((1.00)
20
1.21
+ .04(1.8))
1.11 + .02(1.22)
125
Figure 4 & Table Numerical results for the APoA metric replicator dynamies (RD) and gradient descent (GD) in diagonal PRPGs of dimensions m = 2,..., 20. The two panels show the APoA of each dynamic together with its standard deviation (left), their difference (solid line enveloped by the standard deviation shaded region) and the difference of the maximum APoAs of the dynamics (right) observed over 100 sampled games each dimension. The GD dynamics throughout outperform the RD dynamics suggesting that Theorem 4.6 with the notions of pure- and risk-dominant NE properly refined, may still hold for larger dimensional PRPGi (for the reverse implication in Theorem 4.6 Section 5). Table provides detailed statistics for m 3, 5, 10 and 20.
HIGHER DIMENSIONAL. NUMERICAL EXPERIMENTS
In this section, we present experimental evidence that our approach can be extrapolated on larger setups, i.e., beyond 2-games. Notice that, the extrapolation needs to be done with care since the central notion of risk dominance may not be treat this, by restricting our focus to the class of two-player diagonal PRPGs. Such games can be described by a common payoff matrix U the only non-zero elements of which lic its diagonal, i.c.
in larger game setups. We choose to
is of the form, U == diag (1, u2.-... ), where w.l.o.g, we assume O < u1 < U2 < <... < tmn-
Notice that diagonal PRPG defined as above has the following important traits:
1. Profiles (1, .).................... (m, m) are the only pure NE and, since the game is PRPG, the only stable NE.
2. The pure NE can be ordered in terms of payoffs as u1 < .... Um Consequently the NE (i, i) dominates all NE (i.j). j .
3. The difference in payoff's from any pure NE (i, to some non-diagonal profile (i.j). or (j.i). is
Wy for any j * v. If we define risk to the negative deviation payoffs Harsanyi Selten (988)) then the risk of NE (i. i) is uuf for all i I,..., m, and therefore the pure NE can be ordered in terms of risk with NE (i, be less risky than (j.j) for all j i.....i
Experimental setup. We run experiments in random 2-agent, symmetric diagonal PRPGs of dimen- sions m = 2,3,.... . 20 (size of each agent's is action space). In each game, the payoffs u1, U...... Un selected (pseudo-)randome
and satisfy the following properties: (i) the lowest diagonal payoff, is at least as large some predefined positive constant (set equal to le 12 for the experiments), (ii) the highest payoff, um is equal to the dimension, m, of the game, i.e., um = 2, 3. ... and 20 respectively, and (iii) u2,.... -1 are in ascending order strictly between #1 and um with randomly selected distances between them. For each dimension, we sample 100 random games and run the gradient descent and standard replicator dynamics for 1000 initial conditions till convergence.
The outputs of the simulations of the above experiments are summarized Figure 4 and Table 1. The outputs provide indications that (i) the gradient descent dynamics (continue to) outperform the replicator dynamics all diagonal games in terms average performance, and that (ii) the APoA is lownrebounded by 2, the theoretical bound that we presented in the case of 2 2 games. As Table I suggests, the APoA is, in fact, considerably lower than in all sampled games.
CONCLUSION
We study the class of q-replicator dynamics (QRD), and showed that all QRD converge pointwise to Nash equilibria in perfectly-regular potential games, class of games that encompasses almost all potential games, i.e., the standard models of multi-agent coordination. From the perspective of equilibrium selection and quality, however, convergence provides little information. Even if two dynamics converge and even if they have joint optimal no-regret guarantees, they may still exhibit very different equilibrium selection properties, which, in turn, determine their practical performance. Our analysis provides the first formal comparative analysis of different commiization-divven dynamics by combining diverse techniques and establishes intriguing direction for future work.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTTS
This research was supported in part by the National Research Foundation, Singapore and DSO National Laboratories under its AI Singapore Program (AISG Award No: AISG2-RP-2020-016 grant PIESGP-A TIESGP-AI-202--1 A1-2020-01, AME Programmatic Fund (Grant No.A20H6b0151) from S and Provost's s Chair Professorship grant RGEPPV2101. Ioannis Panageas would like to acknowledge startup grant from UCI. Part of this work was conducted while loannis was visiting Archimedes Research Unit. This work has been partially supported by project MIS 5154714 14 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.
REFERENCES
I. Anagnostides, I. Panageas, G. Farina, and T. Sandholm. On last-iterate convergence beyond zero-sum games. In K. Chaudhuri, Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 536-581. PMLR, 17-23 Jul 2022. URL https: https://proceeiine
mlr. www.prrsssseeee vvw.//v12///// anwgnottidssseee.........at html
J. P. Bailey and G. Piliouras. Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Grae- pel. The mechanics of n-player differentiable games. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 354 363. PMLR, 10-15 Jul 2018. URL
wwa.gssmmr...om mlr.
N. Bard, N. Foerster, S. Chandar, N. Burch, M. Lanctot, H. Song, E. Parisotto, V. Dumoulin, S. Moitra, E. Hughes, I. Dunning, S. Mourad, H. Larochelle, M. G. Bellemare, and M. Bowling. The Hanabi challenge: A new frontier for AI research. Artificial Intelligence, 280:1032100 2020. ISSN 0004-3702. doi: 2010
Y. Cai, A. Oikonomou, and W. Zheng. Tight Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities. CoRR, abs/2204.09228. 2022. URL https:
//doi.org/11 0. 48550/a rxiv 2204 09228
M. Carroll, R. Shah, Mark K. Ho, T. L. Griffiths, A. Seshia, P. Abbeel, and A. Dragan. On the Utility of Learning about Humans for Human-AI Coordination. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
G. Christodoulou and E. Koutsoupias. The price of anarchy finite congestion games. In Proceedings of the -evert-Seventh Annual ACM Symposium on Theory of Computing, STOC '05. pp. 67-73, New York, NY, USA, 2005. Association for Computing Machinery. doi: 10. 145/1060590. 1060600.
Cohen, A. Héliou, and P. Mertikopoulos. Learning with Bandit Feedback in Potential Games. In Pro- ceedings of the s1 International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6372-6381, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97815 10860964.
A. Dafoe, E. Hughes, Y. Bachrach, T. Collins, K. R. McKee, J. Z. Leibo, K. Larson, and T. Graepel. Open Problems in Cooperative AI, 2020.
A. Dafoe, Y. Bachrach, G. Hadfield, E. Horvitz, K. Larson, and T. Graepel. Cooperative Al: machines must learn to find common ground. Nature, 7857:33-36, 2021. doi: 10.
C. Daskalakis and Panageas. Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. In Avrim Blum (ed.). 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 Leibniz International Proceedings in Informatics (LIPlcs), pp. 27:1- 27:18, Dagstuhl, Germany, 2018. Schloss Liiituul---iini-ZZZZZ 978-3-95977-095-8
fuer Informatik. ISBN doi: 10.4230/LIPIss. 2019.27. URL http: //rp///rppss./// daggtuh de/ de/opus/vol http:/oooeeeeeeee wte.te/eeeee..ee. (ttexte/201//111111
10

---

Published as a conference paper at ICLR 2024
Y. N. Dauphin, R. Pascanu, C. Gulcehre. K. Cho, S. Ganguli, and Y. Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Proceedings of the 27th International Conference Neural Information Processing Systems Volume 2, NIPS' 14, pp. 2933-2941, Cambridge, MA, USA, 2014. MIT Press.
L. Flokas, E. V. Vlatakis- Gkaragkounis, T. Lianeas, P. Mertikopoulos, and G. Piliouras. No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix. In Proceedings 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 Coants-Onlin Stochastic Gradient for Tensor Decomposition. In P. Grünwald, E. Hazan, and S. Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 897, Paris, France, 03-06 Jul 2015, PMLR. URL https: /ttps::/proceecingg. mlr press/v40 GelG 1at.0//e15..tmlm
A. Giannou, E.-V. Vlatakis- Gaaarikuukk,,,,usss,, and P. Mertikopoulos. On the Rate Conver- gence of Regularized Learning in Games: From Bandits and Uncertainty to Optimism and Beyond. Part of Advances in Neural Information Processing Systems 34 pre-proceedings (NeurIPS 2021), 2021. URL https: httt:::://proceeeiiiic neur ieeerrpp... ps cctpppperr//221111 hash/bf44DF0abee5633777
603691 7055 html
Wassim M Haddad and VijaySekhar Chellaboina. Nonlinear dynamical systems and control: Lyapunov-bused approuch. Princeton university press, 2008
J. C. Harsanyi. Oddness of the number of equilibrium points: A new proof. International Journal of Game Theory, 2(1):235-250 Dec 1973. ISSN 1432-1270. doi: 10.1007/BF01133752. URL https:://dot
/10 11t.:0.1110000111111
J. C. Harsanyi and R. Selten. A General Theory of Equilibrium Selection in Games. Cambridge: MIT Press., 1988.
Honda. Equilibrium selection for symmetric coordination games with an application to the minimum-effort game. CiteSeerX] 2012.
M. Kaisers and K. Tuyls. FAQ-Learning in Matrix Games: Demonstrating Convergence near Nash Equilibria, and Bifurcation of Attractors in the Battle of Sexes. Proceedings of the 13th AAAI Conference Interactive Decision Theory and Game Theory, AAAIWS' 11-13, pp. 36-42. AAAI Press, 2011.
A. Kianercy and A. Galstyan. Dynamics of Boltzmann Q learning in two-player two-action games. Phys. Rev. E, 85:041145 145, Apr 2012. doi: 10. 10.10031yyeeee:55.4444444
Y. Kim. Equilibrium Selection in n- n-Person Coordination Games. Games and Economic Behavior, 15 (2):033-227) 1996. doi: 1006//0m..m.. 1tt.0///mm..199.00000000 1996.0066.
R. Kleinberg, G. Piliouras, and E. Tardos. Multiplicative Updates Outperform Generic No-Regret Learning in Congestion Games: Extended Abstract. In Proceedings of the forty-First Annual ACM Symposium on Theory of Computing, pp. 533-542, New York, NY, USA. 2009. Association for Computing Machinery. ISBN 9781605585066
doi: 00.1145/1534114.15356
E. Koutsoupias and C. Papadimitriou. Worst-Case Equilibria. In Christoph Meinel and Sophie Tison (eds.). STACS 99, pp. 403- Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. doi: (0.1007/3-540-49111-3
J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and B. Recht. First-order methods almost always avoid strict saddle points. Math. Program., 176(1-2):311-337 2019.
Leonardos and G. Piliouras. Exploration-exploitttion in multi-agent learning: Catastrophe theory meets game theory. Artificial Intelligence, 304: 2022. ISSN 0004-3702. doi: 10. 2021.
Mertikopoulos and W. H. Sandholm. Learning in Games via Reinforcement and Regularization. Mathematics of Operations Research, 197--114973322, 2016. doi: 10. 1287//mor.20166077777
11

---

Published as a conference paper at ICLR 2024
P. Mertikopoulos and W. H. Sandholm. Riemannian game dynamics. Journal of Economic Theory, 177:315-366 364, 2018. ISSN 0022-0531. doi: 10.10166j.et.22188066 20.00000...0.......
Mertikopoulos, C. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pp. 2703-2717, 2018.
doi: 10. 1137/1.978111199799
Mertikopoulos, 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.
net. for./forumm?m wtt./oooommmmmigg-a0 JCCKK JC9KQ
S. G. Nagarajan, D. Balduzzi, and G. Piliouras. From Chaos to Order: Symmetry and Conservation Laws in Game Dynamies. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7186-7196. PMLR, 13-18 Jul 2020. URL https::
mmlr
press/ //s//v1i www.v/11nggarrr a html
Joshua Paik and Christopher Griffin. Completely integrable replicator dynamics associated to competitive networks. Phys. Rev. E, 107:1052202,, May 2023. doi: 10. 10.1105/PhysRev.E.MM 107. L052202..
G. Palaiopanos, I. Panageas, and G. Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Proceedings of the 31 International Conference on Neural Information Processing Systems, NIPS' 17, pp. 5884, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97815 97865908
I. Panageas and G. Piliouras. Average performance of replicator dynamics in potential games via computing regions of attraction. 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.1145/2940716.5 16.20707...4
Panait and S. Luke. Cooperative Multi-Agent Learning: The State of the Art. Autonomous Agents and Multi-Agent Systems, 11)))387 434, Nov 2005. doi: 111007/11458-000
M. Pangallo, J. B.T. Sanders, T. Galla, and J. D. Farmer. Towards a taxonomy of learning dynamics in 2 games. Games and Economic Behavior, 132:1-21, 2022. ISSN 0899-8256. doi: ...1016/..ebb2021111
Georgios Piliouras and Xiao Wang. Constants of motion: The antidote to chaos in optimization and game dynamics, 2021.
T. Roughgarden. Intrinsic Robustness of the Price of Anarchy. ACM, 62(5), nov 2015. ISSN 0004-5411. doi: 10/1145/280883.
Y. Sato, E. Akiyama, and J. P. Crutchfield. Stability and diversity in collective adaptation. Physica D:Nonlinear Phenomena, 210(1):21-57,200)
D. Schmidt, R. Shupp. J. M. Walker, and E. Ostrom. Playing safe in coordination games:: the roles of risk dominance, payoff dominance, and history of play. Games and Economic Behavior, 42(2): 281-299, 2003. doi: 10.1016//0899100001111111100000 (0066888999-25560200052222
B. Swenson, R. Murray, and S. Kar. Regular potential games. Games and Economic Behavior, 124: 432-453, 2020. ISSN 0899-8256. doi: .e..016/..ebb22200099
E. van Damme. Stability and Perfection of Nash Equilibria. Springer-Verlan Berlin, Heidelberg, 1987. ISBN 0387171010.
X. Wang and T. Sandholm. Reinforcement Learning Play 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.10777500182--1444477777
12

---

Published as a conference paper at ICLR 2024
SUPPLEMENTARY MATERIAL FOR BEATING PRICE OF ANARCHY AND GRADIENT DE- SCENT WITHOUT REGRET IN POTENTIAL GAMES
A EXTENSIONS AND CHALLENGES
rigorous average-case analysis in arbitrary games is mathematically and computationally challeng- ing, since closed-form solutions for the boundaries of RoAs not always exist, and since computing RoAs is generally NP-Hard. Nevertheless, it immediate to extend the empirical analysis by approx- imating the APM of interest through counts of frequencies for each limiting equilibrium for multiple random initializations. However, the invariant function approach offers a scalable alternative that promising to work in more complicated settings. Finally, con-uniform distributions over initial conditions that keep the expectation in Definition 4.3) well-defined can be used to study games in which the dynamics converge limit cycles instead NE.
B MISSING PROOFS AND MATERIALS: SECTION 3
To complete the steps in the sketch of the proof of Theorem 3.2, start by showing that the class of perfectly-regufe potential games (PRPG) is well-defined, since restrictions of potential games are also potential games.
Lemma B.1. restriction of a potential game also a potential game.
Proof of Lemma B.I Let I' restriction of potential game and potential function + A R. Take O' A' + R to be the restriction of ④ to A' C A. Then for all k E N, and s, s' E A' we have that:
w/((s) (5 8-k) = (s))) us (5 8 k ((s) (( x
D' (s) 46 (5 $-k),
where the second equality follows from the definition of potential games (cf. seccionn 2 Hence, d' is a potential function, and therefore I' potential game.
Using the recent results of [Swenson et al. (020), it is not difficult show that perfectly-regular potential games are generic, and have a finite number of restricted equilibria. These are the statements Lemma B.2 and Lemma B.3 respectively.
Lemma B.2. Almost all finite potential games are perfectly-regular.
Let RPG, and PRPG denote the sets of regular potential, and perfectly-regular potential games, respectively. Let also I be random finite potential game. Since I is finite, there exist 2 distinct restrictions of I, where m == ΣLEN |Ak]- Then, by Lemma B. we have that any restriction I' of I' is also a random finite potential game, and therefore Pr(I RPG) = with respect the Lebesgue measure Swenson al. (200)). It follows that:
Proof of Lemma B.2
Pr(T E PRPG)
Pr(T & PRPG)
1 - P-r U I' d' RPG)
MeRt
2 1 Σ Pr(T' & RPG) 1,
MER
where the last equality follows from the fact that [Ry| is finite.
Lemma B.3. Every perfectly-regulan finite potential game has a finite number of restricted equilibria.
13

---

Published as a conference paper at ICLR 2024
Proof of Lemma B.3 Let I be perfectly-regular finite potential game, and let I' be one of its restrictions. By the definition of perfectly-regulaa potential game, we have that I is a regular potential game. Furthermore, since I' is finite and A A& for all & E N, it follows that I is finite. But then I is a finite regular potential game and as such it has a finite number of Nash equilibria, i.e., NE(T)) oo Swenson et al. (2020). Finally, since each restricted equilibrium is Nash equilibrium of restrictions of it follows that there exist at most:
Σ INE(T") S 2" max
[NE(T") < 30
L'ERr
ee
restricted equilibria of T. Therefore, the number of restricted equilibria of T is finite.
We, now, consider the g-replicator dynamics of a finite potential game r, given by the dynamical system of equations in equation QRD Our goal for the remainder of this section is to prove that for any interior initial condition (0) E X the dynamics in equation QRD converge pointwise to a Nash equilibrium of given perfectly-regular finite potential game [
The proof proceeds two parts: First, we prove that the dynamics converge to a restricted equilibrium of the game for any initial condition. Second, prove that for any interior initial condition, the dynamics are bound to deviate from any rest-point that is not a Nash equilibrium, and therefore, they have converge to a Nash equilibrium.
Let us begin by proving the first of the two claims. For this, we will use the notion of the w-limit set of sequence (z(f))e20 S X that is generated by the QRD, which is defined
w(+(()) = (a(())))) 1(>
200
where el S denotes the closure of a set S.
Lemma B.4. Given a perfectly-regulat finite potential game I, every w-limit set, with respect to the q q-replicator dynamics, is singleton {x*}, where x² E X is a rest rest-point of the dynamics. Specifically, x² is a Nash equilibrium, if q = O, or a restricted equilibrium, if > O. Furthermore, the set E X lim sr(( = x", s<0)= so)), i.e., the of all limit points, is finite.
((x) = Uxoexta (ar
Proof of Lemma B.4 Let I' be seffecttlyregulat finite potential game. Since I is potential game, by Proposition 6.4 of Mertikopoulos & Sandholm (2018), we have that every w-limit set consists entirely of rest-points of the dynamics. In particular, these Nash equilibria of т, if q or restricted equilibria of r, if > O. However, since I' is perfeetly-regular-ii it suffices for it to be regular for the case of q O-it follows by [emma B.3 that every w-limit set is a finite set. Consider now, the w-limit set of an orbit (z(t))s20 of the dynamics for some arbitrary initial condition <<))= = .p. Since xxt) continuous, the w-limit set (=t))) is the decreasing intersection of compact, connected sets and, therefore, it is connected. Since the w-limit set is finite, the above implies that, in fact it has to be a singleton {a*), where x Sandholm (018)) or restricted equilibrium if q >> 0, respectively. Finally, from the above, we have that the set of all limit points, Q(x') is a subset of the restricted equilibria of I; therefore, since I' is a perfectly-regus regular finite potential game, we have, by Lemma B.3] that the set of restricted equilibria of and, consequently, ((A') are finite.
Nash equilibrium g = 0 Mertikopoulos &
To prove Theorem 3.2 it remains to exclude convergence to restricted equilibria that are not NE of the original game, 1., To establish that, we will show that as the QRD approach limit point att the probability Tk,a, of non-optimally performing actions must go to zero. Thus, all actions in supp zg must be best response against x².g for all agents k E A which implies that at is NE of T.
Proof of Theorem 3.2) If q = 0, the statement follows directly from Lemma B.4 So we only need to consider the q q-Replicator Dynamics for q >> 0. Let be a perfectly-regular finite potential game, and let (z(t)) be trajectory of the q-replicator dynamics with initial condition =0) To E int X.
Recall that the interior of the set X. int X is the set of all joint choice distributions E X with full support, i.c., JE,ag > 0 for all dg Ar and for all & N; all points of X that not in the interior, are called boundary points.
14

---

Published as a conference paper at ICLR 2024
Since 0. we know that the support of xxt) remains constant for all t E R Mertiikoooulos & Sandholm (0018). Thus, since z0) E int X, it follows that art) remains in the interior of X for all 22 0, I.C., 2k.az (t) > 0 for all & E .V and for all ag Ag. Furthermore, by Lemma B.4 we have that the limit oo st) exists and is rest-point of the dynamics, say x="
Assume, now, that x= is not Nash equilibrium. This implies that there exists player and pure action G, of i such that u;(a;, x=;;)) > (,(x)). Moreover, since, x is, by construction, a rest-point, To see this, let assume the absurdum tta, We have
Hia 0 0 for all actions aj. Observe that Fia.
Since Ma, = 0 for all aj. by equation QRD
uz(az, x",1 EnEA, Thog x
for all aj whenever Zio, > 0.
(3)
EaLeA, Fiaz
Furthermore, since ui(ai, > ur(x"), we also have
ui(ai, x x11) > ux(x²)
Σ 0,EA,
Hio u=(a),
EoCEA, Ttax "ui(as,
Σ EA
Via,
by equation 3
(4)
EaGed Fran
EngEA, Viay [u(lakix=1))
EaseA: Fiax"
Clearly, the above reveals a contradiction, and therefore, it must be the case that xia, 0.
Fix c > 0, and consider the set:
B. E E ( Eases, pla, uzlag, + tej.
Eases: "haa
By continuity, B. is open and by equation equation 4 it contains x given small enough. Since at( converges x² - xo, there exists time 4, 2 such that s(l) Therefore, for each > le we have that:
B, for all i > le-
32,a; (1) (Jii, (1)) uu((,,))))) EoSEd, (ot.a, (t)) (t))
(( (1)) 0,
Eajes (Di,a, (t))a
where the last inequality follows because xx() int X for all t 2 0. Finally, by integrating with respect to time, we have that for all t te:
F4,a, 100=-(o f" (r), (t') di + (laa((1) > 24 (1c) 0.
e'mt,
Therefore, by the continuity of zr(1,, we have that sio lim Ti,o; (1) 2 Ni,,, (le) > O, which contradiction assumption that z1a, = 0, which is direct consequence of x not being NE of the game; thus, x² has to be a Nash equilibrium o.
C MISSING PROOFS AND MATERIALS: SECTION 4
For this part, it is useful to use the generic notation used by Pangallo et al. (2022), who provide taxonomy of 2 x games. Consider an arbitrary 2 x 2 symmetric PRPG with payoff with payoff' functions (1( 82) 81) = B.y,g where the payoff matrix B 2x is given by:
B
a b
(5)
that may always be done by possibly re- indexing the agents' actions. If c > d, then the game is dominance-solvad (cf. Table 1 of Pangallo et al. (2022)) and such the dynamics of the game trivial. Hence, may narrow our scope
and set without any loss of the generality d 2
15

---

Published as a conference paper at ICLR 2024
to payoff matrices that satisfy d 2 Also, PRPG games have a finite number of Nash equilibria, and so, we may exclude games where the above inequalities are not strict. All in all, we are going to assume without any loss of the generality that the following conditions hold:
d a and > c.
(6)
Proof of Lemma 4.5 Recall that in the notation of Pangallo al. (202)). an arbitrary 2 symmetric PRPG can be written with payoff functions U1 (11,582) 82) = (2 $1 = B.,.,, where the payoff
matrix B E R2x2 is given by B E5 where we assumed without loss of generality that
> a > b and d> c (cf. equation equation 6 Let also - z) and (y. 11-27 y) with z, y E [0, 1] denote the choice distributions of the two agents, adopting the common notation for the statespace of game dynamics in 2 x 2 games. Thus, by slightly abusing notation, the choice distributions can be conveniently represented by single variables, 2 and y for agents and 2, respectively. The 3 Nash equilibria of such games are x = = and x = y 0, with payoffs a and d, respectively, for both d-c players, and x² = " a-b+d-c' with payoff (a*) + x² x x²) (6 + c) (1 x" ) for both players. Recall that, by definition, the Nash equilibrium = is always mnyoff-dominant due to the possible re-indexing of the actions-and is risk-dominaní if <>> a b.
To prove the claim of the Lemma, we begin by presenting the equations of motion of the q-replicator dynamics as functions of x and y. For the first agent that is:
x ur (a1, y) + (1 x) (a2, 2)
á x² U1 (1(())))
x + (1 x)
(1 - 2)
(uy (a1, /0- u1 (1 8))
+ (1 - z))
x² (1 11--)) x²
(ay c(1 v) by d(1 - v))
(8)
+ (1 - z)9
(1 - x)
[(a b + c)y (d - c)]
x7 + )
2 (1 - x
x + (1 x) K (y y"),
where n === b + Similarly, we may derive the equation of motions for the second agent as ú = ""(1ー)" -=+ (I (0--x") ). Here, (x", v²) is the mixed Nash equilibrium of the game (see above), and it holds that y" = x= Thus, apart from the variables and and the hyperparameter q which is exogenously given, the qrreplicator dynamics depend on the payoffs the game I' only through and x-' d-B It follows that any transformation that preserves the value of x" and scales k by constant may only scale é and y by the same constant; that is, may only affect the convergence rate of the dyanmics, but their limiting behavior. Starting from arbitrary payoff matrix B as given in cquation lett us assume, without any loss of the generality, that the conditions in equation apply. Notice that, since by the aforementioned assumptions we have that d > such that 0 < a + < d- - c. Accordingly, we consider the following sequence transformations: (TI) Add 8 to the first column, (T2) subtract from the second column, and (T3) divide by 6. These lead to:
may set some E IR
(a+d b+6
T227
a b+
0
B =
b
= d-n hid
a++
a+3
#4d 1897
Notice that A Ad-e 8-5 is the payoff matrix of a parametric game Tw. where w = d-c and B = b+g 2431142
e+6
(T2) and (T3) leave x" unaltered and only scale by a constant a that is, the limiting behavior of the q-replicator dynamics is preserved. Furthermore, the iis-ddmminance of the equilibrium points is preserved, because:
Observe, that (T1)
d-c c + 8
> 6
d > a b if and only if
+
Finally, the payoff- dominaceee the Nash equilibrium r = y = is also preserved because, by the definition of 8, we have that d-1 1.
16

---

Published as a conference paper at ICLR 2024
Next, we are going to construct the invariant functions of I w. with respect to the q-replicator dynamics, which are given by Lemma 4.7 that we restate below for completeness. Recall that (a. a) is defined to be the equilibrium point of the game I mi that is, x² = a.
Lemma 4.7 (Invariant functions of QRD in 2 2 symmetric PRPGs). Given 2 x 2 symmetric PRPG, 3. whose agents evolve with respect to the q-replicator dynamics, Q the separable function Vg : 10 + IR, with V (g(z, y) = (x(x) - (,)( and vy (0, R given by
22-9 + (1 xz - 1 axt-a - (1 a) x)²-9
q + 1,2,
2 2-9 q
1 q
1hg (3)) = am((2) + +11 - a) In xx)
q = 1,
(2)
In(x) + In(1 - x) + a - +
1-a
q = 2,
1-x"
remains constant along any trajectory {=(t), b(t)] 1:20 the system. The The function Vg (z(x) is continuous
with respect to the parameter 9 at, both, 9 = 1 and = 2, since lim V (z(x) = V1(x)) and
1 V ()((x) = 22( for all x E (0.
Proof Lemma 4.7 To prove the statement, we will show that the time derivative of the function V (x(t), y(t)) is equal to zero. Let begin by constructing the derivative of vxxx). For q * 2 we have that:
1
(x a) x 9 + x
(x)x)
+
x (1 - 2)
x
(1 - x) 19
(1 (1-x)²
x
x)
Similarly, for q = 1 we have that:
1 1- a
(x
x
x x)
and, for q = 2, we have that:
-
(r-a) + (1 x1
(k(x)
x
x
x²
x)²
112(1 x)2
That is the derivative of (xx) has the general form:
(x) = (x - (x==))((1 - x:) + x:9
20 z) z)
for all 2 O, where À E (1,-1). Notice, that the choice for À is purely stylistic because the invariance of function is not affected by scalar transformations. Using equation 7 from the proof of Lemma 4.5) we have that:
04 (Vg(r.V), v)
2 0V1(2. v)
( v)
dz
Öy
=V((x)² (1(()8
=>w[(x= a)(y a) (y az -a)].
To proceed with the proof Theorem 4.6
we first need to provide the formal definition of the stable and unstable manifolds of the mixed NE of w.
12, with Definition C.I (Stable and unstable manifolds of T Tw. under QRD). Let V
L (g(x,)) y) V St.Stable (z. v) (x y) for all x. y [0, 1] denote the invariant function of the q- replicator dynamics for the 2 x 2 symmetric PRPG, 1 F..3. The unstable manifold of the mixed NE (x. (a, a) under the q-replicator dynamics is the curve MUnstable := {(x,)) y) E (0, 1)2 | x
y): that is, the set of points for which lim 0o x(() lim 1(()) = a. Analogously. the stable manifold of the mixed NE is the curve Mstable == ((x, 3) E (), 1p Vg,stable (I. y) = 0): that is
the set of points for which lim z(t) lim s() a.
We are now ready prove Theorem 4.6
17

---

Published as a conference paper at ICLR 2024
To establish the claim, We will need to have at hand explicit form of the stable manifold Mistable of the mixed NE of Tw.s with respect to the O-replicator dynamics, and GD. In that regard, we now going construct that manifold. Recall that from equation
Proof of Theorem 4.6
2 the invariant function of any QRD in aa is given by Vo y) == vo(x) - ()((y) = 0, where:
Vo(z) = x² + (1 - x²² + az - (1 - a: x) = x² -2ax + a.
2
Therefore, Volz. v) = x²
2ax + a - 322 2ay - a = (x - () + - -2a) = 0 and the stable
manifold (cf. subsection 4.2)
satisfies V. Vt,Stalle = x + y 2a 0. In other words, the stable
manifold is the line segment:
Mstable= {(z, v) E (0, 1y y= 2a x)-
(10)
By equation 10 and Definition C.I. the stable and unstable manifolds of gradient descent (GD) are given by the lines y/ - 2a x and x, respectively, where w+I-3 while the stable and unstable manifolds of the standard replicator dynamics are given as solutions to:
v (z, v) = thn (x) - th (v) = a In + (1 - an
xr
where the line y corresponds solution of the previous equation, although it cannot be expressed explicitly, satisfies y S 2a x, if 2. y 2 2a xx if a < 5 (with equality in both cases only if x oi), and y 20 x otherwise; naturally.
solution. We are going to prove that the single remaining
hence, the statements of Theorem
is not difficult to show that (x)) = =[1-x] (ef. proof Lemma 4.7 and w (a) = x² 22z
-(1-2)²
0. Therefore, 1 is a strictly concave function with maximum at x:
To proceed, it will be useful to define the implicit function y: (0, 1) + (0, 1) such that y(a) - a, and Va E (0, 1) \ {a}: wi (zx. By applying the Intermediate Value Theorem (IVT) on 1 in the intervals (0, a). and (a, 1), we can verify that y is well well-defined bijective function. Note that y = y(x) has correspond to the remaining solution of 1 y).
((x) A a, and t (v(x))
Without any loss of the generality, let us consider the case of a > 3.2 Since vif is strictly decreasing in (0, 1) (el" < O), we have that 1 (x) > for all x E a)), and (x) < for all x E (a, 1). We begin by proving that for all x E (0, a) it holds that [a - x) < (8 + x)), i.e.,
(/((a - x) < < (ax + x). Specifically, we have the following series of equivalences:
Vi(a - x) < - (a + x)
(a-
(a - (1
Since a > 1/2 and x E - a, the latter is equivalent to 2x (1 - 2a) < 0 or equivalently to > 1/2 which holds by assumption. Next, by taking advantage of the above, we can prove that, for all x: E (0, 1 - at. it holds wh (a - x) > v (a + æ)); that is:
S (a - x) /
(i dt = L. dt)
/ -V((t) dt
Ja-s
(1)))
d1 = 1h + x:)
Let us, now, consider some There are three possibilities: 1. < 2a 1; 2. x E (2a - a,; and
x 2 a. If S 2a - 1, then, since y(x) E (0, 1), it follows, trivially, that x + y(x) < 20.
Then, since ti is strictly convex, we have that t/ (xx) (a - 8) > wi (ax). Consequently, by the Intermediate Value Theorem, there must exist some y" (ax, 08) such that vi1 (a- 8) t21 (v*). Clearly 0-5 / y², and, therefore, since 1/1 (a- (y("). ). it must be the case that y(z) = y". Furthermore, x = a 8+y < a = 2a, and, therefore, our claim holds in that case well.
I E (2a a), let us set 6 =
Finally, if x 2 a, let us set = x a. Since a > 0.5, we have that ō E (0, 1 - a), and therefore, dh 5) < 1/1 (a++)) 8) = 1/1 (z)). Furthermore, by the monotonicity of 1/1 in the intervals (a 8, (a, and (Ir, 1), we also have, respectively, that
(v) < ( - 5) (x) for all y a) ()( < (x)
(11)
for all y E (a, x) for all y E (z, 1).
(12)
th t/1 (x)
(13)
18

---

Published as a conference paper at ICLR 2024
In other words, it has to be the case that y(x)) a0,a-6), 6). and, therefore, x y(x) < <atdta-ō= 2a.
It follows that, if a 0.5, y(x) < 2a x. We remark that the case of < / follows identical arguments, while the case = 1 is trivial.
Remark C.2 (Technical intuition of Theorem 4.6). It is important to provide the mathematical (technical) interpretation of Theorem 4.6) From equation [RD] we observe that the speed of the projection dynamics, (g 0). does not depend on the current state, since the x term is eliminated from the right hand side. As a result, the separatrix is a straight line, see e.g., panel I in Figure I As q increases for values berween 0 and 1 for which our analysis applies, the dynamics leave the boundary must faster, cf. panels 2 to 4 in Figure I] while being fixed between the three points, i.e. the corners (0, 1), (1, 0) and the mixed NE. This implies a certain curvature for the separatrix. On the other hand, the center of the simplex, i.e., the (0.5, 0.5) point, belongs to the region of altraction of the disiintm equilibrium under all dynamics. Combining these two, we get that the replicator dynamics create convex separatrix when risk- and payoff- dreef-domnnntt equilibria differ, and concave separatrix when risk- and payoff-dominant do-minantn equilibria coincide, cf. Appendix D This provides the picture that we have, with the straight- line separatrix of the gradient descent (projection) dynamics being below the curved separatrix of the replicator when risk- and dominatt equilibria differ and above when risk- and sayoff-dominan equilibria coincide. The above explanation drives our current proef of [heorem 4.6 Deriving a game-theoretic interpretation (along with the technicul one above) is interesting open question.
Finally, a direct (technical) implication from the proof of Theorem 4.6 is provided in Lemma C.3
which may be of independent interest. Recall from the proof of Theorem 4.6 that the solutions to V (ar, y) = O are the functions y = x and y (0. 1) + (0,1) such that y(a) = a, and for all E (0,1) \ {a} holds that y(х) # a, and tt (y(x)) (z)).
Lemma C.3 (Curvature of the stable manifold of RD). Consider the 1-replicator dynumics (RD) in the parametric game T w. The stable manifold, Mstable of RD in Tw. is given by the curve y -(x). If the payoff-dominan equilibrium, = y = O. is also risk-dominant, then is strictly concave. Conversely, if the non-payof dominant equilibrium, x = y = 1, is risk-dominant, then is strictly convex. Otherwise, y(z)
Proof of Lemma C.3 By differentiating both sides of the implicit function U (1(())) = t/1 (1) with (x)
respect to x, we get that (y(x)))) bijective, 16 is monotonic (V3 < 0), and 4i (v(a)) (a)) = O, the above equality is well-defined for all x E (0, 1) {a). Hence, we have that:
(z), i... (=) কল(া) Notice that, since y is
v" 4 Hb (v))² (M))"
(x) (+))))))))))
(1(
(4)
02 - v) aa - a) y) + x- 20r) (a y) 22 (1-1) x) y)
where the dependency of y to is implied for compactness. Hence, we have that (x(x) < 0 if and (w-w)(g+=-2a) < 0. However, by the Intermediate Value Theorem (IVT) applied on ti in (0, a), and (a. and the definition of y, it follows, trivially, that x S y if, and only if, a S y.
only if
a-y
s-y > O, Vx E (0, \ fa); hence with equality in both inequalities only if r = a. Therefore, a
(²(x== < if, and only if, y 2a < 0, which by the proof of Theorem 4.6 is equivalent to > }. This concludes the proof for the first statement. The second statement follows in a similar manner by requesting v" vxx) O, while the last statement is trivial.
3 be a 2 x symmetric PRPG, where the payoff-dominant equilibrium, x = y = O, is also risk-dominant, i.e., 3 > 1 - w. or equivalently a >> 0.5, where x² = =y" = a is the mixed NE of I a. Recall that, by equation 10 the stable manifold of the mixed NE of I ww, with respect to GD is the line segment
Proof of Theorem 4.8
y = 2a x, for x E (max 2a - 1}. min 1}}. Since a > 0.5, we have that 2a 1 0 and 2a 1: therefore, the extreme points of E are (0, 2a. and (2a, 0). That implies the the RoA of (1, 1) is the triangle with extreme points at (1, 1).
(2a 1, 1), and (1, 2a 1). Since that is right triangle, with both its base and its height equal
19

---

Published as a conference paper at ICLR 2024
04
140
02
32-
Figure The stable manifolds, M St,Stable 4) = 0, (solid blue lines) for the same values of q and the same instance of I' w.,s as in Figure I] in which the payoff- and risk- dominant NE is at the bottom left corner. For all 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 of attraction of the payoff-dominant NE larger for all values of q; however, this is because this NE is also iik-dominant, cf. Theorem 4.6
0 (dashed blue linc). The region
to 2(1 - a), the Lebesque measure of (oA(0,0) is (()oA(1,1) = 2(1 a) subsequently, y (RRA((0))) )) =1 (R = 2(1 a)). We may calculate the APoA of GD ww,8 as function of w and B. Specifically, when > 0.5, i.e., 3 < - we have that:
APoA(w, B) = APDAAGD,TTw... max ME(O, SW
APMsw.jo.up 10.112 (GD, Tw,e)
SW(O,0) 0)
SW(0,0) 0) ((((0)0))<R(o((((( (ROA(0 0)) + SW(1, (RoA(1, 1))
W
wy)(RoA(O,0) 0)) + (ROA(1)1))
w(w + 1 .32
W
w|1 w-1-200 2(1 0
2(1 a)²
w(w - -3
where we used that a 1- that is, for all w, we have that:
1++1- We may, now, perform first-order analysis in APoA B);
1-8
0 @APoA(w,
Aw 4w (w 1) 1- 3)
wwo + 3)2 2(w 1)(1 B) S 0.
03
From the above, it follows that APoA(w, 3) S. APPA (w: 1 w): that is:
3w
2w W w 2,
APoA(w, 3) 4w 2(w 1)w2
where the last inequality follows by letting w + oc. Notice that this bound is tight. It is not difficult see that if a < 0.5, APoA(w, 3) is unbounded.
D VISUALIZATIONS: INVARIANT FUNCTIONS AND SEPARATING MANIFOLDS
In this part, provide systematic, and essentially exhaustive, visualizations of the stable manifolds (separatrices) in the Tm, class.
Same payoff- and risk-dominant NE in I w..B. As mentioned the main part, the separatrix for different values of can be obtained by plotting the 0-level set of the invariant functions in Figure These are depicted in Figure As a sanity check, we also see from Figure that the region of attraction of the payoff- dominant equilibrium for q = 0 (GD dynamics) is larger than the region of attraction for a = (RD).
we next depict the separatrices, stacked for all values of E [0, 10), for different parameterizations of the Tw.9 class (Figure 6 In all panels of Figure 6) parameter is equal to 2. We obtain qualitatively equivalent plots for any w > and 3 small enough. The main takeaways from the (essentially exhaustive) visualizations in the panels of Figure 6 are that (i) the region of attraction of the risk-dominant equilibrium is
Stable manifolds for all > 0. In similar vein to Figure 2
20

---

Published as a conference paper at ICLR 2024
3.2
4.0
233
34
64-
Sialle eusifal Pua
6.3
Suilk naseiael Tix
Statee menisat In For
0.3
Stucko resetised to Se g. 5.20,
Statde mantfal Dut
for 8.22, d
400
96
14
33
32
6.2
12
31
63
21
Figure 6: Stable manifolds (separatrices) for all different values of E [0, 10] (from blue to brown) in different parameterizations of the T game for 2 and varying 3. In all panels. the manifolds for q 0. and q = are shown shades black for reference. The region attraction the payoff-dominant equilibrium (bottom-let corner) shrinks as q increases when this equilibrium is also risk-dominant (a > 0.5) and increases with when this equilibrium is not risk-dominant (o < 0.5). In fact, as / decreases, the payoff-domine becomes increasingly more "risky" and its region of attraction becomes arbitrarily small.
larger for all q 2 O regardless of whether this equilibrium is payoff-domine or not, (ii) the region of attraction of the payoff-dominant equilibrium may become arbitrarily small as this equilibrium becomes arbitrarily risky. In particular, observation (ii) suggests that in this case, it is hopeless to bound any static or average performance measure. This became more transparent with the APoA analysis in the previous Section of the Appendix (cf. Theorem 4.8 in the main paper). We conclude
this part with some visualizations of the stable and unstable manifolds in 2 x 2 non-symmetric
PRPG.
Consider the identical-interest PRPG, ID with identical payoff func- tions Uw, (51, 82) = U., 82) = Aw.B,as..2 where the payoff matrix Amr,8 E R2x2 is given 1
non-symmetric PRPGs.
3 < S w. The game ID a has the same pure NE as the games T namely x =y=00 O, with payoff w, and = y 1, with payoffs 1 for both players, but now the mixed NE is not symmetric and it is given by x = (w (w + 1 3) and y² = w/(w + +1- 3).
by Aw,3 = 8
In Figure 7 we visualize the stable and unstable manifolds for all values of E [0, 10) in an instance of If with w and 3 = -2. In this case, the separating (stable) manifolds do not increase (decrease) monotonically with q as it is evident from the overlapping (equally) colored regions. Thus, it requires a different approach to estimate whether the size of the regions of attraction of the payoff-dominant equilibrium follow certain monotonicity pattern, which again may change depending on whether this equilibrium is also risk-dominant or not. In the context of the current paper, Figure highhlgghts that (i) the geometry of the regions of attraction is highly complex under different algorithms (parametrizations of QRD) even for low-dimensional, identical interest games, and (ii) given this complexity, the findings in the class r ww become even more surprising and intriguing.
Different payoff- and risk-dominant NE in I w.. The main differences in the class I occur between games in which the payoff- and dominant equilibria coincide and games in which they differ. Recall that Figure I shows the invariant function in r w.s instance, where = 2 and B 0.
21

---

Published as a conference paper at ICLR 2024
20
Figure 8: The invariant function, Vo (x, y). for all 2, E [0, 1J2 in the game Tw.e for w 2. 3 4. and the same values of as in Figure = 0 (gradient descent dynamies),
(standard replicator dynamics), q = bog-barrier dynamics), and 20. The invariant function again becomes very steep the boundary as g increases, taking both arbitrarily large negative (dark) and positive (light) values in the vicinity of the NE.
2
20
2.4
04-
3.4
04
02
same values of q and instance of I a as in Figure 8) in which the payoff-dominant NE is at the bottom-left corner and the risk-dominant NE is at the upper-right corner. For all 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-dominant NE is now smaller for all q. because this NE not risk-dominant, cf. Theorem 4.6
Figure The stable manifolds, W StaSta y) 0, (solid blue lines)
i... in which the payoff- and risk- dominant equilibria coincide, Figure 8 we provide an instance in which the payoff- and risk-dominant equilibria differ. Similar to FoFFiuue 5 Figure 9 depicts the separating manifolds (stable manifolds or separatrices) of the regions of attractions of the two pure NE. These are precisely the zero-level sets of the invariant functions shown in Figure As we can see, this case, the region of attraction of the payoff-dominant equilibrium, w is smaller than the region of the, now, risk-dominant equilibrium, 1. Intuitively, when NE becomes risk-dominated, its region of attraction shrinks, even if this NE is payoff-dominant. This is because, for mixed choice of distributions, the risk-dominant NE yields higher utility and is that more "attractive" for the dynamics. This trade-off between high reward at certain state (e.g., w, w) and high risk if that state is not reached (e.g., 3, O, with 0), also explains why socially optimal, but otherwise risky, outcomes, e.g., the adoption of revolutionizing technology or social norm that challenges the status quo, are never reached real-life situations.
On risk-dominane in higher dimensions In diagonal games (D-PRPGs), it is straightforward to make an equilibrium more risky. This is achieved simply by replacing the zero entries in the corresponding line of matrix U by some negative number, e.g..
u1
0
0
02
0
Urisky.m
= diag(u (1, U2, Mm;; risk, -10)
10
10
Um
In this case, the puyoff-domines equilibrium with payoff um. each player becomes more risky, since failure to coordinate on it results to negative payoff of -10 for the agent who selected the corresponding action. Proceeding in a similar fashion, one may replace the zero entries with an (arbitrarily large) negative element in all lines of the matrix except for the first one. In analogy to the Uisky. notation, we will denote such games by Uniky = diag u1 ......, Um risk -r), where > is the risk constant (equal to -10 in the example above). In this way, all equilibria become more risky except for the payoff-dominated one, i.e., the equilibrium with payoffs u, to each agent which corresponds to the action profile in which every agent selects their first action Concerning
An alternative interesting approach to generalize the notion of risk-dominance in arbitrary games is via pairwise comparisons of actions proposed by Honda (002).
22

---

Published as a conference paper at ICLR 2024
experiments, the outcome of Figure 4 is reversed in games of the form Urisk i... in games in which the payoff superior equilibria were more risky (not reported here).
e-Replicater
manitods
0.9
0.7
4.5
Unstable mantfolds
0.3
0.1
Figure 7: Stable and unstable manifolds for all [0, 10j in an instance
identical interest game IDu.s with w and [ = -2 The unique mixed NE is not symmetric and lies at x = 0.8, y" = 0.4. The main difference with the symmetric games in I wa that the regions of attraction of the payoff-dominant equilibrium (bottom-left corner) are not increasing (nor decreasing) in anymore.
23


Reviews:
[{"review_id": "R7UbfC64jj", "reviewer": "Reviewer_xUnV", "summary": "A long line of work in algorithmic game theory has sought to bound the difference between selfish outcomes and socially optimal outcomes. However, these ``Price of Anarchy\" (PoA) bounds hold in a worst-case sense, and need not faithfully represent the real-world performance of concrete dynamics. This work considers the average-case PoA (APoA) of a large family of dynamics, namely Q-Replicator dynamics, in potential games. The main contributions of this work are threefold: first, it is shown that almost all potential games are such that Q-replicator dynamics initialized on any interior point converges to a (finite set of) Nash equilibrium. In particular, this makes average-case notions of PoA almost always well-defined. In the case of 2x2 games, this paper provides a complete characterization of the regions of attraction for different equilibria. The main applications are to exactly characterize in which 2x2 games gradient descent dynamics has a better APoA than replicator dynamics, and moreover, bound the APoA of gradient descent when the payoff- and risk-dominant Nash equilibria coincide. Finally, preliminary empirical evidence is given to suggest that certain generalizations of the results are possible.", "questions": "Recommendation: While I only have a passing familiarity with this line of work, my general impression is that work has very interesting conceptual takeaways. While there is some concern about how general these findings are and the extent to which they might generalize, my current belief is that this work makes interesting progress on the quality of important learning outcomes that would be of interest to the community. For now, I am leaving my score as a 6, but I could increase it in light of other reviewer comments/discussion of the technical novelty compared to Panageas and Piliouras [EC'16].\n\nComments:\n\n---The conceptual goal of providing more refined PoA guarantees for concrete dynamics is a very interesting direction that deserves further study, in my opinion. \n\n---While this work does give good discussion on how the current paper extends the original results of Panageas and Piliouras, it may be worth providing a short discussion on the technical differences that allow these extensions. This would also help convince the reader of the novelty of these results.\n\n---As mentioned above, the main weakness is that the concrete theoretical results on APoA are localized to 2x2 games. It isn't entirely clear what an appropriate generalization would look like with more agents and larger action spaces, and of course, one imagines that the technical analysis quickly becomes intractable. But progress on these questions has to start somewhere and my current impression is that this paper indeed takes steps towards these aims that would be of value to the community.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The conceptual questions addressed by this work are quite interesting. On a technical level, the analysis provides a nontrivial extension of existing work on the performance of these dynamics. The paper is itself quite well-written and the results are supplemented with empirical evaluations that validate the results and suggest intriguing future directions.", "weaknesses": "The theoretical results, while very nontrivial, currently only hold for 2x2 games, and it is not clear conceptually or technically what an appropriate generalization would be. The paper could benefit from a bit more discussion about the technical differences with prior work (i.e. that of Panageas and Piliouras [EC'16]).", "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": "", "extra_scores": {}}, {"review_id": "PYdg7hZzBO", "reviewer": "Reviewer_ycpS", "summary": "This paper studies the convergence properties of q-replicator dynamics in continuous-time potential games. Potential games are a special class of general-sum games in which player utilities can be represented by a potential function. q-replicator dynamics are a class of learning dynamics which take a hyperparameter $q$ as input. If $q=0$ gradient descent is recovered, if $q=1$ replicator dynamics are recovered, and if $q=2$ log-barrier dynamics are recovered. The authors show that q-replicator dynamics converge pointwise to Nash equilibria in a subclass of potential games called Perfectly-Regular Potential Games (PRPGs), which capture almost all finite potential games. \n\nHaving established this result, the authors are interested in analyzing which equilibria are converged to when all players in a game employ q-replicator dynamics. Their main metric of performance is the average price of anarchy (APoA), which measures the price of anarchy, on average, with respect to a uniformly random initialization of the q-replicator dynamics. The authors' main theoretical contributions come in the setting of 2-by-2 PRPGs. In particular, they find that the APoA of running gradient descent is higher than the APoA of running replicator dynamics in 2-by-2 PRPGs if and only if the payoff-dominant equilibrium is also risk-dominant. Here, the \"payoff-dominant\" equilibrium refers to the equilibrium with the highest utility, and an equilibrium is \"risk-dominant\" if it is unilaterally optimal against the uniform distribution of the rest of the agents. \n\nThe authors compliment their theoretical results in 2-by-2 PRPGs with numerical simulations in higher dimensions. They find that, in line with their theoretical results in 2-by-2 games, gradient descent outperforms the replicator dynamics in all diagonal games (i.e. games in which the only non-zero elements of the payoff matrix are along the diagonal). Throughout the submission, the authors provide proof sketches and intuition for their results.", "questions": "Why focus on metrics which measure performance with respect to random initialization instead of other methods of initialization, e.g. initializing to the uniform distribution over actions as is canonical in the literature on learning in games?\n\nDo you have any insights on how your results would carry over to the discrete-time setting?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem of analyzing the convergence guarantees of learning algorithms in games is not a novel problem, but is of great interest to the game theory community. Additionally, obtaining results in this area has traditionally been challenging. While the authors restrict themselves to a subclass of two-by-two potential games, the authors' results are novel and their analysis helps shed some light on this important issue by comparing the convergence properties of gradient descent and replicator dynamics, two canonical algorithms for learning in games. I found the paper to be well-written, and I appreciated the authors' efforts to provide intuition for their results and why they cannot be easily extended beyond the two-by-two setting they consider. The numerical simulations in settings beyond two-by-two games are also a strength, as they help shed light on this problem in a more general setting, despite the issues with extending the authors' theoretical results.", "weaknesses": "One weakness is the restriction to the setting of 2-by-2 Perfectly-Regular Potential Games. However given the challenge of analyzing the convergence dynamics of learning algorithms in games, this is not a large weakness.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)