Abstract
We introduce Energy Reactive Modules Games (ERMGs), an extension of Reactive Modules Games (RMGs) in which actions incur an energy cost (which may be positive or negative), and the choices that players make are restricted by the energy available to them. In ERMGs, each action is associated with an energy level update, which determines how their energy level is affected by the performance of the action. In addition, agents are provided with an initial energy allowance. This allowance plays a crucial role in shaping an agent’s behaviour, as it must be taken into consideration when one is determining their strategy: agents may only perform actions if they have the requisite energy. We begin by studying rational verification for ERMGs and then introduce Endogenous ERMGs, where agents can choose to transfer their energy to other agents. This exchange may enable equilibria that are impossible to achieve without such transfers. We study the decision problem of whether a stable outcome exists under both the Nash equilibrium and Core solution concepts.
Introduction
In the field of Rational Verification, researchers use game theory to check if a multi-agent system will behave as intended, assuming all agents act rationally to satisfy their own temporal logic goals, typically expressed in Linear Temporal Logic (LTL). However, most existing models assume agents have infinite resources. In reality, agents like autonomous robots or distributed sensors are resource-bounded; they require energy to perform actions, and some actions might even replenish energy. Furthermore, in many scenarios, agents might want to cooperate by sharing resources—a concept known as "side payments."
This paper introduces Endogenous Energy Reactive Modules Games (EERMGs), a formal framework for modeling resource-bounded agents who can strategically transfer energy to one another to achieve their goals. The authors demonstrate that while adding energy constraints and "side payments" significantly enriches the strategic landscape, the computational complexity of verifying these games remains manageable within established bounds.
Methods and Framework
The authors build their framework in two steps. First, they define Energy Reactive Modules Games (ERMGs) by extending the Simple Reactive Modules Language (SRML). In this extension, "guarded commands" (the rules defining agent actions) are augmented with an energy component. Each action has an associated energy cost or gain, and agents are constrained by a maximum capacity and an initial endowment.
Building on this, the authors introduce Endogenous ERMGs (EERMGs) as a two-stage game:
- Stage 1 (The Offer Phase): Agents can choose to transfer portions of their initial energy endowment to other agents.
- Stage 2 (The Play Phase): Agents play the resulting ERMG using their updated energy levels.
Strategic Analysis and Key Insights
To analyze these games, the authors use two primary solution concepts: Nash Equilibrium for non-cooperative settings and the Core for cooperative settings where coalitions can coordinate. A key insight is that energy acts as a constraint rather than a goal; agents do not seek to maximize energy but use it as a means to satisfy their LTL objectives. This leads to "Strategic Donation," where a rational agent gives away resources to another agent if that agent's actions are necessary for the donor's goal satisfaction.
The authors utilize a synthetic scenario involving robots moving between locations to illustrate how energy transfers enable stable outcomes that would otherwise be impossible. For instance, if a robot lacks the energy to reach a target state that benefits both itself and another agent, the second agent may rationally choose to transfer energy to the first to facilitate the desired outcome.
Complexity and Results
A major technical finding is that adding energy constraints does not increase the computational complexity of the verification problem from a complexity class perspective. The authors prove that the problems of determining if a strategy profile is a Nash Equilibrium (NASH-MEMBERSHIP) or if a stable outcome exists (E-NASH, E-CORE) remain 2EXPTIME-complete, the same as standard reactive modules games. This is achieved by showing that ERMGs can be reduced to "classic" RMGs, providing a bridge between resource-aware modeling and established verification tools.
Conclusion and Future Work
The EERMG framework provides a robust foundation for modeling resource-bounded strategic interactions. While the current model focuses on static "pre-play" transfers, future work aims to address dynamic energy transfers during game execution. Additionally, exploring incentive engineering—where system designers "nudge" agents toward desirable outcomes through energy subsidies—and the impact of malicious actors who might use energy transfers to obstruct others' goals remain important avenues for research.
Summary updated