Endogenous Energy Reactive Modules Games: Modelling Side Payments among Resource-Bounded Agents

Julián Gutiérrez, David C. Hyland, Muhammad Najib, Giuseppe Perelli, Michael Wooldridge, Lizhen Cui

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).

The formal syntax of an ERMG module, where each guarded command is associated with an energy cost or gain $e_i$.

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.

A state transition system for a robot service example. Energy costs (negative) and gains (positive) are shown on transitions, alongside state labels.

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

BibTeX
@inproceedings{gutierrez2024endogenous,
  author = {Julián Gutiérrez and David C. Hyland and Muhammad Najib and Giuseppe Perelli and Michael Wooldridge and Lizhen Cui},
  title = {{Endogenous Energy Reactive Modules Games: Modelling Side Payments among Resource-Bounded Agents}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=JE2OvPUSGy},
}
Figure