×

On the stability of an adaptive learning dynamics in traffic games. (English) Zbl 1422.91146

Summary: This paper investigates the dynamic stability of an adaptive learning procedure in a traffic game. Using the Routh-Hurwitz criterion we study the stability of the rest points of the corresponding mean field dynamics. In the special case with two routes and two players we provide a full description of the number and nature of these rest points as well as the global asymptotic behavior of the dynamics. Depending on the parameters of the model, we find that there are either one, two or three equilibria and we show that in all cases the mean field trajectories converge towards a rest point for almost all initial conditions.

MSC:

91A43 Games involving graphs
91A26 Rationality and learning in game theory
91A05 2-person games
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] T. Ando, Totally positive matrices, Linear Algebra and Its Applications, 90, 165-219 (1987) · Zbl 0613.15014 · doi:10.1016/0024-3795(87)90313-2
[2] W. B. Arthur, On designing economic agents that behave like human agents, J. Evolutionary Econ., 3, 1-22 (1933) · doi:10.1007/BF01199986
[3] P. Auer; N. Cesa-Bianchi; Y. Freund; R. E. Schapire, The non-stochastic multiarmed bandit problem, SIAM J. on Computing, 32, 48-77 (2002) · Zbl 1029.68087 · doi:10.1137/S0097539701398375
[4] E. Avinieri; J. Prashker, The impact of travel time information on travelers’ learning under uncertainty, Transportation, 33, 393-408 (2006) · doi:10.1007/s11116-005-5710-y
[5] A. Beggs, On the convergence of reinforcement learning, Journal of Economic Theory, 122, 1-36 (2005) · Zbl 1118.91025 · doi:10.1016/j.jet.2004.03.008
[6] A. Beggs, Learning in Bayesian games with binary actions, B. E. J. Theor. Econ., 9 (2009), Art. 33, 30 pp. · Zbl 1192.91031
[7] M. Benaïm, Dynamics of stochastic approximation algorithms, in Séminaire de Probabilités, Lecture Notes in Math., Springer, Berlin, 1709 (1999), 1-68. · Zbl 0955.62085
[8] M. Benaïm; M. Faure, Stochastic approximation, cooperative dynamics and supermodular games, Ann. Appl. Probab., 22, 2133-2164 (2012) · Zbl 1429.62359 · doi:10.1214/11-AAP816
[9] M. Benaïm; M. W. Hirsch, Stochastic approximation algorithms with constant step size whose average is cooperative, Ann. Appl. Probab., 9, 216-241 (1999) · Zbl 0983.62046 · doi:10.1214/aoap/1029962603
[10] T. Börgers; R. Sarin, Learning through reinforcement and replicator dynamics, Journal of Economic Theory, 77, 1-14 (1997) · Zbl 0892.90198 · doi:10.1006/jeth.1997.2319
[11] V. Borkar, Cooperative dynamics and Wardrop equilibria, Systems and Control Letters, 58, 91-93 (2009) · Zbl 1156.91325 · doi:10.1016/j.sysconle.2008.08.006
[12] M. Bravo, An adjusted payoff-based procedure for normal form games, Mathematics of Operations Research, 41, 1469-1483 (2016) · Zbl 1349.91062 · doi:10.1287/moor.2016.0785
[13] G. Brown, Iterative solution of games by fictitious play, in Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, John Wiley & Sons, Inc., New York, N. Y., (1951), 374-376.
[14] R. Cominetti; E. Melo; S. Sorin, A payoff based learning procedure and its application to traffic games, Games and Economic Behavior, 70, 71-83 (2010) · Zbl 1244.91012 · doi:10.1016/j.geb.2008.11.012
[15] M. Coste, An Introduction to O-minimal Geometry, Institut de Recherche Mathématique de Rennes, 1999.
[16] R. Cressman, The Stability Concept of Evolutionary Game Theory: A Dynamic Approach, Springer-Verlag, Berlin, Heidelberg, 1992. · Zbl 0763.92006
[17] C. Daganzo; Y. Sheffi, On stochastic models of traffic assignment, Transportation Science, 11, 253-274 (1977) · doi:10.1287/trsc.11.3.253
[18] D. K. Dimitrov, D. K. and J. M. Peña, Almost strict total positivity and a class of Hurwitz polynomials, Journal of Approximation Theory, 132 (2005), 212-223. · Zbl 1072.15028
[19] I. Erev; A. E. Roth, Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria, American Economic Review, 88, 848-881 (1998)
[20] C. Fisk, Some developments in equilibrium traffic assignment, Transportation Research, 14, 243-255 (1980) · doi:10.1016/0191-2615(80)90004-1
[21] D. Foster; R. V. Vohra, Calibrated learning and correlated equilibria, Games and Economic Behavior, 21, 40-55 (1997) · Zbl 0894.90188 · doi:10.1006/game.1997.0595
[22] D. Foster; R. V. Vohra, Asymptotic calibration, Biometrika, 85, 379-390 (1998) · Zbl 0947.62059 · doi:10.1093/biomet/85.2.379
[23] Y. Freund; R. E. Schapire, Adaptive game playing using multiplicative weights, Games and Economic Behavior, 29, 79-103 (1999) · Zbl 0964.91007 · doi:10.1006/game.1999.0738
[24] D. Fudenberg and D. K. Levine, The Theory of Learning in Games, MIT Press, Cambridge, MA, 1998. · Zbl 0939.91004
[25] F. R. Gantmacher, Applications of the Theory of Matrices, Interscience, New York, 1959. · Zbl 0085.01001
[26] J. Guckenheimer and P. Holmes, Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields, 5^th edition, Springer-Verlag, New York, 1997. · Zbl 0515.34001
[27] J. Hannan, Approximation to Bayes risk in repeated plays, in Contributions to the Theory of Games (eds. M. Dresher, A. W. Tucker, and P. Wolfe), Princeton University Press, 3 (1957), 97-139. · Zbl 0078.32804
[28] S. Hart, Adaptive heuristics, Econometrica, 73, 1401-1430 (2005) · Zbl 1152.91370 · doi:10.1111/j.1468-0262.2005.00625.x
[29] S. Hart and A. Mas-Colell, A reinforcement procedure leading to correlated equilibrium, in Economics Essays: A Festschrift for Werner Hildenbrand (eds G. Debreu, W. Neuefeing and W. Trockel, Springer, (2001), 181-200. · Zbl 1023.91004
[30] J. Hofbauer; W. Sandholm, On the global convergence of stochastic fictitious play, Econometrica, 70, 2265-2294 (2002) · Zbl 1141.91336 · doi:10.1111/1468-0262.00376
[31] J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, UK, 1998. · Zbl 0914.90287
[32] J. Horowitz, The stability of stochastic equilibrium in a two-link transportation network, Transportation Research Part B, 18, 13-28 (1984) · doi:10.1016/0191-2615(84)90003-1
[33] H. J. Kushner and G. G. Yin, Stochastic Approximations Algorithms and Applications, Applications of Mathematics, 35, Springer-Verlag, New York, 1997.
[34] Y. A. Kuznetsov, Elements of Applied Bifurcation Theory, 2^nd edition, Springer-Verlag, New York, 1995. · Zbl 0829.58029
[35] J.-F. Laslier; R. Topol; B. Walliser, A behavioral learning process in games, Games and Economic Behavior, 37, 340-366 (2001) · Zbl 1019.91010 · doi:10.1006/game.2000.0841
[36] R. McKelvey; T. Palfrey, Quantal response equilibria for normal form games, Games and Economic Behavior, 10, 6-38 (1995) · Zbl 0832.90126 · doi:10.1006/game.1995.1023
[37] F. A. Maldonado, Estudio de una Dinámica Adaptativa Para Juegos Repetidos y su Aplicación a un Juego de Congestión, Memoria, Universidad de Chile, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Matemática, Santiago, Chile, 2012.
[38] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000.
[39] K. W. Morton and D. Mayers, Numerical Solution of Partial Differential Equations, Cambridge University Press, 2nd Edition, 2005. · Zbl 1126.65077
[40] J. D. Murray, Mathematical Biology, 2^nd edition, Springer, Berlin, Germany, 1993. · Zbl 0779.92001
[41] M. Posch, Cycling in a stochastic learning algorithm for normal form games, J. Evol. Econ., 7, 193-207 (1997) · doi:10.1007/s001910050041
[42] J. Robinson, An iterative method of solving a game, Ann. Math., 54, 296-301 (1951) · Zbl 0045.08203 · doi:10.2307/1969530
[43] R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory, 2, 65-67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[44] H. L. Smith, Systems of ordinary differential equations which generate an order preserving flow. A survey of results, SIAM Review, 30, 87-113 (1988) · Zbl 0674.34012 · doi:10.1137/1030003
[45] R. Selten; T. Chmura; T. Pitz; S. Kube; M. Schreckenberg, Commuters route choice behaviour, Games and Economic Behavior, 58, 394-406 (2007) · Zbl 1117.90033 · doi:10.1016/j.geb.2006.03.012
[46] L. van den Dries, O-minimal structures and real analytic geometry, in Current Development in Mathematics, International Press, Cambridge, MA, (1999), 105-152. · Zbl 0980.03043
[47] J. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institution of Civil Engineers, 1, 767-768 (1952) · doi:10.1680/ipeds.1952.11362
[48] H. P. Young, Strategic Learning and its Limits, Oxford University Press, 2004.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.