More Like this

1. A Probabilistic Approach to Extended Finite State Mean Field Games

   https://doi.org/10.1287/moor.2020.1071  

   Carmona, René; Wang, Peiqi (May 2021, Mathematics of Operations Research)

   null (Ed.)

   We develop a probabilistic approach to continuous-time finite state mean field games. Based on an alternative description of continuous-time Markov chains by means of semimartingales and the weak formulation of stochastic optimal control, our approach not only allows us to tackle the mean field of states and the mean field of control at the same time, but also extends the strategy set of players from Markov strategies to closed-loop strategies. We show the existence and uniqueness of Nash equilibrium for the mean field game as well as how the equilibrium of a mean field game consists of an approximative Nash equilibrium for the game with a finite number of players under different assumptions of structure and regularity on the cost functions and transition rate between states. 

   more » « less
2. On non-unique solutions in mean field games

   https://doi.org/10.1109/CDC40024.2019.9029906  

   Hajek, Bruce; Livesay, Michael (December 2019, 2019 58th Conference on Decision and Control)

   The theory of mean field games is a tool to understand noncooperative dynamic stochastic games with a large number of players. Much of the theory has evolved under conditions ensuring uniqueness of the mean field game Nash equilibrium. However, in some situations, typically involving symmetry breaking, non-uniqueness of solutions is an essential feature. To investigate the nature of non-unique solutions, this paper focuses on the technically simple setting where players have one of two states, with continuous time dynamics, and the game is symmetric in the players, and players are restricted to using Markov strategies. All the mean field game Nash equilibria are identified for a symmetric follow the crowd game. Such equilibria correspond to symmetric $$\epsilon$$-Nash Markov equilibria for $$N$$ players with $$\epsilon$$ converging to zero as $$N$$ goes to infinity. In contrast to the mean field game, there is a unique Nash equilibrium for finite $N.$ It is shown that fluid limits arising from the Nash equilibria for finite $$N$$ as $$N$$ goes to infinity are mean field game Nash equilibria, and evidence is given supporting the conjecture that such limits, among all mean field game Nash equilibria, are the ones that are stable fixed points of the mean field best response mapping. 

   more » « less
3. Linear-Quadratic Stochastic Differential Games on Directed Chain Networks

   Yichen Feng, Jean-Pierre Fouque (January 2020, Journal of mathematics and statistical science)

   We study linear-quadratic stochastic differential games on directed chains inspired by the directed chain stochastic differential equations introduced by Detering, Fouque and Ichiba. We solve explicitly for Nash equilibria with a finite number of players and we study more general finite-player games with a mixture of both directed chain in- teraction and mean field interaction. We investigate and compare the corresponding games in the limit when the number of players tends to infinity. The limit is characterized by Catalan functions and the dy- namics under equilibrium is an infinite-dimensional Gaussian process described by a Catalan Markov chain, with or without the presence of mean field interaction. 

   more » « less
4. Linear-Quadratic Stochastic Differential Games on Directed Chain Networks

   Feng, Yichen; Fouque, Jean-Pierre; Ichiba, Tomoyuki (January 2021, Journal of mathematics and statistical science)

   null (Ed.)

   We study linear-quadratic stochastic differential games on directed chains inspired by the directed chain stochastic differential equations introduced by Detering, Fouque and Ichiba. We solve explicitly for Nash equilibria with a finite number of players and we study more general finite-player games with a mixture of both directed chain interaction and mean field interaction. We investigate and compare the corresponding games in the limit when the number of players tends to infinity. The limit is characterized by Catalan functions and the dynamics under equilibrium is an infinite-dimensional Gaussian process described by a Catalan Markov chain, with or without the presence of mean field interaction. 

   more » « less
5. On the existence of Nash Equilibrium in games with resource-bounded players

   Halpern, Joseph Y; Pass, Rafael; Reichman, Daniel (September 2019, Proceedings of the 12th International Symposium on A Game Theory (SAGT)})

   We consider computational games, sequences of games G = (G1,G2,...) where, for all n, Gn has the same set of players. Computational games arise in electronic money systems such as Bitcoin, in cryptographic protocols, and in the study of generative adversarial networks in machine learning. Assuming that one-way functions exist, we prove that there is 2-player zero-sum computational game G such that, for all n, the size of the action space in Gn is polynomial in n and the utility function in Gn is computable in time polynomial in n, and yet there is no ε-Nash equilibrium if players are restricted to using strategies computable by polynomial-time Turing machines, where we use a notion of Nash equilibrium that is tailored to computational games. We also show that an ε-Nash equilibrium may not exist if players are constrained to perform at most T computational steps in each of the games in the sequence. On the other hand, we show that if players can use arbitrary Turing machines to compute their strategies, then every computational game has an ε-Nash equilibrium. These results may shed light on competitive settings where the availability of more running time or faster algorithms can lead to a “computational arms race”, precluding the existence of equilibrium. They also point to inherent limitations of concepts such as “best response” and Nash equilibrium in games with resource-bounded players. 

   more » « less