
-
Previous Article
On class of non-transferable utility cooperative differential games with continuous updating
- JDG Home
- This Issue
-
Next Article
Foundations of semialgebraic gene-environment networks
Approachability in population games
1. | Jan C. Willems Center for Systems and Control, ENTEG, Fac. Science and Engineering University of Groningen |
2. | Dip. di Ingengneria, Università di Palermo, IT |
3. | Magdalen College, Oxford, UK |
This paper reframes approachability theory within the context of population games. Thus, whilst a player still aims at driving her average payoff to a predefined set, her opponent is no longer malevolent but instead is extracted randomly at each instant of time from a population of individuals choosing actions in a similar manner. First, we define the notion of 1st-moment approachability, a weakening of Blackwell's approachability. Second, since the endogenous evolution of the population's play is then important, we develop a model of two coupled partial differential equations (PDEs) in the spirit of mean-field game theory: one describing the best-response of every player given the population distribution, the other capturing the macroscopic evolution of average payoffs if every player plays her best response. Third, we provide a detailed analysis of existence, nonuniqueness, and stability of equilibria (fixed points of the two PDEs). Fourth, we apply the model to regret-based dynamics, and use it to establish convergence to Bayesian equilibrium under incomplete information.
References:
[1] |
R. J. Aumann,
Utility theory without the completeness axiom, Econometrica, 30 (1962), 445-462.
doi: 10.2307/1913746. |
[2] |
R. J. Aumann,
Markets with a continuum of traders, Econometrica, 32 (1964), 39-50.
doi: 10.2307/1913732. |
[3] |
R. J. Aumann and M. B. Maschler, Repeated Games with Incomplete Information, MIT Press, 1995.
![]() ![]() |
[4] |
F. Bagagiolo and D. Bauso,
Objective function design for robust optimality of linear control under state-constraints and uncertainty, ESAIM: Control, Optimisation and Calculus of Variations, 17 (2011), 155-177.
doi: 10.1051/cocv/2009040. |
[5] |
M. Bardi,
Explicit solutions of some linear-quadratic mean field games, Network and Heterogeneous Media, 7 (2012), 243-261.
doi: 10.3934/nhm.2012.7.243. |
[6] | |
[7] |
D. Bauso, E. Lehrer, E. Solan and X. Venel,
Attainability in repeated games with vector payoffs, INFORMS Mathematics of Operations Research, 40 (2015), 739-755.
doi: 10.1287/moor.2014.0693. |
[8] |
M. Benaïm, J. Hofbauer and S. Sorin, Stochastic approximations and differential inclusions, SIAM Journal on Control and Optimization, 44 (2005), 338–348.
doi: 10.1137/S0363012904439301. |
[9] |
D. Blackwell,
An analog of the minimax theorem for vector payoffs, Pacific J. Math., 6 (1956), 1-8.
doi: 10.2140/pjm.1956.6.1. |
[10] |
F. Blanchini,
Set invariance in control – a survey, Automatica, 35 (1999), 1747-1768.
doi: 10.1016/S0005-1098(99)00113-2. |
[11] |
L. E. Blume, A. Brandenburger and E. Dekel,
Lexicographic probabilities and choice under uncertainty, Econometrica, 59 (1991), 61-79.
doi: 10.2307/2938240. |
[12] |
N. Cesa-Bianchi and G. Lugosi, Prediction, Learning and Games, Cambridge University Press, 2006.
doi: 10.1017/CBO9780511546921.![]() ![]() ![]() |
[13] |
B. Edelman, M. Ostrovsky and M. Schwarz,
Internet advertising and the generalised second-price auction: Selling billions of dollars worth of keywords, American Economic Review, 97 (2007), 242-259.
|
[14] |
N. J. Elliot and N. J. Kalton,
The existence of value in differential games of pursuit and evasion, J. Differential Equations, 12 (1972), 504-523.
doi: 10.1016/0022-0396(72)90022-8. |
[15] |
Jeffrey C. Ely and William H. Sandholm,
Evolution in Bayesian games I: Theory, Games and Economic Behavior, 53 (2005), 83-109.
doi: 10.1016/j.geb.2004.09.003. |
[16] |
D. Foster and R. Vohra,
Regret in the on-line decision problem, Games and Economic Behavior, 29 (1999), 7-35.
doi: 10.1006/game.1999.0740. |
[17] |
John C. Harsanyi,
Games with incomplete information played by 'bayesian' players, i–iii. part ii. Bayesian equilibrium points, Management Science, 14 (1968), 320-334.
doi: 10.1287/mnsc.14.5.320. |
[18] |
S. Hart,
Adaptive heuristics, Econometrica, 73 (2005), 1401-1430.
doi: 10.1111/j.1468-0262.2005.00625.x. |
[19] |
S. Hart and A. Mas-Colell,
A general class of adaptive strategies, Journal of Economic Theory, 98 (2001), 26-54.
doi: 10.1006/jeth.2000.2746. |
[20] |
S. Hart and A. Mas-Colell,
Regret-based continuous-time dynamics, Games and Economic Behavior, 45 (2003), 375-394.
doi: 10.1016/S0899-8256(03)00178-7. |
[21] |
M. Y. Huang, P. E. Caines and R. P. Malhamé,
Large population stochastic dynamic games: Closed loop McKean-Vlasov systems and the nash certainty equivalence principle, Communications in Information and Systems, 6 (2006), 221-252.
doi: 10.4310/CIS.2006.v6.n3.a5. |
[22] |
M. Y. Huang, P. E. Caines and R. P. Malhamé,
Large-population cost-coupled LQG problems with non-uniform agents: Individual-mass behaviour and decentralized $\epsilon$-nash equilibria, IEEE Trans. on Automatic Control, 9 (2007), 1560-1571.
doi: 10.1109/TAC.2007.904450. |
[23] |
M. Y. Huang, P. E. Caines and R. P. Malhamé, Individual and mass behaviour in large population stochastic wireless power control problems: Centralized and nash equilibrium solutions., In Proc. of the IEEE Conference on Decision and Control, volume 42, pages 98–103, HI, USA, December 2003. |
[24] |
B. Jovanovic and R. W. Rosenthal,
Anonymous sequential games, Journal of Mathematical Economics, 17 (1988), 77-87.
doi: 10.1016/0304-4068(88)90029-8. |
[25] |
J.-M. Lasry and P.-L. Lions,
Jeux à champ moyen. I. Le cas stationnaire, Comptes Rendus Mathematique, 343 (2006), 619-625.
doi: 10.1016/j.crma.2006.09.019. |
[26] |
J.-M. Lasry and P.-L. Lions,
Jeux à champ moyen. II. horizon fini et controle optimal, Comptes Rendus Mathematique, 343 (2006), 679-684.
doi: 10.1016/j.crma.2006.09.018. |
[27] |
J.-M. Lasry and P.-L. Lions,
Mean field games, Japanese Journal of Mathematics, 2 (2007), 229-260.
doi: 10.1007/s11537-007-0657-8. |
[28] |
E. Lehrer,
Allocation processes in cooperative games, International Journal of Game Theory, 31 (2002), 341-351.
doi: 10.1007/s001820200123. |
[29] |
E. Lehrer,
Approachability in infinite dimensional spaces, International Journal of game Theory, 31 (2002), 253-268.
doi: 10.1007/s001820200115. |
[30] |
E. Lehrer,
A wide range no-regret theorem, Games and Economic Behavior, 42 (2003), 101-115.
doi: 10.1016/S0899-8256(03)00032-0. |
[31] |
E. Lehrer and E. Solan,
Excludability and bounded computational capacity strategies, Mathematics of Operations Research, 31 (2006), 637-648.
doi: 10.1287/moor.1060.0211. |
[32] |
E. Lehrer, E. Solan and D. Bauso, Repeated games over networks with vector payoffs: the notion of attainability, in Proceedings of the NetGCoop 2011, IEEE, Paris, France, 2011. |
[33] |
E. Lehrer and S. Sorin, Minmax via differential inclusion, Journal of Convex Analysis, 14(2): 271–273, 2007. |
[34] |
M. Maschler, E. Solan and S. Zamir, Game Theory, Cambridge University Press, Cambridge, 2013.
doi: 10.1017/CBO9780511794216.![]() ![]() ![]() |
[35] |
E. Roxin,
Axiomatic approach in differential games, J. Optim. Theory Appl., 3 (1969), 153-163.
doi: 10.1007/BF00929440. |
[36] |
W. H. Sandholm, Population Games and Evolutionary Dynamics, MIT Press, Cambridge, MA, 2010.
![]() ![]() |
[37] |
W. H. Sandholm,
Evolution in Bayesian games II: Stability of purified equilibria, Journal of Economic Theory, 136 (2007), 641-667.
doi: 10.1016/j.jet.2006.10.003. |
[38] |
A. S. Soulaimani, M. Quincampoix and S. Sorin,
Approachability theory, discriminating domain and differential games, SIAM Journal of Control and Optimization, 48 (2009), 2461-2479.
|
[39] |
P. Varaiya,
The existence of solutions to a differential game, SIAM Journal of Control and Optimization, 5 (1967), 153-162.
doi: 10.1137/0305009. |
[40] |
H. R. Varian,
Position auctions, International Journal of Industrial Organization, 25 (2007), 1163-1178.
doi: 10.1016/j.ijindorg.2006.10.002. |
[41] |
N. Vieille,
Weak approachability, Mathematics of Operations Research, 17 (1992), 781-791.
doi: 10.1287/moor.17.4.781. |
[42] |
John von Neumann,
Zur Theorie der Gesellschaftsspiele, Math. Ann., 100 (1928), 295-320.
doi: 10.1007/BF01448847. |
[43] |
S. Zamir, Bayesian games: Games with incomplete information, in Computational Complexity, Vol. 1–6, Springer, New York, 2012.
doi: 10.1007/978-1-4614-1800-9_16. |
show all references
References:
[1] |
R. J. Aumann,
Utility theory without the completeness axiom, Econometrica, 30 (1962), 445-462.
doi: 10.2307/1913746. |
[2] |
R. J. Aumann,
Markets with a continuum of traders, Econometrica, 32 (1964), 39-50.
doi: 10.2307/1913732. |
[3] |
R. J. Aumann and M. B. Maschler, Repeated Games with Incomplete Information, MIT Press, 1995.
![]() ![]() |
[4] |
F. Bagagiolo and D. Bauso,
Objective function design for robust optimality of linear control under state-constraints and uncertainty, ESAIM: Control, Optimisation and Calculus of Variations, 17 (2011), 155-177.
doi: 10.1051/cocv/2009040. |
[5] |
M. Bardi,
Explicit solutions of some linear-quadratic mean field games, Network and Heterogeneous Media, 7 (2012), 243-261.
doi: 10.3934/nhm.2012.7.243. |
[6] | |
[7] |
D. Bauso, E. Lehrer, E. Solan and X. Venel,
Attainability in repeated games with vector payoffs, INFORMS Mathematics of Operations Research, 40 (2015), 739-755.
doi: 10.1287/moor.2014.0693. |
[8] |
M. Benaïm, J. Hofbauer and S. Sorin, Stochastic approximations and differential inclusions, SIAM Journal on Control and Optimization, 44 (2005), 338–348.
doi: 10.1137/S0363012904439301. |
[9] |
D. Blackwell,
An analog of the minimax theorem for vector payoffs, Pacific J. Math., 6 (1956), 1-8.
doi: 10.2140/pjm.1956.6.1. |
[10] |
F. Blanchini,
Set invariance in control – a survey, Automatica, 35 (1999), 1747-1768.
doi: 10.1016/S0005-1098(99)00113-2. |
[11] |
L. E. Blume, A. Brandenburger and E. Dekel,
Lexicographic probabilities and choice under uncertainty, Econometrica, 59 (1991), 61-79.
doi: 10.2307/2938240. |
[12] |
N. Cesa-Bianchi and G. Lugosi, Prediction, Learning and Games, Cambridge University Press, 2006.
doi: 10.1017/CBO9780511546921.![]() ![]() ![]() |
[13] |
B. Edelman, M. Ostrovsky and M. Schwarz,
Internet advertising and the generalised second-price auction: Selling billions of dollars worth of keywords, American Economic Review, 97 (2007), 242-259.
|
[14] |
N. J. Elliot and N. J. Kalton,
The existence of value in differential games of pursuit and evasion, J. Differential Equations, 12 (1972), 504-523.
doi: 10.1016/0022-0396(72)90022-8. |
[15] |
Jeffrey C. Ely and William H. Sandholm,
Evolution in Bayesian games I: Theory, Games and Economic Behavior, 53 (2005), 83-109.
doi: 10.1016/j.geb.2004.09.003. |
[16] |
D. Foster and R. Vohra,
Regret in the on-line decision problem, Games and Economic Behavior, 29 (1999), 7-35.
doi: 10.1006/game.1999.0740. |
[17] |
John C. Harsanyi,
Games with incomplete information played by 'bayesian' players, i–iii. part ii. Bayesian equilibrium points, Management Science, 14 (1968), 320-334.
doi: 10.1287/mnsc.14.5.320. |
[18] |
S. Hart,
Adaptive heuristics, Econometrica, 73 (2005), 1401-1430.
doi: 10.1111/j.1468-0262.2005.00625.x. |
[19] |
S. Hart and A. Mas-Colell,
A general class of adaptive strategies, Journal of Economic Theory, 98 (2001), 26-54.
doi: 10.1006/jeth.2000.2746. |
[20] |
S. Hart and A. Mas-Colell,
Regret-based continuous-time dynamics, Games and Economic Behavior, 45 (2003), 375-394.
doi: 10.1016/S0899-8256(03)00178-7. |
[21] |
M. Y. Huang, P. E. Caines and R. P. Malhamé,
Large population stochastic dynamic games: Closed loop McKean-Vlasov systems and the nash certainty equivalence principle, Communications in Information and Systems, 6 (2006), 221-252.
doi: 10.4310/CIS.2006.v6.n3.a5. |
[22] |
M. Y. Huang, P. E. Caines and R. P. Malhamé,
Large-population cost-coupled LQG problems with non-uniform agents: Individual-mass behaviour and decentralized $\epsilon$-nash equilibria, IEEE Trans. on Automatic Control, 9 (2007), 1560-1571.
doi: 10.1109/TAC.2007.904450. |
[23] |
M. Y. Huang, P. E. Caines and R. P. Malhamé, Individual and mass behaviour in large population stochastic wireless power control problems: Centralized and nash equilibrium solutions., In Proc. of the IEEE Conference on Decision and Control, volume 42, pages 98–103, HI, USA, December 2003. |
[24] |
B. Jovanovic and R. W. Rosenthal,
Anonymous sequential games, Journal of Mathematical Economics, 17 (1988), 77-87.
doi: 10.1016/0304-4068(88)90029-8. |
[25] |
J.-M. Lasry and P.-L. Lions,
Jeux à champ moyen. I. Le cas stationnaire, Comptes Rendus Mathematique, 343 (2006), 619-625.
doi: 10.1016/j.crma.2006.09.019. |
[26] |
J.-M. Lasry and P.-L. Lions,
Jeux à champ moyen. II. horizon fini et controle optimal, Comptes Rendus Mathematique, 343 (2006), 679-684.
doi: 10.1016/j.crma.2006.09.018. |
[27] |
J.-M. Lasry and P.-L. Lions,
Mean field games, Japanese Journal of Mathematics, 2 (2007), 229-260.
doi: 10.1007/s11537-007-0657-8. |
[28] |
E. Lehrer,
Allocation processes in cooperative games, International Journal of Game Theory, 31 (2002), 341-351.
doi: 10.1007/s001820200123. |
[29] |
E. Lehrer,
Approachability in infinite dimensional spaces, International Journal of game Theory, 31 (2002), 253-268.
doi: 10.1007/s001820200115. |
[30] |
E. Lehrer,
A wide range no-regret theorem, Games and Economic Behavior, 42 (2003), 101-115.
doi: 10.1016/S0899-8256(03)00032-0. |
[31] |
E. Lehrer and E. Solan,
Excludability and bounded computational capacity strategies, Mathematics of Operations Research, 31 (2006), 637-648.
doi: 10.1287/moor.1060.0211. |
[32] |
E. Lehrer, E. Solan and D. Bauso, Repeated games over networks with vector payoffs: the notion of attainability, in Proceedings of the NetGCoop 2011, IEEE, Paris, France, 2011. |
[33] |
E. Lehrer and S. Sorin, Minmax via differential inclusion, Journal of Convex Analysis, 14(2): 271–273, 2007. |
[34] |
M. Maschler, E. Solan and S. Zamir, Game Theory, Cambridge University Press, Cambridge, 2013.
doi: 10.1017/CBO9780511794216.![]() ![]() ![]() |
[35] |
E. Roxin,
Axiomatic approach in differential games, J. Optim. Theory Appl., 3 (1969), 153-163.
doi: 10.1007/BF00929440. |
[36] |
W. H. Sandholm, Population Games and Evolutionary Dynamics, MIT Press, Cambridge, MA, 2010.
![]() ![]() |
[37] |
W. H. Sandholm,
Evolution in Bayesian games II: Stability of purified equilibria, Journal of Economic Theory, 136 (2007), 641-667.
doi: 10.1016/j.jet.2006.10.003. |
[38] |
A. S. Soulaimani, M. Quincampoix and S. Sorin,
Approachability theory, discriminating domain and differential games, SIAM Journal of Control and Optimization, 48 (2009), 2461-2479.
|
[39] |
P. Varaiya,
The existence of solutions to a differential game, SIAM Journal of Control and Optimization, 5 (1967), 153-162.
doi: 10.1137/0305009. |
[40] |
H. R. Varian,
Position auctions, International Journal of Industrial Organization, 25 (2007), 1163-1178.
doi: 10.1016/j.ijindorg.2006.10.002. |
[41] |
N. Vieille,
Weak approachability, Mathematics of Operations Research, 17 (1992), 781-791.
doi: 10.1287/moor.17.4.781. |
[42] |
John von Neumann,
Zur Theorie der Gesellschaftsspiele, Math. Ann., 100 (1928), 295-320.
doi: 10.1007/BF01448847. |
[43] |
S. Zamir, Bayesian games: Games with incomplete information, in Computational Complexity, Vol. 1–6, Springer, New York, 2012.
doi: 10.1007/978-1-4614-1800-9_16. |





