Figure 1.
Full game tree of dominoes
-
Previous Article
Good strategies for the Iterated Prisoner's Dilemma: Smale vs. Markov
- JDG Home
- This Issue
-
Next Article
A note on differential games with Pareto-optimal NASH equilibria: Deterministic and stochastic models†
July
2017, 4(3): 205-216.
doi: 10.3934/jdg.2017013
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) |
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.
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 and 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. |
| [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. |
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. |
| [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. |
Figure 2.
Collapsed game tree for dominoes
Figure 3.
Full game tree for Jehiel's example
Figure 4.
Collapsed game tree for Jehiel's example
Figure 5.
Counting paths
| [1] |
Serap Ergün, Bariş Bülent Kırlar, Sırma Zeynep Alparslan Gök, Gerhard-Wilhelm Weber. An application of crypto cloud computing in social networks by cooperative game theory. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1927-1941. doi: 10.3934/jimo.2019036 |
| [2] |
Grace Gao, Sasank Maganti, Karen A. Monsen. Older adults, frailty, and the social and behavioral determinants of health. Big Data & Information Analytics, 2017 doi: 10.3934/bdia.2017012 |
| [3] |
Domènec Ruiz-Balet, Enrique Zuazua. Control of reaction-diffusion models in biology and social sciences. Mathematical Control and Related Fields, 2022, 12 (4) : 955-1038. doi: 10.3934/mcrf.2022032 |
| [4] |
Nicola Bellomo, Livio Gibelli, Nisrine Outada. On the interplay between behavioral dynamics and social interactions in human crowds. Kinetic and Related Models, 2019, 12 (2) : 397-409. doi: 10.3934/krm.2019017 |
| [5] |
Astridh Boccabella, Roberto Natalini, Lorenzo Pareschi. On a continuous mixed strategies model for evolutionary game theory. Kinetic and Related Models, 2011, 4 (1) : 187-213. doi: 10.3934/krm.2011.4.187 |
| [6] |
Anna Lisa Amadori, Astridh Boccabella, Roberto Natalini. A hyperbolic model of spatial evolutionary game theory. Communications on Pure and Applied Analysis, 2012, 11 (3) : 981-1002. doi: 10.3934/cpaa.2012.11.981 |
| [7] |
Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377 |
| [8] |
Marianne Akian, Stéphane Gaubert, Antoine Hochart. A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors. Discrete and Continuous Dynamical Systems, 2020, 40 (1) : 207-231. doi: 10.3934/dcds.2020009 |
| [9] |
Tinggui Chen, Yanhui Jiang. Research on operating mechanism for creative products supply chain based on game theory. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1103-1112. doi: 10.3934/dcdss.2015.8.1103 |
| [10] |
Amina-Aicha Khennaoui, A. Othman Almatroud, Adel Ouannas, M. Mossa Al-sawalha, Giuseppe Grassi, Viet-Thanh Pham. The effect of caputo fractional difference operator on a novel game theory model. Discrete and Continuous Dynamical Systems - B, 2021, 26 (8) : 4549-4565. doi: 10.3934/dcdsb.2020302 |
| [11] |
Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic and Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051 |
| [12] |
Yadong Shu, Ying Dai, Zujun Ma. Evolutionary game theory analysis of supply chain with fairness concerns of retailers. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022098 |
| [13] |
Juan Gabriel Brida, Viktoriya Semeshenko. Special Issue on: Complex systems in economics. Journal of Dynamics and Games, 2020, 7 (3) : i-ii. doi: 10.3934/jdg.2020011 |
| [14] |
Ross Cressman, Vlastimil Křivan. Using chemical reaction network theory to show stability of distributional dynamics in game theory. Journal of Dynamics and Games, 2021 doi: 10.3934/jdg.2021030 |
| [15] |
Eunha Shim, Beth Kochin, Alison Galvani. Insights from epidemiological game theory into gender-specific vaccination against rubella. Mathematical Biosciences & Engineering, 2009, 6 (4) : 839-854. doi: 10.3934/mbe.2009.6.839 |
| [16] |
Hideo Deguchi. A reaction-diffusion system arising in game theory: existence of solutions and spatial dominance. Discrete and Continuous Dynamical Systems - B, 2017, 22 (10) : 3891-3901. doi: 10.3934/dcdsb.2017200 |
| [17] |
King-Yeung Lam. Dirac-concentrations in an integro-pde model from evolutionary game theory. Discrete and Continuous Dynamical Systems - B, 2019, 24 (2) : 737-754. doi: 10.3934/dcdsb.2018205 |
| [18] |
Wai-Ki Ching, Sin-Man Choi, Min Huang. Optimal service capacity in a multiple-server queueing system: A game theory approach. Journal of Industrial and Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73 |
| [19] |
Jaimie W. Lien, Vladimir V. Mazalov, Jie Zheng. Pricing equilibrium of transportation systems with behavioral commuters. Journal of Dynamics and Games, 2020, 7 (4) : 335-350. doi: 10.3934/jdg.2020026 |
| [20] |
Patrizia Daniele, Cristinca Fulga, Guiomar Martín-Herrán, Vladimir Mazalov, Leon Petrosyan, Bruno M. P. M. Oliveira, Carlos Ramos, Gerhard-Wilhelm Weber, Nikolay Zenkevich. Foreword: Special Issue "EURO 2019: Games in economics, finance and biology". Journal of Dynamics and Games, 2021, 8 (2) : i-iv. doi: 10.3934/jdg.2021016 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]