Incentive Engineering for Concurrent Games

David Hyland, Julian Gutierrez, Michael J. Wooldridge

Abstract

We consider the problem of incentivising desirable behaviours in multi-agent systems by way of taxation schemes. Our study employs the concurrent games model: in this model, each agent is primarily motivated to seek the satisfaction of a goal, expressed as a Linear Temporal Logic (LTL) formula; secondarily, agents seek to minimise costs, where costs are imposed based on the actions taken by agents in different states of the game. In this setting, we consider an external principal who can influence agents' preferences by imposing taxes (additional costs) on the actions chosen by agents in different states. The principal imposes taxation schemes to motivate agents to choose a course of action that will lead to the satisfaction of their goal, also expressed as an LTL formula. However, taxation schemes are limited in their ability to influence agents' preferences: an agent will always prefer to satisfy its goal rather than otherwise, no matter what the costs. The fundamental question that we study is whether the principal can impose a taxation scheme such that, in the resulting game, the principal's goal is satisfied in at least one or all runs of the game that could arise by agents choosing to follow game-theoretic equilibrium strategies. We consider two different types of taxation schemes: in a static scheme, the same tax is imposed on a state-action profile pair in all circumstances, while in a dynamic scheme, the principal can choose to vary taxes depending on the circumstances. We investigate the main game-theoretic properties of this model as well as the computational complexity of the relevant decision problems.

Introduction

In multi-agent systems (MAS), autonomous agents act according to their own interests, often defined by complex logical goals. While Rational Verification allows us to check if such systems will behave correctly, it is inherently reactive. If a system fails to meet a global objective, a mechanism is needed to steer it toward compliance.

This paper, presented at TARK 2023, introduces "Incentive Engineering" for concurrent games. It explores how an external "principal" can use taxation to influence agent behavior toward a desired global objective, even when agents have strict lexicographic preferences: their absolute priority is satisfying a Linear Temporal Logic (LTL) goal, with cost minimization being only a secondary concern. This means a principal cannot simply "buy off" an agent to abandon its primary mission; instead, taxes must function as a sophisticated tie-breaking mechanism.

Modeling Incentives in Concurrent Games

The authors model the system as a Concurrent Game Arena where agents choose actions simultaneously over infinite rounds. The principal aims to impose a taxation scheme such that the resulting Nash Equilibria of the game satisfy a global objective $\Upsilon$.

Figure 1: (a) Illustration of agent preferences where goal satisfaction is prioritized over cost. (b) A grid-world example with two robots demonstrating the need for strategic steering.

As shown in Figure 1(a), agents first ensure their strategy $\vec{\sigma}$ belongs to the set of Nash Equilibria that satisfy their goal ($NE_{\gamma_i}(\mathcal{G}^0)$). Within that set, they prefer strategies with lower costs ($c_i$). The principal's task is to adjust these costs so that the rational choice for the agent aligns with the system's global goal.

Static vs. Dynamic Taxation

A key technical contribution is the distinction between two types of taxation:

  1. Static Taxation: A fixed tax is applied to a specific action profile in a specific state, regardless of history.
  2. Dynamic Taxation: The tax is determined by a finite-state machine that tracks the game's history, allowing the principal to punish specific sequences of behavior.

The research demonstrates that dynamic taxation is strictly more powerful than static taxation. In infinite games, static taxes are prefix-independent and cannot effectively target early stages of a run to prevent agents from falling into "bad" (but goal-satisfying) equilibria. Dynamic taxes can use memory to eliminate these undesirable paths.

Formal Implementation and Complexity

The paper investigates two primary implementation problems: E-Nash Implementation (can a scheme ensure at least one Nash Equilibrium satisfies the goal?) and A-Nash Implementation (can a scheme ensure all Nash Equilibria satisfy the goal?).

Figure 4: (a) A formal concurrent game arena with states $s_0 \dots s_3$. (b) A dynamic taxation scheme represented as a finite-state machine.

Figure 4 illustrates the formal structures used: a game arena (a) and a dynamic taxation scheme (b) that tracks transitions to determine costs. The authors prove that E-Nash Implementation is 2EXPTIME-complete, matching the complexity of standard rational verification. This suggests that adding a principal does not necessarily increase the worst-case computational burden.

Conclusion

This work provides a formal foundation for incentive engineering in MAS. By characterizing "eliminability"—the conditions under which "bad" behaviors can be taxed away—the authors show how memory-dependent incentives can steer rational agents. Future work includes refining the complexity bounds for A-Nash implementation and extending the model to stochastic environments or multi-agent reinforcement learning (MARL) contexts.

Summary updated

Abstract

:We consider the problem of incentivising desirable behaviours in multi-agent systems by way of taxation schemes. Our study employs the concurrent games model: in this model, each agent is primarily motivated to seek the satisfaction of a goal, expressed as a Linear Temporal Logic (LTL) formula; secondarily, agents seek to minimise costs, where costs are imposed based on the actions taken by agents in different states of the game. In this setting, we consider an external principal who can influence agents' preferences by imposing taxes (additional costs) on the actions chosen by agents in different states. The principal imposes taxation schemes to motivate agents to choose a course of action that will lead to the satisfaction of their goal, also expressed as an LTL formula. However, taxation schemes are limited in their ability to influence agents' preferences: an agent will always prefer to satisfy its goal rather than otherwise, no matter what the costs. The fundamental question that we study is whether the principal can impose a taxation scheme such that, in the resulting game, the principal's goal is satisfied in at least one or all runs of the game that could arise by agents choosing to follow game-theoretic equilibrium strategies. We consider two different types of taxation schemes: in a static scheme, the same tax is imposed on a state-action profile pair in all circumstances, while in a dynamic scheme, the principal can choose to vary taxes depending on the circumstances. We investigate the main game-theoretic properties of this model as well as the computational complexity of the relevant decision problems.
BibTeX
@inproceedings{hyland2023incentive,
  author = {David Hyland and Julian Gutierrez and Michael J. Wooldridge},
  title = {{Incentive Engineering for Concurrent Games}},
  booktitle = {TARK},
  year = {2023},
  url = {https://openreview.net/forum?id=cXPtiOl6sM},
}
Figure