Characterizing the Convergence of Game Dynamics via Potentialness
Authors: Martin Bichler
Davide Legacci
Panayotis Mertikopoulos
Matthias Oberlechner
Bary Pradelski
Venue: Accepted by TMLR ()

Abstract: Understanding the convergence landscape of multi-agent learning is a fundamental problem of great practical relevance in many applications of artificial intelligence and machine learning.
  While it is known that learning dynamics converge to Nash equilibrium in potential games, the behavior of dynamics in many important classes of games that do not admit a potential is poorly understood.
 To measure how ``close'' a game is to being potential, we consider a distance function, that we call ``potentialness'', and which relies on a strategic decomposition of games introduced by Candogan et al. (2011).
  We introduce a numerical framework enabling the computation of this metric, which we use to calculate the degree of ``potentialness'' in generic matrix games, as well as (non-generic)  games that are important in economic applications, namely auctions and contests. Understanding learning in the latter games has become increasingly important due to the wide-spread automation of bidding and pricing with no-regret learning algorithms. 
  We empirically show that potentialness decreases and concentrates with an increasing number of agents or actions;
  in addition, potentialness turns out to be a good predictor for the existence of pure Nash equilibria and the convergence of no-regret learning algorithms in matrix games.
  In particular, we observe that potentialness is very low for complete-information models of the all-pay auction where no pure Nash equilibrium exists, and much higher for Tullock contests, first-, and second-price auctions, explaining the success of learning in the latter. In the incomplete-information version of the all-pay auction, a pure Bayes-Nash equilibrium exists and it can be learned with gradient-based algorithms. Potentialness nicely characterizes these differences to the complete-information version.

Published in Transactions on Machine Learning Research (03/2025)
Characterizing the Convergence of Game Dynamics via Po- tentialness
Martin Bichler
m. m.bichler@tum.de
Deportment of Computer Science, Technical University of Munich
Davide Legacci
Unio. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG
Panayotis Mertikopoulos
manopptt.mmrttioopoloooiiii
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG
Matthias Oberlechner
matthias hatriiias.bbeeeccneerttttt..mm
Department of Computer Science, Technical University of Munich
Bary Pradelski
bary. harg.pradelski@enny
Maison Frangnise d'Oxford, CNRS
Reviewed on OpenReview: /ttp::///penrevviee net/ forum? id- Is9APAP94V
Abstract
Understanding the convergence landscape of multi-agent learning is fundamental problem of great practical relevance in many applications of artificial intelligence and machine learn- ing. While is known that learning dynamics converge to Nash equilibrium in potential games, the behavior dynamics many important classes of games that do not admit potential poorly understood. To measure how "close" a game to being potential, we consider a distance function, that we call "potentialness", and which relies on strategic decomposition of games introduced by Candogan et al. (2011). We introduce numerical framework enabling the computation of this metric, which we use to calculate the degree of "potentialness" in generic matrix games, as well as (non-generic) games that are important in economic applications, namely auctions and contests. Understanding learning in the lat- ter games has become increasingly important due to the wide-spread automation of bidding and pricing with no-regret learning algorithms. We empirically show that potentialness decreases and concentrates with an increasing number of agents or actions; in addition, po- tentialness turns out to be good predictor for the existence of pure Nash equilibria and the observe that
convergence of no-regret learning algorithms in matrix games. In particular, models of the all-pay auction where no
potentialness is very low for complete-informatte pure Nash equilibrium exists, and much higher for Tullock contests, first-, and second-price auctions, explaining the success of learning in the latter. In the incomplete-informan version of the all-pay auction, a pure Bayos-Nash equilibrium exists and can be learned with gradient- algorithms. Potentialness nicoly characterizes these differences the complete-informattin version.

---

