Paths to Equilibrium in Games
Authors: Bora Yongacoglu
Gurdal Arslan
Lacra Pavel
Serdar Yuksel
Venue: NeurIPS 2024 spotlight (2024)
Keywords: game theory
multi-agent reinforcement learning
strategic dynamics
Primary area: algorithmic_game_theory
TL;DR: We study a path connectivity structure of games that is relevant to strategic dynamics and iterative learning algorithms in multi-agent systems. We prove that paths to equilibrium exist in all normal-form games.

Abstract: In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. This paper studies sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning, where an agent who is best responding in one period does not switch its strategy in the next period. This constraint merely requires that optimizing agents do not switch strategies, but does not constrain the non-optimizing agents in any way, and thus allows for exploration. Sequences with this property are called satisficing paths, and arise naturally in many MARL algorithms.  A fundamental question about strategic dynamics is such: for a given game and initial strategy profile, is it always possible to construct a satisficing path that terminates at an equilibrium? The resolution of this question has implications about the capabilities or limitations of a class of MARL algorithms. We answer this question in the affirmative for normal-form games. Our analysis reveals a counterintuitive insight that suboptimal, and perhaps even reward deteriorating, strategic updates are key to driving play to equilibrium along a satisficing path.

Paths to Equilibrium in Games
Bora Yongacoglu University of Toronto
Gürdal Arslan
University of Hawaii Manoa
vora.yoonaccolluuutroooo ca
gurdalShawaii.. Shwwaih.wwaee..
Lacra Pavel University of Toronto
Serdar Yüksel
Queen's ' University
navel@contrrol.oooooooo toronto. edu
yuksel@queensu.
Abstract
In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies new data arrives, producing sequence of strategy profiles. This paper studies sequences of strategies satisfying a pairwise constraint inspired by policy updating reinforcement learning, where an agent who is best responding in one period does not switch its strategy in the next period. This constraint merely requires that optimizing agents do not switch strategies, but does not constrain the non-optimizing agents in any way, and thus allows for exploration. Sequences with this property are called satisficing paths, and arise naturally in many MARL algorithms. A fundamental question about strategic dynamics is such: for given game and initial strategy profile, always possible to construct satisficing path that terminates at an equilibrium? The resolution this question has implications about the capabilities or limitations of class MARL algorithms. We answer this question in the affirmative for normal-form games, Our analysis reveals a counterintuitive insight that reward deteriorating strategic updates are key to driving play to equilibrium along a satisficing path.
Introduction
Game theory is mathematical framework for studying strategic interaction between self interrsetd agents, called players. an n-player normal-form game, each player 1,... n. selects a strategy x' E X' and receives a reward R (x ..... .."),,,,"),, which depends on the collective strategy profile (x ...., x²) =: (a',x xexxx), "). Player i's optimization problem is to best respond to the strategy x of its counterparts, choosing x² E X to maximize R' R'(x', x)). Game theoretic models are pervasive in machine learning, appearing in fields such as multi-agent systems 21,, multi-oojective reinforcement learning 24], and adversarial model training 77. among many others.
In multi-agent reinforcement learning (MARL), players use learning algorithms to revise their strategies in response to the observed history of play, producing sequence {&, { in the set of strategy profiles X := X2 x
X Due to the coupled reward structure of multi-agent systems, each player's 's learning problem involves a moving target: since an individual's 's reward function depends on the strategies of the others, strategy revision by one agent prompts other agents to revise their own strategies. Convergence analysis of MARL algorithms can therefore be difficult, and the development of tools for such analysis is an important aspect of multi-agent learning theory.
strategy profile (xt) is called a Nash equilibrium all players simultaneously best respond one another. Nash equilibrium is concept of central importance in game theory, and the tasks of computing, approximating, and learning Nash equilibrium have attracted enduring attention in theoretical machine learning 47 27
31.. Convergence equilibrium strategies has long been a predominant, but not unique design goal in MARL (53] In this paper, we study
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

mathematical structure of normal- foomm games with the twin objectives of (i) better understanding the capabilities or limitations of existing MARL algorithms and (ii) producing insights for the design of new MARI. algorithms.
A number of MARL algorithhs approximate dynamical systems (x1) on the set of strategy profiles
X in which the next strategy for player i is selected as r/., f fx,,,, where x, (z]..... ........:....................... 2x." is the strategy profile in period f. A sampling of such algorithms will be offered shortly. This approach facilitates analysis of the algorithm, as one separately considers the convergence of {>x h22 induced by the update functions Ji= on one hand, and the approximation of {xx J22 by the algorithm's 's iterates [& 1 on the other. In this work, we consider update functions that satisfy a quasi-rationalin condition called satisficing: when agent is best responding. the update rule instructs the agent to continue using this strategy. That is, if x² is a best response to x'', then f' xx ) = x². This quasi-rationalie constraint generalizes the best response update and is desirable for stability of the resulting dynamics, as guarantees that Nash equilibria are invariant under the dynamics. Moreover, the satisficing condition is only quasi-rational, in that it imposes no constraint strategy updates when an agent is not best responding, and so allows for exploratory strategy updates. Update rules that incorporate exploratory random search when strategy is deemed unsatisfactory are common in MARL theory
66 32
Our goal is to better understand the capabiliiies/lmitation of MARL algorithms that use the satisficing principle to select successive strategies, potentially augmented with random exploration when an agent is not best responding. Examples include 19 20
33
12 10 and [52]. Instead of studying
particular collection of strategy update functions, we abstract the problem to the level of sequences in X, which allows us to implicitly account for experimental strategy updates. A sequence (x))121 of strategy profiles is called a sutisficing puth if, for each player i and time I, one has that wi+1 ar whenever xi is a best response to x The central research question of this paper is such:
For a normal-form game I and initial strategy profile X1, is it always possible construct a satisficing from X1 to a Nash equilibrium of the game I?
Since many MARL algorithms operate using the satisficing principle (or otherwise approximate pro-
cesses that involve satisficing update rules, e.g. (48),, the resolution of this question has implications for the effectiveness of such MARL algorithms. Indeed, the question has been answered in the affir- mative for two-player normal-fore games by [19 and for n-player symmetric Markov games by [52). and in both classes of games this has directly lead to MARL algorithms with convergence guarantees for approximating equilibria. In addition to removing a theoretical obstacle, positive resolution of this question would establish that uncoordinated, distributed random search can effectively assist Nash-seeking algorithms to achieve last-iterate convergence guarantees in a more general class of games than previously possible.
Contributions. We give a positive answer to the question above: for any finite n-player game T and any initial strategy profile x,, there exists a satisficing path beginning at X and ending at a Nash equilibrium of T. This partially answers an open question posed by [52] We prove this result by analytically constructing a satisficing path from an arbitrary initial strategy profile to a Nash equilibrium. Our approach is somewhat counterintuitive, in that it does not attempt to seek Nash cquilibrium by improving the performance of unsatisfied players (players who are not best responding a given strategy profile), but by updating strategies in way that increases the number of unsatisfied players at each round. This tactic leverages the freedom afforded to unsatisfied players to explore their strategy space and avoids the challenge of cyclical strategy revision that occurs when agents attempt to best respond to their counterparts (37]. This insight provides a new approach to MARL algorithm design beyond the well-structured settings considered in prior work.
Notation, We let A A denote the set of probability measures over a set A. For n E N, we let [n) := [1,
.......... 2,,...., .n. For a point x. the Dirac measure centered at x is denoted 8,. When discussing a fixed agent i, the remaining collection of agents are called i's counterparts or counterplayers.
Related Work. A vast number of MARL algorithms have been proposed for iterative strategy adjustment while playing a game. The most widely studied class of algorithms of this type involve each player running a no-regret algorithm on its own stream of rewards. The celebrated fictitious play algorithm (9] and its descendants are special cases of this class. Although the convergence behavior of fictitious play and its variants has been studied extensively, convergence results are typically available

---

only for games exhibiting special structural properties amenable to analysis 25 Indeed, the convergence properties of fictitious play are intimately connected to those of best response dynamics, full information dynamical system evolving in continuous time where the evolution rule for player i's strategy is governed by its best response multi-function. By harnessing such connections, convergence results for fictitious play and a number of other MARL algorithms have been obtained by analyzing the dynamical systems induced by specific update rules (5 49).
29
45
46
A related line of research considers strategic dynamics defined by strategy update functions, taking the form 1 (x(x in discrete time or an analogous form in continuous time. In the case of deterministic strategy updates, [22] studied strategic dynamics in continuous time and showed that the strategy update functions, analogous to I above, satisfy regularity conditions as well a desirable property called uncoupledness, by which f cannot depend on the reward functions of i's counterplayers, then the resulting dynamics are not Nash convergent in general. These results were recently generalized by (38]. Additional possibility and impossibilityy results were presented by (2). who studied strategic dynamics in a different setting, where players do not observe counterplayer strategies. Under stochastic strategic dynamics, a number of positive results were obtained by incorporating exogenous randomness into one's ' strategy update, along with finite recall of recent play 23 19 20]
In the regret testing algorithm of [19], players revise their strategies according to whether or not their most recent strategy met a satisfaction criterion: if zj performed within c of the optimal performance against x; player i continues using it and picks 21+1 = z]. Otherwise, player i experiments and selects x/+1 according to a probability distribution over X Conditional
strategy updates similar to this have appeared in several other works, such as [2] 10 11). and the regret testing algorithm has been extended in several ways [1
A game is said to have the sutisficing paths property if every initial strategy profile is connected to some equilibrium by a satisficing path. As we discuss in the next section, satisficing paths can be interpreted as a natural generalization of best response paths. Consequently, the problem of identifying games that have the satisficing paths property is a theoretically relevant question analogous to characterizing potential games [4]] or determining when game has the fictitious play property The concept of satisficing paths was first formalized in (52) in the context of multi-state Markov games, where it was shown that n-player symmetric Markov games have the satisficing paths property and this fact could be used to produce a convergent MARL algorithm. However, the core idea of satisficing paths appeared earlier, before this formalization: in the convergence analysis of the regret testing algorithm in 19). it was shown that two- -vo-player normal-forn games have the satisficing paths property, though this terminology was not used. These earlier works made no claims about the existence of paths in general-sum n-player games, which is the focus of this paper.
39. 40
2 Normal-form games
A finite, n-player normal- game I is described by list r = (n, A,,,, where n is the number of players, A = A x ... x A" is a finite set of action profiles, and r = (r") (e((xx))) is collection of
reward functions, where r² A + R describes the reward of player as a function of the action profile. The th component of A is player i's action set A'.
Description of play. Each player i E [n] selects a probability vector x' E A& and then selects its action a' according a' x². The vector x' is called player i's mixed strategy, and we denote player i's set of mixed strategies by X' := AAt. Players are assumed to select their actions without observing one another's actions, and the collection of actions {a' E [n]] is assumed be mutually independent. The set of mixed strategy profiles is denoted X : x² X ... ... After the action profile = (a'...., an) is selected, each player i receives reward r r(a)).
Player i's performance criterion is its expected reward, defined for each strategy profile x E X as
RR ( xx Ea~x (a."...,.")],
where Easx signifies that a œ5 for each player j E [n] and we have used the convention that x (z', x and x- = (z'...., ...., x² _++1 .... ..). Since player i's objective depends on the
strategies of its counterplayers, the relevant optimality notion is that of (c-) best responding.
Definition 1. A mixed strategy xt E Exi is called e-best response to the strategy x E X if
(x,, x > R (x' x -E Vx x.
3

---

The standard solution concept for n-player normal form games is that of (c-) Nash equilibrium, which entails situation in which all players are simultaneously (e-) best responding one another.
Definition 2. For 2 a strategy profile x, (ar2, x.) E is called an e-Nash equilibrium if. for every player i E [m), xt, is an e-best response 10 x,
Putting = 0 above, one recovers the classical definitions of best responding and Nash equilibrium. For any c 2 0, the set of c-best responses to a strategy x is denoted BR, (x") C X
2.1 Satisficing Paths
We now present the concept of satisficing paths as generalized best response paths. Definition 3. sequence of strategy profiles (x4)121 in is called a best response path if. for every
t 221 1 and every player E [n], we have
a (some of, E (R)())))
fx, E BR)(x,"), else.
T++ =
The preceding definition of best response paths can relaxed in several ways, and such relaxations are often desirable to avoid non-convergent cycling behavior (see [37 for an example). A common relaxation involves synchronizing players or incorporating inertia, so that only a subset of players switch their strategies at given time, which can be help achieve coordination in cooperative settings [32 48 51. Beyond cooperative settings, the use of best response dynamics to seek Nash equilibrium may not be justified. In purely adversarial settings, for instance, best response paths cycle and fail to converge (3), and some alternative strategic dynamics are needed to drive play to equilibrium. Consider the following generalization of the best response update:
1+1 = Jat (
if of E (x))),)), else.
The update defined above is characterized by "win-stay, lose-shift" principle [T] 44 which only constrains the player to continue using a strategy when it is optimal. On the other hand, the player not forced to use a best response when of BR, (x,"), and may experiment with suboptimal responses according to function f³ X X Allowing the function f' to be any function from X to X one generalizes best response updates and obtains a much larger set of sequences (x))221 and greater flexibility to approach equilibrium from new directions. This motivates the following definition of satisficing paths.
Definition 4. A sequence of strategy profiles (x.) where T E N U (xo), is called a satisficing path if satisfies the following pairwise satisfaction constraint for any player E [m] and any t:
at (R) + sit1 x/.
The intuition behind satisficing paths is that they are the result of an iterative search process in which players settle upon finding an optimal strategy (i.e. a best response to the strategies of counterplayers) but are free to explore different strategies when they are not already behaving optimally. Note, however, that the definition above merely a formal property of sequences of strategy profiles X and is agnostic to how satisficing path is produced. The latter point will be important in the coming sections, where we analytically obtain a particular satisficing path as part of an existence proof.
We note that Condition II) constrains only optimizing players. It does not mandate a particular update for the so-called unsatisfied player i, for whom at & (x, In particular, #|+1 can be any strategy without restriction, and 2 & BR, is allowed. In addition to best response paths, constant sequences (xt)12) with x, = x are always satisficing paths, even when x is not a Nash equilibrium. Moreover, since arbitrary strategy revisions are allowed when player is unsatisfied, if X1 E X a strategy profile for which all players are unsatisfied, then (x1, X²) a satisficing path for any Xg X.
As special case, I may simply be best response selector, recovering the best response update.

---

The game I' has the satisficing paths property if for any E X. there exists satisficing path (x..X.....) such that, for some finite T = T(1)). ) the strategy profile xT a Nash equilibrium
Definition 5.
Satisficing paths were initially formalized in [52]. where it was proved that two-player games and n- player symmetric games have the satisficing paths property. However, whether general-sum n-player games have the satisficing paths property was left as an open question. We answer this open question Theorem presented in the next section.
3 Existence of paths in normal-form games
Theorem 1. Any finite normal-form game T has the satisficing paths property.
Proof sketch. Before presenting the formal proof, we describe the intuition of its main argument. In the proof of Theorem [] we construct satisficing path from an arbitrary initial strategy x1 Nash equilibrium by repeatedly switching the strategies of unsatisfied players in a way that grows the set of unsatisfied players after the update. Once the of unsatisfied players is maximal, we argue that Nash equilibrium can be reached in one step by switching the strategies of the unsatisfied players. The final point represents the main technical challenge the proof, as switching the strategies of unsatisfied players changes the objective functions for the previously satisfied players. We address this challenge by showing the existence
Nash equilibrium on the boundary of a strategy subset in which previously satisfied players remain satisfied.
To give the complete proof, will require some additional notation, detailed below, and some supporting results, detailed in Appendix A and Appendix B
Additional notation. We require notation for the following sets, defined for any X:
Sat(x)= = {i E [r]] x² E BR, ()) and UnSat(x): == [r]] \ Sat(xx..
A player in Sat(x) S [n] is called satisfied (at x), and player in UnSat(x) is called unsatisfied (at x). For x E X, we also define
Access(x) = (y X o = =x 2', Vi E Sat(x))
Access(x) is the subset of strategies that are accessible from strategy x, to mean one can obtain strategy y E Access(x) S X from by switching (at most) the strategies of players who were unsatisfied at x. We define a subset NoBetter(x)) S Accoss(x) as
NoBetter(x) {y E Access(x) x) UnSat(x) S UnSat(y)) { Access (x) Vi Un)at(x), UnSat(y)).
The set NoBetter(x) consists of strategies y that are accessible from x and also fail to improve the status of players who were previously unsatisfied. The set name NoBetter(x)) is chosen to suggest that the players unsatisfied at x are not better off at y NoBetter(x), since they are unsatisfied at both x and We observe x E NoBetter(x)) hence NoBetter(x) is non-empty.
Finally, we define a Worse x) C NoBetter(x)
Worse(x) == {y E NoBetter(x) : UnSat(x) Ç UnSat(y))
= {y E NoBetter(x) E Sat(x) : i UnSat(y)).
The set Worse(x) consists of strategies that are accessible from x, that leave all previously unsatisfied players unsatisfied, and flip at least one previously satisfied player to being unsatisfied. In particular, if E Worse(x), this means [UnSat(y)] > [UnSat(x) + 1. We observe that Worse(x) may be empty, and Worse(x) NoBetter(x) C Access(x).
AA more general definition, involving 2 0 best responding and strategy subsets was studied in 52 In this paper, consider true optimality and no strategic constraints, which additionally aids clarity.
5

---

3.1 Proof of Theorem
Remark In the proof below, we analytically construct a frthfrom x, to a Nash equilibrium. The process of selecting strategies x1, x1;X2, "2, and switching the component stralegy of euch player is done centrally, by the analyst, and should not be interpreted as a learning algorithm.
Proof. X1 E X be any initial strategy profile. We must produce a satisficing path of finite length terminating at Nash equilibrium. Equivalently, we must produce a sequence x1,.... XT with X++1 E Access( xx) for each / and X7 a Nash equilibrium, where the length 7 may depend on X1- In the trivial case that X1 is Nash equilibrium, we put 7 = 1. The remainder of this proof focuses on the non-trivial case, where X₁ is not a Nash equilibrium.
To begin, we produce satisficing path X....., X2 follows. We put & = 1, and while both Sat(x;) A ø and Worse(x,) + Ø, we arbitrarily fix X++1 E Worse(x,) and increment f- t+1 By construction, have
Ø + UnSat(x1) _ UnSatt(x) & UnSat(x.+1)
for each non-terminal iteration I, where the inequality holds because is not a Nash equilibrium. Thus, the number of unsatisfied players is strictly increasing along this satisficing path. Since the number of unsatisfied players is bounded above by and since have assumed UnSat(xx)) ) 2 1, this process terminates in at most n 1 steps. Letting i denote the terminal index of this process, we have k S
By the construction of the path (x1...... xx), (at least) one of the following holds index k: either Sat(x;) = Ø or Worse(X+) = Ø. In other words, either no player is satisfied at Xg, or there is no accessible strategy that grows the subset unsatisfied players.
Case 1: Sat(xx) = Ø, and all players are unsatisfied at Xk- In this case, we may switch the strategy of each player i E [n]] to any successor strategy. That is, Access(xx) X. We fix arbitrary Nash equilibrium z., put X++1 2. and let T = k - 1. Then, (X1...., xT) is a satisficing path terminating at equilibrium.
Case 2: (x+) # @ and Worse(xx) = Ø. In this case, there are no accessible strategies that strictly grow the set of unsatisfied players.
Ø, the following holds: for any strategy y E NoBetter(xx) and any satisfied player i E (xx). we have that i E Sat(y). (Otherwise, if i UnSat(y), then y E &Worse(xx) since it flipped a satisfied player. But this contradicts the emptiness of Worse(Xx).)
Since Worsc(x;)
We now argue that there exists strategy profile x, accessible from X such that all players unsatisfied Xg are satisfied x.. That is, there exists an accessible strategy x, Access (xx) such that
UnSat(xx)) C (at(x.).
To see that such a strategy x. exists, note that fixing the strategies of the players satisfied at Xx defines new game, say I' with n players, and the new game I' admits Nash equilibrium x, = (#f) )eUuSSa(xe)) We extend x, to strategy profile in the larger game I' by putting ø! = o UnSat(xx). By construction,
for players& i E Sat(x:) while putting x! . for players holds.
have that x E BR/ (x,² for each j UnSat(xx),
From (2 it clear that x, & NoBetter(xx). since NoBetter(xg) consists of strategies accessible from Xạ in which unsatisfied agents remain unsatisfied, while the previously unsatisficd agents are satisfied at x.. We now state a key technical lemma, which asserts that although x, does not belong to NoBeeter(xx)), it is limit point of this set. A proof of Lemma given in Appendix
Lemma 1. If Worse(xxx) Ø, then there exists sequence {yr) with y: E NoBetter(xs)) for each t, such that lim Yt = X..
We will argue that x, is a Nash equilibrium for the original game r. For each player i E [n]. we introduce function Fs X - Ie given by ((xxx-1) max,'ea' (,,'",,, for each x (xt,, E X. The functions (F ] have the following useful properties, which are well known (35). and are summarized in Appendix A For each player E [n]: (a) F² is continuous
R x x)),

---

on X; (b) ('(x) 2 0 for all x X; (c) for any x ' E X strategy x' is a best response to x if and only (x''
0.
Let (-)) be a sequence in NoBetter(xe) converging to x,, which exists by Lemma | For any previously satisfied player i Sat(x;), since Worse(x*) Ø and Yt NoBetter(xx, (xx), from previous observation, we have that i E (y)( Equivalently, zi. (y Re-writing this using
the function F* and the notation yd = z for satisfied players E Sat(xx). we have F (3 = for all E N and for any E Sat (x+). By continuity of 1S, we have
0 lim (y.)) F (Jiin yz) Fxx)); 10000
establishing that player satisfied at x., and thus that (xt( C (x.) Then, by 2 we had Un C Sxt( hence Sat(x.) = [ri], and x, is Nash equilibrium accessible from X₃-- We put T and Xy = x,, which completes the proof, since (x1,...,Xy) is a satisficing path terminating at a Nash equilibrium.
3.2 Algorithmic insights from the proof of Theorem 1
When coupled with a MARL algorithm that uses an exploratory satisficing strategy update, play will be driven along satisficing paths. Theorem shoows that for any starting strategy profile, some such path connects the strategy profile to an equilibrium, and so a sufficiently exploratory strategy update may drive play to equilibrium along satisficing path. This offers important insights for the design of MARL algorithms. The first takeaway from Theorem is that play can be driven to equilibrium by changing only the strategies of those players who are not best responding. In particular, this means that a satisfied agent does not need to continue updating its strategy after becomes satisfied. As we will discuss in the next section, this property is helpful in distributed and decentralized multi-agent systems, where agents are able to assess whether they are satisfied but may not be able to assess whether the overall system is at equilibrium.
second, more subtle takeaway comes from the proof of Theorem I and relates the unorthodox and counterintuitive exploration scheme used to drive play to equilibrium. In the proof, one sees that suboptimal-ant perhaps even awarrddeeteriorating--- strratggi updates were key to driving play to equilibrium along a satisficing path. As we outline below, this construction runs against the conventional approaches to designing MARL algorithms, and it can be used to avoid common pitfalls of MARL algorithms such as cyclical behavior.
At high level, many existing multi-agent learning algorithms update the strategy parameter in a reward-improving direction at each step. A related approach, described earlier, increments the strategy parameter
regret-minimizing direction, which has a similar effect. While such algorithms are sensible from the point of view of single self-interested individual, they may fail to drive play to a Nash equilibrium when all players adopt similar algorithms [36] 18 37]. To address this non-convergence issue, one recurring algorithmic modification involves manipulating step sizes, either with mixture of fast agents and slow agents [3] or with each individual varying its step sizes according to its performance [8] However, such approaches only come with provable convergence guarantees in select subclasses of games with exploitable structure. In instances where step size manipulation does not (or cannot) yield convergence, the analysis of Theorem | may offer an alternative route to algorithm modification.
With these two takeaways in mind, we envision at least two design principles that will be useful for future MARL algorithms. First, strategic updating may incorporate some measure of randomness when a player is not satisfied. This principle has been previously used with some success, but comes with drawback relating complexity. A second principle, which we believe be new, leverages the second takeaway above, involving counterintuitive path construction: players may alternate between seward-impovving periods (during which strategy updates are done in a conventional way and/or
that improves the agent's 's reward) and suboptimal periods (during which random strategy updates may be used). The timing of such periods or the extent of the randomness in strategic updates may be made to depend on whether cycles in the strategy iterates were detected. By incorporating suboptimal exploration in an adaptive manner, a MARI, algorithm can break cycles as needed but rely conventional algorithms the remainder of the time.
7

---

4
Discussion
Extension to Markov games
This paper focused normal-form games with finitely many actions per player due to the central position that normal-form games occupy in game theory. Indeed, insights and intuition developed in normal-form games helpful for understanding more complex models of strategic interaction. Of special note, finite normal-form games can be generalized to model dynamic strategic environments where rewards and environmental parameters evolve over time according to the history of play. We now describe the extension of Theorem to Markov games, one generalization of finite normal-form games that is popular model in MARL. Due to space limitations, formal model for Markov games is postponed to Appendix C
In n-player Markov game, agents interact across discrete time. Each agent i [nx] observes sequence of state variables {st taking values in a finite state space and selects a sequence of actions {ai taking values in finite action set A'. In this dynamic model, player i's reward in period t, denoted r (st, at), depends on both the action profile a, and also on the state st- The state process evolves according to (jointly controlled) transition probability function T as 8141 (- a.). Rewards are discounted across time using a discount factor y E (0, 1), and player i attempts to maximize its expected 7-discounted return. In this generalization of finite normal-form games, policies (defined as mappings from states to probability distributions over actions) generalize mixed strategies, and the solution concept of Markov perfect equilibrium refines the concept of Nash cquilibrium and serves as a popular stability objective for MARL algorithm designers [53].
Partial results for multi-state Markov games have previously been obtained in special classes of games and used produce MARL algorithms 52. The analysis presented in this paper uses a rather different approach that seems promising for extending those results. In the proof of Theorem [ we used functions 3== characterize best responding in finite normal-form game. In fact, analogous functions can also be obtained for policies in multi-state Markov games, and these functions (c.f. [52 Lemmas 2. 2.10-2.13 13]). For this reason, and due to the central role of continuity in our proof, it seems likely that Theorem [ can be extended to general-sum Markov games. However, one aspect of the extension remains open, namely the generalization of Lemmal I In Appendix C we describe the issue that precludes direct generalization our normal-form proof of Lemma] I but we note that this appears to be related only to the proof technique rather than a fundamental obstacle to the generalization.
satisfy the same desired properties invoked in the proof of Theorem [
On decentralized learning
Multi-agent reinforcement learning algorithms based on the "win-stay, lose-shift" principle char- acteristic of satisficing paths are especially well suited to decentralized applications, since players are often able to estimate the performance of their current strategy as well as the performance of an optimal strategy, even under partial information. In decentralized problems, coordinated search of the set X of strategy profiles for a Nash equilibrium is typically infeasible, and players must select successor strategies in a way the depends only on quantities that can be locally accessed or estimated.
For instance, consider trivial coordinated search method, where player selects w441 uniformly random from X whenever x, was not Nash equilibrium and selects o/ - =f only when x, is Nash equilibrium. This process is clearly ill suited to decentralized applications, because player i's strategy update depends on both a locally estimable condition (whether player is best responding to x,' well as condition that cannot be locally estimated (whether another player j is best responding to x The satisfaction (win-stay stan-stay constraint plays key role local stopping condition for satisficing paths, and rules out coordinated search of the set X such as the trivial update outlined above. Examples of decentralized or partially decentralized learning algorithms leveraging satisficing paths in their analysis include 19 33 52 The analytic results of this paper suggest that algorithms such as these can be extended to wider classes of games and enjoy equilibrium guarantees under different informational constraints on the players.
8

---

On complexity and dynamics
In Theorem we showed that for any finite n-player normal-form game I' and any initial strategy profile X1 E X. there exists a satisficing path Xi....,, XT of finite length 7 = T(11) terminating at Nash equilibrium Xy. From the proof of Theorem [ one makes the following observations. First, the length of such a path can be uniformly bounded above as T(x1) I n. Second, there exists collection of strategy update functions {L X -> X [n|} whose joint orbit is the satisficing path described by the proof of Theorem I That is, (+xx) = xi- for each player i E [n], every 0 S t S T - 1, and every x, X, where of is player i's component of x, in the satisficing path initialized at X1-
The proof of Theorem is is semi-constructive. At each step along the path, we describe how the next strategy profile should be picked (c.g. Xt+1 E (x:)s but we do not suggest an algorithm for computing it. In at least one place, namely Case I where we put XT := Z. the path construction involves moving jointly to Nash equilibrium in one step. The computational complexity of such step is prohibitive [13], underscoring that ours is analytical existence result rather than computational prescription.
Although we have shown that there exists a discrete-time dynamical system on X that converges
to Nash equilibrium n steps and can be characterized by update functions {ff 1 we note that
our possibility result does not contradict the impossibility results of [2 2 or [38]. In particular,
the functions 1.
{f need not be (and usually will not be) continuous, violating the regularity
conditions of [ and [8], and furthermore the functions {/+) 1n depend crucially on the game I'
in way that violates the uncoupledness conditions of 22 and 22.
Open questions and future directions
Several interesting questions about satisficing paths remain open. We now briefly describe some that we find especially practical or theoretically relevant.
While this paper dealt with satisficing paths defined using best responding constraint, the original definition was stated using an e-best responding constraint, according to which a player who was e-best responding was not allowed switch its strategy. Putting O, one recovers the definition used here, but one may also select c >> 0, which can be desirable to accommodate for estimation error in multi-agent reinforcement learning applications. The added constraint reduces freedom to switch strategies, and thus makes it more challenging to construct paths starting from a given strategy profile. On the other hand, the collection of Nash equilibria is a strict subset of the set of c-Nash equilibria, and one can attempt to guide the process to different terminal point in larger set. At this time, it is not clear to us whether the main result this paper holds for small e > O. It is clear, however, that the proof technique used here will have to be modified, since we have relied on Lemma [ whose proof involved an indifference condition and invoked the fundamental theorem of algebra, and relaxing to >>0 0 would render such argument ineffective.
second interesting question for future work whether multi-state Markov games with n > players have the satisficing paths property. The case with n = 2 was resolved by [52), but the proof technique used there did not generalize to n 2 3. By contrast, our proof technique readily accommodates any number of players, but is designed for stateless normal-form games. Our proof used multi-linearity of the expected reward functions ( ) which does not generally hold in the multi-state setting.
In this work, satisficing paths were defined in a way that allowed an unsatisfied player i change its strategy to any strategy in its set X", without constraint. This is interesting in many problems where the set of strategies can be explicitly and directly parameterized, but may be unrealistic in games where the set of strategies is poorly understood or in which a player can effectively represent only a subset of its strategies y S. X². In such games, the question more relevant for algorithm design is whether the game admits satisficing paths to equilibrium within the restricted subset ) x ... x )" This point was implicitly appreciated by both 119 and 20 and explicitly noted (52). Some negative results were recently established in [50] for games admitting pure strategy Nash equilibrium when randomized action selection was not allowed and the constrained set was given by ) A
underscoring the importance of the topology of the sets appearing in the proof of Theorem
9

---

Conclusion
Satisficing paths can be interpreted as natural generalization best response paths in which players may experimentally select their next strategy in periods when they fail to best respond to their counterplayers. While (inertial) best response dynamics drive play to equilibrium in certain well- structured classes of games, such potential games and weakly acyclic games [166], the constraint of best responding limits the efficacy of these dynamics in games with cycles in the best response graph [43]. In such games, best response paths leading equilibrium do not exist, and multi-agent reinforcement learning algorithms designed to produce such paths will not lead to equilibrium.
In this paper, we have shown that every finite normal-fom game enjoys the satisficing paths property. By relaxing the best response constraint for unsatisfied players, one ensures that paths equilibrium exist from any initial strategy profile. Multi-agent reinforcement learning algorithms designed to produce satisficing paths, rather than best response paths, thus do not face the same fundamental ob- stacle of algorithms based on best responding. While algorithms based satisficing have previously been developed for two-player games normal-form games, symmetric Markov games, and several other subclasses of games, the findings of this paper suggest that similar algorithms can be devised for the wider class of n-player general-sum -um normal- formal-form games.
References
[1] ARSLAN, G., AND YÜKSEL, S. Decentralized Q-learning for stochastic teams and games. IEEE Transactions on Automatic Control 62, 4 (2017), 1545-1558.
[2] BABICHENKO, Y. Completely uncoupled dynamics and Nash equilibria. Games and Economic Behavior 76, (2012), 1-14.
[3] BALCAN, M.-F., PUKDEE, R., RAVIKUMAR, P., AND ZHANG, H. Nash equilibria and pitfalls of adversarial training in adversarial robustness games. In International Conference on Artificial Intelligence and Statistics (2023), PMLR, pp. 9607-9636.
[4] BAUDIN, L., AND LARAKI, R. Fictitious play and best-response dynamics identical interest and zero-sum stochastic games. In International Conference on Machine Learning (2022), PMLR, pp. 1664-1690.
[5] BENATM, M., HOFBAUER, J., AND SORIN, S. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization 44, (2005), 328-348.
[6] BLUME,, I.. E. The statistical mechanics of strategic interaction. Games and Economic Behavior
5, (1993), 387-424.
[7] BOSE, J., GIDEL., G., BERARD, H., CIANFLONE,, A., VINCENT, P., LACOSTE--JULIEN, S.,
AND HAMILTON, W. Adversarial example games. Advances in Neural Information Processing Systems 33 (2020), 8921-8934.
[8] BOWLING, M., AND VELOSO, M. Multiagent learning using a variable learning rate. Artificial Intelligence 136, (2002), 215-250.
[9] BROWN, G. W. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation 13, 1 (1951), 374.
[10] CANDOGAN, O., OZDAGLAR, A., AND PARRILO,
Near-potential games: Geometry and dynamics. ACM Transactions Economics and Computation (TEAC) 1, (2013), 1-32.
[11] CHASPARIS, G. C., ARAPOSTATHIS, A., AND SHAMMA, J. S. Aspiration learning in coordination games. SIAM Journal on Control and Optimization 51, 1 (2013), 465-490.
[12] CHIEN, S., AND SINCLAIR, A. Convergence to approximate Nash equilibria in congestion games. Games and Economic Behavior 71, 2 (201 1), 315-327.
[13] DASKALAKIS. C., FOSTER, J., AND GOLOWICH, N. Independent policy gradient methods for competitive reinforcement learning. Advances Neural Information Processing Systems 33 (2020), 5527-5540.
[14] DASKALAKIS, C., FRONGILLO, R., PAPADIMITRIOC, H., PIERRAKOS, G., AND VALIANT, G. On learning algorithms for Nash equilibria. Algorithmic Game Theory: Third International Symposium (2010), Springer. pp. 114-125.
10

---

[29] LESLIF, D. S., AND COLLINS, E. J. Generalised weakened fictitious play. Games and [15] DASKALAKIS, C., GOLDBERG, P. W., AND PAPADIMITRIOU, C. H. The complexity of computing a Nash equilibrium. Communications of the ACM 52, 2 (2009), 89-97.
[16] FABRIKANT, A., JAGGARD, A. D., AND SCHAPIRA, M. On the structure of weakly acyclic games. In Algorithmic Game Theory: Third International Symposium (2010), Springer, pp. 126- 137.
[17] FLOKAS, L.., SANTAKISGGKARAGKOON
E.- E.-V., LIANEAS, T., MERTIKOPOULOS, P., AND PILIOURAS, G. No-regret learning and mixed Nash equilibria: They do not mix. Advances in Neural Information Processing Systems 33 (2020), 1380-1391.
[18] FLOKAS, L., VLATAKIS KLATAKIS-GKARAGKOUUS GKRRGKOUUSSS,, E.-V., AND PILIOURAS, G. Poincaré recurrence. cycles and spurious equilibria in gradient-descent-assee for non-convex non-concave zero-sum games. Advances in Neural Information Processing Systems 32 (2019).
[19] FOSTER, D., AND YOUNG, H. P. Regret testing: Learning to play Nash equilibrium without knowing you have opponent. Theoretical Economics 1, (2006), 341-367.
[20] GERMANO, F., AND LUGOSI, G. Global Nash convergence of Foster and Young's ' regret testing. Games and Economic Behavior 60, 1 (2007), 135-154.
[21] GRONAUER, S., AND DIEPOLD, K. Multi-agent deep reinforcement learning: A survey. Artificial Intelligence Review (2022), 1-49.
[22] HART, S., AND MAS-COLELL, A. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review 93, 5 (2003). 1830-1836.
[23] HART, S., AND MAS-COLELL, A. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economic Behavior 57, (2006), 286-303.
[24] HAYES, C. F., RÄDULESCU, R., BARGIACCHI, E.., ET AL. A practical guide multi-objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems 36, 1 (2022), 26.
[25] HOFBAUER, J., AND SANDHOLM, W. H. On the global convergence of stochastic fictitious play. Econometrica 70, 6 (2002), 2265-2294.
[26] HSIEII, Y.-G., ANTONAKOPOULOS, K., AND MERTIKOPOULOS, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In Conference on Learning Theory (2021), PMLR, pp. 2388-2422.
[27] JAFARI, A., GREENWALD, A., GONDEK, D., AND ERCAL, G. On no-regret learning, fictitious play, and Nash equilibrium. In International Conference on Machine Learning (2001), vol. 1, pp. 22-222-333 2233.
[28] LESLIE, D. S., AND COLLINS, E. J. Individual Q-leariing in normal form games. SIAM Journal on Control and Optimization 44, (2005), 495-514.
Economic Behavior 56, 2 (2006), 285-298.
[30] LEVY, Y. Discounted stochastic games with no stationary Nash equilibrium: Two examples. Econometrica 81, 5 (2013), 1973-2007.
[31] LU, Y. Two-scale gradient descent ascent dynamics finds mixed Nash equilibria of continuous games: A mean-field perspective. In International Conference on Machine Learning (2023), PMLR, pp. 22790-22811.
[32] MARDEN, J. R., AND SHAMMA,, J. S. Revisiting log-linear learning: Asynchrony, com- pleteness and payoff-based implementation. Games and Economic Behavior 75, 2 (2012).
[33] MARDEN, J. R., YOUNG, H. P., ARSLAN, G., AND SHAMMA, J. S. Payofff based dynamics for multiplayer weakly acyelic games. SIAM Journal on Control and Optimization 48, 1 (2009), 373-396.
[34] MARDEN, J. R., YOUNG, H. P., AND PAO, L. Y. Achieving Pareto optimality through distributed learning. SIAM Journal on Control and Optimization 52, 5 (2014), 2753-2770.
[35] MASCHLER, M., ZAMIR, S., AND SOLAN, E. Game Theory. Cambridge University Press,
2020.

---

[36] MAZUMDAR, E., RATLIFF, L. J., AND SASTRY, S. S. On gradient- baadee learning in continuous games. SIAM Journal on Mathematics of Data Science 1 (2020), 103-131.
[37] MERTIKOPOULOS, P.. PAPADIMITRIOU, C., AND PILIOURAS. G. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (2018), SIAM, pp. 2703-2717
[38] MILIONIS, J., PAPADIMITRIOU, C., PILIOURAS, G., AND SPENDLOVE, K. An impossibilitty theorem in game dynamics. Proceedings of the National Academy of Sciences 120, 41 (2023).
[39] MONDERER, D., AND SELA, A. A 2 game without the fictitious play property. Games and Economic Behavior 14, (1996), 144-148.
[40] MONDERER, D., AND SHAPLEY, L. S. Fictitious play property for games with identical interests. Journal of Economic Theory 68, (1996), 258 358.665.
[41] MONDERER, D., AND SHAPLEY, L. S. Potential games. Games and Economic Behavior 14, 1 (1996), 124-143
[42] NowÉ, A., VRANCX, P., AND DE HAUWERE, Y.-M. Game theory and multi-agent reinforce- ment learning. Reinforcement Learning: State-of-the-Ar (2012), 441-470.
[43] PANGALLO, M., HEINRICII T., AND DOYNE FARMER, J. Best reply structure and equilibrium convergence in generic games. Science Advances 5, 2 (2019).
[44] POSCII, M. Win-stay, lose-shift strategies for repeated mames-memory length, aspiration levels and noise. Journal of Theoretical Biology 198, 2 (1999), 183-195.
[45] SAYIN, M. O., PARISE, F., AND OZDAGLAR, A. Fictitious play in zero-sum stochastic games. SIAM Journal on Control and Optimization 60, 4 (2022), 2095-21 14.
[46] SAYIN, M. O., ZIIANG, K., AND OZDAGLAR, A. Fictitious play in Markov games with single controller. In Proceedings of the 23rd ACM Conference on Economics and Computation (2022), pp. 919-936.
[47] SINGH, S., KEARNS, M. J.. AND MANSOUR, Nash convergence of gradient dynamics in general-sum games. In Uncertainty in Artificial Intelligence (2000), pp. 541-548.
[48] SWENSON, B.. EKSIN, C., KAR, S., AND RIBEIRO, A. Distributed inertial best-response dynamics. IEEE Transactions on Automatic Control 63, 12 (2018), 4294-4300.
[49] SWENSON, B., MURRAY, R., AND KAR, On best-response dynamics in potential games. SIAM Journal on Control and Optimization 56, 4 (2018), 2734-2767.
[50] YONGACOGLU, B., ARSLAN, G., PAVEL, L., AND YÜKSEL, S. Generalizing better response paths and weakly acyclic games. In IEEE 63rd Conference on Decision and Control (To Appear, 2024).
[51] YONGACOGLU, B., ARSLAN, G., AND YÜKSEL, S. Decentralized learning for optimality in stochastic dynamic teams and games with local control and global state information. JEEE Transactions on Automatic Control 67, 10 (2022), 5230-5245.
[52] YONGACOGLU, B., ARSLAN, G., AND YÜKSEL, S. Satisficing paths and independent multiagent reinforcement learning in stochastic games. SIAM Journal on Mathematics of Data Science 5, 3 (2023), 745-773.
[53] ZHANG, K., YANG, Z., AND BAŞAR, T. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control (2021), 321-384.
Appendix: Proofs of technical lemmas
We now discuss the properties of the auxiliary functions {F* : : [n]] that were used in the proof of Theorem and we prove Lemmal]
We remark that for each player E [n], we identify their set of mixed strategies X = -Ag with the probability simplex in R& Thus, 2 inherits the Euclidean metric from I |A'l, Neighbourhoods and limits in 8 (or its subsets) are defined with respect to this metric. Similarly, we inherit a Fuclidean
metric for X. For 0, we let Nx(x) denote the g-neighbourhood of the strategy profile X.
12

---

A Properties of the auxiliary functions
We begin by discussing the properties of the auxiliary functions {4* E [n]]. as they are relevant to characterizing best responses. The facts below are well known. For reference, see the text of [35]
Recall that for each player i [n], the function F X R is defined
F' x max E'EA'
(6ai, (x E X.
We now show that for any E [n]] the following hold:
a. F is continuous on X,
b. ['xx 2 for all x E X, and
c. For any x E X- a strategy x² is best response x and only if Fi(x", x- 0.
The expected reward function (x) Earx [r'(a)]
can be expressed as sum of products:
(x)x) Σ r'(a)) a~x (a ā) REA
Σ aeA
raaa at) II r' (T'), V
From this form, is immediate that H² is continuous on X. Moreover, can easily be shown that Ri is multi-linear in x. That is, for any E [m], fixing x x we have that x + R' R'xx', x) 9) is linear
Since R' is continuous X and A is finite set, one has that the pointwise maximum of finitely many continuous functions is continuous. Thus, the function
x x b max R' ( a'Es
is continuous X- Since F² F* (x²xx-*)= max Ie (ōg., x (xr,xx is the difference of continuous functions, F is also continuous. This proves item
From the multi-linearity of R', we have that, for fixed x i E X-i the optimization problem supzigx R' R'(x", ") equivalent to linear program
1,
sup W. 2 x' ER
subject to
where "'x- E ARA' is a vector defined by "xx-(aa) == R (5,,, x
The vertices of the feasible set for the latter linear program are precisely the points (5. a² E At). This implies that max, Ht' (6,r, 2 [2" x²) for any x', x',x - Items b and e follow. From this formulation, one can also see that player E [n] is satisfied at x X if and only if its strategy x' is supported on the set of maximizers argmax, ea (6.r, x x=)
B Proof of Lemma I
Recall that the proof of Theorem I x, was defined be some strategy accessible from X₃ X such that all players unsatisfied at X₁. were satisfied at The statement of Lemma [ following.
was the
Lemma If Worse(xx) Ø, then there exists sequence {y:) with y: NoBetter(xx) for each I, such that lim Yt X..
Proof. Suppose, the contrary, that no such sequence exists. Then, there exists some Ç 0 such that for every E Access(xx) n (x.)). one has z & NoBetter(xx). That is, some player unsatisfied at
'Of course, scaling inputs of Ht means the resulting argument is no longer probability vector. However. simply linearly extend Rt to be function on R.d, where d Σ A2
13

---

XR is satisfied at z. Equivalently, for some E UnSat(X;), we have 2' E BR (z "). This implies that for that player i, that value of Ç, and the strategy profile (2* z Nx(x)., supported on the set argmax, {It (6gi, z {)
For each & 2 0, we define strategy profile we E X as follows:
(1 - E)at + {Uniform(A'), if E UnSat(xx)
else.
Note that we have defined w = o for i E Sat(xx); which to say that we change only the strategies of the unsatisfied players, meaning we E Access(xx). We will show that i > 0 is sufficiently small, then continuity of the functions {F" NE|u) guarantees that We E NoBetter (xx).
Indeed, player i E [n]] is unsatisfied at x5 if and only if it fails to best respond, z & (RR(xx))) ) Using the function Ft, this is equivalent to ( Xx > 0. For each player i E UnSat(x:), let o; > be such that (xxx) 2 02 > 0. Define ō = min for : UnSattxx)).
The following statement holds by the continuity of the functions {F*)= for each player i E [n]. there exists e; > such that if strategy profile x belongs to the e, neighbourhood of X2 (i.e. E Ne, (x)), then (x) (xx)) < a Since Fx (x(x) 2 o. it follows that ['x) 5/2 > 0,
and player is not best responding at x E (x).
Let ē min : E [n]]. By taking & < é/ E/(2n), one has that We E (xxxxx). From the preceding remarks, one can see that UnSat(Xx) S UnSat(we), since all players who were unsatisfied at
X₁ remain unsatisfied at we. Since w = oe for any player j E Sat(x:), one also has that Wg Axcess(Xx). These two parts combine to show that Wg E NoBetter(xx).
Fixing & 0 at sufficiently small value (E E (0, 2/2)), the preceding deductions show that Wg E (xoBette(xx)). By the earlier discussion, we have that We $ Nx(x)..
very important aspect of this construction that wf (at) > 0 for each i E UnSat(Xx) and action a' E A', so that w is fully mixed for each player who was unsatisfied at X2-
Next, for each E [0, 1] and player E Un we define
2 (1 A)xr Aue.
We also define =f = z for players i E Sat(x:). For sufficiently small values of X. say À S 2, we have that ny E (x.), which implies 2A & NoBetter(xx).
This implies that there exists a player it e UnSat((x)) for whom
o E <'BR'' (2)") for infinitely many A E (0,
(The existence of such a player is perhaps not obvious. As we previously noted, for À X, we have ZA & NoBetter(xs), which means there exists some player (A) that was unsatisfied at x; and is satisfied at иx. The identity of this player may change with X. To see that some partieular individual must satisfy this best response condition infinitely often, one can apply the pigeonhole principle to the set (X, X/2, 1/mm) for arbitrarily large m.)
By our definition of 2f as a convex combination involving Uniform(A")) we have that 2f is fully mixed and puts positive probability each action in A Using the characterization involving ( and the fact that 21 is fully mixed together imply that
Fri, the fact that ox E BRY"
Rel (oa, 2 = R² (oar, 2x
st ) for any a, a' E At".. This can be equivalently re-written as II (1 (a²) )a)(
Σ rdd (a,a
Σ
(d',a (1))
II { (1- {)oo(aa Auo (a²)
just
Σ
(a, = pd (a', a1))
II {11 2)rd(aa) + >ueg(a')) (3)
14

---

for any d' E A."..
The lefthand side of the final equality (3) is a polynomial in À of finite degree, but admits infinitely many solutions (from our choice of i. This implies that it is the zero polynomial. In turn, this implies that the left side of (3) holds for any À E [0. 1J, and in particular for À 1. This means =f e BR (z] meaning ž1 & NoBetter(xt). On the other hand, we have 21 = Wg E NoBetter(Xx)) contradiction.
Thus, we see that there exists a sequence {y:]==1 with yz E NoBetter(xs) for i, such that lim Y+ X+.
C Markov games: model and connections to Theorem
Markov games are popular model in the field of multi-agent reinforcement learning. Since the model is quite standard, we offer short description of the fundamental objects and notations, and we then describe connections between Theorem ! and a possible extension to multi-state Markov games.
A Markov game with players and discounted rewards is described by a list G = (n, A, 7). where S is finite set of statess, A A ... A" a finite set of action profiles, and r (r') )== is collection of reward functions, where r² S A - R describes the reward to player A transition probability function T P(S|S A) governs the evolution of the state process, described below, and discount factor y E (0, 1) is used to aggregate rewards across time.
Description of play. Markov games are played across discrete time, indexed by L N. At time I, the state variable is denoted 8, E S and each player E [rx] selects an action af E A according to distribution 7' (-]st): at (-(ss) The transition probability function π E P(A'(S) called player i's policy, and we denote player i's set of policies by II == P(Á"SS) For any time t N. the collection of actions {a] mutually conditionally independent given sy. Upon selection of the action profile a, := (ai) each player i receives the reward r (s(s,, at), and the state transitions from 8, to 8t-1 according to 8t+1 ~ (-))),,a)).
Player i's performance criterion is its expected dddicountedd return, which depends on the state variable and the collective policy profile isolate player i's policy. We let := III x ... x Il denote the set of policy profiles. For each pair (xr, 8) II 8, player i's expected 7-discounted return is given by
(m ..... T"), which also denote by (T² . --) to
V' -.. .ss = EN
(' az)
1=1
where Exr denotes that for every / 2 1, we have that of ~ (110)) for each player j E [n] and, implicitly, 8141 T[- ar). Definition 6. For e 2 O, a policy oi E IT' is called an c-best response to π if
(i (1 V (T', π (,,) - Vx E III,
Vs E
Definition 7. For O, policy profile n. (T)) E IT's is called Markov perfect equilibrium if. for each player E [n], n. is an c-best response to क..
Putting 0 into the definitions above, recover the classical definitions of best responding and
Markov perfect equilibrium. In analogy normal-form games, we use BR BRi(T") (1) C II' to denote player i's set of beest-responses to a given counterplayer policy profile π
Remarks on Markov games
As is conventional in the literature on MARL, we focus on policies that are stationary. Markovian, and possibly randomized. That is, we focus on policies for player i that map states 8, S distributions over the agent's action set A* and sample each action a; from that distribution in time-invariant and history-independeent manner. principle, agents could use policies that depend also on the time index / or on the history of states and actions. However, the bulk of works on MARL consider this simpler class of policies and this is justifiable for several reasons. We refer the reader to 30) for summary of such justifications.
15

---

Markov games generalize both normal-form games (taking the state space S to be singleton) and also MDPs (taking the number of players 1). Moreover, when player i's counterplayers follow a stationary policy π - II as assumed in this work, player i's stochastic control problem is equivalent single-agent MDP (whose problem data depend on ") follows that player i's set of (stationary) best responses to is non-empty. Furthermore, player i's best response condition can be characterized using the familiar action value (Q-) functions of reinforcement learning theory. We briefly summarize this below.
In addition the objective criterion V' -.. which called the value function, we may also define the action value function Q' for player i as
(
s,,') En
Σ
x (s ax)
=s s
1=1
for (I" ") E II, (s E 8 A We further define an optimal action value function for player i against nー
" denoteed Q v.
(x- a²) = max Q' n. s,,"", V(s, ESX =iell
For any policy (m², conditional expectations as V (TT, = En r' is s)Q' (TI 8, a'). From this, it follows that
express player i's value function using its Q-function and
max O ( max Vi n. EIP
s), Vs E.
a' EA
This equality allows us to characterize best responses using a function s : II + R, analogous to the function F appearing in the normal-form case. We define f'(TT) as
(' n = max
max O (5, - ('(TT s) V
sES
The functions {f'} Fi=i defined above possess the three properties required of the functions [Fi) in the proof of Theorem 1 (a) f is continuous on II [52 (b) f'( 2 for all π E n
and (c) f'(r", π 1) 0 if and only if n is best response to
On extending Theorem to Markov games
We now turn our attention to the task of extending Theorem T to Markov games. Following the proof of Theorem [ virtually all steps can be reproduced in the multi-state setting. To begin, one can construct satisficing path TT, N2, ... T& by growing the set of unsatisfied players at each iteration until either UnSat(Tr (Tx)) = [n]] or Worse(T = Ø. the latter case, one can consider the subgame involving only the players in UnSat (T)) and obtain Markov perfect equilibrium म. for that subgame, which can then be extended to policy profile n. E Access(TT)) (T:) by putting
if UnSat(TT),
if Sat(me).
n R
To complete the extension of Theorem to Markov games, one must show that this policy π,, E II is Markov perfect equilibrium of the n-player Markov game. Since the functions {f also satisfy the continuity and semi cemi-definiteness properties described in Appendix A one possible technique for completing this proof involves showing that the policy π, is limit point of the set NoBetter(mT In other words, one possible technique for completing this proof requires extending Lemma to the multi-state case.
Up to this point, analysis parallel. However, it is in the extension of Lemma] | that the presence of state leads to a discrepancy the analysis that will necessitate novel proof technique for the extension of Theorem Markov games. We elaborate below on this discrepancy.
stateless case
multi-state case have been conducted perfectly in
16

---

Normal-form game analysis. In the context of finite normal-form games, our proof of Lemma | in Appendix [ involves proof by contradiction that exploits the explicit form of an indifference condition in the stateless case. In simple terms, if player i is best responding and placing positive probability on every action, then any two actions offer equal expected payoff. symbols, we note that RC ( x) = R' (8ag, x) and only if
Σ
[r' a r' r' a ')] Px (a-)(
EAA
(a(aaj r' rab, a a²)] [I = O.
For reasons that will be clarified below, we refer to the expressions [r' . a a) (a a a] as coefficient terms, and we refer to the terms Px + (a = I[i {ar (a')} as strategy durategy-dependent terms. We remark that in the case of normal-form games, the coefficient terms above do not depend on the strategy x x
Our proof of Lemma in Appendix B considered a one ane-paraeeter family of strategies parameterized by À E [0, 1]. As part of an intricate proof by contradiction, we obtained an indifference condition, (3). for a player it who played each action with positive probability while also best responding. Due
to the explicit parameterization by À of the strategy 2.,, we able to recognize that the indifference condition in (3) is characterized by the roots of a polynomial in A. Critically, the lefthand-side of (3) a polynomial in À because the coefficient terms do depend on the strategy z and hence do not depend on A, while the strategy-dependee terms are polynomials in X.
Markov game analysis. By contrast, Consider an agent who is best responding to a policy π - and places positive probability on actions aj and a in state The optimality condition is turned into indifference condition between of and a² in state as follows:
study indifference conditions in Markov games.
(= (8,
max (x.-((s,a)) a'EA'
One can show that Q satisfies the following equality for any (s,a") E ESx
(s. = Σ
r' (ss, a +
a'' a² max
1 at) Pr Pa (ss),
of EA
sEES
where Pr (a- - 11 T² (a'ls) denotes the probability of the action profile a in state under policy æ. analogy to the normal-form case, we refer P (1a)) the strategy-dependens term and we refer to the term enclosed in square brackets as the coefficient term. However, unlike the normal-form case, here is clear that the (so-called) coefficient term also depends on the policy л through the term maxa; EA Q (s, ..).
Suppose now that we obtain a one me--aarameter family of policies { [w : : X 1] parameterized by some À E [0, 1]. in analogy to our construction of nı in Appendix B Since the coefficient term depends on the policy of player i's counterplayers, one has that the indifference condition
0²,' (s, 0 _ (s,
cannot generally be characterized by the roots of polynomial in the parameter
Without characterization of the indifference condition polynomial in the policy parameter, our proof technique in Appendix B becomes unsuitable for the multi-state setting: we cannot invoke the fundamental theorem of algebra to conclude that the coefficient terms are identically zero, and thus we cannot obtain the contradiction critical to our proof by contradiction, where we found that player zt is in fact indifferent even at the extreme parameter value of 1.
*Although this indifference condition does not generally yield a polynomial X, one can easily find special cases of Markov games which it does. For instance, if player i's action does not influence transition probabilities. the indifference condition will yield polynomial and the normal form proof technique will go through without modification.
17

---

In summary, the proof technique employed in Appendix B to prove Lemma Trelies crucially on the specific explicit form the indifference condition in stateless, finite normal-form games. Passing to the multi-state setting, the analogous indifference condition takes different form, and so the specific derivations cannot be repurposed for a simple extension of Lemma] [ However, it is also important to recognize that this phenomenon is a limitation of the proof technique and does not pose a fundamental obstacle to the generalization of Theorem per se. Indeed, the remaining elements of the proof of Theorem [ carry over seemlessly to the multi-state case, including various continuity conditions for functions characterizing best responses. therefore seems promising that one can generalize Theorem to to apply to Markov games by applying similar machinery used in this paper but substituting a different proof for that of Lemma to take advantage topological or geometric structure shared by both normal-ford and Markov games. We leave this interesting open question for future research.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claimed contributions consist of positive theoretical result (Theorem) ! which we prove rigorously. Additionally, we connect this theoretical finding multi-agent reinforcement learning more broadly, which is described in the discussion sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We identify practical limits of the applicability of the theory contained in this paper, and we compare it to existing impossibility results which were already previously known. In the discussion section, we compare and contrast our result with other results on limitations of multi-agent learning.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Yes, the paper contains complete, correct, and well-documented proof'.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification: This paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccggudeeeeeeeeeeee/eeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This paper's research conforms in every respect to the code of ethics provided by NeurIPS.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
In the discussion section of our work, we describe the broader impact of our work in the context of machine learning algorithm design. However, since our work is theoretical in nature and does not provide an algorithm itself, its broader societal impact cannot be assessed at this time.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
22

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The work presented in this paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "ViVQFgbDbL", "reviewer": "Reviewer_a3ET", "summary": "The paper delves into the strategic dynamics of MARL, focusing on the evolution of strategy profiles among agents. It introduces satisficing paths, a sequence of strategies where an agent that is best responding in one period does not switch strategies in the next, which allows for exploration in optimization. The central question addressed is whether, for any given game and initial strategy profile, it's always possible to construct a satisficing path that leads to Nash Equilibrium. The paper provides a positive answer for normal-form games, suggesting that reward-deteriorating strategic updates can drive play towards Nash equilibrium. The analysis has implications for MARL algorithms, which offers new insights into algorithm design that could avoid common drawbacks like cyclical behaviour.", "questions": "1. How can the theoretical results be practically implemented in MARL algorithms?\n2. Are there any known limitations or exceptions where satisficing paths might not lead to equilibrium?\n3. Can the concepts presented be extended to continuous action spaces or other game types?", "limitations": "See above comments.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides a significant theoretical result regarding the existence of satisficing paths in normal-form games.\n2. It offers a novel perspective on how suboptimal strategic updates can aid convergence to equilibrium, contrary to typical reward-improving approaches.\n3. The findings have clear implications for MARL algorithm design, suggesting potential modifications to enhance convergence properties.\n4. The results are not limited to two-player games but extend to n-player general-sum normal-form games.", "weaknesses": "1. The paper is theoretical, and it's unclear how the insights would translate into practical MARL algorithms without empirical validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Our theoretical results have some practical consequences for MARL algorithms. First, they can be used to justify and analyze existing algorithms (such as those of references [19], [20], [33], and others) beyond the narrower classes of games for which they were designed. Second, our results inform algorithm design in MARL to break cycles, as described in Lines 298-308 of our paper. In particular, one can combine random search when unsatisfied with cycle-breaking random search (or otherwise selective, non-best-responding strategic updates). These added ingredients will influence the trajectory of strategy iterates to follow satisficing paths, which we have shown have the potential to lead to equilibrium even in cases where the smaller set of best-response paths do not lead to equilibrium.\n\n2. Thank you for this important question. Yes indeed, satisficing paths to equilibrium do not exist in all game theoretic settings, and negative results do exist. In this paper, we show that *mixed extensions* of  finite, normal-form games (where strategies can be probability distributions over a set of actions) always admit at least one satisficing path terminating at equilibrium from any initial strategy profile. On the other hand, if strategies are not allowed to be randomized, then one can produce examples of games with a pure Nash equilibrium and an initial strategy profile that is not connected to the Nash equilibria by a satisficing path. \n\n3. Absolutely, the definitions of satisficing can be extended, but the proof techniques for Theorem 1 may not carry over automatically. Some details of our proofs rely on linear programming formulations where the feasible set is an n-dimensional simplex and so admits a finite number of extreme points. Our proof subsequently took advantage of this fact. When one considers continuous action spaces, the number of extreme points may not be finite, and this loss of finiteness may prevent our subsequent analysis. Although our proof technique may not immediately carry over in this more general setting, we believe similar ideas can be carried out in a generalization of this work.", "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": "bLJYpb89hg", "reviewer": "Reviewer_sDku", "summary": "The paper answers the following question affirmatively: \"For an arbitrary n-player normal-form game and an arbitrary initial strategy profile x1, is it always possible to construct a satisficing path from x1 to a Nash equilibrium of the game?\".", "questions": "cf. my comments in the \"Weaknesses\" section.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The presentation of the paper is excellent, in particular it is very clear which research question is tackled by the authors. The proof of the main result (including lemmas) is not trivial and offers interesting elements.", "weaknesses": "I have one main complaint, and this is related to my disagreement with the following sentence at the beginning of section 3.2: \n\n``Theorem 1 shows that play will be driven along satisficing paths to an equilibrium\".''\n\nI disagree, because to have the guarantee that it will be driven to an equilibrium, you still need to find a way to get all unsatisfied players to the equilibrium, and this is not a trivial task at all. What your theorem 1 shows is the existence of such path to equilibrium. However, you construct this path in a very specific way, and even in the case where all players are unsatisfied (that is your Case 1, page 6), you need to find a way to transition from this situation of all-unsatisfied-players to an equilibrium (Case 1, page 6 assumes that you know such an equilibrium). And finding this is not easy if you don't know an equilibrium a priori. In other words: in large games, it may occur that almost every path is satisficing because almost no player will be exactly satisfied. This makes me wonder about the usefulness of the concept of satisficing path. The idea of weakening best-response paths where all players best-respond is interesting, but the current definition of satisficing path may be too weak.\n\nTo summarize: the paper presents an existence result, but it would be much stronger and more meaningful if authors presented an algorithm to reach Nash equilibria along satisficing paths without knowing the Nash equilibrium a priori.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your engaged reading and review of our paper!\n\nOur aim with the original wording at the beginning of Section 3.2 was to contrast approaches based on satisficing with approaches based (for instance) on best responding, where in the latter it is possible that no path to equilibrium exists from a particular starting point. In the revised version, Section 3.2 will begin with the following: \"When coupled with a MARL algorithm that uses an exploratory satisficing strategy update, play will be driven along satisficing paths. Theorem 1 shows that for any starting strategy profile, some such path connects the strategy profile to an equilibrium, and so a sufficiently exploratory strategy update may drive play to equilibrium along a satisficing path.\" \n\nWith regards to a point raised in your summary, we wish to note that algorithms based (implicitly) on the satisficing principle with sufficient exploratory search when unsatisfied were proposed in references [19] and [20]. Those algorithms were restricted to special classes of games less general than those considered here (namely, two-player games in [19] and games satisfying regularity conditions in [20]). Those algorithms discretize each player's strategy set and select new strategies from this discrete subset. The satisfaction condition used in these papers replaced best responding by approximate best responding, and the authors showed that, in their specific subclasses of games, MARL using discretized satisficing leads to approximate equilibrium with arbitrarily high probability. One of the objectives of our paper was to show that such algorithms actually have theoretical basis beyond the settings considered in [19] and [20]. We believe Theorem 1 serves this objective and offers an interesting perspective on its own.  As a topic of future work, we agree that it would be interesting to study how the existence of paths interfaces with discretization and approximate best responding, which were jointly needed for the algorithmic guarantees of [19] and [20].", "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": "QgNH28v8qT", "reviewer": "Reviewer_1c5w", "summary": "This paper explores the dynamics of strategy updates in MARL and game theory, focusing on sequences of strategies satisfying a pairwise constraint. This constraint requires that the agent best responding in one period does not switch its strategy in the next period but does not constrain the non-optimizing agents in any way. Sequences of strategy with this property are called satisficing paths. In this paper, authors have shown that every finite normal-form game enjoys the satisficing paths property. Overall, the paper provides a new perspective on achieving equilibrium in multi-agent systems and has significant implications for the design and analysis of MARL algorithms.", "questions": "1.\tThis paper provides extensive theoretical results and these results are compelling, have authors considered validating findings through empirical experiments? I am wondering how satisficing paths perform in practical multi-agent reinforcement learning scenarios.\n\n2.\tAuthors have proved that any finite normal-form games have the satisficing paths property. How do you envision the scalability of your approach to larger, more complex game settings? Are there specific scalability challenges that need to be addressed?\n\n3.\tHere, I just wondering have authors considered exploring alternative pathways or strategies for reaching equilibrium. If yes, how do these alternatives compare to satisficing paths in terms of convergence speed and robustness?", "limitations": "Yes, the authors provided limitations.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper studies a very interesting problem: is it always possible to construct a satisficing path that terminates at equilibrium for a given game and initial strategy profile? The main strengths of this paper are:\n1. The introduction of satisficing paths as a generalization of the best response path is both novel and insightful. \n\n2. The authors provide rigorous proof that any finite normal-form game has the satisficing paths property. This proof is well-structured and addresses an open question in the field.\n\n3. The paper’s finding that reward-deteriorating strategic updates can drive play to equilibrium is counterintuitive yet compelling.\n\n4. The practical implications for the design of MARL algorithms are articulated. The paper provides concrete suggestions on how to incorporate satisficing updates and exploratory strategies, which could improve convergence properties and performance in a wider range of games.", "weaknesses": "1. Although this paper provides extensive theoretical results, it lacks empirical validation. Including experimental results or simulations, even a simple example, to demonstrate the practical applicability and performance of satisficing paths in real-world scenarios would strengthen the paper’s impact.\n\n2. While the theoretical contributions are significant, the proof techniques used are complex and may not be easily accessible to all readers. Providing more intuitive explanations could make the results more understandable to a broader audience. Although it is not a large weakness, it would improve the readability if it can be resolved.\n\n3. The paper offers valuable algorithmic insights but falls short of providing detailed guidance on implementing these insights in practical MARL algorithms. Including specific case studies would make the theoretical contributions more actionable for practitioners.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind words and for your questions. Efficiency and practical performance are important considerations for work on MARL. Our theoretical study here is somewhat orthogonal to efficiency, and we do not take a position on the exploratory (\"lose-shift\") mechanism used by any particular satisficing-based MARL algorithm, but we can say a few things about the connections between this theory and efficiency.\n\n1. Satisficing paths can be produced as the output of many different MARL algorithms. In fact, they can be produced by any algorithm that respects the \"win-stay\" condition of keeping an old strategy whenever it is a best response to the last period's strategy profile. This means a wide class of algorithms are available to us for simulation purposes, and a given algorithm may be highly effective (or highly ineffective) for a given game. As such, we believe that simulations of a particular MARL algorithm in a specific game may not be a meaningful representation of the theoretical findings of this paper, on the existence of paths.\n\n2. In [20], the authors studied a particular satisficing algorithm that relied purely on exploration to drive play Nash equilibria. The authors of that work offered some remarks on how their algorithm scales with the number of agents and the size of their action sets. In the case of *purely* randomized exploration when players are unsatisfied, the authors observed that their algorithm scales poorly and inefficiently. Their observations underline the fact that a well-selected strategy update function is needed to ensure good performance in larger, more complex games. \n\n3. We have considered a spectrum of pathways for reaching equilibrium, with one end of the spectrum being pure best response dynamics (possibly with inertia) and the other end being purely exploratory strategy updates (when players are unsatisfied). In terms of convergence speed, dynamics based on best responding without exploration can be very quick in some settings, such as potential games, but can also fail to converge in other settings, such as zero-sum games. Thus, algorithms based on exploration with the satisficing principle tend to be more robust, if slower, than algorithms on the other end of the spectrum. Of course, there are other paradigms for algorithm design outside of this spectrum, which we believe are also very interesting.", "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": "2mn0qy7SFw", "reviewer": "Reviewer_HTV5", "summary": "The authors study and affirm the possibility of constructing a satisficing path to a Nash equilibrium, from any initial strategy profile, in n-player normal-form games. Satisficing paths generalize best-response paths in that a player that is not best responding is not restricted in its strategy update. Players that were previously best-responding maintain their strategy. The authors use their results in a discussion to suggest that future design of MARL algorithms incorporate exploration periods among strategies, especially when they are not best-responding. The authors go on to discuss their contributions in the contexts of Markov games, decentralized learning, and dynamical systems.", "questions": "If there's enough space, could you elaborate on the open question left by (51) on line 73? It seems that the satisficing principle is significantly studied (line 55) but I don't have the best understanding for how or why this principle is a significant in the pre-existing literature.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is well-described and well thought-out. Satisficing improvements is an interesting concept and could be useful in MARL research. The main contribution (Theorem 1) seems to provide a useful conclusion about how MARL algorithms could interface with satisficing paths rather than the best-response concept. Good extension beyond the work of (51) (line 183). It's good that the proof is not immediate, especially with Lemma 1 in Appendix A. Good proof sketch on Line 189. Overall, I believe this paper would provide a fruitful conceptual addition to the MARL research discussion.", "weaknesses": "Remark 1 suggests the algorithm is centralized rather than decentralized and learning-based. Under Case 1 you say \"fix an arbitrary Nash equilibrium $z^*$.'' How does one discover \"z^*?\" Isn't the point of using MARL algorithms to (1) use decentralized learning to discover a NE, or (2) identify that NE from a centralized perspective, which is PPAD-complete? I am confused how the centralized entity forms its recommendations for which strategies agents should play next. \n\nA similar confusion holds for Case 2: I could be reading this not clearly enough, but the proof appears to suggest ``make most agents unsatisfied then arbitrarily jump to a NE (subject to feasibility via the remaining satisficed agents).'' Could you please elaborate how this is not a trivial conclusion (line 367)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your close reading of our paper and for sharing your concerns. We wish to primarily address the points of confusion identified in your review, but perhaps it would be helpful to first address your question on the connection between our work and the previous literature. \n\nIndeed, the satisficing principle has been widely employed in several previous works across game theory and MARL, such as those identified on Line 55. While the principle itself is natural and widely used, the graph theoretic structure was studied only indirectly by early proponents of satisficing algorithms (e.g. [19], [20]), and the terminology of satisficing was not introduced until later. Since this idea appeared inherently in earlier algorithms, it is somewhat well studied, with some interesting theorems proved incidentally while studying convergence properties of specific algorithms. On the other hand, since it was not formalized until later, some fundamental structural questions (such as the open question we answer) were not addressed head-on in those earlier works. \n\nComplementing and building on existing work, our theoretical study on the structure of satisficing paths may be interpreted as being upstream of the analysis of specific MARL algorithms. One aim of our work was to show that such paths to equilibrium exist, since this existence result is necessary for any satisficing-based MARL algorithm to be effective. That being said, it is important to note that the structure we study is separate from any individual satisficing-based MARL algorithm. In fact, the process described in the Proof of Theorem 1 is not an algorithm, but an existence proof described procedurally. Remark 1 cautions the reader that each step of this procedure is analytic rather than algorithmic. As an existence proof, justified non-constructive steps (e.g. the selection of an arbitrary Nash equilibrium z^{*} by the analyst, which is guaranteed to exist) are acceptable, and questions of complexity of such non-constructive steps are not applicable as it relates to an existence proof such as ours. Nevertheless, these questions are certainly relevant and important for downstream applications such as the complexity analysis of specific MARL algorithms.", "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:
Dear AC and reviewers,

We would like to thank you all for your time and effort in reading and reviewing our paper, and we would like to thank the reviewers for their thoughtful input and positive evaluations. For your convenience, we have responded to each reviewer's questions separately below.

Kind regards,
The Authors.

Meta-review: All reviewers see the novelty and usefulness of the main contribution of the work, which establishes that "satisficing paths" can always be used to find equilibrium in normal-form games.
Decision: Accept (spotlight)