Finite State N-player and Mean Field Games

Mean field games represent limit models for symmetric non-zero sum dynamic games when the number N of players tends to infinity. In this thesis, we study mean field games and corresponding N- player games in continuous time over a finite time horizon where the position of each agent belongs to a finite state space. As opposed to previous works on finite statemean field games, we use a probabilistic representation of the system dynamics in terms of stochastic differential equations driven by Poisson random measures. Firstly, under mild assumptions, we prove existence of solutions to the mean field game in relaxed open-loop as well as relaxed feedback controls. Relying on the probabilistic representation and a coupling argument, we show that mean field game solutions provide symmetric εN- Nash equilibria for the N-player game, both in open-loop and in feedback strategies (not relaxed), with εN≤ constant √N. Under stronger assumptions, we also find solutions of the mean field game in ordinary feedback controls and prove uniqueness either in case of a small time horizon or under monotonicity. Then, assuming that players control just their transition rates from state to state, we show the convergence, as N tends to infinity, of the N-player game to a limiting dynamics given by a finite state mean field game system made of two coupled forward-backward ODEs. We exploit the so-called master equation, which in this finite-dimensional framework is a first order PDE in the simplex of probability measures. If the master equation possesses a unique regular solution, then such solution can be used to prove the convergence of the value functions of the N players and of the feedback Nash equilibria, and a propagation of chaos property for the associated optimal trajectories. A sufficient condition for the required regularity of the master equation is given by the monotonicity assumptions. Further, we employ the convergence results to establish a Central Limit Theorem and a Large Deviation Principle for the evolution of the N-player optimal empirical measures. Finally, we analyze an example with<−1,1> as state space and anti-monotonous cost,and show that the mean field game has exactly three solutions. The Nash equilibrium is always unique and we prove that the N-player game always admits a limit: it selects one mean field game solution, except in one critical case, so there is propagation of chaos. The value functions also converge and the limit is the entropy solution to the master equation, which for two state models can be written as a scalar conservation law. Moreover, viewing the mean field game system as the necessary conditions for optimality of a deterministic control problem, we show that the N-player game selects the optimum of this problem when it is unique.

I giochi a campo medio rappresentano modelli limite per giochi dinamici, simmetrici ed a somma non zero, quando il numero N di giocatori tende all’infinito. In questa tesi consideriamo giochi a campo medio e ad N giocatori in cui la posizione di ogni giocatore appartiene ad un insieme degli stati finito. Il tempo è continuo e l’orizzonte temporale è finito. A differenza dei precedenti lavori sull’argomento, utilizziamo una rappresentazione probabilistica delle dinamiche in termini di equazioni differenziali stocastiche rispetto a misure aleatorie di Poisson. Per prima cosa dimostriamo l’esistenza di soluzioni del gioco a campo medio con controlli rilassati, sia open-loop che feedback, in ipotesi piuttosto generali. Basandoci sulla rappresentazione probabilistica e su un argomento di accoppiamento, mostriamo che le soluzioni del gioco a campo medio forniscono εN equilibri di Nash per il gioco ad N giocatori, in strategie sia open-loop che feedback (non rilassate), con εN≤ costante √N. In ipotesi più forti troviamo anche soluzioni del gioco a campo medio con controlli feedback ordinari e dimostriamo l’unicità se l’orizzonte temporale è abbastanza piccolo oppure sotto ipotesi di monotonia. Poi, assumendo che i giocatori controllino solamente il proprio tasso di transizione da stato a stato, mostriamo la convergenza, per N che tende all’infinito, del gioco ad N giocatori alla dinamica limite data dal sistema del gioco a campo medio costituito da due ODE accoppiate, una in avanti e l’altra all’indietro. Sfruttiamo la cosiddetta master equation che nel presente contesto finito dimensionale è una PDE del primo ordine nel simplesso delle misure di probabilità. Se la master equation possiede una soluzione classica, allora tale solutione può essere usata per provare la convergenza delle funzioni valore degli N giocatori e degli equilibri di Nash feedback, ed anche la proprietà di propagazione del chaos per le traiettorie ottimali associate. Una condizione sufficiente per la regolarità richiesta per la master equation è data dalle ipotesi di monotonia. Inoltre impieghiamo il risultato di convergenza per stabilire un Teorema Limite Centrale ed un Principio delle Grandi Deviazioni per l’evoluzione delle misure empiriche ottimali. Infine analizziamo un’esempio in cui lo spazio degli stati è <−1,1> ed il costo è anti-monotono, e mostriamo che il gioco a campo medio possiede esattamente tre soluzioni. L’equilibrio di Nash è sempre unico e proviamo che il gioco ad N giocatori ammette sempre un limite: seleziona una singola soluzione del gioco a campo medio, tranne in un caso critico, pertanto c’è propagazione del chaos. Anche le funzioni valore convergono ed il limite è dato dalla soluzione di entropia della master equation, la quale in questo caso può essere scritta come una legge di conservazione scalare. Inoltre, vedendo il sistema del gioco a campo medio come le condizioni necessarie di ottimalità di un problema di controllo deterministico, mostriamo che il gioco ad N giocatori seleziona esattamente l’ottimo di questo problema quando è unico.