Abstract
The overall aim of our research is to develop techniques to reason about the equilibrium properties of multi-agent systems. We model multi-agent systems as concurrent games, in which each player is a process that is assumed to act independently and strategically in pursuit of personal preferences. In this article, we study these games in the context of finite-memory strategies, and we assume players' preferences are defined by a qualitative and a quantitative objective, which are related by a lexicographic order: a player first prefers to satisfy its qualitative objective (given as a formula of Linear Temporal Logic) and then prefers to minimise costs (given by a mean-payoff function). Our main result is that deciding the existence of a strict epsilon Nash equilibrium in such games is 2ExpTime-complete (and hence decidable), even if players' deviations are implemented as infinite-memory strategies.
Introduction
In the fields of game theory and formal verification, agent preferences are typically modeled as either qualitative (success/failure) or quantitative (numerical rewards). For instance, a robot might be tasked with reaching an exit without crashing (qualitative, often modeled via Linear Temporal Logic or LTL) or minimizing its fuel consumption (quantitative, often modeled via mean-payoff functions). However, real-world multi-agent systems—such as autonomous robot swarms or complex software processes—frequently require both.
This research addresses the challenge of finding stable outcomes in concurrent games where players have lexicographic preferences: they prioritize satisfying a logical LTL goal before seeking to maximize a secondary mean-payoff reward. We focus on the existence of strict $\epsilon$-Nash equilibria, a solution concept that ensures stability by requiring that any unilateral deviation results in a strictly worse outcome by at least a small margin.
Methodology
The proposed framework models agent interactions as concurrent games played on finite graphs. The algorithmic pipeline for solving these games involves several key steps:
- Automata Transformation: Each player's LTL goal is converted into a Deterministic Parity Automaton (DPW). This integrates the logical requirements directly into the game's state space, transforming the problem into a Lex(parity, mean-payoff) game.
- Zero-Sum Analysis: To evaluate the stability of a strategy profile, the "punishing value"—the worst-case payoff opponents can force upon a deviating player—must be computed. This is shown to be achievable in polynomial time relative to the state space size.
- Graph Reduction and Linear Programming: The search for an equilibrium is reduced to identifying an "ultimately periodic path" in a multi-weighted graph. A novel application of Linear Programming is used to detect $\eta$-multicycles, which represent sets of cycles satisfying required payoff thresholds.
- Finite-State Implementation: The focus is on strategies implementable by finite-state machines, ensuring that the resulting behaviors can be practically programmed into physical agents or software.
Key Insights and Theoretical Nuances
A significant advantage of this lexicographic approach is its ability to capture rational behavior more accurately than models that attempt to collapse qualitative and quantitative goals into a single numerical value, which often necessitates arbitrary weighting.
The research also highlights subtle difficulties inherent in mean-payoff games. For example, in infinite-duration games, one cannot simply negate weights to convert a minimization problem into a maximization one, as the limit-average of a sequence may not behave symmetrically under negation.
Results
The central finding of this work is that the decision problem for the existence of a strict $\epsilon$-Nash equilibrium is 2ExpTime-complete. Notably, this complexity class is the same as that for standard LTL games, indicating that the addition of quantitative mean-payoff objectives does not increase the exponential complexity of the problem. Furthermore, the problem remains decidable even when allowing for infinite-memory deviations, provided the equilibrium strategies themselves remain finite-state.
Discussion and Future Work
While this work provides a solid theoretical foundation for the rational synthesis of multi-agent systems, several avenues for future research remain. The current results are specific to strict $\epsilon$-Nash equilibria; characterizing ordinary Nash equilibria in this combined setting may prove more challenging. Additionally, the doubly exponential complexity suggests that practical applications will need to focus on restricted LTL fragments (like GR(1)) or employ heuristic search methods to mitigate state-space explosion. Future investigations into the sufficiency of memoryless strategies for certain game arenas could also significantly reduce computational requirements.
Summary updated