2023/10/26 by Cătălin Dima, Dima, Catalin, Wojciech Jamroga +1
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.2310.17234
openalex publication_date 2023/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Real-life agents seldom have unlimited reasoning power. In this paper, we propose and study a new formal notion of computationally bounded strategic ability in multi-agent systems. The notion characterizes the ability of a set of agents to synthesize an executable strategy in the form of a Turing machine within a given complexity class, that ensures the satisfaction of a temporal objective in a parameterized game arena. We show that the new concept induces a proper hierarchy of strategic abilities -- in particular, polynomial-time abilities are strictly weaker than the exponential-time ones. We also propose an ``adaptive'' variant of computational ability which allows for different strategies for each parameter value, and show that the two notions do not coincide. Finally, we define and study the model-checking problem for computational strategies. We show that the problem is undecidable even for severely restricted inputs, and present our first steps towards decidable fragments.