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

Julian Gutierrez, David Hyland, Muhammad Najib, Giuseppe Perelli, Michael J. Wooldridge

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.

The syntax of an energy-aware module in SRML, showing guarded commands with energy updates.

Building on this, the authors introduce Endogenous ERMGs (EERMGs) as a two-stage game:

  1. Stage 1 (The Offer Phase): Agents can choose to transfer portions of their initial energy endowment to other agents.
  2. 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.

A state transition diagram illustrating a synthetic scenario where robots move between locations with specific energy costs and gains.

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

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.
BibTeX
@inproceedings{gutierrez2024endogenous,
  author = {Julian Gutierrez and David Hyland and Muhammad Najib and Giuseppe Perelli and Michael J. Wooldridge},
  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},
}

Loading related content...

Figure