October 2018, 5(4): 265-282. doi: 10.3934/jdg.2018017

On the stability of an adaptive learning dynamics in traffic games

1. 

San Diego State University, Computational Science Research Center, San Diego, CA 92182, USA

2. 

Universidad Adolfo Ibáñez, Facultad de Ingeniería y Ciencias, Santiago, Chile

* Corresponding author: mdumett@sdsu.edu

Computational Science Research Center, San Diego State University, California, USA. 
Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile.

Received  August 2017 Revised  June 2018 Published  August 2018

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.

Citation: Miguel A. Dumett, Roberto Cominetti. On the stability of an adaptive learning dynamics in traffic games. Journal of Dynamics & Games, 2018, 5 (4) : 265-282. doi: 10.3934/jdg.2018017
References:
[1]

T. Ando, Totally positive matrices, Linear Algebra and Its Applications, 90 (1987), 165-219. 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 (1933), 1-22. doi: 10.1007/BF01199986.

[3]

P. AuerN. Cesa-BianchiY. Freund and R. E. Schapire, The non-stochastic multiarmed bandit problem, SIAM J. on Computing, 32 (2002), 48-77. doi: 10.1137/S0097539701398375.

[4]

E. Avinieri and J. Prashker, The impact of travel time information on travelers' learning under uncertainty, Transportation, 33 (2006), 393-408. doi: 10.1007/s11116-005-5710-y.

[5]

A. Beggs, On the convergence of reinforcement learning, Journal of Economic Theory, 122 (2005), 1-36. 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. doi: 10.2202/1935-1704.1452.

