Abstract
Verifying properties of multi-agent systems with resource production and consumption is a known challenge, often leading to undecidability. This paper investigates the boundary of decidability in Resource Agent Logic (RAL). By introducing "idle actions"—the ability for agents to remain inactive at no cost—and defining a specific proponent-restricted, positive fragment ($prRAL^r$) with constraints on the "Until" operator, the authors identify a significant decidable subset. We discuss the reduction from Minsky machines used to prove undecidability in broader fragments and the labeling algorithm that handles infinite state spaces via productive loops.
Introduction
In the design and verification of multi-agent systems, a fundamental challenge is reasoning about the strategic capabilities of agents under resource constraints. While logics like Alternating-time Temporal Logic (ATL) excel at modeling strategies, they often ignore the physical or economic costs of actions. Integrating resources into these logics typically leads to infinite state spaces, especially when agents can produce resources. This paper explores the boundary of decidability in Resource Agent Logic (RAL), identifying a significant fragment that remains automatically verifiable even with resource production.
Mapping the Decidability Landscape
The core difficulty in resource-aware logics is that resource production can make the model-checking problem undecidable—meaning no algorithm can guaranteed a correct answer in finite time. To explore this, the authors introduce Resource-Bounded Models with idle actions ($iRBMs$). In these models, agents always have the option to "idle," performing an action that neither consumes nor produces resources.
Despite the inclusion of idle actions, many fragments of RAL remain undecidable. The authors prove this using reductions from Minsky machines (two-counter machines). By mapping the halting problem of a Minsky machine to a model-checking problem in RAL, they demonstrate that if the latter were decidable, the former would be too—a known impossibility.
As shown in Figure 1, the reduction involves constructing states that simulate the machine's counters and transitions. The "fail" and "halt" states correspond to the machine's execution outcomes, showing that even simple resource-flat models ($rfRAL$) are undecidable for two or more agents.
The $prRAL^r$ Fragment and the Labeling Algorithm
To find a decidable "sweet spot," the authors define a new fragment: $prRAL^r$. This fragment is characterized by three key restrictions:
- Proponent-restriction: Resource bounds only apply to the agents within the "winning coalition" being analyzed.
- Positivity: Cooperation modalities cannot appear under a negation.
- U-restriction: In an "until" formula ($\phi_1 U \phi_2$), the left-hand side ($\phi_1$) must be purely propositional.
The authors propose a labeling algorithm for $prRAL^r$ that utilizes a depth-first and-or search. The algorithm's primary innovation is its handling of infinite state spaces through the identification of "productive loops." These are cycles in the model where agents can gain an arbitrary amount of resources. When the algorithm detects such a loop, it abstracts the resource value to "arbitrary" ($arb$), effectively pruning the infinite search tree.
Key Results and Insights
The research yields several critical insights into the nature of resource-aware verification:
- The Power of Idling: Idle actions are not just a modeling convenience; they are a critical semantic bridge. They ensure that if a goal is reached, agents can persist in that state indefinitely without further cost, aligning finite strategic success with infinite temporal paths.
- Decidability Boundary: The paper proves that while resource-flatness alone is insufficient for decidability (Theorem 1), combining it with proponent-restriction and the "Until" constraint results in a decidable logic (Theorem 2).
- Strategic Abstraction: The "Until" restriction prevents the need to track complex, nested strategic requirements while resources are fluctuating, which is a major driver of undecidability in more expressive fragments.
Conclusion and Future Work
This work successfully draws a new line on the boundary of decidability for resource-aware multi-agent systems. By identifying $prRAL^r$, the authors provide a framework for verifying systems where agents can both consume and produce resources, provided they have the option to remain idle.
However, the fragment's restrictions—particularly the propositional "Until" and the requirement for idle actions—limit its applicability to systems where "staying still" is costly (e.g., hovering drones). Future research may focus on relaxing these constraints or exploring alternative semantic interpretations of resource usage to broaden the scope of decidable verification.
Summary updated