A Dynamic-Logical Characterization of Solutions to Sight-limited Extensive Games

• Autorzy: Liu C. , Liu F. , Su K.

Identyfikatory

DOI

10.3233/FI-2018-1645

• Języki publikacji: EN

Abstrakty

EN

An unrealistic assumption in classical extensive game theory is that the complete game tree is fully perceivable by all players. To weaken this assumption, a class of games (called games with short sight) was proposed in literature, modelling the game scenarios where players have only limited foresight of the game tree due to bounded resources and limited computational ability. As a consequence, the notions of equilibria in classical game theory were refined to fit games with short sight. A crucial issue that thus arises is to determine whether a strategy profile is a solution to a game. To study this issue and address the underlying idea and theory on players’ decisions in such games, we adopt a logical way. Specifically, we develop a logic called DLS through which features of these games are demonstrated. More importantly, it enables us to characterize the solutions to these games via formulas of this logic. Moreover, we study the algorithm for model checking DLS, which is shown to be PTIME-complete in the size of the model. This work not only provides an insight into a more realistic model in game theory, but also enriches the possible applications of logic.

Słowa kluczowe

EN

dynamic logic; extensive games; model checking; short sight; solution concept

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 158, nr 1/3
• Strony: 149--169
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Liu C.

• School of Computer Science and Technology, Dalian University of Technology, P.R. China

autor

Liu F.

• Department of Philosophy, Tsinghua University, Beijing, P.R. China

autor

Su K.

• Department of Computer Science, Jinan University, P.R. China
• Institute for Integrated and Intelligent Systems, Griffith University, Australia

Bibliografia

• [1] Halpern JY, Pucella R. A Logic for Reasoning about Evidence. Journal of Artificial Intelligence Research, 2006;26:1-34.
• [2] Shoham Y, Leyton-Brown K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, New York, NY, USA, 2008. ISBN-0521899435.
• [3] Wu G, Luo X, Zhong Q. A Game Model with Private Goal and Belief. In: PRICAI 2014: Trends in Artificial Intelligence: 13th Pacific Rim International Conference on Artificial Intelligence, Gold Coast, QLD, Australia, December 1-5, 2014, volume 8862 of LNCS. Springer, Cham 2014, pp. 270-283. https://doi.org/10.1007/978-3-319-13560-1_22.
• [4] Bonanno G, Magill M, Van Gaasback K. Branching Time Logic, Perfect Information Games and Backward Induction. Technical report, University of California, Davis, Department of Economics, 2003. http://wp.econ.ucdavis.edu/98-13.pdf.
• [5] Lorini E, Moisan F. An Epistemic Logic of Extensive Games. Electronic Notes in Theoretical Computer Science, 2011;278:245-260. https://doi.org/10.1016/j.entcs.2011.10.019.
• [6] Ramanujam R, Simon SE. Dynamic Logic on Games with Structured Strategies. In: Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR 2008, Sydney, September 16-19, 2008. AAAI Press. 2008, pp. 49-58. ISBN-978-1-57735-384-3.
• [7] van Benthem J, Pacuit E, Roy O. Toward a Theory of Play: A Logical Perspective on Games and Interaction. Games, 2011;2(1):52-86. doi:10.3390/g2010052.
• [8] Cui J, Luo X, Sim KM. A New Epistemic Logic Model of Regret Games. In: Knowledge Science, Engineering and Management - 6th International Conference, KSEM 2013, Dalian, China, August 10-12, 2013. Proceedings. volume 8041 of LNCS. Springer, Berlin 2013, pp. 372-386. https://doi.org/10.1007/978-3-642-39787-5_31.
• [9] Grossi D, Turrini P. Short sight in extensive games. In: AAMAS. 2012 pp. 805-812. ISBN-0-9817381-2-5978-0-9817381-2-3.
• [10] Harrenstein P, van der Hoek W, Meyer JJC, Witteveen C. A Modal Characterization of Nash Equilibrium. Fundamenta Informaticae, 2003;57(2-4):281-321.
• [11] Harel D, Kozen D, Tiuryn J. Dynamic Logic. In: Handbook of Philosophical Logic. MIT Press, 1984 pp. 497-604.
• [12] Fischer MJ, Ladner RE. Propositional Dynamic Logic of Regular Programs. J. Comput. Syst. Sci., 1979;18(2):194-211. https://doi.org/10.1016/0022-0000(79)90046-1.
• [13] Osborne MJ, Rubinstein A. A Course in Game Theory. MIT Press, 1994.
• [14] Blackburn P, de Rijke M, Venema Y. Modal logic. Cambridge University Press, 2001. https://doi.org/10.1017/CBO9781107050884.
• [15] Benthem JV. Modal Logic for Open Minds. Center for the Study of Language and Information Lecture Notes, Stanford University, 2010. ISBN-1575866986, 9781575866987.
• [16] Lange M. Model checking propositional dynamic logic with all extras. Journal of Applied Logic, 2006;4(1):39-49. https://doi.org/10.1016/j.jal.2005.08.002.
• [17] Strassen V. Gaussian elimination is not optimal. Numerische Mathematik, 1969;13:354-356. doi:10.1007/BF02165411.
• [18] Warshall S. A theorem on boolean matrices. Journal of the ACM, 1962;9(1):11-12. doi:10.1145/321105.321107.
• [19] Liu C, Liu F, Su K. A Logic for Extensive Games with Short Sight. In: Grossi D, Roy O, Huang H (eds.), LORI, volume 8196 of Lecture Notes in Computer Science. Springer. 2013 pp. 332-336. ISBN-978-3-642-40947-9.
• [20] Silver D, Huang A, Maddison CJ, Guez A, Sifre L, van den Driessche G, Schrittwieser J, Antonoglou I, Panneershelvam V, Lanctot M, Dieleman S, Grewe D, Nham J, Kalchbrenner N, Sutskever I, Lillicrap T, Leach M, Kavukcuoglu K, Graepel T, Hassabis D. Mastering the game of Go with deep neural networks and tree search. Nature, 2016;529:484-503. doi:10.1038/nature16961.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).