A myopic adjustment process for mean field games with finite state and action space

Neumann, Berenice Anne Article — Published Version A myopic adjustment process for mean field games with finite state and action space International Journal of Game Theory Provided in Cooperation with: Springer Nature Suggested Citation: Neumann, Berenice Anne (2023) : A myopic adjustment process for mean field games with finite state and action space, International Journal of Game Theory, ISSN 1432-1270, Springer, Berlin, Heidelberg, Vol. 53, Iss. 1, pp. 159-195, https://doi.org/10.1007/s00182-023-00866-z This Version is available at: https://hdl.handle.net/10419/317029 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) International Journal of Game Theory (2024) 53:159–195 https://doi.org/10.1007/s00182-023-00866-z 1 3 ORIGINAL PAPER A myopic adjustment process formean field games withfinite state andaction space BereniceAnneNeumann1 Accepted: 22 June 2023 / Published online: 1 August 2023 © The Author(s) 2023 Abstract In this paper, we introduce a natural learning rule for mean field games with finite state and action space, the so-called myopic adjustment process. The main motivation for these considerations is the complexity of the computations necessary to determine dynamic mean field equilibria, which makes it seem questionable whether agents are indeed able to play these equilibria. We prove that the myopic adjustment process converges locally towards strict stationary equilibria under rather broad conditions. Moreover, we also obtain a global convergence result under stronger, yet intuitive conditions. Keywords Mean field games· Learning in games· Finite state space· Finite action space JEL Classification C73· C70 1 Introduction Mean field games have been introduced by Lasry and Lions (2007) and Huang etal. (2006) in order to make dynamic games with a large number of players tractable. The central idea is to approximate these games with many players by a game with a continuum of anonymous players. Thereafter a vibrant field of research emerged in particular concerning games where the dynamics of the individual players are described by diffusions. For a first overview consider the monographs of Bensoussan etal. (2013) and Carmona and Delarue (2018a, 2018b) or the lecture notes by Cardaliaguet (2013). However, a central problem for applications is that equilibria are described by forward-backward systems of (stochastic) differential equations and are, therefore, notoriously intractable. * Berenice Anne Neumann [email protected] 1 Trier University, Universitätsring 19, 54296Trier, Germany 160 B.A.Neumann 1 3 Recently, also mean field games with finite state space have been considered, for example in Gomes etal. (2013), Cecchin and Fischer (2018), Belak etal. (2021), Carmona and Wang (2021), Doncel etal. (2019), Neumann (2020) and Carmona and Delarue (2018a, Section 7.2). Also in these games dynamic equilibria are described by forward-backward systems of differential equations. Moreover, considering stationary equilibria allows for closed-form solutions: This was first demonstrated in several applications including the spread of corruption, botnet defence, paradigm shift in science and consumer choice (Besancenot and Dogguy 2015; Kolokoltsov and Bensoussan 2016; Kolokoltsov and Malafeyev 2017; Gomes etal. 2014). Thereafter, in Neumann (2020) results yielding a semi-explicit characterization of stationary equilibria in general mean field games with finite state and action space have been derived. For applications it is now clearly desirable to understand whether stationary equilibria are an adequate description of agents’ behaviour. One approach is to discuss the question in how far these equilibria are suitable limit objects of dynamic equilibria when the finite time horizon tends to infinity (consider Kolokoltsov and Malafeyev (2018) for the analysis of an example). The second approach is to understand in how far stationary equilibria arise when agents apply certain only partly rational decision rules. This approach is a classical one in standard game theory and known as learning. Why players should play equilibrium strategies is a classical concern. The explanation that agents arrive at these strategies from “introspection and computation” is challenged by many facts: The computational complexity of the problems at hand, the question which equilibrium to choose in case of multiple equilibria as well as experimental evidence (Fudenberg and Levine 1998). Because it was observed in experiments that agents “learn” to play equilibria after some time, many authors focussed on the definition and analysis of partially rational “learning rules” (for example fictitious play or partial best response) mostly for static games. For an overview consider the monograph of Fudenberg and Levine (1998) or the survey by Nachbar (2009). Recently, learning has also been discussed for mean field games with diffusionbased dynamics: On the one hand, in Cardaliaguet and Hadikhanloo (2017) fictitious play for repeated games with finite time horizon has been introduced, which thereafter has been analysed in subsequent publications (Hadikhanloo 2017; Briani and Cardaliaguet 2018) and extended to discrete time finite state mean field games with finite time horizon (Hadikhanloo 2018). On the other hand, in Mouzouni (2018) a learning procedure similar to the myopic adjustment process considered here has been introduced. In this paper existence and local convergence under strong assumptions (quadratic Hamiltonian and Lasry–Lions monotonicity condition) have been proved. We highlight, that the methods for diffusion-based mean field games cannot be adapted to our setting of a mean field game with finite state and action space, since the crucial assumption for most methods (a unique optimizer of the Hamiltonian) is typically not satisfied (see Neumann 2020,Remark 2.5). Another branch of literature analyses learning methods for discrete time mean field games with finite state and action space from a reinforcement learning perspective, see the survey by Lauriére etal. (2022) for an overview. These learning 161 1 3 A myopic adjustment process formean field games withfinite… methods do not aim to explain how players adjust their behaviour in a (partially) rational way, but how to obtain nearly optimal solutions using data or samples. Hence, these methods include (generalizations of) classical (economically motivated) learning rules like fictitious play (Perrin etal. 2020) or best-response based methods (Guo etal. 2019), but also others. Up to the knowledge of the author, this paper is the first paper that considers learning in continuous time mean field games with finite state and action space. The learning procedure we consider in this paper is motivated from an economic standpoint as a partially rational decision procedure for the agents. Namely, we introduce a myopic adjustment process, where agents choose to play a best response for the scenario that the current state distribution in the population will persist for all future times. Moreover, whenever the current state distribution in the population changes, the agent will adjust his strategy to the new best response. We highlight that, in contrast to most other learning procedures, we do not assume that all agents choose the same strategy as best response. Given the players’ choices the state distribution of the population gradually changes as described by the chosen strategies. This differs from best-response based methods, where the distribution would immediately change to the stationary distribution given the best response. This definition yields to a formulation of this process as a differential inclusion and we can prove existence of this process under a continuity assumption. Thereafter we address the question whether the process converges locally or globally towards stationary equilibria. In this context we first obtain under suitable conditions an analogue of the classical result from the theory of matrix games that a strict equilibrium is locally stable. Thereafter, we also establish a global convergence result under stronger, yet intuitive conditions, which are different to the conditions used in analogous contexts in evolutionary game theory. Since the proof is rather complex and technical we first provide a result for a two strategy setting in which case the general idea becomes clear. Thereafter, we provide the general statement. Let us conclude the introduction by relating the myopic adjustment process with the notion of evolutionary game dynamics for population games as in Sandholm (2010, 2015). In the setting of a static game among a continuum of small, anonymous players, an evolutionary game dynamic describes the evolution of the strategy choices using so-called revision protocols, which are simple myopic rules to adjust the behaviour based on the observed strategies by all others. The myopic adjustment process considered here can be seen as an extension of this idea to dynamic games where each agent has an individual state that evolves over time (according to the action he chooses) and earns a reward that depends on his individual state, his individual action and the distribution of states of the other agents. Thus, in contrast to standard learning procedures the game is not played repeatedly and the agents do not learn from round to round, but the agents learn while playing the game. A second difference is that besides the strategies also a state evolves over time, an idea that occurs also in Marden (2012). In this paper a global state taking finitely many values that evolves over time is introduced and the static game that is played repeatedly depends on this state. However, here we introduce an individual state for each agent, which has, up to the knowledge of the author, not been considered so far. Due to fact that the adjustment of strategies and the evolution of the individual states happen 162 B.A.Neumann 1 3 simultaneously, classical results from evolutionary game theory cannot be applied. However, since the myopic adjustment process looks somehow similar to classical evolutionary game dynamics the results often have the same flavour. In this sense, we prove as in Sandholm (2014) that the myopic adjustment process converges locally towards strict equilibria and similar to Hofbauer and Sandholm (2009) and Zusai (2020) we propose gradient conditions to ensure global convergence of the adjustment process. The rest of the paper is structured as follows: Sect.2 describes the mean field game model considered in this paper. Section3 introduces the myopic adjustment process and justifies its definition as a sensible partially rational learning rule. Moreover, it presents the myopic adjustment process for a simple example. In Sect.4 we study the local convergence of the myopic adjustment process and in Sect. 5 we investigate the global convergence first for the special case of two strategies, thereafter in a general setting. The AppendixA describes an algorithm to verify the conditions of the general global convergence theorem, AppendixB contains all proofs. 2 Stationary equilibria ofmean field games withfinite state andaction space This section describes the mean field game model. The setup is the same as in Neumann (2020) and we refer the reader to this paper for more details. Moreover, we remark that the model has been first introduced in an analytic formulation and without the notion of stationary equilibria in Doncel etal. (2019). We consider a continuum of agents. Let S={1, …,S} ( S>1 ) be the set of possible states of each player and let A={1, …,A} be the set of possible actions. With P(S) we denote the probability simplex over S and with P(A) the probability simplex over A . We refer to an element m∈P(S) that describes the distribution of states in the population as social state, whereas the state i∈S of an individual agent is called the individual state. A (mixed) strategy is a measurable function 𝜋∶S×[0, ∞) →P(A) , (i,t)↦(𝜋ia(t))a∈A with the interpretation that 𝜋ia(t) is the probability that at time t and in the individual state i the player chooses action a. A strategy 𝜋=d∶S×[0, ∞) →P(A) is deterministic (or a pure strategy) if it satisfies for all t≥0 and for all i∈S that there is an a∈A such that dia(t)=1 and dia � =0 for all a�∈A⧵{a} . Sometimes the following equivalent representation is helpful: Namely, we represent a deterministic strategy as a function d∶S×[0, ∞) →A,(i,t)↦di(t) with the interpretation that di(t)=a states that at time t in the individual state i action a is chosen. A stationary strategy is a map 𝜋∶S×[0, ∞) →P(A) such that 𝜋ia(t)=𝜋ia for all t≥0 . With Π we denote the set of all (mixed) strategies and with Πs the set of all stationary strategies. Similarly, we denote by D the set of all deterministic strategies and by Ds the set of all deterministic stationary strategies. Let for all a∈A and m∈P(S) the matrices (Q⋅⋅a(m))a∈A be conservative generators, that is Qija(m)≥0 for all i,j∈S with i≠j and ∑j∈ SQ ija (m)= 0 for all i∈S . The individual dynamics of each player given a Lipschitz continuous 163 1 3 A myopic adjustment process formean field games withfinite… flow of social states m∶[0, ∞) →P(S) and a strategy 𝜋∶S×[0, ∞) →P(A) are given as a Markov process X𝜋(m) with given initial distribution x0∈P(S) and infinitesimal generator given by the Q(t)-matrix Given the initial condition x0∈P(S) , the goal of each player is to maximize his expected discounted reward, which is given by where r∶S×A×P(S)→ℝ is a real-valued function and 𝛽∈(0, 1) is the discount factor. That is, for a fixed flow of social states m∶[0, ∞) →P(S) the individual agent’s decision problem is a Markov decision process with expected discounted reward criterion and time-inhomogeneous reward functions and transition rates. In this paper we work under the following standing assumption, which ensures the well-definition of the model as well as the existence of dynamic as well as stationary equilibria (Neumann 2020): Assumption A1 For all i,j∈S and all a∈A the function m↦Qija(m) mapping from P(S) to ℝ is Lipschitz-continuous in m. For all i∈S and all a∈A the function m↦ria(m) mapping from P(S) to ℝ is continuous in m. Definition 2.1 Given an initial distribution m0∈P(S) , a mean field equilibrium is a pair (m,𝜋) consisting of a flow of social states m∶[0, ∞) →P(S) with m(0)=m0 and a strategy 𝜋∶S×[0, ∞) →P(A) such that • the distribution of the process X𝜋(m) at time t is given by m(t), and • Vm0 (𝜋,m) ≥ V m0 (𝜋 � ,m ) for all 𝜋�∈Π . Definition 2.2 A stationary mean field equilibrium is given by a stationary strategy 𝜋 and a vector m∈P(S) such that • the law of X𝜋(m) at any point in time t is given by m, and • for any initial distribution x0∈P(S) we have V x 0( 𝜋,m )≥ Vx 0( 𝜋 � ,m ) for all 𝜋�∈Π . As discussed in Neumann (2020) this is a sensible notion of stationary equilibrium: Indeed, the second condition ensures that an agent will at no time benefit from deviating from the equilibrium strategy since irrespective of his current state or distribution, respectively, the strategy 𝜋 is optimal for him. ( Q𝜋(m(t),t))ij = ∑ a∈A Qija(m(t))𝜋ia(t) . (1) V x0(𝜋,m)=𝔼 [ ∫∞ 0 (∑ a∈ A rX𝜋(m)a(m(t))𝜋X𝜋(m)a(t) ) e−𝛽tdt ], 164 B.A.Neumann 1 3 3 The myopic adjustment process In general, it is not possible to compute dynamic mean field equilibria for the considered game; it is not even possible to explicitly characterize solutions of the individual control problem for a given non-constant flow of social states. Moreover, also in the case of a finite time horizon, the search for equilibria can only be reduced to a forward-backward system of ODEs, which can, most of the time, be only solved numerically (see Belak etal. 2021). The aim of this section is to motivate and define a reasonable alternative decision mechanism for the agents. In contrast to Cardaliaguet and Hadikhanloo (2017) we cannot assume that the game is played repeatedly, but instead we have to assume that the agent changes his strategy during the game. In contrast to classical evolutionary game theory, we moreover assume that the agents can change their strategy at any time t. We note that the game at time t with current distribution m is, due to the time-homo- geneous formulation and the infinite time horizon, equivalent to the game started at time 0 with initial distribution m. Moreover, we remind ourselves that the influence of the individual agent on the game characteristics and thus on the payoff of the other players is negligible. Therefore, it is reasonable to assume that the agents do not try to influence the other players’ choices, but that they only maximize their own payoff. Because of time-homogeneity and the negligible influence on other players, we assume that the agents choose Markovian strategies that only depend on the current individual state and current social state. We assume that the agent when choosing an optimal strategy given the current social state m assumes that the social state is constant. Indeed, by construction of the dynamics and since Q is uniformly bounded, the social state will be close to m for a certain time horizon. Since the rewards and transition rates are continuous, this means that for this time horizon the approximation that the social state is constant works well. For a longer time horizon a sensible prediction of the evolution of the social state is complex, since the agent would also need to take into account that the population’s strategy might change due to the change in the social state. However, since the agent is allowed to change his strategy at any time (in particular if the social state changes drastically), it is reasonable to assume that he focuses on the near future, i.e. chooses a strategy that maximizes his reward given the constant prediction m. Given such a constant prediction of the evolution of the social state, the optimization problem becomes a tractable Markov decision process with stationary transition rates and rewards (see Neumann 2020,Lemma 3.1). It is well known that there is always an optimal stationary strategy for the considered optimization problem (Guo and Hernández-Lerma 2009) and it is again natural to assume that agents choose such a stationary strategy. We remark that this assumption that agents choose a stationary strategy is classical and that there are several conceptual reasons for the use of these strategies (see Maskin and Tirole 2001). Namely, stationary Markov strategies are the simplest (rational) form of decision-making in this context. Moreover, this type of strategies is related to subgame perfection, which is as discussed earlier a reasonable requirement in our setting. Indeed, these strategies ensure that a game with the same relevant characteristics (i.e. individual and social state) is played in 165 1 3 A myopic adjustment process formean field games withfinite… the same way. Finally, the restriction on this type of strategies reduces the number of possible best responses and thus increases predictive power. In order to characterize the optimal stationary strategies that could be chosen by the agent let us review the relevant results on Markov decision processes with stationary transition rates and rewards. By V𝜋(m)=(V𝜋 𝛿i (m)) i∈ S we denote the reward vector for the Markov decision process, which collects for each i∈S the expected discounted reward defined in (1) given that the individual agent starts in state i, chooses strategy 𝜋∈Π and the social state is m for all times. A strategy 𝜋 is optimal if it satisfies V𝜋(m)≥V𝜋 (m) pointwise for all 𝜋 ∈Π . Moreover, if 𝜋 is optimal we have V𝜋(m)=V∗(m) , where V∗(m) is the unique solution of the optimality equation For our purpose now the following result explicitly characterizing the set of all optimal stationary strategies proves to be useful (see Neumann 2020,Section3): Define and set Then the set of all optimal stationary strategies is given by conv(D(m)) . So all in all we assumed that at any time any agent can change his strategy and he will do this using his current individual state and the current social state. Moreover, we argued that every agent will choose a strategy from the set conv(D(m)) . However, we cannot assume that all agents choose a particular strategy nor that the agents or groups of them agree on a common strategy. Moreover, we also cannot describe which agents will choose which strategy. The only sensible assumption is that the population chooses aggregately a strategy from the set conv(D(m)) . The next lemma describes how the social state evolves if all agents adopt this decision mechanism: Lemma 3.1 Let m∶[0, ∞) →P(S) be the distribution of the population, where at time t≥0 any agent chooses a strategy from conv(D(m(t))) . Then for almost all t≥0 . With these preparations we define the myopic adjustment process as a solution of the differential inclusion in the sense of Deimling (1992) given by (2). Namely, a trajectory of the myopic adjustment process is an absolutely continuous function m∶[0, ∞) →P(S) such that 𝛽 V∗ i(m)=max a∈A { ria(m)+ ∑ j ∈ S Qija(m)V∗ j(m) } ,i∈S . O i(m) =∶ argmaxa∈A { ria(m)+ ∑ j∈S Qija(m)V∗ j(m) } D(m)∶={d∶S → A|d(i)∈Oi(m)for all i∈S}. (2)  m (t)∈F(m(t)) ∶= conv { (Q d (m(t))) T m(t)∶d∈D(m(t)) } 166 B.A.Neumann 1 3 We remark, that the use of differential inclusions as a modelling tool for situations where uncertainty, the absence of control or a variety of available dynamics occurs is classical (Aubin and Cellina 1984). Before we start the analysis of the long-term behaviour, we note, relying ona classical existence result for differential inclusions, that under AssumptionA1 a solution of the differential inclusion exists. Theorem3.2 The differential inclusion defined by (2) and (3) admits a solution m∶[0, ∞) →P(S) . Let us briefly compare the myopic adjustment process to classical evolutionary game dynamics. The central difference is that here two layers of adjustment have to be considered, namely the adjustment of strategies and the evolution of the individual states, whereas in classical evolutionary game dynamics only the adjustment of the strategies matters. Also from the motivation/construction the processes differ: First, here we consider learning during a dynamic game, whereas in classical evolutionary game dynamics it is assumed that agents learn from round to round in a static game. Second, here the agent is allowed to change his strategy at any time, in classical evolutionary game dynamics he can often do this only at random times. This means that in evolutionary game dynamics the change of strategies is rather continuous, whereas here it is abrupt and sometimes discontinuous. However, since the individual agent’s states are modelled by a Markov chain and the map m↦D(m) is upper semi-continuous (see the proof of Theorem3.2), the resulting evolution of the social state is again upper semi-continuous. Yet, besides all the differences, the emerging processes are both dynamical systems on a probability simplex having a similar structure. Therefore, also the results have a similar flavour, although the economic intuitions behind the results are different. For our purpose, it is central to understand how stationary equilibria and the trajectories of the myopic adjustment process interact. The following observation, which is classical for many learning procedures, is a first step: Remark 3.3 By definition, a point is a stationary point of (3) if and only if it is a stationary mean field equilibrium. This is immediate, since 0∈F(m(t)) implies that □ (3) m(t)∈F(m(t)) for almost all t≥0, m(0)=m0. 0 ∈conv ⎧ ⎪ ⎨ ⎪ ⎩ � � i∈S� a∈A miQija(m(t))dia � j∈S ∶d∈D(m(t)) ⎫ ⎪ ⎬ ⎪ ⎭ =⎧ ⎪ ⎨ ⎪ ⎩ � � i∈S � a∈A miQija(m(t))𝜋ia�j∈S ∶𝜋∈conv(D(m(t)))⎫ ⎪ ⎬ ⎪ ⎭ . 173 1 3 A myopic adjustment process formean field games withfinite… where V d 1(m) and V d 2(m) are the reward vectors of the Markov decision process with transition rates Qija(m) and ria(m) . Moreover, assume that g is twice continuously differentiable and Lipschitz continuous. Since V d 1(m)≥V d 2(m) or V d 1(m)≤V d 2(m) for all m∈P(S) by classical results on Markov decision processes it is immediate that g(m)<0 if and only if D(m)={d1} , g(m)=0 if and only if D(m)={d1,d2} and g(m)>0 if and only if D(m)={d2} . This means that g(m) describes the behaviour of agents given the social state m∈O . Therefore, we have Theorem5.1 Assume that for all m∈O such that g(m)=0 it holds that ∇g(m)≠0 . Furthermore, assume that the nonlinear Markov chains with transition rate matrix functions Q d 1(m) and Q d 2(m) converge in the limit towards some stationary distribution. (i) Assume that for all m∈O such that g(m)=0 it holds that Then the myopic adjustment process converges towards some stationary mean field equilibrium with deterministic equilibrium strategy from U . (ii) Assume that for all m∈O such that g(m)=0 it holds that Then the myopic adjustment process converges towards some stationary mean field equilibrium with deterministic equilibrium strategy from U . (iii) Assume that for all m∈O such that g(m)=0 it holds that Then the myopic adjustment process either converges towards a deterministic stationary mean field equilibrium with equilibrium strategy from U or there is a T>0 such that the process satisfies g(m(t)) = 0 for all t>T . The gradient conditions in the theorem now link for the case that both strategies are simultaneously optimal (i.e. g(m)=0 ) the evolution of the strategic behaviour of the individual agents ( ∇g(m) ) with the evolution of the social state given the deterministic strategies d1 and d2 (given by Q d 1(m)) T m and Q d 2(m)) T m , respectively). The conditions state that this evolution should be in the same F (m) ∶= ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ �∑ i∈SmiQd1 ij (m) � j∈S g(m)<0 conv��∑i∈SmiQd1 ij (m)�j∈S ,�∑i∈SmiQd2 ij (m)�j∈S�g(m)=0 �∑ i∈SmiQd2 ij (m) � j ∈ S g(m)>0 . ⟨(Q d 1(m)) T m,∇g(m)⟩>0 and ⟨(Q d 2(m)) T m,∇(−g)(m)⟩<0. ⟨(Q d 1(m)) T m,∇g(m)⟩<0 and ⟨(Q d 2(m)) T m,∇(−g)(m)⟩>0. ⟨(Q d 1(m)) T m,∇g(m)⟩≥0 and ⟨(Q d 2(m)) T m,∇(−g)(m)⟩≥0. 174 B.A.Neumann 1 3 “direction” for all points m∈P(S) that satisfy g(m)=0 . Moreover, they explicitly encode the direction to which the social state moves under the myopic adjustment process: The conditions in case (i) state that when g(m)=0 the social state heads to the set where the strategy d2 is optimal, and the conditions in case (ii) state that when g(m)=0 the social state heads to the set where the strategy d1 is optimal. In case (iii) the conditions say, that when g(m)=0 and the population chooses d1 the distribution tends into the set where d2 is optimal, and, when g(m)=0 and the population chooses d2 the distribution tends into the set where d1 is optimal. Therefore, the trajectory will always stay in the set where both strategies are simultaneously optimal. The proof of the theorem relies on the fact that the shape of the myopic adjustment process F does only depend on the fact whether g(m)=0 , g(m)<0 or g(m)>0 . Depending on the gradient conditions we prove for each of the three cases that once g(m(t)) >0 or g(m(t)) <0 or g(m(t)) = 0 , respectively, the function g(m(⋅)) will be greater or less or equal zero for all future times. This yields, together with the fact that Q d 1( ⋅ ) and Q d 2( ⋅ ) are converging in the limit, to the desired convergence result. Example 5.2 Let us consider the following example, which consists of two “good” states, where a positive reward is earned, and one “bad” state, where no reward is earned. The agents in the “good” state face congestion effects, namely there is a risk, increasing in the share of individuals in that state, to go to the “bad” state. The control options are to switch between the two good states. One can interpret this model as a stylized model of the choice between two mobile phone providers, where the customer faces the risk of a breakdown in connection that increases in the share of customers using the same provider. For simplicity, we assume that agents in the “bad” state have no choice option, but recover into each of the two states with equal probability. The formal characterization is given by S={1, 2, 3} and A={change,stay} together with and r ⋅ stay(m)=r ⋅ change(m)=(1, 1, 0) , where all constants are strictly positive. A visualization of the model is given in Fig.2. In Neumann (2019) it is shown that there are infinitely many mixed strategy equilibria with equilibrium distribution Q ⋅⋅change(m)= ⎛ ⎜ ⎜ ⎝ −(b+em1+𝜖)b em1+𝜖 b−(b+em2+𝜖)em2+𝜖 𝜆𝜆−2𝜆 ⎞ ⎟ ⎟ ⎠ Q⋅⋅stay(m)= ⎛ ⎜ ⎜ ⎝ −(em1+𝜖)0em1+𝜖 0−(em2+𝜖)em2+𝜖 𝜆𝜆−2𝜆 ⎞ ⎟ ⎟ ⎠ 175 1 3 A myopic adjustment process formean field games withfinite… with equilibrium strategies satisfying 𝜋1,change =𝜋2,change . To apply Theorem 5.1 we first note, that in Neumann (2023) it is shown that the relevant Markov chains are strongly ergodic and thus, converge to some limit distribution. Moreover, choosing U= {(change,stay),(stay,change)} , O = (− 𝜖 b ,∞) × (− 𝜖 b ,∞) × ℝ and g(m)=m1−m2 we obtain that Thus, Theorem 5.1 yields that either convergence towards a stationary equilibrium with an equilibrium strategy from U happens or that there is a T≥0 such that g(m(t)) = 0 for all t≥T . Since there is no stationary equilibrium with an equilibrium strategy from U it is clear that there is a T≥0 such that g(m(t)) = 0 for all t≥T , which means that m1(t)=m2(t) for all t≥T . Thus, also m1(t)= m2(t) . By (3), this yields that Thus, for almost all t≥T the trajectory of the myopic adjustment process has to satisfy which is a Riccati equation, for which [0,1] is flow invariant and for which a unique classical solution for any initial condition m0∈[0, 1] exists. Numerical simulations �√ 4𝜆2+8𝜆𝜖 +𝜖2−2𝜆−𝜖 2𝜖, √ 4𝜆2+8𝜆𝜖 +𝜖2−2𝜆−𝜖 2𝜖,4𝜖+4𝜆− √ 4𝜆2+8𝜖𝜆 +𝜖2 2𝜖 � ⟨ Q cs (m)) T m,∇−g(m) ⟩ =2bm2 ≥ 0 ⟨ Qsc(m))Tm,∇g(m) ⟩ =2bm 2 ≥ 0. − 𝜋1,change(t)bm1(t)−em1(t) 2 −𝜖m1(t)+𝜋2,change(t)bm1(t)+𝜆m3(t) =𝜋1,change(t)bm1(t)−𝜋2,change(t)bm1(t)−em1(t)2−𝜖m1(t)+𝜆m3(t) , i.e. −𝜋 1,change (t)bm 1 (t)+𝜋 2,change (t)bm 1 (t)=0. m1 (t)=−em 1 (t) 2 − (𝜖 +2 𝜆) m 1 (t)+ 𝜆, Fig. 2 Representation of Example5.2 1:1P 2:1P 3:0P b/0 b /0 em2+ λ em1+ λ 176 B.A.Neumann 1 3 indicate that in our setting with initial conditions m0∈[0, 1] convergence towards the distribution of the stationary mixed strategy equilibria is likely. □ 5.2 Global convergence forthegeneral case The idea in the simple two strategy case was that the set of social states, where d1 or d2 or both strategies, respectively, are optimal is characterized by the function g. Describing the behaviour in a neighbourhood of {m∈O∶g(m)=0} by gradient conditions allows understand that once g(m(t)) = 0 it will not happen again (in case (i) or (ii)) or g(m(t)) will remain at 0 (in the case (iii)) for all future times, which then allows to understand the exact behaviour of the myopic adjustment process from this time on. Here, we want use a similar approach: First, we define a function gd such that gd(m)<0 means that d is the unique optimal strategy for m ( D(m)=d ), gd(m)=0 means that d is one of multiple optimal strategies ( |D(m)|≥2, d∈D(m) ) and gd(m)>0 means that d is not optimal for m. Thereafter, we set up gradient conditions for all those m∈O satisfying gd(m)=0 that again describe consistent behaviour. Assumption A2 For each m∈O there is a strategy d∈U such that d∈D(m) . Moreover, let us write Opt unique (d) for the set of all m∈O such that D(m)={d} and Optsome(d) for the set of all m∈O such that d∈D(m) . For these sets let us assume the following: Assumption A3 For each strategy d∈U there exists a twice continuously differentiable, Lipschitz continuous function gd∶O→ℝ such that and such that for all d∈U and all m∈{ m ∈ O ∶ g d( m )=0} we have ∇gd(m)≠0 . Assumption A4 For any m∈P(S) there are at most two strategies d∈U such that m∈Optsome(d) . Assumption A5 The set P(S) is flow invariant for m∈F(m) . Assumption A6 For all d∈U and all d1,d2∈U satisfying Optsome( d 1)∩Optsome( d 2) ≠ � we have Optunique (d)={m∈O∶gd(m)<0 } Opt some (d)={m∈O∶gd(m)≤0} 177 1 3 A myopic adjustment process formean field games withfinite… or Let us briefly comment on the assumptions: The AssumptionsA2,A3 andA4 are automatically satisfied in the previously described case with |U|=2 . The fifth assumption could be replaced by Assumption A6 with strict inequalities for m∈P(S) with mi=0 for some i∈S (see AppendixB). However, this would make the statement less general, since for example AssumptionA5 is satisfied in Example 5.2, but Assumption A6 with strict inequalities for m∈P(S) with mi=0 for some i∈P(S) is not satisfied. The AssumptionA6 captures partly the conditions imposed in the three different cases of Theorem5.1. The rest of these conditions will be described by the family of digraphs that helps to characterize the long-term behaviour of the myopic adjustment process: For any d∈U let D(d) be a digraph with vertex set U and arc set given by d1→d2∈A(D(d)) if and only if Optsome(d1)∩Optsome(d2)≠� and This digraph can be interpreted as follows: If d1→d2 then the nonlinear Markov chain with generator Qd(⋅) will when it hits the set Optsome(d1)∩Optsome(d2) tends to the set Optsome(d2) . If the digraph D(d) is acyclic then it provides a good description of the behaviour of solutions of m=(Qd(m))Tm . Namely, by a well known result from graph theory there is in this case an acyclic ordering, which is an ordering d1≤⋯≤du of the vertices of D(d) such that whenever di≤dj there is no edge from dj to di . For this acyclic ordering one can prove that for any strategy k∈{1, …,u} the set P (S)∩ ⋃l≥k Opt some (d l) is flow invariant, i.e. once the trajectory hits this set, it will never leave it. Loosely speaking, this means that the trajectory moves through the optimality sets Optsome(dl) in a way that is consistent with the arrows in the digraph D(d). Before we present the main theorem of the section, we verify that the consumer choice model introduced in Example3.4 satisfies all assumptions: Example 5.3 We choose O= (−𝛿,1+𝛿)2 , U={cs,ss,sc} and setting ⟨( Q d( m ))T m ,∇ g d 1 ( m )⟩≥0 for all m ∈Optsome( d 1)∩Optsome( d 2) ⟨(Qd(m))Tm,∇gd 1 (m)⟩≤0 for all m∈Optsome(d1)∩Optsome(d2). ⟨ (Q d (m)) T m,∇g d 1(m) ⟩> 0 for all m∈Opt some (d 1 )∩Opt some (d 2 ) . g cs (m)=m 1 −k 1 g ss(m)=−(m1−k1)⋅(k2−m1 ) gsc (m)=k 2 −m 1 , 178 B.A.Neumann 1 3 completes the set-up. Moreover, noting that k1<k2 and it is immediate that AssumptionsA2,A3 andA4 are satisfied. AssumptionA5 is immediate since in a neighbourhood of (1,0) and (0,1) we face a classical ODE that can be solved explicitly and for which moreover P(S) is flow invariant. Moreover, also Assumption A6 is satisfied since the sets Optsome(d1)∩Optsome(d2) are singletons. With all these preparations let us now formulate the main theorem of this section: Theorem5.4 Let AssumptionsA1,A2,A3, A4,A5 andA6 hold and assume that: (i) For all d∈U the nonlinear Markov chain with transition rate matrix function Qd(⋅) converges in the limit to some stationary distribution. (ii) For all d∈U the digraph D(d) is acyclic. (iii) There exists an ordering d1,d2,…,du of U such that for each i∈{1, …,u} there exists an acyclic ordering ≤D(d i ) of D(di) such that (iv) If everyordering that satisfies the conditions of (iii) has the same final vertex  d , then for any d∈ U ⧵{  d} either Optsome(d)∩Optsome( d)=� or  d→d∉D(  d) with Then for any initial condition m0∈P(S) the myopic adjustmentprocess either converges towards the distribution m of some deterministic mean field equilibrium (m,d) or there is a T>0 and a strategy d∈U such that the trajectory stays in for all t≥T . Let us first comment that all four conditions can be intuitively justified: Condition (i) guarantees that whenever we stay inside an optimality set Optunique(d) for all subsequent times then we converge towards a deterministic stationary mean ∇ gcs(m)= ( 1 0 ) ⇒∇gcs(k1,m2) ≠0 ∇ gcs(m)=(k2+k1−2m1 0)⇒∇gss(k1,m2)≠ 0 and ∇gss(k2,m2)≠ 0 ∇ gsc(m)= ( −1 0 ) ⇒∇gsc(k1,m2)≠ 0, di≤D(d i ) d j for all j ≥ i . ⟨(Qd(m))Tm,∇gd(m)⟩<0 for all m∈Optsome(d)∩Optsome( d). P (S)∩ ( Opt some (d)⧵Opt unique (d) ) 179 1 3 A myopic adjustment process formean field games withfinite… field equilibrium. Condition (ii) ensures that the evolution of the social state given strategy di is consistent on all sets where two strategies are simultaneously optimal, i.e. the evolution tends for all points to the set where a particular strategy is optimal. Moreover, the condition ensures that the evolution is not cyclic in the sense that it moves through a sequence of optimality sets again and again. Condition (iii) then links like the gradient conditions in Theorem5.1 the evolution of the strategic behaviour with the evolution of the social state. First, it requires that for any pair of strategies that are simultaneously optimal the behaviour is locally as specified in Theorem5.1. Second, it also requires that the behaviour of the agents on all these sets where two strategies are simultaneously optimal is consistent, in the sense that the behaviour is not cyclic as described before. The mainly technical condition (iv) ensures that for the final vertex of the acyclic ordering we will never jump from Optunique(d) to Optsome(d)⧵Optunique(d) and back infinitely often, which is necessary to ensure the desired convergence. The conditions (iii) and (iv) seem to be rather complex. However, relying on the well-known fact that a digraph is acyclic if and only if there is an acyclic ordering of its vertices as well the classical algorithm to obtain such a sequence, it is also possible to verify conditions (iii) and (iv) using a (polynomial-time) algorithm. This is in detail explained in AppendixA. If we compare the conditions here with the conditions of Theorem5.1, we see that condition (i) of Theorem5.4 is also present in the conditions of Theorem5.1. The other three conditions (ii)–(iv) are equivalent to the three distinct cases covered in Theorem5.1. Such a case distinction is however, not sensible in the context of a larger number of strategies, for which reason we utilize the formalization by the digraphs D(d). To conclude the section, let us apply Theorem5.4 in the consumer choice model introduced in Example3.4. Example 5.5 We already verified in Example5.3 that the model satisfies AssumptionsA1–A6. Moreover, condition (i) of Theorem5.4 is satisfied since Qd(m) is a standard Markov chain with irreducible generator. Condition (ii) is satisfied since we can solve the differential equation m=(Qd(m))Tm explicitly and obtain that these solutions are monotone in m1 . Using the algorithm from Sect. A we obtain that conditions (iii) and (iv) are only satisfied in those three of eight cases discussed in Neumann (2020) where a unique equilibrium exists. In these cases global convergence towards this unique equilibrium is obtained since the solution cannot remain in the sets {(k1,1−k1)} or {(k2,1−k2)} for all t≥T for some T≥0 . In the other five cases the condition (iii) is not satisfied since we obtain that in the sets Optsome (sc)∩Optsome(cc) or Optsome (cs)∩Optsome(cc) the trajectories of the myopic adjustment process can evolve non-uniquely either it moves towards Optunique(sc) or it moves towards Optunique(ss) or it stays in Optsome (cs)∩Optsome(cc) (or with cs replaced by sc). In the current two-dimensional setting with linearly ordered optimality sets we still observe convergence (which however cannot be expected in 180 B.A.Neumann 1 3 general). However, for the starting point (k1,1−k1) or (k2,1−k2) the long-term behaviour is somewhat unstable. Indeed, the trajectory can remain at (k1,1−k1) (or (k2,1−k2) respectively)until time T∈[0, ∞] and thereafter the process can either converge to the equilibrium given the strategy sc (or cs respectively) or it converges to the equilibrium given the strategy ss. This behaviour is illustrated in Fig.3. 6 Conclusion This paper introduces a learning procedure for mean field games with finite state and action space. More precisely, at any time the agents assume that the social state is constant and choose the optimal strategy given this social state. The learning procedure is non-standard since it involves two layers of adjustment - the adjustment of the strategies and the evolution of the individual states. Yet, we obtain local and global stability results that are similar to classical results from evolutionary game theory: We show that strict equilibria are locally stable if the dynamics have constant transition rates that form an irreducible generator or if the dynamics are a nonlinear sink on the probability simplex. Moreover, we prove global convergence under assumptions that ensure that at each point at most two strategies primarily influence the evolution of the myopic adjustment process and that at each point the local payoff structure and transition rates guide the agent consistently to some direction. Fig. 3 Some of the infinitely many possible solutions with initial condition (m0)1=k1 and (m0)1=k2 . Additionally, the red vertical lines depict the stationary points given the strategies cs, ss and sc (from bottom to top) and the blue vertical lines depict the crucial thresholds k1 and k2 181 1 3 A myopic adjustment process formean field games withfinite… Appendix A. Analgorithm toverify theconsistency condition The question whether an ordering satisfyingcondition (iii) in Theorem5.4 exists or not seems to be complex at first sight. One would have to check for all possible permutations whether the ordering satisfies the condition. However, the close connection to the notion of acyclic orderings allows to provide a polynomial algorithm that determines whether such an ordering exists or not. As in the case of acyclic orderings, it is moreover possible to formulate a polynomial time algorithm to find all orderings satisfying (iii). Due to the additional notational complexity, we omit this here. Our algorithm is a modification of the following simple algorithm to determine an acyclic ordering if it exists: Namely, in each step a vertex with indegree 0 is picked, added to the tail of the acyclic ordering obtained so far and deleted from the digraph (Bang-Jensen and Gutin 2010,Section2.1). Since we want to construct an ordering {d1,…,dS} such that {di+1,…,dS} lies behind di in an acyclic ordering of D(di) for each strategy di∈U the central modification of the algorithm is that when we add a vertex to the ordering we do not only delete the vertex and its arcs from the digraphs, but that we also add arcs in order to ensure that an acyclic ordering of D(d)⧵{d1,…,di} is also an acyclic ordering of D(d). More precisely, if we add d to the ordering since it had indegree 0 in D(d), then we add the arcs d1→d2 to the graphs D(  d) for all  d∈  V whenever d1→d and d→d2 are both arcs in D(  d) . This yields that two vertices d1,d2∈  V are connected in the modified digraph if and only if they are connected in the original graph D(  d) . This algorithm is formalized in Algorithm1 and Algorithm2. Algorithm 1: GraphModification Data: A digraph D=(V,A)and avertex x Result: Anew digraph ˆ D=(ˆ V, ˆ A)such that ˆ V=V\{x}andfor all x1,x 2∈ˆ Vthereisapath from x1to x2in Dif andonly if thereisa path from x1to x2in ˆ D 1ˆ V←− V\{x} 2ˆ A←− A 3for x1such that x1→x∈Ado 4for x2such that x→x2∈Ado 5add x1→x2to ˆ A 6delete all arcs containing xfrom ˆ A 182 B.A.Neumann 1 3 Algorithm 2: An AlgorithmtoFindan Acyclic Ordering (ifitexists) Data: Afamily of digraphs (D(d))d∈U Result: An ordering (d1,...,du)ofUsatisfying (iii) or ∅(ifnosuchordering exists) 1ˆ V←− U 2I←− setofall d∈U with indegree 0inD(d) 3O←− am emptylist 4while Inon-empty do 5removeanelement dfrom I 6removedfrom ˆ V 7add dto the tailofO 8for ˆ d∈ˆ Vdo 9D(ˆ d)←GraphModification(D(ˆ d),d)) 10 if ˆ dhas no incoming arcs in D(ˆ d)then 11 add ˆ dto I 12 if ˆ Vis non-empty then 13 return ∅ 14 else 15 return O The proof that the algorithm works as desired relies on the following two easy-to- verify properties of Algorithm1: Lemma A.1 Let D be a digraph, x be a vertex of D and  D=(  V,  A) be the digraph resulting from Algorithm1 applied for D and x. Then the following statements hold: (i) Let x 1 ,x 2 ∈  V . Then there is a path from x1 to x2 in D if and only if there is a path from x1 to x2 in  D . (ii) Let ≤ D be an acyclic ordering of  D . Then there is an acyclic ordering ≤ of D such that x 1≤ x 2 ⇔x 1≤ D x 2 for all x 1 ,x 2 ∈  V . (iii) Let ≤D be an acyclic ordering of D. Then there is an acyclic ordering ≤ of  D such that x1≤x2 ⇔ x1≤Dx2 for all x 1 ,x 2 ∈  V . Theorem A.2 The algorithm is correct, that is whenever an ordering exists the algorithm finds one and if no ordering exists the algorithm returns ∅ . Proof If the algorithm returns an ordering O=(d1,…,du) , then in each step we find a strategy di such that di has indegree 0 in the digraph Since di has indegree 0, we obtain (for example by using the standard algorithm to find an acyclic ordering, which was informally described in the beginning of this section) an acyclic ordering of  D(d i ) such that di≤dj for all j>i . By CorollaryA.1,  D(di)=GraphModification(… GraphModification(D(di),d1),…,di−1). 189 1 3 A myopic adjustment process formean field games withfinite… again a contradiction. Thus, it either holds that g(m(t)) <0 for all t≥0 or that g(m(t)) >0 for all t≥T with T≥0 , which by the first observation yields the desired convergence. Analogously, in case (ii) we obtain that whenever g(m(T)) = 0 for some T≥0 , then g(m(t)) <0 for all t>T . In case (iii) we have that whenever g(m(T)) = 0 for some T≥0 , then g(m(t)) = 0 for all t≥T . Indeed, assume that there is a  t>T such that g(m( t)) >0 . Since g is Lipschitz continuous and m is Lipschitz continuous as long as g(m(⋅)) >0 we have that there is an 𝜖>0 such that g(m( t−𝜖)) = 0 and g(m(t)) >0 for all  t−𝜖<t≤ t . In particular for some 𝜖2∈(0, 𝜖1) we have for almost all  t−𝜖1<t≤ t−𝜖2 that a contradiction. Similarly, we obtain for the case that there is a  t>T such that g(m( t)) <0 that there are 0<𝜖 2<𝜖 1 such that for almost all  t−𝜖1<t≤ t−𝜖2 we have again a contradiction. Thus, either g(m(t)) <0 for all t≥0 , or g(m(t)) >0 for all t≥0 , in which case we obtain convergence towards some stationary equilibrium with a deterministic equilibrium strategy, or there is a T>0 such that g(m(t)) = 0 for all t≥T . ◻ Lemma B.1 Let AssumptionsA2,A3 andA4 hold. Moreover, assume that for all d1,d2∈U satisfying Optsome(d1)∩Optsome(d2)≠� we either have for all m∈Optsome(d1)∩Optsome(d2) such that mi=0 for some i∈S or for all m∈Optsome(d1)∩Optsome(d2) such that mi=0 for some i∈S . Then the set P(S) is flow invariant for m∈F(m) . Proof We first note that { m∈ℝ S ∶ ∑i∈S m i =1 } is flow invariant for F since ∑i∈S mi(t)=0 holds almost surely because all transition rate matrices are conservative. Therefore, if at time  t1 a solution of m∈F(m) leaves the set P(S) at least one component mi( t1) has to be zero. By AssumptionA4 there are at most two strategies d1,d2∈U such that gd 1 (m( t1)) ≤ 0 and gd 2 (m( t1)) ≤ 0 . In particular, there is an 𝜖>0 such that gd(m)>0 for all d≠d1,d2 and m∈N𝜖(m( t1)) . Let us define 𝜙=gd1 and note that gd2(m)=gd1(m) for m∈Optsome(d1)∩Optsome(d2) . Thus, the consistency condition yields that one of the following three cases will hold for all m∈Optsome(d1)∩Optsome(d2) simultaneously: • ⟨(Q d 1(m)) T m,∇𝜙(m)⟩>0 and ⟨(Q d 2(m)) T m,∇−𝜙(m)⟩<0 0 < 𝜕 𝜕t g(m(t)) = ⟨ Qd2(m(t))Tm(t),∇g(m(t)) ⟩≤0, 0 > 𝜕 𝜕t g(m(t)) = ⟨ Qd1(m(t))Tm(t),∇g(m(t)) ⟩≥0, ⟨(Qd(m))Tm,∇gd 1 (m)⟩>0 ⟨ (Q d (m)) T m,∇g d 1(m) ⟩<0 190 B.A.Neumann 1 3 • ⟨(Q d 1(m)) T m,∇𝜙(m)⟩<0 and ⟨( Qd 2( m )) Tm ,∇−𝜙( m )⟩>0 • ⟨(Q d 1(m)) T m,∇𝜙(m)⟩>0 and ⟨( Qd 2( m )) Tm ,∇−𝜙( m )⟩>0. In particular, the results presented in Filippov (1988,§4 and §10) yield that the solution in N 𝜖( m ( t 1)) is the solution of a classical ordinary differential equation m=(  Q(m))Tm with  Q(m) being Q d 1(m) in the first case, Q d 2(m) in the second case and in the third case. In all three cases we obtain that  Q(⋅) is Lipschitz continuous. Moreover, we have that P(S) is flow invariant for m=(  Q(m))Tm with  Q(m) : Indeed, it suffices to show that (  Q(m)) T m∈TP ( S ) (m ) , which works as in the proof of Theorem3.2. All in all, this is the desired contradiction. ◻ In order to prove Theorem5.4 we first present two auxiliary lemmata describing flow invariant sets for m∈F(m) : Lemma B.2 Let ≤ be an ordering of U satisfying (iii) and enumerate the deterministic stationary strategies such that d1≤d2≤⋯≤du . Furthermore, let 1≤k≤u . Then the set is flow invariant for F. Proof We prove the statement by backward induction on k. Let first k=u and assume that m∶[0, ∞) → ℝ S is a solution of m∈F(m) starting in m0∈P(S)∩Optsome(du) . By AssumptionA5 we immediately have that m(t)∈P(S) for all t≥0 . Moreover, it is immediate by definition of Optsome(du) as well as gdu that gd u (m(0)) ≤0 . We will now prove that whenever there is a T≥0 such that gd u (m(T)) = 0 then gd u (m(t)) ≤0 for all t>T . This and the continuity of the function gdu then yields, again by definition of Optsome(du) as well as gdu the desired claim. So assume that there is a T1>0 such that gd u (m(T1)) >0 . Then by the Lipschitz continuity of gdu there is a T2≥0 and a 𝛿>0 such that gd u (m(T2)) = 0 and gd u (m(t)) >0 for all t∈(T2,T2+𝛿] . Then by definition of Optsome(du) as well as gdu and AssumptionA4 we immediately have that there is a unique strategy dl∈ U ⧵{du} such that gd l (m(T2)) = 0 . Moreover, there is an 𝜖1∈(0, 𝛿) such that gd l (m(t)) <0 for all t∈(T2,T2+𝜖1) : Indeed, assume that there is no 𝜖>0 satisfying this property. Then for all n∈ℕ ⟨ (Qd 1 (m))Tm,∇𝜙(m) ⟩ ⟨ (Qd1(m))Tm,∇𝜙(m)⟩+�−⟨(Qd2(m))Tm,∇𝜙(m)⟩�Qd1(m) +− ⟨ (Qd2(m))Tm,∇𝜙(m) ⟩ ⟨ (Qd1(m))Tm,∇𝜙(m) ⟩ + � − ⟨ (Qd2(m))Tm,∇𝜙(m) ⟩� Qd2(m ) P (S)∩ (⋃ l≥k Optsome(dl) ) 191 1 3 A myopic adjustment process formean field games withfinite… there is a t n∈[T,T+ 1 n] such that gd l (m(tn)) ≥0 . Let n1 k be the subsequence such that g dl (m(t n1 k)) = 0 and let n2 k be the subsequence such that g dl (m(t n2 k)) >0 . At least one of these sequences consist of infinitely many elements. Let us first assume that ( n 1 k ) k∈ℕ consists of infinitely many elements. Then, by definition of Optsome(dl) as well as gdl , there is another strategy d n 1 k ≠d u ,dl such that gd n1 k(m(t n1 k)) = 0 . Since U is finite there is at least one strategy dj that occurs infinite many times in the sequences (d n k 1 )k∈ℕ . Let us choose a subsequence ( n 3 i ) i∈ℕ such that d n 3 i =dj for all i∈ℕ . Then we obtain that (t n3 i ) i∈ ℕ is a sequence converging to T2 such that g dj (m(t n3 i)) = 0 for all i∈ℕ . In particular, by continuity, we obtain gd j (m(T2)) = 0 , a contradiction. Let us now assume that ( n 2 k ) k∈ℕ consists of infinitely many elements. By AssumptionA4 and by definition of gd there is at least one strategy d n 2 k ≠d u ,dl such that gd n2 k(m(t n2 k)) ≤0 . Since U is finite there is at least one strategy dj that occurs infinitely many times in the sequence ( dn 2 k) k∈ℕ . Let ( n 4 k ) k∈ℕ be the sequence such that d j =d n 4 k . Now we obtain that (t n4 k) k∈ ℕ is a sequence converging to T2 and that satisfies g dj (m(t n4 k)) ≤0 . Therefore, by continuity of gdj , we obtain gd j (m(T2)) ≤ 0 , a contradiction. By definition of the ordering ≤ , we have that dl≤D(d l ) d u in the acyclic ordering ≤D(d l ) of the graph D(dl) . This means that there is no edge from du to dl in D(dl) , which by definition of the digraph means that for all m∈Optsome(du)∩Optsome(dl) . In total, we obtain for some 𝜖2∈(0, 𝜖1) and for almost all t∈(T2,T2+𝜖2) that holds, a contradiction. Let now k<u and assume that m∶[0, ∞) → ℝ S is a solution of m∈F(m) starting in m0 ∈P(S)∩ ⋃l≥k Opt some (d l) . By Assumption A5 we immediately have that m(t)∈P(S) . Moreover, by the induction hypothesis, the set P (S)∩ ⋃l≥k+1 Opt some (d l) is flow invariant. Therefore, if the trajectory would leave P (S)∩ ⋃l≥k Opt some (d l) , then for T =sup{t ≥ 0∶m(t)∈P(S)∩ ⋃l≥k Opt some (d l)} we would have that m(T)∈Optsome(dk) . As before, by definition of Optsome(dk) and gdk , this is equivalent to gd k (m(T)) = 0 and gd k (t)>0 for some 𝛿>0 and all t∈(T,T+𝛿) . By definition of Optsome(d) and d, AssumptionA5 and the requirement that m leaves the set P (S)∩ ⋃l≥k Opt some (d l) after T we obtain that there is a unique l<k such that gd l (m(T)) = 0 . As in the base case we can now prove that there is an 𝜖1∈(0, 𝛿) such that gd l (m(t)) <0 for all t∈(T,T+𝜖1) . The ordering ≤ now yields that dl≤D(d l ) d k in the acyclic ordering ≤D(d l ) of the graph D(dl) . This means that there is no edge from dk to dl in D(dl) , which by definition of the digraph means that ⟨( Qd l( m )) Tm ,∇ g d u ( m )⟩≤0 0 < 𝜕 𝜕t gdu(m(t)) = ⟨ (Qdl(m))Tm,∇gdu(m) ⟩ < 0 192 B.A.Neumann 1 3 for all m∈Optsome(dk)∩Optsome(dl) . In total, we obtain for some 𝜖2∈(0, 𝜖1) and for almost all t∈(T,T+𝜖2) that holds, a contradiction. ◻ Lemma B.3 Let d∈U be a deterministic stationary strategy such that for any other strategy  d∈ U ⧵{d} either Optsome(d)∩Optsome( d)=� or  d→d∉D(  d) with Then P( S )∩Optunique(d) is flow invariant for F. Proof Let m∶[0, ∞) → ℝ S be a solution of m∈F(m) starting in m0∈ P ( S )∩Optunique(d) . By AssumptionA5 it is immediate that m(t)∈P(S) for all t≥0 . By definition of Optunique(d) it is moreover immediate that gd(m(0)) <0 . Now assume that there is a T>0 such that gd(m(T)) = 0 . Then, by definition of Optsome(d) and g d and AssumptionA4, there is a unique strategy  d∈ U ⧵{d} such that g d(m(T)) = 0 . Now the assumption of the lemma yields that In total, we obtain, since gd is twice continuously differentiable, that for some 𝜖>0 and almost all t∈(T−𝜖,T) we have a contradiction. ◻ Proof of Theorem5.4 We note that if a trajectory stays inside a set Optunique(d) for all t>T , then by condition (i) the trajectory will converge towards a stationary point given Qd(⋅) . Let d1,…,du be an ordering that satisfies (iii) and assume that i is maximal such that m (0)∈P(S)∩ �⋃k≥i Opt some (dk) � , then m(0)∈Optsome(di) . If the trajectory does not leave the set P( S )∩Optunique(d i ) we have by the previous observation convergence towards a deterministic stationary mean field equilibrium. Else, by the flow invariance of P(S) there is a t0≥0 such that the trajectory will stay in for all t≥t0 or there is a t1>0 such that m(t1)∉P(S)∩Optsome(di) . Then we find, since P (S)∩ �⋃k≥i Opt some (d k ) � is flow invariant an  i>i such that m (t 1 )∈P(S)∩ �⋃k≥  i Opt some (d k ) � and we can reapply the previous argument. ⟨ (Qdl(m))Tm,∇gdk(m) ⟩≤0 0 < 𝜕 𝜕t gdk(m(t)) = ⟨ (Qdl(m))Tm,∇gdk(m) ⟩≤0 ⟨(Qd(m))Tm,∇gd(m)⟩<0 for all m∈Optsome(d)∩Optsome( d). ⟨ (Q d (m)) T m,∇g d (m) ⟩ <0 for all m∈Opt some (d)∩Opt some (  d) . 0 < 𝜕 𝜕t gd(m(t)) = ⟨ (Qd(m(t)))Tm,∇gd(m(t)) ⟩ < 0, P (S)∩ ( Opt some (d i )⧵Opt unique (d i ) ) 193 1 3 A myopic adjustment process formean field games withfinite… If we reach the final vertex d of an ordering that satisfies (iii) and there is another strategy  d that is also the final vertex of an ordering, then we obtain that both P(S)∩Optsome(d) and P( S )∩Optsome(  d) are flow invariant, which in particular yields that P( S )∩Optsome(d)∩Optsome(  d) is flow invariant, which yields that whenever a trajectory leaves P( S )∩Optunique(d) , then it will remain in for all times, which proves the claim. If there is a unique final vertex d then we obtain, by Lemma B.3, that P( S )∩Optunique(d) is flow invariant. Thus, if the trajectory leaves the set P( S )∩Optsome(d)⧵Optunique(d) , then we have convergence towards a deterministic stationary mean field equilibrium. ◻ Funding Open Access funding enabled and organized by Projekt DEAL. Data availability Not applicable since no datasets were generated or analysed in the study. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http:// creat iveco mmons. org/ licen ses/ by/4. 0/. References Asmussen S (2003) Applied probability and queues, Stochastic modelling and applied probability, vol 51, 2nd edn. Springer, New York, ISBN 0-387-00211-1 Aubin J-P, Cellina A (1984) Differential inclusions: set-valued maps and viability theory, Grundlehren der mathematischen Wissenschaften, vol 264. Springer, Berlin. https:// doi. org/ 10. 1007/ 978-3- 642- 69512-4 Bang-Jensen J, Gutin GZ (2010) Digraphs: theory, algorithms and applications. Springer Monographs in Mathematics, 2nd edn. Springer, London, ISBN 978-0-85729-041-0 Belak C, Hoffmann D, Seifried FT (2021) Continuous-time mean field games with finite state space and common noise. Appl Math Optim 84:3173–3216. https:// doi. org/ 10. 1007/ s00245- 020- 09743-7 Bensoussan A, Frehse J, Yam P (2013) Mean field games and mean field type control theory. Springer Briefs in Mathematics. Springer, New York. ISBN 978-1-4614-8507-0 Besancenot D, Dogguy H (2015) Paradigm shift: a mean field game approach. Bull Econ Res 67(3):289– 302. https:// doi. org/ 10. 1111/ boer. 12024 Briani A, Cardaliaguet P (2018) Stable solutions in potential mean field game systems. Nonlinear Differ Equ Appl NoDEA 25(1). https:// doi. org/ 10. 1007/ s00030- 017- 0493-3 Cardaliaguet P (2013) Notes on mean field games (from P.-L. Lions’ Lectures at Collège de France). https:// www. cerem ade. dauph ine. fr/ ~carda liagu et/ MFG20 130420. pdf Cardaliaguet P, Hadikhanloo S (2017) Learning in mean field games: the fictitious play. ESAIM Control Optim Calc Var 23 (2):569–591. https:// doi. org/ 10. 1051/ cocv/ 20160 04 P( S )∩Optsome(d)∩Optsome( d)⊆ P ( S )∩Optsome(d)⧵Optunique(d) 194 B.A.Neumann 1 3 Carmona R, Delarue F (2018a) Probabilistic theory of mean field games with applications I: mean field FBSDEs, control, and games, Probability Theory and Stochastic Modelling, vol 83. Springer International Publishing. https:// doi. org/ 10. 1007/ 978-3- 319- 58920-6 Carmona R, Delarue F (2018b) Probabilistic theory of mean field games with applications II: mean field games with common noise and master equations, Probability Theory and Stochastic Modelling, vol 84. Springer International Publishing. https:// doi. org/ 10. 1007/ 978-3- 319- 56436-4 Carmona R, Wang P (2021) A probabilistic approach to extended finite state mean field games. Math Oper Res 46(2):471–502. https:// doi. org/ 10. 1287/ moor. 2020. 1071 Cecchin A, Fischer M (2018) Probabilistic approach to finite state mean field games. Appl Math Optim. https:// doi. org/ 10. 1007/ s00245- 018- 9488-7 Deimling K (1992) Multivalued differential equations, de Gruyter Series in Nonlinear Analysis and Applications, vol 1. Walter de Gruyter & Co., Berlin, ISBN 3-11-013212-5 Doncel J, Gast N, Gaujal B (2019) Discrete mean field games: existence of equilibria and convergence. J Dyn Games 6(3):221–239. https:// doi. org/ 10. 3934/ jdg. 20190 16 Filippov AF (1988) Differential equations with discontinuous righthand sides, Mathematics and its Applications, vol 18. Springer Netherlands, Dordrecht. https:// doi. org/ 10. 1007/ 978- 94- 015- 7793-9 Fudenberg D, Levine DK (1998) The theory of learning in games, MIT Press Series on Economic Learning and Social Evolution, vol 2. The MIT Press, Cambridge, ISBN 978-0-262-06194-0 Gomes DA, Mohr J, Souza RR (2013) Continuous time finite state mean field games. Appl Math Optim 68(1):99–143. https:// doi. org/ 10. 1007/ s00245- 013- 9202-8 Gomes D, Velho RM, Wolfram M-T (2014) Socio-economic applications of finite state mean field games. Philos Trans R Soc A 372:20130405. https:// doi. org/ 10. 1098/ rsta. 2013. 0405 Guo X, Hernández-Lerma O (2009) Continuous-time Markov decision processes: theory and applications, Stochastic Modelling and Applied Probability, vol 62. Springer, Berlin, ISBN 978-3-642-26072-8 Guo X, Hu A, Xu R, Zhang J (2019) Learning mean-field games. In: Wallach H, Larochelle H, Beygelzimer A, d’Alché Buc F, Fox E, Garnett R (eds) Advances in neural information processing systems, vol32 Hadikhanloo S (2017) Learning in anonymous nonatomic games with applications to first-order mean field games. Preprint. arXiv: 1704. 00378 Hadikhanloo S (2018) Learning in mean field games. PhD thesis, Université Paris-Dauphine, Paris. http:// www. cmap. polyt echni que. fr/ ~saeed. hadik hanloo/ PhD_ Thesis. pdf Hirsch MW, Smale S (1974) Differential equations, dynamical systems, and linear algebra. Pure and Applied Mathematics. A Series of Monographs and Textbooks. Academic Press Inc, Orlando. ISBN 0-12-349550-4 Hofbauer J, Sandholm WH (2009) Stable games and their dynamics. J Econ Theory 144(4):1665–1693. https:// doi. org/ 10. 1016/j. jet. 2009. 01. 007 Huang M, Malhamé RP, Caines PE (2006) Large population stochastic dynamic games: closed-loop McKean–Vlasov systems and the Nash certainty equivalence principle. Commun Inf Syst 6(3):221– 252. https:// proje cteuc lid. org/ euclid. cis/ 11837 28987 Kolokoltsov VN (2010) Nonlinear Markov processes and kinetic equations, Cambridge Tracts in Mathematics, vol 182. Cambridge University Press, Cambridge, ISBN 978-0-521-11184-3 Kolokoltsov VN, Bensoussan A (2016) Mean-field-game model for botnet defense in cyber-security. Appl Math Optim 74(3):669–692. https:// doi. org/ 10. 1007/ s00245- 016- 9389-6 Kolokoltsov VN, Malafeyev OA (2017) Mean-field-game model of corruption. Dyn Games Appl 7(1):34–47. https:// doi. org/ 10. 1007/ s13235- 015- 0175-x Kolokoltsov VN, Malafeyev OA (2018) Corruption and botnet defense: a mean field game approach. Int J Game Theory 47:977–999. https:// doi. org/ 10. 1007/ s00182- 018- 0614-1 Lasry J-M, Lions P-L (2007) Mean field games. Jpn J Math 2(1):229–260. https:// doi. org/ 10. 1007/ s11537- 007- 0657-8 Lauriére M, Perrin S, Geist M, Pietquin O (2022) Learning mean field games: a survey. arXiv: 2205. 12944 Logemann H, Ryan EP (2014) Ordinary differential equations: analysis, qualitative theory and control. Springer Undergraduate Mathematics Series. Springer, London. ISBN 978-1-4471-6397-8 Marden JR (2012) State based potential games. Automatica 48(12):3075–3088. https:// doi. org/ 10. 1016/j. autom atica. 2012. 08. 037 Maskin E, Tirole J (2001) Markov perfect equilibrium: I. Observable actions. J Econ Theory 100(2):191– 219. https:// doi. org/ 10. 1006/ jeth. 2000. 2785 195 1 3 A myopic adjustment process formean field games withfinite… Mouzouni C (2018) On quasi-stationary mean field games models. Appl Math Optim. https:// doi. org/ 10. 1007/ s00245- 018- 9484-y Nachbar J (2009) Learning in games. In: Meyers RA (ed) Encyclopedia of complexity and systems science. Springer, New York, pp 5177–5187. https:// doi. org/ 10. 1007/ 978-0- 387- 30440-3_ 307 Neumann BA (2019) Stationary equilibria of mean field games with finite state and action space: existence, computation, stability, and a myopic adjustment process. PhD thesis, Universität Hamburg. https:// ediss. sub. unihambu rg. de/ vollt exte/ 2020/ 10313/ Neumann BA (2020) Stationary equilibria of mean field games with finite state and action space. Dyn Games Appl 10:845–871. https:// doi. org/ 10. 1007/ s13235- 019- 00345-9 Neumann BA (2023) Nonlinear Markov chains with finite state space: invariant distributions and longterm behaviour. J Appl Probab 60(1):30–44. https:// doi. org/ 10. 1017/ jpr. 2022. 23 Perrin S, Perolat J, Laurière M, Geist M, Elie R, Pietquin O (2020) Fictitious play for mean field games: continuous time analysis and applications. In: Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H (eds) Advances in neural information processing systems, vol 33 Sandholm WH (2010) Population games and evolutionary dynamics. Economic learning and social evolution. MIT Press, Cambridge. ISBN 978-0-262-19587-4 Sandholm WH (2014) Local stability of strict equilibria under evolutionary game dynamics. J Dyn Games 1(3):485–495. https:// doi. org/ 10. 3934/ jdg. 2014.1. 485 Sandholm WH (2015) Population games and deterministic evolutionary dynamics, chapter13. In: Young HP, Zamir S (eds) Handbook of game theory with economic applications, vol 4. Elsevier, pp 703– 778. https:// doi. org/ 10. 1016/ B978-0- 444- 53766-9. 00013-6 Zusai D (2020) Gains in evolutionary dynamics: a unifying and intuitive approach to linking static and dynamic stability. arXiv: 1805. 04898 v7 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.