Affiliations: [a] School of Computer Science and Technology, Dalian University of Technology, P.R. China. liuchanjuan0612@163.com | [b] Department of Philosophy, Tsinghua University, Beijing, P.R. China | [c] Department of Computer Science, Jinan University, P.R. China | [d] Institute for Integrated and Intelligent Systems, Griffith University, Australia
Correspondence:
[*]
Address for correspondence: School of Computer Science and Technology, Dalian University of Technology, P.R. China
Note: [†] This work is supported by NSFC grant (Nos. 61472369, 61672051, 61702075) and the Fundamental Research Funds for the Central Universities of China under Grant (No. DUT16RC(3)065). We are also indebted to the anonymous reviewers of PRIMA 2015 and the journal of Fundamenta Informaticae for their valuable comments on this paper.
Abstract: 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.
Keywords: Extensive games, Short sight, Dynamic logic, Solution Concept, Model checking
