Game theory and dynamic programming in alternate games

Eduardo Espinosa-Avila; Pablo Padilla Longoria; Francisco Hernández-Quiroz

doi:10.3934/jdg.2017013

Article Contents

2017, Volume 4, Issue 3: 205-216. Doi: 10.3934/jdg.2017013

This issue Previous Article A note on differential games with Pareto-optimal NASH equilibria: Deterministic and stochastic models^† Next Article Good strategies for the Iterated Prisoner's Dilemma: Smale vs. Markov

Game theory and dynamic programming in alternate games

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
* Corresponding author

Received: November 30, 2016

Revised: March 31, 2017

Published: September 2017

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

Abstract Full Text(HTML) Figure(7) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 91A25, 91B06; Secondary: 91B50.

Citation:

Full Text(HTML)

Figure 1. Full game tree of dominoes

Download: Full-size image PowerPoint slide

Figure 2. Collapsed game tree for dominoes

Download: Full-size image PowerPoint slide

Figure 3. Full game tree for Jehiel's example

Download: Full-size image PowerPoint slide

Figure 4. Collapsed game tree for Jehiel's example

Download: Full-size image PowerPoint slide

Figure 5. Counting paths

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[7]	P. Jehiel, Limited horizon forecast in repeated alternate games, Journal of Economic Theory, 67 (1995), 497-519. doi: 10.1006/jeth.1995.1082.
[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.
[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.
[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.
[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.