Published in Transactions on Machine Learning Research (03/2025)
1 Introduction
Multi-agent systems and multi-agent learning have drawn considerable attention, owing to their massive deployment in machine learning enabled applications and their increasing economic impact, with agents automatically ordering goods, setting prices, or bidding in auctions (Yang & Wang 2020). In contrast to other applications of machine learning, the input in multi-agent learning is non-stationary and depends on the strategic behavior and learning of other agents, which leads to challenging computation and learning problems that go well beyond the "business as usual" framework of empirical risk minimization.
The literature on learning in games has a long history and asks what type of equilibrium behavior (if any) may arise in the long run of process of learning and adaptation, in which agents are trying to (myopically) maximize their payoll while adapting to the actions of other agents through repeated interactions (Fudenberg) & Levine 1998 Hart & Mas-Colell 2003). To that end, many learning algorithms have been developed ranging from iterative best-response to first-order online optimization algorithms in which agents follow their utility gradient in each step MMetiikppollos & Zhou 2019 Bichler et al. 2023
It is known that the dynamics of learning agents do not always converge to a Nash equilibrium (NE) (Daskalakis et al., 2010 Flokas al.] 2020); they may cycle, diverge, or be chaotic, even in zero-sum games, where computing Nash equilibria is tractable (Mertikopoulos et al. 2018 Palaiopanos et al. 2017). In fact, HHart& & Mas- Colell 2003) showed that in general uncoupled dynamics do not converge to Nash equilibrium in all games. With this negative result at hand, there lacks a comprehensive characterization of games that are "learnable"; however our understanding is much better for certain classes of games.
On the one hand, no-regret algorithms and dynamics do not converge in games with only mixed Nash equilibria (Flokas et al. 2020 Giannou et al. 2021a). On the other hand, if the underlying game is an exact potential game, then no-regret and oth learning algorithms converge to s-NE with minimal exploration (Heliou et al. 2017 Mertikopoulos et al. 20224). Importantly, even though many classes of games of interest are not exact potential games (Candogan et al.
2013a]b) b), experimental evidence shows that even if games are not exact potential games, learning dynamics oflen converge to Nash equilibrium. Beyond exact potential games there is no good understanding of the behavior of learning dynamics.
Partially motivated by this, Candogan et al.] (2011) introduced a game decomposition that allows one to characterize how "close" a game is to being potential by resolving it into a potential and a harmonic com- ponent (plus a "non-strategie" part which does not affect the game's equilibrium structure and unilateral payoff differences). In contrast to potential games, the exponential weight / replicator dynamics perhaps the most widely studied no-regret dynamics- - does not converge in any harmonic game, and instead exhibit a quasi-periodic behavior known as Poincaré recurrence (Legacci et al. 2024). Based on this dynamical di- chotomy between potential and harmonic games, we consider a mcasure of potentialness and analyze generic normal-form games, as well as several classes of games steming in economic applications. We show that potentialness provides a useful indicator for both the existence of pure Nash equilibria and the convergence of no-regret algorithms. While the latter was already part of the motivation of Candogan et al. (2013a) the former is novel connection emerging from our empirical exploration. In particular, we find that the average potentialness in random games decreases and concentrates on a value with increasing numbers of agents or actions: Games with a potentialness below 0.4 rarely exhibit convergence, while games with val- ues larger than 0.6 mostly do. We also categorize specific games, such as Jordan's matching pennies game (Jordan 1993 where learning dynamics are known not to converge (or, more precisely, to converge to a non-terminating cycle of best responscs).
Economically motivated games such as auctions and contests have more structure in the payoffs. The analysis of these games is relevant today because pricing and bidding are increasingly being automated via learning agents. Learning agents are used to bid in display ad auctions, but they are also used by automated agents that set prices on online platforms such as Amazon (Chen el al. 2016). Whether we can expect the dynamics of such multi-agent interactions to converge to an equilibrium or exhibit inefficient price cycles or even chaos, is an cconomically important question. We find that the potentialness is very low for all-pay auctions and much higher for Tullock contests, first- and second-price auctions. Indeed, our experiments show that learning algorithms do not converge for all-pay auctions, but they do so for the other economic
2

---

Published in Transactions on Machine Learning Research (03/2025)
games. The low potentialness of the all-pay auction also connects to the fact that it does not possess a pure
Nash equilibrium.
In summary, we use the decompasition of Candogan et al. (2011) to define a metric that helps us characterize whether a game is learnable under standard no-regret learning dynamics, and to what extent. This is in stark contrast to brute-force approach, where different initial conditions need to be explored. Our analysis of economic games motivated by the observation that first-order no-regret dynamics- such the replicator dynamics in particular appear to converge in wide array of classes of games with important applications, such as auctions and contests. Known sufficient conditions for convergence such as monotonicity or variational stability (Mertikopoulos & Zhou, 2019) are not even satisfied in simple economic games such as the first-price auction (Bichler et al. 2025). However, the notion of potentialness provides a crisp characterization of these differences as it does in simple normal-form games such as Matching Pennies and the Prisonner's Dilemma. Overall, potentialness provides us with a mcans to characterize convergence in the many games where known sufficient conditions appear to be too strong. This can help us analyze algorithmic markets where learning algorithms are increasingly used to submit bids or set prices (Bichler et. al. 2024).
2 Related Literature
In this paper, we focus throughout on repeated normal-form games, where players move simultancously and receive the payolls as specified by the combination of actions played. The theory of learning in games examines what kind of equilibrium arises as a consequence of a process of learning and adaptation, in which agents are trying to maximize their payoff while learning about the actions of other agents in repeated games (Fudenberg & Levine 1998). For example, fictitious play is a natural method by which agents iteratively search for a pure Nash equilibrium (NE) and play a best response to the empirical frequency of play of other players (Brown 1951). Several algorithms have been proposed based on best or better response dynamics for finite and simultancous move games, ultimately lcading to a vast corpus of literature (Abreu & Rubinstein
1988 Hart& & MaseC 2000; Fudenberg & Levine 1998 Hart & Mas-Colel] 2003: Young 2004), while
more recent contributions draw on first-order online optimization methods such as online gradient descent
or online mirror descent to study the question of convergence (Mertikopoulos & Zhou 2019:
Bichler et al.
2023
Learning dynamics do not always converge to equilibrium (Daskalakis et al. 2010 Flokas et al., 2020 Learning algorithms can cycle, diverge, be chaotic; even in zero-sum games, where the NE is tractable [Mertikopoulos et al. 2018 Palaiopanos et al.; 2017). Sanders et al. (2018) argues that chaos is typical behavior for more general matrix games, Recent results have shown that learning dynamics do not converge in games with mixed Nash equilibria (Giannou et al. 2021abb On the positive side, Mertikopoulos & Zhou (2019) showed conditions for which no-external--egree learning algorithms result in a NE finite games if they converge. However, in general, the dynamics of matrix games can be arbitrarily complex and hard to characterize (Andrade et al. 2021).
While there is no comprehensive characterization of games that are "learnable" and one cannot expect that uncoupled dynamics lead to NE in all games (Hart & Mas- Colell 2003), there are some important results regarding the broad class of no-regret learning algorithms. One can distinguish between internal (or conditional) regret and a weaker version, called 'external (or unconditional) regret'. External regret compares the performance of an algorithm to the best single action in retrospect; internal regret, on the other hand, allows one to modify the online action sequence by changing every occurrence of given action by alternative action. For learning rules that satisfy the stronger no-internal regret condition, the empirical frequency of play converges to the game's set of correlated equilibria (Foster& & Vohra 1997 Hart & Mas- Colell 2000). The set of correlated equilibria (CE) is a non-cmpty, convex polytope that contains the convex hull of the game's Nash equilibria. The coordination in CE can be implicit via the history of play (Foster) & Vohra 1997). On the other hand, algorithms that are no-external-regret learners converge by definition to the set of coarse correlated equilibria (CCE) in finite games (Foster & Vohral 1997 Hart & 2000). This set, in turn, contains the set of CE such that we get NE C CE C CCE. In contrast to correlated equilibria, in a coarse correlated equilibrium, every player could be playing a strictly dominated strategy
3

---

Published in Transactions on Machine Learning Research (03/2025)
for all time (Viossat & Zapechehnyuk 2013). which makes CCE fairly weak, non-rationalizable solution concept.
An important class of games in which a variety of learning algorithms converge to NE is that of potential games (onnerer & Shapley 1996). In these games, the difference any player's utility under a change in strategy captured by the variation of global potential function; as a consequence, any sequence of pure NE (Heliou al. 2017 Christodoulou et al., 2012 Anagnostides et al. 2022). Remarkably, the class of congestion games is equivalent to that of potential games (Rosenthal,
improvements by players converges
1973 Monderer & Shapley 1996); however, while many games are not potential games, no-regret algorithms
still converge to NE, raising the following question: what fundamental property enables this convergence!
Partially motivated by this question, Candogan et al. (2011) propose a decomposition of finite normal form games into three components, with distinctive strategical properties. This decomposition can be leveraged to approximate a given game with a potential game, which in turn can be used to characterize the long-tow torg-term behavior of the dynamics in the original game (Candogan et al., 2013a bb. In particular, Candogan el al. (2013a) examine the convergence of best-response and legit-best-resoonse dynamics in the sense of Blum & Kalai 1999) and they show that, if only one player updates per turn, the dynamics remain convergent
in slight perturbations of potential games]
An important caveat is that the class of dynamics considered by Candogan et al. 2013a can result in positive regret. Moreover, unlike the setting studied here, players do not move simultaneously but sequentially, Our focus is broader, as we aim to understand the behavior of no-regret dynamics across the full spectrum of potentialness not just in near-potential games and to determine where the convergence of regularized no- regret learning methods fails. In doing so, also provide first positive answer to the open question posed by Candogan et al. (2013a), who asked whether the replicator petiicatoo/follo-lllie gellow-the-regullriiiee-eeee staple among no-regret learning schemes, remains convergent under small perturbations of potential games.
dynamics,
3 Preliminaries
In this section, we recall the definitions of normal-form game, Nash equilibrium, and potential game. Definition 1 (Normal-form game). A finite normal-form game consists of tuple G = (N, u), where
N is a finite set of N players, indered by i;
A A x ... x AN, where A is fimile set of A, actions available to player i;
(n ........ uN), where u; : A R is a payoff or utility function for player i E N.
An element (a (ai.....aN) aN) E A is referred to as an action profile; we denote by A -II: AI the total number thereof.
A normal-form game is hence fully specified by the prescription of the strategies available each player, and of the outcomes resulting from simultancous and strategic interaction.
Rather than explicitly selecting an action also called pure strategy from the available options, players may instead mír, meaning they randomize over their available actions according to a probability distribution, referred to as a mixed stralegy.
Definition 2 (Mixed strategy). Given the normal-form game G = AN.A,u) u), the set of mixed strategies for player is S, = ((A)), the set of probability distributions (or lotteries) over A An element s E is called strategy profile.
A Nash equilibrium is a strategy profile such that no player has an incentive to unilaterally deviate from their chosen strategy:
IImportatlly, the dynamics cousidered by Candogan all (2013a) not the simultancous best-reply dynamics of Cilboa & Matsui (199]) or the logit dynamics Fudenberg & Levine (1999): (ofbauuer Sandholm (2009) but rather turn-by-tum updates where each player abserves the play of their opponents and plays (logit) best-response.
4

---

Published in Transactions on Machine Learning Research (03/2025)
Definition 3 (Nash equilibrium). In a normal-form game G (W.A, u), strategy profile s* ................................ .88) E 81 x.... x SN is a Nash equilibrium if
(f1,8))....88
us (s s-,) 2 6",)) for all i EWW, 81 E S,
(1)
where s-1 = -8i 82: .2:.....
N.
A potential game is a game in which strategic interactions are fully captured by single a scalar function, aligning individual players' incentives with its maximization:
Definition 4 (Potential game). A game G = (N,A, u) is a called potential if there erists a function Φ: A R such that, for every player i E N and every pair of action profiles a, a' E A that differ only in the action of player i (that is, a; + dl and a_i = a-i= =d=s), the following condition holds:
ua(a) - =u((a) = o(a) -(a').
(2)
When this is the case, o is called potential function of the game.
4 Potentialness of a game
In this section we provide an overview of a combinatorial decomposition technique for finite games in normal form, originally introduced by Candogan et al. (2011). Subsequently, we leverage such decomposition to define the potentialness of game, measure of its closeness to being a potential game. This measure, closely related to the mazimum pairwise difference introduced by Candogan et al. (2013a), can be used as a prodictor for the existence of strict pure Nash-equilibria (SPNE) in a game, and of the limiting behavior of learning dynamics thereof.
Deviation map Given a finite game in normal form G= (N,,,)), pairs of strategy profiles (a, that differ only in the strategy of one player are called unilateral deviations, and their space is denoted by E. Representing a game in terms of utility differences between unilateral deviations rather than in terms of utilities themselves captures the strategic structure of game in an effective way, in the sense that games with different utilities but identical utility differences between unilateral deviations share the same set of Nash equilibria Candogan et al. (201))
To achieve this representation of the game G= (N,A, consider ils response gruph I(N, A), that is the graph with node for each of the A pure strategy profile in A, and an edge for each of the E = [8| = A EEEN(A, - unilatcral deviations in & (Biggar & Shames 2023
2
This graph is an instance of simplicial complex: K, that is, loosely speaking, a collection of oriented dimensional faces (points, segments, triangles, tetrahedrons, ...) with &t E {0,1....} [Jonsson] 2007). Given simplicial complex K one can build family of vector spaces {Ck}k=o,1,... called chain groups, where each chain group Cg is the space spanned by the k-dimensional faces of the complex K, i.e., the space of assignments of a real number to each k-dimensional face of the complex (Munkres 1984).
In this work, we restrict our attention to the chain groups Co and C₁ on the response graph T(W, A) of a game. Co A the space of assignments of a real number to each vertex a E A, and C₁ _ R is the space of assignments of a real number to each edge (a,a') E E; an element in C1 is called flow on the graph.
Note that the potential function Φ A + R of potential game is precisely an assigument of number to each pure strategy profile a E A: as such, it is an element of Co. In a similar way, observe that the collection of utility functions u = (ut)iEN: A + R is the assignment of a number u;(a) E IR to each pure strategy profile E A for each player i E WV; as such, it can be considered as an element of "N copies of Co", that is u E u = Co x ... x Co.
The key observation is that the differences between unilatoral deviations of game = (N, A, u) can be represented as special flow Du in C₁ on A(V,A), called deviation flow of the game, by means of the deviation map:
5

---

Published in Transactions on Machine Learning Research (03/2025)
Definition 5 (Deviation map). The deviation map of the game G (N.A,2) u) is the lincar map
D :u + C1
(3)
Du
such that, for all U and all (a,d') E
(Du)(aaa)= - ua(a)
(4)
for the (necessarily eristing and unique) i e N such that 0s a4.
In words, the deviation flow Du C1 assigns to each edge (a, a') E & of the response graph, i.e., to every unilateral deviation of the game, the utility difference of the deviating player i e N.
The image of the deviation map, Im D C C1, defines the space of feasible flows on game's response graph. Among these, two lypes are particularly relevant: polential flows and harmonic flows.
Potential flows For a given number players and actions per player, representing a game via its deviation flow Du rather then payoff u preserves all the stralegic information of the game, allowing for a concise characterization of potential games. To introduce it, we need the following definition:
Definition 6 (Gradient map). The gradient map
is the linear map
do : Co + Ci
(5)
1 - doΦ
such that
(doo) o(d') - :(a)
(6)
for all o Co and all (a,a') e E. It now immediate show that
Proposition 1. A game G = A,) potential with potential function o if and only if Du doΦ for some & E Co.
Proof. Let G A, be a potential game with potential function d. Then
Du = ua(a') - (a = s(a') - o(a) = (doo)
for all (a. E E, where i E N is the actor the deviation (a, Thus, Du = dno. Conversely, let G (N,A, be a game with Du = dop for some & Co. Then
u,(a') u, (a) = Du(a,')) = (doo) = o(a') o(a)
for i N and all (a, a') acted by Thus, the game is potential with potential function ø.
The proposition means that the space of potential games is the linear subspace D-1 Im do C U; in light of this we call the image of the gradient map, Im C C1, the space potential flows.
Harmonic flows Endowing Co and C₁ with an Fuclidean-like inner product (s one can define the divergence map 0 = db G + Co as the adjoint operator of the gradient map, namely (X, do (0, X, 6) for all X C, and all & E Co. The flows in the subspace ker 0 E Cn are called harmonic flowe and the games whose flow harmonic, i.e., the games in D ker 0 U. are called harmonic games.
2The gradient map is instance of so-called bo-boundary maps: Munkres 1984 for details. Thee term harmonic refers combinatorial Hodge theory Dodziuk 1976 0: ker dj, where dj defined analogously dg- Candogan making these definitions of harmonic flows consistent..
kernel of the Laplacian operator ker Ai
2011 show, each feasible flow belongs ker d1:

---

Published in Transactions on Machine Learning Research (03/2025)
Hodge decomposition of feasible flows Leveraging the combinatorial Hodge decomposition theoren it can be shown that potential flows and harmonic flows completely characterize feasible flows:
Theorem (Candogan et al. (2011) Combinatorial Hodge decomposition of feasible flows). The space of feasible flows is the orthogonal direct of the subspaces of potential flows and harmonic flows:
Im D Im @ ker d
Equivalently, every feasible Du flow can be decomposed in unique way as Du = Dup + Dun. where the potential flow Dup E Im dg is the orthogonal projection of Du onto Im do, and the harmonic flow Dug E ker 0 is the orthogonal projection of Du onto ker Ø
The docomposition 7 takes place in the space Im C C1 of feasible flows. In Appendix A.1 we discuss how to derive corresponding decomposition in the space U of actual payolls, allowing for the unique decomposition of any game's payoff u
up Uy U,,, where up is normalized potential game, ut normalized harmonic game, and ux non-stralegic game; c.f. Figure | for example, and Candogan et al. (2011) for further details. However, the decomposition (7) in the space of feasible flows suffices to introduce the measure of potentialness used in this work, as the deviation flow of non-strategic games is identically zero (see Appendix A.1
Payoff
Potential
Harmonic
Non- StratSrate
0.00
0.00
0.17
0.17
40.35
40.50
40.00
0.53 0.33 0.35
Agent
0.00
1.00
0.00
-033
0.17
0.17
-0.00
0.50
-0.50
0.3
0.33
0.00
0.00
1,00
0.17
-0.35
0.17
-0.50
0.00
0.50
0.33
0.33
0.33
1.00
0.00
0.17
0.17
0.50
-0.00
0.33
0.33
Agent
0.00
0.00
L.00
00.3
0.17
0.17
-0.00
-0.50
0.50
0.33
0.33
0.35
1.00
0.00
0.00
0.17
00.3
0.17
0.50
-0.00
00.50
0.33
0.35
0.35
Figure 1: Decomposition of the Shapley game.
Endowing 24 with an inner product structure, Candogan et al. (2011) show that up is the potential game closest This allows Candogan al. (2013a b) to characterize the limiting behavior of dynamics in the game in terms of the properties of the potential game up and of the distance between and up, concept that is made precise in the next paragraph.
Potentialness The potential component Dup of the deviation flow Du of a game can be used build a measure of how close to being potential game the game is. To compute it,, Candogan et al. [001 introduce the orthogonal projection onto the subspace of potential flows; by the properties of the Sloore-Penroes pscudo-inverse do Ci + Co of the gradient map (Golan 1992) such projection is e= dodo C. + C2 so that
Dup eDu E Im C
Candogan al. 2013a b) use the deviation map to define the mazimum pairwise difference between two games as 8(u, u') D|Du Du' In particular, since the potential component up of game is (up to non-strategic game) the potential game closest to the original game, they use the maximum pairwise difference ōu, up) = || Du Dupll |Du,l between game and its potential component up measure of closeness to being a potential game for the game u. In this spirit we give the following definition:
4See Jiang et 201 for concise presentation and proof. 5Tn work The 2- 2-norm, whereas Candogan al. 2013a use the infinity norm.

---

Published in Transactions on Machine Learning Research (03/2025)
Definition 7 (Potentialness). The potentialness of game G (N, A, u) is the real number
Duup
P(u) = ||Dupl| Duull
(9)
Proposition 2. The potentialness of game fulfills
(1) P(u) [0,1]
(i)) P(u) = - ō(u, up) = + u is a potential game
(ti) P(u) is harmonic game
Proof. Consider the game G (N, u) and its potentialness
Du
P(u) 11Dupl] Duall
(i) is obvious that P(u)= [0;
(ii) Since o(u, up] = Duxll it is also obvious that P(u) = 1 = 8(u, up) = O. Let this be the case, then Du = Dup + Du, = Dup E Im do, so Du = dop for some ø E Co. ic. the game is potential by Proposition 1
Conversely, let G = AW, be a potential game. Then Dup = Du, since Dup is the ort ortoogl projection of Du onto Im do, and such projection leaves Du invariant since Du doe itself belongs to Im dg. Hence, ||Dunl| = 0.
(iii) It is obvious that P(u) 0 + ||Dupll = 0; if this is the case then Du = Dun, so the game is harmonic by definition.
Conversely, if the game is harmonic then Du = Dun, by an argument analogous to the one in point which implies that ||Dupl = 0.
In light of these properties, a game's potentialness provides concise measure of its proximity to being potential game. In the next sections, we examine the computational complexity of computing potentialness, and explore the existence of strict pure Nash equilibria (SPNE) as well as the asymptotic behavior of learning dynamics as a function of potentialness.
Scalability To compute the potentialness of a game with payoff functions E Ut two computational expensive steps are required: computing the deviation flow, u + Du, and projecting it onto the space of potential flows, Du + eDu. Since these operations involve the linear maps D u + Ci of Equation (3) and C1 - C1 of Equation {8), the caleulations reduce to matrix-vector multiplications.
Given a game G = AW the operators D and depend only on the number of actions A and agents N, not on the payoff function u E U. Thus, the matrices representing these operators need to be computed only once for each combination of N and A, allowing them to be precomputed and reused. However, this preprocessing step is costly, as matrix size grows exponentially with the number of agents. The projection Du + eDu, the most computationally expensive step, involves the matrix e of size dim C1 x dim C1, where for 2N++2) For reference, in game with five actions per
dim C - EieN(A 1). In games where all agents have the same number of actions, i.e., A all i E N, the number of entries in scales agent, the number of entries in e is of order 10a for N = 2, 10 for N 3, and 10" for N == 4.
For the larger settings considered in Figure 2 (three agents with 12 actions each, and four agents with 7 actions each), computing these matrices takes approximately 2-3 minutes. However, this cost is incurred only once. Once the matrices are available, computing potentialness very fast, as the dominant cost reduces to a matrix-vector multiplication of complexity mN)2))N+2) The average runtime (over 100 runs) for computing potentialness in our experiments, performed standard notebook, is shown in Figure 2
8

---

Published in Transactions on Machine Learning Research (03/2025)
c-m
c-m"
c-m
Time in
10
# Agents
P.cciinss
Figure Average runtime for computing potentialness over 100 runs, with precomputed matrices.
5 Numerical Experiments
We conduct our numerical experiments on randomly generated and economically motivated games. Our analysis focuses mainly on two aspects, namely, the existence of strict pure Nash-equilibria (SPNE) and the convergence of learning dynamics function of the potentialness of the games
To analyse learning dynamics, consider online mirror descent (OMD) (Nemirovskij & Yudin 1983 with entropic regularization, leading to the update steps outlined in Algorithm | OMD is natural choice among no-regret algorithms due to its favorable regret properties, and belongs to the broader class of follow-the- regularized-leade (FTRL) algorithms
Shaley-Shwartz 2012
Algorithm 1: Online Mirror Descent
Input initial mixed strategies 8;,0 for t= to T do for agent = to N do observe gradient Ui,e set 81, Pa P (ner,));
end
end
The entropic regularization introduces in Algorithm proz-mapping Pa Rd - Rdd of the form
Pr(y) = (x, exp y, )) 1d
(10)
Ej=1 2, exp()))
where d E N denotes the dimension of the player's strategy space, i.c., d Aū; see, e.g., Nemirovski (005
Juditsky et al. (2011) for further details.
The convergence properties of the algorithm depend on the chosen step-size nhe We use a step-size sequence of the form 7/. 7/ - for some No 0 and 8 E (0, 1], and consider Algorithm ] to have converged to (approximate) NE of the game if the relative utility loss, f((s;) predefined tolerance of 10-8 for all agents E N within a fixed number of itcrations, T = 2 000. In the above, br; denoles a best response of agent i given the opponents' stralegy profile 8-i,t-
(s:))/u, (br,, falls below
oTehe code available Github httpp:://github.ccmm// httpss//ggtthb....oo///rrrrrrrrr learning

---

Published in Transactions on Machine Learning Research (03/2025)
Standard Games
Before examining randomly generated games, first briefty analyze the potentialness
of standard games. The results are summarized in Table
Game
Actions
P(u)
Matching Pennies
2x2
0.00
Battle of the Sexes
2x2
0.94
Prisoners' Dilemma
2x2
1.00
Shapley Game
3x3
0.36
Jordan Game (a,
2x2
[0.00, 0.50]
Table 1: Potentialness standard matrix games. The payoff matrices for the first three games are from Nisan (2007), while the matrix for the Shapley game given Figure [ The matrix for the Jordan game is taken from Jordan (1993) Def 2.1). OMD converges to pure NE only the Battle of the Sexes and the Prisoner's Dilemma, both of which exhibit relatively high values of potentialness.
Pure equilibria exist only in the Battle of the Seres and the Prisoner's Dilemma. The Prisoner's Dilemma, being a potential game, has a potentialness of exactly 1, whereas the Battle of the Sexes, despite not being potential game, still exhibits relatively high potentialness. In both cases, OMD converges to pure NE.
Matching Pennies, the Shapley Game, and the Jordan Game are known to have only mixed equilibria. Since OMD can converge only to strict NE (Giannou et al. 2021a), it does not converge in these games. Consistently, Matching Pennies, as harmonic game, has potentialness of exactly zero, while the Shaplcy and Jordan games, being neither harmonic nor polential, exhibit relatively low potentialness.
Interestingly, the potentialness of the Jordan Game, when the parameters of the payoff matrices are sampled uniformly at random, varies between and 0.5.
Random Games In this section, we investigate three key aspects of potentialness in random games. First, we analyze how potentialness varies as function of the number of agents and available actions. Second, we explore the connection between potentialness and the existence of strict Nash equilibria. Third, we examine the relationship between potentialness and the long-term behavior of learning dynamics random games.
To generate a random game = (N, u) for a certain setting (number of agents N and actions per agent As), we independently sample each payoff value from a uniform distribution, i.e., uz(a) u([0, 1]) for all A and i E N; our dataset consists of 10 games for each considered setting.
0.6
# Agents
# Actions
Density
2
4
12
0.2
0.0
0.2
0.4 Potentialness
0.6
0.8
1.0
Figure 3: Empirical distribution of potentialness in 106 randomly generated games for cach considered setting. Increasing the size of the games reduces the variance and the mean of the distribution.
10

---

Published in Transactions on Machine Learning Research (03/2025)
The resulting empirical distributions of potentialness for randomly generated games with different settings are presented in Figure 3 this leads us to the following observation:
Observation 1. As the size of the gume increases (in terms of either the number of agents or actions), both the variance and the mean of the observed potentialness distribution decrease.
Our next objective is to analyze the connection between potentialness and the long-term behavior of learning dynamics. As natural intermediate step, we first examine the existence of strict Nash equilibria strategy distributions for which Equation (1) holds as a strict incquality as a function of potentialness. The reason is twofold. First, strict Nash equilibria are the only possible candidates for the convergence of learning algorithms: Giannou al. (2021a) show that strategy distribution asymptotically stable under FTRL algorithms (such Algorithm 1 if and only if it is strict Nash equilibrium. Second, strict Nash equilibria necessarily correspond to pure strategy profiles. Since potential games always admit at least pure Nash equilibrium (Monderer & Shapley 1996). one might expect. that games with high levels of potentialness have higher probability of possessing strict (hence, pure) Nash equilibrium (SPNE)
1.0
exist))
P(SPNE exists)
1
Agents
# Actions
0.4
2
4
12
10
24
0.0
0.2
0.4
0.6
0.8
1.0
Potentialness
Figure 4: Relationship between potentialness and existence of SPNE across different settings. Vertical axis: empirical probability of SPNE existence as function of the setting. Horizontal axis: Potentialness values. The width of the horizontal lines represonts the obscrved range of potentialness values for cach sctting, corresponding to the support of the densities shown in Figure 3 The dot on each line indicates the average potentialness for that setting. As game size increases, mean potentialness decreases, and the probability of SPNE existence approaches 1/e (dotted horizontal line).
Rinott & Scarsini (2000) showed that the probability of the existence pure Nash equilibrium randomly drawn games converges to 1/e as either the number players or the number of actions per player increases. This tendency is evident in Figure which also illustrates the following: across different settings, the average potentialness increases, does the probability of SPNE existence.
Next, we examine the relationship between SPNE existence and potentialness within the same setting. For each setting, we discretize the potentialness range [0, 1] into 20 intervals J = k-1 & 20 20 for k= 1,.., 20, partition games accordingly, and compute the fraction of games in each group that have at least one SPNE; the results are visualized in Figure 5 We summarize our findings in the following observation:
Observation 2.
Both across different settings and within the same setting, a higher potentialness increases the likeláhood that a game has least one SPNE.
A pure Nash equilibrium fails be strict ties occur. In the context of random games, pure Nash equilibrium is strict. with probahility 1, ties with probahility zero.
11

---

Published in Transactions on Machine Learning Research (03/2025)
P(SPNE exists)
# Agents
# Actions
0.6
2
4
10
24
0.4 Potentialness
Figure 5: Relationship between potentialness and existence of SPNE within the same setting. Vertical axis: empirical probability of SPNE existence function of potentialness. Horizontal axis: polentialness values. For each setting, higher potentialness increases the likelihood that game has at least SPNE.
Next, we examine the relationship between potentialness and the long-term behavior of learning dynamics in random games. The existence of SPNE ensures local convergence of learning algorithms (Mertikopoulos & 'Zhou 2019), prompting the question of whether higher potentialness not only increases the probability of having an SPNE, but also influences its basin of attraction the set of initial conditions leading to convergence.
Following the same approach as before, we partition for each setting (number of agents and actions) the potentialness range into 20 intervals, Is = (020 20 for 1....,,0,, 20, and group together games with potentialness in Ig- For each group k;
Algorithm 1 with step-size Ne no 1-3 letting 1/ 2 and f 20- The initial condition is fixed to the uniform strategy, $1.0 A,'1, 1, for all agents i. The fraction of converging instances in games that possess a SPNE is plotted against the group's potentialness value, with results shown in Figure and summariied in Observation
3
P(Convergence SPNN exists)
0.8
# Agents
# Actions
2
0.4
12
0.0
0.2
0.4
0.6
0.8
1.0
Potentialncss
Figure 6: Empirical probability of convergence of Algorithm [ as a function of potentialness, The analysis considers only random games with at least one SPNE; higher potentialness increases the likelihood of reaching oquilibrium.
12

---

Published in Transactions on Machine Learning Research (03/2025)
Observation 3. Higher potentialness increases the likelihood of reaching equilibruu using Algorithm assuming the eristence of at least one SPNE.
Remark. Different initial conditions, uniformly sompled over the feasible space, lead to the same outcomes stated in Observation analogue results; however, bigger step-sizes ensure better convergence rates.
discussed in Appendiz A.2 Employöng smaller step-sizes similarly leads to
Economic Games As compared to random matrix games, many games analyzed in the economic sciences have more structure in the payoffs. Arguably, one of the most important classes of economic games are auctions and contests, which are widely used to describe strategic interaction in markets (Krishnaj (009)). In these games, the utility functions of agents have a specific form, and the allocation rule is monotonic in the bids. Well-known auctions and contests include:
First-Price Sealed-Bid (FPSB) Auction
u,aa 04) = zz(a) (vs a.)
(11)
Second-Price Sealed-Bid (SPSB) Auction
ui(a, vz) = zz(a) ((i max a,) zfi
(12)
All-Pay Auction
ui(a, vz) =z)(a) . Uss ai
(13)
War of Attrition (WoA)
u,(a, v.) = x2((a) -0; max a,) - (1 - -xx(a))
(14)
jzi
Tullock Contest
V 6 F:aa
a
if E5
ua(a, Us) =
(15)
else
In the above, a, E A, represents the bid of agent i, and a E A = action) profile. Similarly, i corresponds to agent i's value, and x:(a) A - [0, is the allocation function, which incorporates random tie-breaking rule, given by
IIEx A, denotes the complete bid (or
if 04 = maxjeX Aj.
x;(a) =
(16)
if a maxjeN aj.
where Dmax denotes the nimber of bids that attain the maximum.
Auctions are typically defined over continuous action spaces, where each player's bid is real number, normalized without loss of generality to the interval A, = [00,]] 1]. However, the decomposition proposed by Candogan al. (2011) applies only to finite games. To make it applicable, discretize each action space A, into A, equidistant points. We remark that, for practical purposes, auctions are inherently discrete, bids can only be submitted up to finile number of decimal places.
The choice of discrotization appears to have little impact on a game's potentialness. Figure presents potentialness levels computed for varying discretizations and agents valuations. As the discretization becomes finer, the potentialness stabilizes an asymptotic value; however, the number of pure Nash equilibria can exhibit sharp changes. For instance, in the symmetric First-Price Sealed-Bie Auction, there is one strict NE for A, 21, whercas for A, 20, additional non-strict pure NE emerges alongside the strict NE.
Observation 4. inherent property of the underbying (continuous) game, and does not depend on the choice of discretization.
The potentialness of the discretized economic gomes given in Equations [11 to 115 an
13

---

Published in Transactions on Machine Learning Research (03/2025)
1.0
0.8
Games
Potentialness
Contest
0.6
SPSB
FPSB
WoA
Allpay
0.0
10
20
25
# Actions
Figure 7: Potentialness of the economic games given in Equations 11 to (15), with 2 agents. We consider different discretizations (that is, number of actions), and different valuations. The solid lines show the potentialness in the symmetric setting, where both agents have values 21 02 1, while the dashed line shows the asymmetric settings with 11 4, 12 1. As the discretization becomes finer, the potentialness stabilizes at asymptotic value.
A detailed analysis of the decomposition of first- and second-price auctions reveals that their harmonic components are identical. When varying the payment rule through convex combinations of the first- and socond-price rules, only the potential and non-strategic components of the decomposition change. This observation supports the intuition that the allocation rule determines the strategic difficulty posed by the game. In contrast, contesis, that have smoothed version of this allocation, show higher level of potentialness.
Given a game decomposed into its potential and harmonic components, == up + uHz potentialness describes the relative weight of the potential component over the harmonic onc. One can then build a game with prescribed level of potentialness by considering the convex combination Wo == aup + a)uH, with a E [0, 1]. Figure g shows the convergence behavior of Algorithm [ as a function of potentialness in games built with this procedure from the economic games given in Equations
11 to 15
Allpay
WoA
FPSB
0.5
SPSB
Contest
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Potentialness
Figure Convergence of OMD in economic games. Each square corresponds to convex combination Ua = aup (1-a)uH of the potential and harmonic components of the respective economic game (vertical be read the horizontal axis. The color of the square
axis); the corresponding level of potentialness shows the empirical frequency of convergence to an equilibrium using OMD (1 = 28 2 for 102 randomly generated initial strategies. The stars indicate the potentialness of the original economic game. For each game, there exists a potentialness threshold above which the algorithm converges; this threshold is lower for games with a higher original potentialness, suggesting that convergence in games with high potentialness is relatively more robust against harmonic perturbations.
14

---

Published in Transactions on Machine Learning Research (03/2025)
We observe that, for each game, there exists potentialness threshold beyond which the algorithm begins to converge. As expected, this threshold coincides with the existence of an SPNE: When potentialness exceeds a certain game-specific value, an SPNE exists, and and Algorithm I converges; below this threshold, no pure equilibrium cxists, and Algorithm| ] fails to converge. Furthermore, this threshold is lower for games with a higher original potentialness, suggesting that convergence games with high potentialness is relatively more robust against harmonic perturbations.
Among the considered economic games, the all-pay auction is the "hardest to learn", namely it is the one with lowest potentialness, and hightest convergence threshold. Interestingly, while the all-pay auction in the complete-information setting only has a mixed equilibrium, its incomplete-informatiie admit pure Bayes-Nash equilibria (BNE). The work of Bichler et al. (2023) shows that BNE are learnable in discrete games using first-order methods such as Algorithm I. To better understand the different equilibrium structures between the complete and the incomplete information case, we extend our analysis to the richer Bayesian framework, examining through the lens of potentialness.
counterpart can
Bayesian Economic Games Boyesion (or incomplete-iifoormatioo games are the standard approach in auction theory to model the economic games we considered (Krishna 2009). Compared to normal-form game, a Bayesian games B = VN, F, u) is characterized by an additional type space V and known prior distribution F over this type space. Each player i E ' observes a private type, which is drawn from Vj according to the prior distribution F. In the examples given in Equations {II) to [15), the private type is the valuation 24. After observing their values, the agents play an action, i.e. submit a bid a E A,, and receive their utility uz(a;, a- 0;), which depends on their type. pure strategy in such a Bayesian game is function B : Vi- + A; that maps players' types to actions. Given a strategy prosile, one can compute the expected (ex-ante) utility u, Eu-plu, (B((),, profile 3, where no player can increase the expected utility û by deviating.
e4]l A Bayes-Nash equilibrium (BNE) is a strategy
As in the complete-information case, we consider only finite action spaces, and additionally assume finite type spaces. This allows us to reformulate the Bayesian game as a finite normal-form game, decompose it using Equation 7 and analyze its potentialness, as given by Equation (9). The actions of the induced normal- form game consist of all the possible strategies of the original incompleee-infomant an agent. with V, types and A; actions in the Bayesian game translates to an agent with A. pure actions in the normal-form representation. Clearly, the size of the resulting normal-form game grows rapidly and quickly becomes intractable. To mitigate this issue, we restrict our analysis to non-decreusing strulegies, is customary in auction theory. This reduces the number of strategies to (V=tA="), enabling us to analyze Bayesian games with two players and up to four actions and types, corresponding to 35 non-decreasing strategies. The payoffis in the normal-form game represent the expected utilities in the Bayesian game, and the pure Nash equilibria in the normal-form game correspond to Bayes-Nash equilibria the Bayesian game.
game. Specifically,
Following this procedure, four actions, up to four types, and a uniform prior distribution. Our findings, summarized in Figure g and Observation 5 reveal a notable pattern: the Bayesian version of each game exhibits higher polentialness than its information counterpart (where the number of types is one). Specifically, potentialness increases as the number of types grows.
constructed the normal-form representation of Bayesian economic games with
In particular, the increase in potentialness substantial for the all-pay auction; with two or four types, it even leads to the existence of a pure BNE, This is especially noteworthy because learning algorithms successfully converge to equilibrium in Bayesian games with a BNE (Bichler et al., 2023). whereas in the complete-informatiin version of the all-pay auction which only admits mixed Nash equilibria convergence does not occur, cf. Figure
Observation 5. Potentialness consistently increases with the rembeer of types in the Bayesian versions of the considered games. In particular, while Algorithm fails to converge in the complete-informatiin all-pay auction, il successfully converges lo a pure Bayes- Nash equilibriwm in the Buyesian version of the game.
15

---

Published in Transactions on Machine Learning Research (03/2025)
1.0
0.8
Games
Potentianness
Contest
0.6
SPSB
FPSB
WoA
Allpay
8.2
2 Number of Tyyees
Figure 9: Potentialness of Bayesian economic games.. We consider the Bayesian version of economic games with two agents, each having four actions, A; 0.0, 0.3, 0.6, 0.9, and independent, uniformly distributed types V; { I,..., Vi), where V denotes the number of types. Potentialness consistently increases the mumber of types grows.
6 Conclusions
Understanding whether learning algorithms converge a Nash equilibrium has been a long-standing question in game theory, and characterizing which games permit convergence and which do not remains open problem in the study of learning in games. While it is well established that exact potential games guarantee convergence, we extend this analysis by relaxing this condition, investigating convergence in games that are quantitatively distant from being potential games. A decomposition technique allows us to measure how "potential" a specific normal-form game is: For random matrix games, we find that potentialness serves as a strong predictor for the existence of strict Nash equilibria, and for the convergence of online mirror descent. Economically motivated games, such auctions and contests, impose additional structure on payoffs. Here, too, potentialness observed to increase with the number of types proves to be reliable predictor of convergence.
Unlike individual simulation runs, where convergence heavily depends on algorithm initialization, poten- tialness provides an ex-ante predictor of average convergence, offering systematic approach to studying learning in games. This insight addresses a long-standing question the litcrature by shifting the focus from empirical simulations to a more principled measure of convergence potential.
Future research should aim further validate these findings by examining a wider range of no-regret learning dynamics and expanding the analysis to broader classes of games. Additionally, improving the computational efficiency of potentialness, extending its application to continuous games, and leveraging it to design more effective learning algorithms remain key open directions.
Acknowledgments
This project was funded by the Deutsche Porschungsgemmeinsccaft (DFG, German Research Foundation) under Grant No. BI 1057/9: and Project Number 277991500. It is based upon work supported by the National Science Foundation under Grant No. 19281928930 and by the Alfred P. Sloan Foundation under grant G-2021-16778, while M. Bichler, D. Legacci, B. Pradelski, and M. Oberlechner were in residence at the Simons Laufer Mathematical Sciences Institute (formerly MSRI) in Berkeley, California, during the Fall 2023 semester. This work was also supported in part by the French National Research Agency (ANR) the frame- work of the PEPR IA FOUNDRY project SEER-23-PEIA-DOON (ANR-15-IDEX-02 the LabEx PERSYVAL P3TA-0003) and IRGA-SPICE. P. Mertikopoulos also affiliated with Archimedes, Athena Research Center,
the "Investissements d d'avenir" program 11--111--A--005...101 MIAI@ Grenoble Alpes (ANR-19-
16

---

Published in Transactions on Machine Learning Research (03/2025)
and was partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationFU Program.
References
Dilip Abreu and Ariel Rubinstein. The structure of nash equilibrium in repeated games with finite automata. Econometricn, (6(6))12299-2)) 1281, 1988.
Toannis Anagnostides, Toannis Panageas, Gabricle Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning, pp. 536 581. PMLR, 2022.
Gabriel P Andrade, Rafael Frongillo, and Georgios Piliouras. Learning in matrix games can be arbitrarily complex. In Conference on Learning Theory, pp. 159-185. PMLR, 2021.
Martin Bichler, Maximilian Fichtl, and Matthias Oberlechner. Computing Bayes-Nash equilibrium in auction games via gradient dynamics. Operalions Research, 2023. doi: 10. 2012.0002222222..
Martin Bichler, Alok Gupta, and Matthias Oberlechner. Revenue in first and second-price display advertising
auctions: Understanding markets with learning agents, 2024. URL htttps//aaxxxv..or////////2222
Martin Bichler, Stephan B Lunowa, Matthias Oberlechner, Fabian R Pieroth, and Barbara Wohlmuth. On the convergence of learning algorithms in bayesian auction games. Proceedings of the AAAI, 2025.
Oliver Biggar and Iman Shames. The graph structure of two-player games. Scientific Reports, 13(1):1833, February 2023.
Avrim Blum and Adam Tauman Kalai. Universal portfolios with and without transaction costs. Machine Learning, 35(3):193 205, 1999.
George W Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation (311)3374336, 1951.
Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3):474-503 2011.
Ozan Candogan, Asuman Ozdaglar, and Pablo A Parrilo. Dynamics in near-potential games. Games and Economic Behavior, 82:66-90, 1.66600,440 2013a.
Ozan Candogan, Asuman Ozdaglar, and Pablo A Parrilo. Near-potential games: Geometry and dynamics. ACM Trunsactions on Economics and Computation (TEAC), 1(2):1 32, 2013b.
Le Chen, Alan Mislove, and Christo Wilson. An empirical analysis of algorithmic pricing amazon mar- ketplace. In Proceedings of the 25th international conference on World Wide Web, pp. 1339-1349, 2016.
George Christodoulou, Vahab Mirrokni, and Anastasios Sidiropoulos. Convergence and approximation in potential games. Theoretical Computer Science, 438:13-27, 2012.
Constantinos Daskalakis, Rafacl Frongillo, Christos H Papadimitrion, George Picrrakos, and Gregory Valiant. On learning algorithms for Nash equilibria. In International Symposium on Algorithmic Game Theory, pp. 114 125. Springer, 2010.
Jozef Dodziuk. Uhiite-Diffeence Approach to the Hodge Theory of Harmonic Forms. American Journal of Mathematics, 98(1):79-104 1976.
Beno Eckmann. Harmonische Funktionen und Randwertaufgaben in einem Komplex. Commentart Mothe- matici Helvetici, 17(1):240 255, December 1944.
Lampros Flokas, Emmanouil Vasileios Vlatakis- Gkaragkounis, Thanasis Liancas, Panayotis Mertikopoulos, and Georgios Piliouras. No-regret learning and mixed Nash equilibria: They do not mix. In NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
17

---

Published in Transactions on Machine Learning Research (03/2025)
Dean P Foster and Rakesh V Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, (1-2))::0 1997.
Joel Friedman. Computing Betti numbers via combinatorial Taplacians. In Proceedings of the Twenly- Fighth Annual ACM Symposium on Theory of Computing STOC '96, pp. 386 391, Philadelphia, Vennsylvaniaa United States, 1996. ACM Press.
Drew Fudenberg and David K. Levine. The Theory of Learning in Games, volume 2 of Economic learning and social evolution. MIT Press, Cambridge, MA, 1998.
Drew Fudenberg and David K. Levine. Conditional universal consistency. Games and Economic Behavior, 29(1):104 130, 1999.
Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragooon and Panayotis Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT '11 Proceedings of the 34th Annual Conference on Learning Theory, 2021a.
A Ageliii Giannou, Emmanouil Vasileios Vlatakis- Gaaaaakona,,,,,,, and Panayotis Mertikopoulos. The conver- gence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond. In NewrIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021b.
Itzhak Gilboa and Akihiko Matsui. Social stability and equilibrium. Econometrica, 59(3):859 867, May 1991.
Jonathan S. Golan. Foundations of Linear Algebra. Springer Science & Business Media, 1992. ISBN 978- 94-015-8502-6.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econo- metrica, 117) 2000.
Sergiu Hart and Andreu Mas- Colell. Uncoupled dynamics do not lead to Nash equilibrium American Economic Review, 93(5): 1836, 2003.
Amélic Helion, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit foodback in potential games. Advances in Neural Information Processing Systems, 30, 2017.
Josef Hofbauer and William H. Sandholm. Stable games and their dynamics. Journal of Economic Theory, 144(4):1665-1693, July 2009.
Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. Statistical ranking and combinatorial Hodge theory. Mathematical Programming, 127(1):203 244, 2011.
Jakob Jonsson. Simplicial Compleres of Graphs. Springer Science & Business Media, 2007.
James S. Jordan. Three problems in learning mixed stratogy Nash equilibria. Games and Economic Behavior. 5(3):368-386, July 1993.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving Variational Inequalities with Stochastic Mirror-Prox Algorithm. Stochastic. Systems, 1(1):17-58, 58, June 2011.
Vijay Krishna. Auction theory. Academic press, 2009.
Davide Legacci, Panayotis Mertikopoulos, and Bary S. R. Pradelski. A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights. In JCML '24: Proceedings of the 41st International Conference on Machine Learning, 2024.
Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, (7311-2):465-- 507, January 2019.
18

---

Published in Transactions on Machine Learning Research (03/2025)
Panayotis Mertikopoulos, Christos H. Papadimitrion, and Georgios Piliouras. Cycles in adversarial reg- ularized learning. In SODA '18: Proceedings of the 29th annaual ACM-STAM Symposium Discrele. Algorithms, 2018.
Panayotis Mertikopoulos, Ya-Ping Hsich, and Volkan Cevher. A unified stochastic approximation framework for learning in games. Mathematical Programming, 203:559-609, January 2024.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124 143, 1996.
James R Munkres. Flements of Algebraic Topology. Perseus Books, 1984.
Arkadi Nemirovski. Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lips- chitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems. SIAM J. on Optimization, 15(1):229-255) January 2005.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Noam Nisan (ed.). Algorithmic Game Theory. Cambridge University Press, Cambridge New York, 2007. ISBN 978-0-521-87282-9, OCLC: ocn 12n1222699
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with con- stant step-size in congestion games: Convergence, limit cycles and chaos. In NIPS '17 Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
Yosef Rinott and Marco Scarsini. On the number of pure strategy nash equilibria in random games. Games and Economic Behavior, 33(2):274-29) 2000.
Robert W. Rosenthal. A class of games possessing pure-stratogy Nash equilibria. International Journal of Game Theory, 2(1):65 67, December 1973.
James BT Sanders, J Doyne Farmer, and Tobias Galla. The prevalence of chaotic dynamics in games with many players. Scientific Reports, 8(1):1-13, 2018
Shai Shalev-Shwarlz. Online learning and online convex optimization. Foundations and TrendsB in Machine Learning, (22):107-194, 2012.
Yannick Viossat and Andriy Zapechelnyuk. No-regret. dynamics and fictitious play. Journal of Economic Theory, 148(():825-84)) 842, 2013.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv:2011.000 100588,, 2020.
H Peyton Young. Strategic learning and its limits. OUP Oxford, 2004.
19

---

Published in Transactions on Machine Learning Research (03/2025)
A Appendix
A.1 Decomposition in the space of payoffs
The reason Candogan al. [2011) work in the space C1 of flows rather than in the space U of payoffs to achieve decomposition of games is twofold: first, the combinatorial Hodge theorem holds true on the space C₁ of flows (and in general on every chain group Cg of a simplicial complex), while there is no such a theorem for the space Uf of payoffs; second, two games u * u' such that Du = Du', albeit having different payoffs, display the same strategical properties and are effectively the "same" game so looking at the deviation flow rather than the payoff one gets rid of a redundancy that intrinsic in the formulation of a game.
Non-strategic games of non-strategic games.
To make this last point more precise Candogan et al. (2011) introduce the notion
Definition A finite game in normal form G (W, u) is called non-strategic if has zero deviation
flow:
Du = 0.
(17)
The space of non-strategic games is denote by
K. = ker D.
(18)
In a non-strategic game, all players are indifferent among all of their choices:
Proposition 3 (Candogan et al. 2011). The game G = (N, is non-strategic if and only if uidd, a.) u,(""' am:,,
(19)
for all N, all a- A-x, and all a/, d' As.
Since ::44 - C1 a linear map between vector spaces, the space of non-strategic games a linear subspace K. U. 1t follows by the definition of non-strategie games that two games have the same deviation flow if and only if their difference is non-strategie game, and in this case we say that the two games are stralegically equivalent.
Normalized games Being strategically equivalent is equivalence relation the space U of payoffs; select representative element in each equivalence class [u] by choosing complement of K. in U and projecting E U onto such complement along K. A natural choice is that of using the orthogonal complement K- of the space of non-stralegic games with respect to the Euclidean inner-product U;; we refer to such procedure as normalization, and following Candogan et al. (001]) we give the following definition:
Definition 9. A finâte game in normal form G (N, A,u) is called normalized if
L K-
(20)
Normalized games enjoy the "no-leftover" property: the sum of any player's payoffs over their choices zero for any fixed choice by the other players.
Proposition (Candogan et al. 2011).
The gume G = A,), is normalized if and only if
Σ u(dl, =0)) =0 a'
(21)
for all i i N and all a_; E A_
&Quoting Candogan al. 2013bb, if Iwwo games have the deviation flowj, then the oguilibrium sets these games sdentical. However, payoffs equilibria may differ, and hence they may different in of their efficiency (such Paveto efficiency) properties (see Candogan all (011)).
20

---

Published in Transactions on Machine Learning Research (03/2025)
Decomposition in the space of payoffs After normalizing the space U of payoffs one can translate the decomposition of feasible flows (Equation 7 in the main text) from Im D c C1 to U by means of the Pooore-Penrooe ageudo-incerse, D : C1 + U of the deviation map.
Recall from Section that the space of potential games is D Im do C. U, and that the space harmonic games D- ker d C U. Their intersections with the space K-+ l of normalized games give the spaces of normalized potential games and of normalized harmonic games:
Definition 10. The space of normalized potential games is the linear subspace
== (potential gumees)nk cu.
(22)
The space of normalized harmonic games is the linear subspace
H = (harmonic games) n K cu.
(23)
Theorem (Candogan et al. (2011) Combinatorial Hodge decomposition of finite normal form games).
The space U is the direct sum of the subspaces of normalized potential games, normalized harmonic games, and non-stralegic games:
= D H@K.
(24)
Equivalently, given a finite normal form game G (N, A, u) the payoff function can be uniquely decomposed the sum u up un uy of normalized potential game up, normalized harmonic game uh, and mon-strategic game ug.
Decomposition components Recall that the deviation map is a linear map D : u - C₁ from the space of payoffs to the space of flows. By the propertics of the Moore-Penrowe psoudo-inverse the orthogonal projection onlo
C1 - u
of the deviation map (Golan, 1992), the operator II == ĐD u IC+ (ker D)+. Recall furthermore that e C1 + C1 is the orthogonal projection onto the subspace of potential flows.
These operator can be used to obtained explicit expressions for the components of the decomposition in the space of payoffs:
Proposition 5 (Candogan et al. 2011 ) Given the finite normal form game G (N, A,), the components
up, Un and uxc of the combinatorial Hodge decomposition of finite normal form games are given by
uk EK
up = DeDu EP
Wg ux up H
9That is, after quatienting away the kernel of the deviation map.
21

---

Published in Transactions on Machine Learning Research (03/2025)
A.2 Additional Numerical Experiments
Following the experiment illustrated in Figure 6 grouped logether games with similar polentialness, and applied Algorithm ! with ?o = 2 and = 1/20. However, instead of fixing the uniform strategy as the initial condition, we randomly sampled 25 initial strategics for cach game. The first plot in Figure [10 shows the empirical probability of convergence of Algorithm | as a function of potentialness various settings. The findings align with those Figure @ confirming that higher potentialness increases the likelihood of reaching equilibrium regardless of specific initializations.
1.0
1.0
P(Convergence SPNE exists)
PrCoovergencc SPN exists)
0.8
0.8
Agenis
Actions
A Agents
0.6
# Actions
4
0.4
10
24
10
0.2
Potentialness
Potentialness
Figure 10: Empirical probability of convergence of Algorithm in random games with SPNE function of potentialness in various settings. Left: randomly drawn initialization points. Right: standard deviation of the convergence probability.
On the second plot, we restrict our focus to settings with only actions, and include the standard deviation of the convergence probability (colored areas) along with empirical probability of convergence (solid lines) of Algorithm D as function of potentialness. We observe that the probability of convergence given strict NE i.e. the size of the equilibrium's basin of attraction varies significantly among games with similar potentialness, as reflected in the relatively large standard deviations. However, the overall relationship between high potentialness and high convergence remains robust in expectation.
22


Reviews:
[{"review_id": "v7edahaQBd", "reviewer": "Reviewer_gADN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**: \n\nthe paper addresses a problem of interest, namely the extent to which being near to a potential game is a useful metric to the tractability of a game, several works are starting to address the problem in even more complex scenarios than the ones considered here, for instance [1] addresses Markov Games.\n\n**Weaknesses**:\n\nthe paper contributions are rather limited to my view. The definition is based directly on previous works and the theoretical characterisation is thus the one of related works, the numerical challenges of the which are not addressed (i.e. the numerical burden is described, rather then treated), the definition is descriptive and not prescriptive (no insights on algorithmic design are available, such as for [2] for instance).\n\n[1] An $\\alpha$-potential game framework for $N$-player dynamic games, Xin Guo and Xinyu Li and Yufei Zhang\n[2] Newton Optimization on Helmholtz Decomposition for Continuous Games Giorgia Ramponi, Marcello Restelli", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces the property of potentialness (in the sense of [1]) as a way to (empirically) characterise a game in terms of existence of strict pure NE and the limiting behaviour of several learning dynamics for several games of interests.\n\n\n[1] Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3):474–503, 2011.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Out of one error in references visualised with \"(??)\", I would recommend to address at least two of the following points in order to increase the contributions of the paper:\n\n- Extend the analysis to more complex games, for example state-based (Markov) games.\n- Analyse possible ways to measure potentialness in a numerically efficient way.\n- Try to add some insights on how standard algorithms should be adapted in view of this property.\n\nIn general, what I am more concerned about is that the contributions seem limited to some empirical observations over some cases of interests, based on a (numerically challenging) property directly inspired on previous work, which I think would not be sufficient for the standards.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OxexS41i09", "reviewer": "Reviewer_4yCV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The manuscript is well-motivated and clearly written. The definition of potentialness is intuitive, and appears to well-correlate with algorithm convergence. The paper provided a comprehensive study on the proposed metric, including the complexity of an algorithm that computes it, as well as behaviour under various games (continuous, different # players, etc.). \n\nI have a few questions and comments:\n1. The values of potentialness seem only comparable among similar #players and #actions, as shown in Figures 5 and 6. Have the authors considered variants that are more invariant to these parameters (so that, e.g., we can compare games with different #players or #actions)?\n2. I have trouble understanding Figure 4. What are the lengths of the horizontal lines supposed to indicate?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission investigates a metric of multi-player games, named _potentialness_, that correlates with (1) the existence of pure NE and (2) the convergence of no-regret algorithms. The authors lead with a detailed description of the preliminaries on potential games and related algorithms. The authors motivated the definition of potentialness via game decomposition, and evaluated it on random games, economic games, as well as some classical examples. Through these experiments, the authors empirically demonstrate the behavior of potentialness as #players and #actions vary, and its correlation with convergences of various algorithms. In particular, for continuous games, the authors also evaluated the effect of discretization for computing potentialness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Small changes:\n1. intro paragraph 2: adaptto -> \"adapt to\"\n2. intro paragraph 3: missing bibtex (shows up as question mark)", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "B6MbQhiaOq", "reviewer": "Reviewer_HBmG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\nThe concept of potentialness is novel and offers a unique perspective for analyzing game convergence. The paper clearly distinguishes its contributions from prior work and provides appropriate citations to related literature. While I am not an expert in game theory, I have reviewed the mathematical derivations to the best of my ability, and they appear to be correct.\n\n**Weaknesses:**\n\nIt would be beneficial for the authors to explore how the concept of potentialness scales to more complex game structures, such as those involving continuous action spaces.\nThe paper would benefit from a more detailed discussion of the computational complexity associated with calculating potentialness in large-scale games.\nThere are some typographical errors: \"adaptto\" should be corrected to \"adapt to\" (page 1), there are errors in the references (pages 1-2), and the code link provided is invalid (page 8).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the concept of \"potentialness\" as a measure to assess how close a game is to being a potential game, which is crucial for predicting the convergence of multi-agent learning systems. The authors provide empirical evidence that potentialness is indicative of both the existence of pure Nash equilibria and the convergence of no-regret learning algorithms. Furthermore, the paper investigates the impact of the number of agents and actions on potentialness and compares various economic games using this metric.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical changes that would impact recommendation for acceptance:**\n\nThe paper could benefit from improving the overall writing quality. Some sections lack clarity and could be made more concise. I recommend a thorough revision to enhance readability and ensure the arguments are presented more clearly. Authors should add the correct code link to verify the implementability.\n\n**Changes that would strengthen the work:**\n\nAdditionally, the authors should further elaborate on the applicability and feasibility of the proposed algorithm in large-scale games and in settings with continuous action spaces. This would provide a more comprehensive understanding of the algorithm's scalability and practical utility in more complex scenarios.", "broader_impact_concerns": "I think there are no related ethical concerns about this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces "potentialness" as a metric to assess how close a game is to being a potential game, aiming to understand the existence of pure Nash equilibria and convergence of no-regret learning algorithms. The study is well-motivated, clearly written, and empirically explores the behavior of potentialness across different game settings, including random and economic games.

After the rebuttal, two reviewers lean toward acceptance, while one remains skeptical about the work's overall contribution. The responses addressed several concerns, but the necessity and broader impact of potentialness as a metric remain open questions. Given the positive balance of opinions, the paper is recommended for Conditional Acceptance with revisions to clarify its significance, improve writing quality, and address computational concerns. Strengthening the justification for potentialness and exploring its broader applicability will enhance its impact.
Decision: Accept (poster)