[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. doi: 10.1007/BFb0096509.

[8]

M. Benaïm and M. Faure, Stochastic approximation, cooperative dynamics and supermodular games, Ann. Appl. Probab., 22 (2012), 2133-2164. doi: 10.1214/11-AAP816.

[9]

M. Benaïm and M. W. Hirsch, Stochastic approximation algorithms with constant step size whose average is cooperative, Ann. Appl. Probab., 9 (1999), 216-241. doi: 10.1214/aoap/1029962603.

[10]

T. Börgers and R. Sarin, Learning through reinforcement and replicator dynamics, Journal of Economic Theory, 77 (1997), 1-14. doi: 10.1006/jeth.1997.2319.

[11]

V. Borkar, Cooperative dynamics and Wardrop equilibria, Systems and Control Letters, 58 (2009), 91-93. 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 (2016), 1469-1483. 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. CominettiE. Melo and S. Sorin, A payoff based learning procedure and its application to traffic games, Games and Economic Behavior, 70 (2010), 71-83. 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. doi: 10.1007/978-3-642-49981-4.

[17]

C. Daganzo and Y. Sheffi, On stochastic models of traffic assignment, Transportation Science, 11 (1977), 253-274. 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. doi: 10.1016/j.jat.2004.10.010.

[19]

I. Erev and A. E. Roth, Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria, American Economic Review, 88 (1998), 848-881.

[20]

C. Fisk, Some developments in equilibrium traffic assignment, Transportation Research, 14 (1980), 243-255. doi: 10.1016/0191-2615(80)90004-1.

[21]

D. Foster and R. V. Vohra, Calibrated learning and correlated equilibria, Games and Economic Behavior, 21 (1997), 40-55. doi: 10.1006/game.1997.0595.

[22]

D. Foster and R. V. Vohra, Asymptotic calibration, Biometrika, 85 (1998), 379-390. doi: 10.1093/biomet/85.2.379.

[23]

Y. Freund and R. E. Schapire, Adaptive game playing using multiplicative weights, Games and Economic Behavior, 29 (1999), 79-103. doi: 10.1006/game.1999.0738.

[24]

D. Fudenberg and D. K. Levine, The Theory of Learning in Games, MIT Press, Cambridge, MA, 1998.

[25]

F. R. Gantmacher, Applications of the Theory of Matrices, Interscience, New York, 1959.

[26]

J. Guckenheimer and P. Holmes, Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields, 5th edition, Springer-Verlag, New York, 1997.

[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.

[28]

S. Hart, Adaptive heuristics, Econometrica, 73 (2005), 1401-1430. 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.

[30]

J. Hofbauer and W. Sandholm, On the global convergence of stochastic fictitious play, Econometrica, 70 (2002), 2265-2294. doi: 10.1111/1468-0262.00376.

[31]

J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, UK, 1998. doi: 10.1017/CBO9781139173179.

[32]

J. Horowitz, The stability of stochastic equilibrium in a two-link transportation network, Transportation Research Part B, 18 (1984), 13-28. 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. doi: 10.1007/978-1-4899-2696-8.

[34]

Y. A. Kuznetsov, Elements of Applied Bifurcation Theory, 2nd edition, Springer-Verlag, New York, 1995. doi: 10.1007/978-1-4757-2421-9.

[35]

J.-F. LaslierR. Topol and B. Walliser, A behavioral learning process in games, Games and Economic Behavior, 37 (2001), 340-366. doi: 10.1006/game.2000.0841.

[36]

R. McKelvey and T. Palfrey, Quantal response equilibria for normal form games, Games and Economic Behavior, 10 (1995), 6-38. 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. doi: 10.1137/1.9780898719512.

[39]

K. W. Morton and D. Mayers, Numerical Solution of Partial Differential Equations, Cambridge University Press, 2nd Edition, 2005. doi: 10.1017/CBO9780511812248.

[40]

J. D. Murray, Mathematical Biology, 2nd edition, Springer, Berlin, Germany, 1993. doi: 10.1007/b98869.

[41]

M. Posch, Cycling in a stochastic learning algorithm for normal form games, J. Evol. Econ., 7 (1997), 193-207. doi: 10.1007/s001910050041.

[42]

J. Robinson, An iterative method of solving a game, Ann. Math., 54 (1951), 296-301. doi: 10.2307/1969530.

[43]

R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory, 2 (1973), 65-67. 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 (1988), 87-113. doi: 10.1137/1030003.

[45]

R. SeltenT. ChmuraT. PitzS. Kube and M. Schreckenberg, Commuters route choice behaviour, Games and Economic Behavior, 58 (2007), 394-406. 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.

[47]

J. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institution of Civil Engineers, 1 (1952), 767-768. doi: 10.1680/ipeds.1952.11362.

[48]

H. P. Young, Strategic Learning and its Limits, Oxford University Press, 2004. doi: 10.1093/acprof:oso/9780199269181.001.0001.

show all references

References:
[1]

T. Ando, Totally positive matrices, Linear Algebra and Its Applications, 90 (1987), 165-219. 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 (1933), 1-22. doi: 10.1007/BF01199986.

[3]

P. AuerN. Cesa-BianchiY. Freund and R. E. Schapire, The non-stochastic multiarmed bandit problem, SIAM J. on Computing, 32 (2002), 48-77. doi: 10.1137/S0097539701398375.

[4]

E. Avinieri and J. Prashker, The impact of travel time information on travelers' learning under uncertainty, Transportation, 33 (2006), 393-408. doi: 10.1007/s11116-005-5710-y.

[5]

A. Beggs, On the convergence of reinforcement learning, Journal of Economic Theory, 122 (2005), 1-36. 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. doi: 10.2202/1935-1704.1452.

[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. doi: 10.1007/BFb0096509.

[8]

M. Benaïm and M. Faure, Stochastic approximation, cooperative dynamics and supermodular games, Ann. Appl. Probab., 22 (2012), 2133-2164. doi: 10.1214/11-AAP816.

[9]

M. Benaïm and M. W. Hirsch, Stochastic approximation algorithms with constant step size whose average is cooperative, Ann. Appl. Probab., 9 (1999), 216-241. doi: 10.1214/aoap/1029962603.

[10]

T. Börgers and R. Sarin, Learning through reinforcement and replicator dynamics, Journal of Economic Theory, 77 (1997), 1-14. doi: 10.1006/jeth.1997.2319.

[11]

V. Borkar, Cooperative dynamics and Wardrop equilibria, Systems and Control Letters, 58 (2009), 91-93. 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 (2016), 1469-1483. 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. CominettiE. Melo and S. Sorin, A payoff based learning procedure and its application to traffic games, Games and Economic Behavior, 70 (2010), 71-83. 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. doi: 10.1007/978-3-642-49981-4.

[17]

C. Daganzo and Y. Sheffi, On stochastic models of traffic assignment, Transportation Science, 11 (1977), 253-274. 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. doi: 10.1016/j.jat.2004.10.010.

[19]

I. Erev and A. E. Roth, Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria, American Economic Review, 88 (1998), 848-881.

[20]

C. Fisk, Some developments in equilibrium traffic assignment, Transportation Research, 14 (1980), 243-255. doi: 10.1016/0191-2615(80)90004-1.

[21]

D. Foster and R. V. Vohra, Calibrated learning and correlated equilibria, Games and Economic Behavior, 21 (1997), 40-55. doi: 10.1006/game.1997.0595.

[22]

D. Foster and R. V. Vohra, Asymptotic calibration, Biometrika, 85 (1998), 379-390. doi: 10.1093/biomet/85.2.379.

[23]

Y. Freund and R. E. Schapire, Adaptive game playing using multiplicative weights, Games and Economic Behavior, 29 (1999), 79-103. doi: 10.1006/game.1999.0738.

[24]

D. Fudenberg and D. K. Levine, The Theory of Learning in Games, MIT Press, Cambridge, MA, 1998.

[25]

F. R. Gantmacher, Applications of the Theory of Matrices, Interscience, New York, 1959.

[26]

J. Guckenheimer and P. Holmes, Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields, 5th edition, Springer-Verlag, New York, 1997.

[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.

[28]

S. Hart, Adaptive heuristics, Econometrica, 73 (2005), 1401-1430. 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.

[30]

J. Hofbauer and W. Sandholm, On the global convergence of stochastic fictitious play, Econometrica, 70 (2002), 2265-2294. doi: 10.1111/1468-0262.00376.

[31]

J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, UK, 1998. doi: 10.1017/CBO9781139173179.

[32]

J. Horowitz, The stability of stochastic equilibrium in a two-link transportation network, Transportation Research Part B, 18 (1984), 13-28. 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. doi: 10.1007/978-1-4899-2696-8.

[34]

Y. A. Kuznetsov, Elements of Applied Bifurcation Theory, 2nd edition, Springer-Verlag, New York, 1995. doi: 10.1007/978-1-4757-2421-9.

[35]

J.-F. LaslierR. Topol and B. Walliser, A behavioral learning process in games, Games and Economic Behavior, 37 (2001), 340-366. doi: 10.1006/game.2000.0841.

[36]

R. McKelvey and T. Palfrey, Quantal response equilibria for normal form games, Games and Economic Behavior, 10 (1995), 6-38. 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. doi: 10.1137/1.9780898719512.

[39]

K. W. Morton and D. Mayers, Numerical Solution of Partial Differential Equations, Cambridge University Press, 2nd Edition, 2005. doi: 10.1017/CBO9780511812248.

[40]

J. D. Murray, Mathematical Biology, 2nd edition, Springer, Berlin, Germany, 1993. doi: 10.1007/b98869.

[41]

M. Posch, Cycling in a stochastic learning algorithm for normal form games, J. Evol. Econ., 7 (1997), 193-207. doi: 10.1007/s001910050041.

[42]

J. Robinson, An iterative method of solving a game, Ann. Math., 54 (1951), 296-301. doi: 10.2307/1969530.

[43]

R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory, 2 (1973), 65-67. 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 (1988), 87-113. doi: 10.1137/1030003.

[45]

R. SeltenT. ChmuraT. PitzS. Kube and M. Schreckenberg, Commuters route choice behaviour, Games and Economic Behavior, 58 (2007), 394-406. 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.

[47]

J. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institution of Civil Engineers, 1 (1952), 767-768. doi: 10.1680/ipeds.1952.11362.

[48]

H. P. Young, Strategic Learning and its Limits, Oxford University Press, 2004. doi: 10.1093/acprof:oso/9780199269181.001.0001.

Figure 1.  Stability region in the $2 \times 2$ traffic game
Figure 2.  Three fixed points with $\psi'(\bar w)>1$
Figure 3.  Fixed points of $\psi$: $\psi'(\bar w)>1$ (left) vs $\psi'(\bar w)<1$ (right)
Figure 4.  Stability region for a $2 \times 2$ symmetric game in the $\mu$-$q$ parameters
[1]

J. M. Peña. Refinable functions with general dilation and a stable test for generalized Routh-Hurwitz conditions. Communications on Pure & Applied Analysis, 2007, 6 (3) : 809-818. doi: 10.3934/cpaa.2007.6.809

[2]

MirosŁaw Lachowicz, Tatiana Ryabukha. Equilibrium solutions for microscopic stochastic systems in population dynamics. Mathematical Biosciences & Engineering, 2013, 10 (3) : 777-786. doi: 10.3934/mbe.2013.10.777

[3]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics & Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020

[4]

Henri Schurz. Moment attractivity, stability and contractivity exponents of stochastic dynamical systems. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 487-515. doi: 10.3934/dcds.2001.7.487

[5]

Alexandra Rodkina, Henri Schurz, Leonid Shaikhet. Almost sure stability of some stochastic dynamical systems with memory. Discrete & Continuous Dynamical Systems - A, 2008, 21 (2) : 571-593. doi: 10.3934/dcds.2008.21.571

[6]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117

[7]

Saul Mendoza-Palacios, Onésimo Hernández-Lerma. Stability of the replicator dynamics for games in metric spaces. Journal of Dynamics & Games, 2017, 4 (4) : 319-333. doi: 10.3934/jdg.2017017

[8]

Zaki Chbani, Hassan Riahi. Existence and asymptotic behaviour for solutions of dynamical equilibrium systems. Evolution Equations & Control Theory, 2014, 3 (1) : 1-14. doi: 10.3934/eect.2014.3.1

[9]

Ivan Werner. Equilibrium states and invariant measures for random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2015, 35 (3) : 1285-1326. doi: 10.3934/dcds.2015.35.1285

[10]

Xiaoming Wang. Numerical algorithms for stationary statistical properties of dissipative dynamical systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4599-4618. doi: 10.3934/dcds.2016.36.4599

[11]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control & Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010

[12]

Liming Wang. A passivity-based stability criterion for reaction diffusion systems with interconnected structure. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 303-323. doi: 10.3934/dcdsb.2012.17.303

[13]

Alain Bensoussan, Jens Frehse, Jens Vogelgesang. Systems of Bellman equations to stochastic differential games with non-compact coupling. Discrete & Continuous Dynamical Systems - A, 2010, 27 (4) : 1375-1389. doi: 10.3934/dcds.2010.27.1375

[14]

Shu Zhang, Yuan Yuan. The Filippov equilibrium and sliding motion in an internet congestion control model. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 1189-1206. doi: 10.3934/dcdsb.2017058

[15]

S.Durga Bhavani, K. Viswanath. A general approach to stability and sensitivity in dynamical systems. Discrete & Continuous Dynamical Systems - A, 1998, 4 (1) : 131-140. doi: 10.3934/dcds.1998.4.131

[16]

Karl P. Hadeler. Quiescent phases and stability in discrete time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 129-152. doi: 10.3934/dcdsb.2015.20.129

[17]

Matthew Macauley, Henning S. Mortveit. Update sequence stability in graph dynamical systems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1533-1541. doi: 10.3934/dcdss.2011.4.1533

[18]

A. Mittal, N. Hemachandra. Learning algorithms for finite horizon constrained Markov decision processes. Journal of Industrial & Management Optimization, 2007, 3 (3) : 429-444. doi: 10.3934/jimo.2007.3.429

[19]

Jian Mao, Qixiao Lin, Jingdong Bian. Application of learning algorithms in smart home IoT system security. Mathematical Foundations of Computing, 2018, 1 (1) : 63-76. doi: 10.3934/mfc.2018004

[20]

Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1

 Impact Factor: 

Metrics

  • PDF downloads (24)
  • HTML views (208)
  • Cited by (0)

Other articles
by authors

[Back to Top]