American Institute of Mathematical Sciences

Advanced
July  2017, 4(3): 205-216. doi: 10.3934/jdg.2017013

Game theory and dynamic programming in alternate games

Eduardo Espinosa-Avila 1,, , Pablo Padilla Longoria 2, and  Francisco Hernández-Quiroz 3,

1. 

Graduate Program in Computer Science, Institute of Applied Mathematics and Systems Research Annex Building, Third Floor, Circuito Escolar s/n, Cd. Universitaria, 04510, Mexico City, Mexico, National University of Mexico (UNAM)
2. 

Institute of Applied Mathematics and Systems Research, Circuito Escolar s/n, Cd. Universitaria, 04510, Mexico City, Mexico, National University of Mexico (UNAM)
3. 

Faculty of Sciences, Circuito Exterior s/n, Cd. Universitaria, 04510, Mexico City, Mexico, National University of Mexico (UNAM)

* Corresponding author

Received  December 2016 Revised  April 2017 Published  April 2017

Fund Project: The first author is supported by the National Council of Science and Technology (CONACyT) and the National University of Mexico (UNAM).

We present an analysis of different classes of alternate games from different perspectives, including game theory, logic, bounded rationality and dynamic programming. In this paper we review some of these approaches providing a methodological framework which combines ideas from all of them, but emphasizing dynamic programming and game theory. In particular we study the relationship between games in discrete and continuous time and state space and how the latter can be understood as the limit of the former. We show how in some cases the Hamilton-Jacobi-Bellman equation for the discrete version of the game leads to a corresponding HJB partial differential equation for the continuous case and how this procedure allow us to obtain useful information about optimal strategies. This analysis yields another way to compute subgame perfect equilibrium.

Keywords: Game theory, economics, social and behavioral sciences.
Mathematics Subject Classification: Primary: 91A25, 91B06; Secondary: 91B50.
Citation: Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013
References:
[1]

A. Baltag and S. Smets, Keep changing your beliefs, aiming for the truth, Erkenntnis, 75 (2011), 255-270.  doi: 10.1007/s10670-011-9294-y.  Google Scholar

[2]

E. Espinosa-Avila and F. Hernández-Quiroz, Bounded rationality in a dynamic alternate game, Proceedings of TARK'13 Theoretical Aspects of Rationality and Knowledge, 2013, 71{ 77. Google Scholar

[3]

L. C. Evans, Partial Differential Equations, American Mathematical Society, Second Edition, Graduate Studies in Mathematics, Volume: 19, Providence, RI, 2010. doi: 10.1090/gsm/019.  Google Scholar

[4]

D. Fernández-Duque, E. Espinosa-Avila and F. Hern´andez-Quiroz A logic for bounded rationality, Proceeding of the short presentations of Advances in Modal Logics, AiML'14, 2014, 34-38. Google Scholar

[5]

IBM DeepBlue, What are the differences between last year's rendition of Deep Blue and this year's model?, IBM DeepBlue faq https://www.research.ibm.com/deepblue/meet/html/d.3.3a.html IBM. Retrieved Aug 29,2016. Google Scholar

[6]

IBM DeepQA, What kind of technology is Watson based on?, DeepQA faq https://www.research.ibm.com/deepqa/faq.shtml IBM. Retrieved Aug 29,2016. Google Scholar

[7]

P. Jehiel, Limited horizon forecast in repeated alternate games, Journal of Economic Theory, 67 (1995), 497-519.  doi: 10.1006/jeth.1995.1082.  Google Scholar

[8]

T. A. Marsland and Y. Björnsson, From minimax to manhattan, Proceedings of Deep Blue Versus Kasparov: The Significance for Artificial Intelligence, Collected Papers from the 1997 AAAI Workshop, (1997), 31-36.   Google Scholar

[9]

