Abstract
This paper introduces Endogenous Energy Reactive Modules Games (ERMGs), a formal framework for verifying multi-agent systems where agents are limited by finite energy resources. Unlike traditional models that assume infinite capacity, ERMGs incorporate energy costs and gains into agent actions. We further extend this to Endogenous ERMGs, which allow agents to strategically redistribute initial energy endowments (side payments) to achieve mutually beneficial outcomes. We demonstrate that while these additions increase model realism, the computational complexity of checking for Nash Equilibria and the Core remains 2EXPTIME-complete, matching standard Reactive Modules Games. Our results provide a foundation for verifying systems where resource management is critical to strategic stability.
Introduction
In the field of Rational Verification, researchers analyze whether a multi-agent system will reach a desired state assuming all participants act in their own self-interest. Traditionally, these models assume agents have infinite resources. However, real-world agents—such as autonomous robots or cloud-based software services—are strictly constrained by resources like battery life or operational budgets.
This research addresses two major gaps in current models: the impact of resource boundedness on strategic behavior and the role of strategic transfers. In many scenarios, a "resource-rich" agent might benefit from giving energy to a "resource-poor" peer to enable an action that satisfies both their goals. Formalizing these endogenous transfers allows us to understand how resource redistribution affects the stability of the game.
Formalizing Energy-Constrained Systems
The researchers build upon Reactive Modules Games (RMGs), a standard language for describing concurrent systems, extending them into Energy Reactive Modules Games (ERMGs). In an ERMG, every action (guarded command) has an associated energy cost or gain. Agents possess an initial endowment and a maximum capacity; if an agent's energy is depleted, they are forced to "skip" (idling).
As shown in the module syntax, guards $\phi$ and energy requirements $e_i$ determine the enabledness of actions. This creates a dynamic where energy is not a goal in itself, but a constraint that restricts the "strategy space"—the set of possible moves available to agents seeking to satisfy their Linear Temporal Logic (LTL) objectives.
Strategic Energy Transfers
To model cooperation through resource sharing, we introduce Endogenous ERMGs. This model operates as a two-stage game. In the Offer Phase, agents can choose to transfer portions of their initial energy to others. In the subsequent Execution Phase, the game is played using these modified energy levels.
This mechanism allows for "side payments" that can shift the underlying strategic structure. By giving energy to a peer, an agent can "buy" a stable outcome that satisfies their own goal, which might have been unreachable under the original endowments.
Complexity and Decidability
A key finding of this work is that adding energy levels and a pre-play transfer phase does not make the problem exponentially harder to solve. The authors prove that checking for Nash Equilibria and the Core in these settings remains 2EXPTIME-complete, the same complexity class as standard RMGs. This indicates that the added realism of resource constraints does not come with a prohibitive computational penalty.
Illustrative Example: The Robot Service Game
To validate the framework, the authors utilize a synthetic example involving two robots ($s_1$ and $s_2$) coordinating to service specific locations.
In this transition system, energy costs for moving between states can prevent a Nash Equilibrium from forming. However, by allowing energy transfers, one robot can enable the other to reach a target state (such as $t$), resulting in a stable, mutually beneficial outcome that was previously impossible.
Conclusion and Future Work
ERMGs provide a robust framework for rational verification in resource-constrained environments. We have shown that strategic resource redistribution is a powerful tool for engineering stability. Future work will explore dynamic transfers that occur during gameplay, conditional transfers, and mechanism design where an external designer modifies energy levels to force agents toward socially desirable outcomes.
Summary updated