Natural Strategic Ability under Imperfect Information

Strategies in game theory and multi-agent logics are mathematical objects of remarkable combinatorial complexity. Recently, the concept of natural strategies has been proposed to model more human-like reasoning about simple plans and their outcomes. So far, the theory of such simple strategic play was only considered in scenarios where all the agents have perfect information about the state of the game. In this paper, we extend the notion of natural strategies to games with imperfect information. We also show that almost all the complexity results for model checking carry over from the perfect to imperfect information setting. That is, verification of natural strategies is usually no more complex for agents with uncertainty. This tells games of natural strategic ability clearly apart from most results in game theory and multi-agent logics. KEYWORDS [Agent Theories and Models] Logic and Game Theory; Logics for agents and multi-agents systems; [Verification and Validation of Agent-based Systems] Verification techniques for multi-agents systems, including model checking;