V. Mirrokni, N. Thain and A. Vetta, A theoretical examination of practical game playing: Lookahead search, SAGT'12 Proceedings of the 5th international conference on Algorithmic Game Theory, Universitat Politècnica de Catalunya, 7615 (2012), 251-262. doi: 10.1007/978-3-642-33996-7_22.  Google Scholar

[10]

R. Parikh, L. S. Moss and C. Steinsvold, Topology and epistemic logic, Handbook of Spatial Logics, (2007), 299-341.  doi: 10.1007/978-1-4020-5587-4_6.  Google Scholar

[11]

D. K. Smith, Dynamic programming and board games: A survey, European Journal of Operational Research, 176 (2007), 1299-1318.  doi: 10.1016/j.ejor.2005.10.026.  Google Scholar

show all references

References:
[1]

A. Baltag and S. Smets, Keep changing your beliefs, aiming for the truth, Erkenntnis, 75 (2011), 255-270.  doi: 10.1007/s10670-011-9294-y.  Google Scholar

[2]

E. Espinosa-Avila and F. Hernández-Quiroz, Bounded rationality in a dynamic alternate game, Proceedings of TARK'13 Theoretical Aspects of Rationality and Knowledge, 2013, 71{ 77. Google Scholar

[3]

L. C. Evans, Partial Differential Equations, American Mathematical Society, Second Edition, Graduate Studies in Mathematics, Volume: 19, Providence, RI, 2010. doi: 10.1090/gsm/019.  Google Scholar

[4]

D. Fernández-Duque, E. Espinosa-Avila and F. Hern´andez-Quiroz A logic for bounded rationality, Proceeding of the short presentations of Advances in Modal Logics, AiML'14, 2014, 34-38. Google Scholar

[5]

IBM DeepBlue, What are the differences between last year's rendition of Deep Blue and this year's model?, IBM DeepBlue faq https://www.research.ibm.com/deepblue/meet/html/d.3.3a.html IBM. Retrieved Aug 29,2016. Google Scholar

[6]

IBM DeepQA, What kind of technology is Watson based on?, DeepQA faq https://www.research.ibm.com/deepqa/faq.shtml IBM. Retrieved Aug 29,2016. Google Scholar

[7]

P. Jehiel, Limited horizon forecast in repeated alternate games, Journal of Economic Theory, 67 (1995), 497-519.  doi: 10.1006/jeth.1995.1082.  Google Scholar

[8]

T. A. Marsland and Y. Björnsson, From minimax to manhattan, Proceedings of Deep Blue Versus Kasparov: The Significance for Artificial Intelligence, Collected Papers from the 1997 AAAI Workshop, (1997), 31-36.   Google Scholar

[9]

V. Mirrokni, N. Thain and A. Vetta, A theoretical examination of practical game playing: Lookahead search, SAGT'12 Proceedings of the 5th international conference on Algorithmic Game Theory, Universitat Politècnica de Catalunya, 7615 (2012), 251-262. doi: 10.1007/978-3-642-33996-7_22.  Google Scholar

[10]

R. Parikh, L. S. Moss and C. Steinsvold, Topology and epistemic logic, Handbook of Spatial Logics, (2007), 299-341.  doi: 10.1007/978-1-4020-5587-4_6.  Google Scholar

[11]

D. K. Smith, Dynamic programming and board games: A survey, European Journal of Operational Research, 176 (2007), 1299-1318.  doi: 10.1016/j.ejor.2005.10.026.  Google Scholar

Figure 1.  Full game tree of dominoes
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Collapsed game tree for dominoes
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Full game tree for Jehiel's example
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Collapsed game tree for Jehiel's example
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Counting paths
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Two squared grids $5\times5$ and $10\times10$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Two rectangular grids $5\times10$ and $10\times5$
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051
[2]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[3]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[4]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458
[5]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024
[6]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347
[7]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

 Impact Factor: 

Tools

Metrics

  • PDF downloads (72)
  • HTML views (73)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences