Computationally Feasible Strategies
arXiv:2310.17234
Abstract
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.
References in corpus (7)
- Algorithms for Omega-Regular Games with Imperfect Information
- Reasoning About Strategies: On the Model-Checking Problem
- Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time
- Model-Checking an Alternating-time Temporal Logic with Knowledge, Imperfect Information, Perfect Recall and Communicating Coalitions
- Alternating-time temporal logic with finite-memory strategies
- The Complexity of Multi-Mean-Payoff and Multi-Energy Games
- Twelve Simple Algorithms to Compute Fibonacci Numbers