Theory and Practice of Natural Strategy Checking in Concurrent Games with Imperfect Information
摘要
In this paper, we explore strategy-checking algorithms in concurrent games with imperfect information, analyzing their computational complexity in comparison to the perfect information setting. Precisely, we analyze uniform natural strategies used by agents with limited memory and computational capacity. We examine the decision problems of Sure Winning and IsNash, as well as other similar decision problems in formal strategic reasoning. Additionally, we develop a tool that demonstrates the practical applicability of the proposed framework.