[1] |
Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics and Games, 2021, 8 (4) : 445-465. doi: 10.3934/jdg.2021006 |
[2] |
Diogo A. Gomes, Gabriel E. Pires, Héctor Sánchez-Morgado. A-priori estimates for stationary mean-field games. Networks and Heterogeneous Media, 2012, 7 (2) : 303-314. doi: 10.3934/nhm.2012.7.303 |
[3] |
Tigran Bakaryan, Rita Ferreira, Diogo Gomes. A potential approach for planning mean-field games in one dimension. Communications on Pure and Applied Analysis, 2022, 21 (6) : 2147-2187. doi: 10.3934/cpaa.2022054 |
[4] |
Max-Olivier Hongler. Mean-field games and swarms dynamics in Gaussian and non-Gaussian environments. Journal of Dynamics and Games, 2020, 7 (1) : 1-20. doi: 10.3934/jdg.2020001 |
[5] |
Salah Eddine Choutri, Boualem Djehiche, Hamidou Tembine. Optimal control and zero-sum games for Markov chains of mean-field type. Mathematical Control and Related Fields, 2019, 9 (3) : 571-605. doi: 10.3934/mcrf.2019026 |
[6] |
Diogo Gomes, Marc Sedjro. One-dimensional, forward-forward mean-field games with congestion. Discrete and Continuous Dynamical Systems - S, 2018, 11 (5) : 901-914. doi: 10.3934/dcdss.2018054 |
[7] |
Diogo A. Gomes, Hiroyoshi Mitake, Kengo Terai. The selection problem for some first-order stationary Mean-field games. Networks and Heterogeneous Media, 2020, 15 (4) : 681-710. doi: 10.3934/nhm.2020019 |
[8] |
Jianhui Huang, Shujun Wang, Zhen Wu. Backward-forward linear-quadratic mean-field games with major and minor agents. Probability, Uncertainty and Quantitative Risk, 2016, 1 (0) : 8-. doi: 10.1186/s41546-016-0009-9 |
[9] |
René Carmona, Kenza Hamidouche, Mathieu Laurière, Zongjun Tan. Linear-quadratic zero-sum mean-field type games: Optimality conditions and policy optimization. Journal of Dynamics and Games, 2021, 8 (4) : 403-443. doi: 10.3934/jdg.2021023 |
[10] |
Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control and Related Fields, 2022, 12 (2) : 371-404. doi: 10.3934/mcrf.2021026 |
[11] |
Pierre Cardaliaguet, Jean-Michel Lasry, Pierre-Louis Lions, Alessio Porretta. Long time average of mean field games. Networks and Heterogeneous Media, 2012, 7 (2) : 279-301. doi: 10.3934/nhm.2012.7.279 |
[12] |
Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics and Games, 2019, 6 (3) : 221-239. doi: 10.3934/jdg.2019016 |
[13] |
Yves Achdou, Manh-Khang Dao, Olivier Ley, Nicoletta Tchou. A class of infinite horizon mean field games on networks. Networks and Heterogeneous Media, 2019, 14 (3) : 537-566. doi: 10.3934/nhm.2019021 |
[14] |
Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173 |
[15] |
Martin Burger, Marco Di Francesco, Peter A. Markowich, Marie-Therese Wolfram. Mean field games with nonlinear mobilities in pedestrian dynamics. Discrete and Continuous Dynamical Systems - B, 2014, 19 (5) : 1311-1333. doi: 10.3934/dcdsb.2014.19.1311 |
[16] |
Adriano Festa, Diogo Gomes, Francisco J. Silva, Daniela Tonon. Preface: Mean field games: New trends and applications. Journal of Dynamics and Games, 2021, 8 (4) : i-ii. doi: 10.3934/jdg.2021025 |
[17] |
Lucio Boccardo, Luigi Orsina. The duality method for mean field games systems. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1343-1360. doi: 10.3934/cpaa.2022021 |
[18] |
Levon Nurbekyan. One-dimensional, non-local, first-order stationary mean-field games with congestion: A Fourier approach. Discrete and Continuous Dynamical Systems - S, 2018, 11 (5) : 963-990. doi: 10.3934/dcdss.2018057 |
[19] |
Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks and Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243 |
[20] |
Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems. Networks and Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]