Strategic Reasoning with a Bounded Number of Resources: the Quest for Tractability - Archive ouverte HAL Access content directly
Journal Articles Artificial Intelligence Year : 2021

Strategic Reasoning with a Bounded Number of Resources: the Quest for Tractability

(1, 2) , (3, 4)
1
2
3
4
Stéphane Demri

Abstract

The resource-bounded alternating-time temporal logic RB±ATL combines strategic reasoning with reasoning about resources. Its model-checking problem is known to be 2EXPTIME-complete (the same as its proper extension RB±ATL$^⁎$) and fragments have been identified to lower the complexity. In this work, we consider the variant RB±ATL+ that allows for Boolean combinations of path formulae starting with single temporal operators, but restricted to a single resource, providing an interesting trade-off between temporal expressivity and resource analysis. We show that the model-checking problem for RB±ATL+ restricted to a single agent and a single resource is $\Delta_{2}^{P}$-complete, hence the same as for the standard branching-time temporal logic CTL+. In this case reasoning about resources comes at no extra computational cost. When a fixed finite set of linear-time temporal operators is considered, the model-checking problem drops to PTIME, which includes the special case of RB±ATL restricted to a single agent and a single resource. Furthermore, we show that, with an arbitrary number of agents and a fixed number of resources, the model-checking problem for RB±ATL+ can be solved in EXPTIME using a sophisticated Turing reduction to the parity game problem for alternating vector addition systems with states (AVASS).

Dates and versions

hal-03298703 , version 1 (23-07-2021)

Identifiers

• HAL Id : hal-03298703 , version 1
• DOI :

Cite

Francesco Belardinelli, Stéphane Demri. Strategic Reasoning with a Bounded Number of Resources: the Quest for Tractability. Artificial Intelligence, 2021, 300, pp.103557. ⟨10.1016/j.artint.2021.103557⟩. ⟨hal-03298703⟩

124 View