Equilibria for games with combined qualitative and quantitative objectives

Julian Gutierrez, Aniello Murano, Giuseppe Perelli, Sasha Rubin, Thomas Steeples, Michael J. Wooldridge

This paper explores the intersection of logic and optimization in multi-agent systems. By combining qualitative goals (logical requirements) with quantitative objectives (numerical rewards), the authors provide a framework for reasoning about how rational agents—like autonomous robots or software processes—interact when they have complex, tiered priorities.

TL;DR

The authors present a framework for multi-player games where agents prioritize satisfying a logical goal (expressed in Linear Temporal Logic) before optimizing a numerical reward (mean-payoff). They prove that finding a stable outcome—a strict $\epsilon$-Nash equilibrium—in these games is decidable and 2ExpTime-complete, providing a solid theoretical foundation for the "Rational Synthesis" of multi-agent systems.

What Problem Does This Paper Address?

In traditional game theory and formal verification, agent preferences are usually modeled in one of two ways:

  1. Qualitative: A player either succeeds or fails (e.g., "The robot must reach the exit without crashing"). This is often modeled using Linear Temporal Logic (LTL).
  2. Quantitative: A player earns a numerical score (e.g., "Minimize fuel consumption"). This is often modeled using mean-payoff functions.

Real-world scenarios often require both. A robot's primary directive is to complete its task safely (qualitative), but among all safe paths, it should choose the most efficient one (quantitative). This paper addresses the challenge of finding equilibria in games where players have these lexicographic preferences: they first maximize the chance of satisfying their LTL goal, and only then do they seek to maximize their mean-payoff reward.

Methods

The authors model these interactions as concurrent games played on finite graphs. To solve for equilibria, they employ a multi-step algorithmic pipeline:

  • Automata Transformation: They first convert each player's LTL goal into a Deterministic Parity Automaton (DPW). This effectively "bakes" the logical requirements into the game's state space, turning the problem into a Lex(parity, mean-payoff) game.
  • Zero-Sum Analysis: To determine if a strategy profile is stable, one must know the "punishing value"—the worst-case payoff a coalition of opponents can force upon a single player if they deviate. The authors show how to compute these values in polynomial time relative to the state space (though exponential in the number of priorities).
  • Graph Reduction and Linear Programming: The search for an equilibrium is reduced to finding an "ultimately periodic path" in a multi-weighted graph. They use a novel application of Linear Programming to detect $\eta$-multicycles, which represent sets of cycles that collectively satisfy the required payoff thresholds.
  • Solution Concept: They focus on strict $\epsilon$-Nash equilibria. In this setting, any unilateral deviation by a player results in an outcome that is strictly worse by at least a small margin ($\epsilon$), making the equilibrium more stable than "ordinary" Nash equilibria.

Datasets

Not discussed in the paper. As a theoretical contribution to computer science and game theory, the work focuses on complexity analysis and algorithmic proofs rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Lexicographic Advantage: By treating logic as the primary goal and rewards as secondary, the model captures "rational" behavior more accurately than models that try to collapse both into a single numerical value (which often requires arbitrary weighting).
  • Finite-State Implementation: The authors focus on strategies that can be implemented by finite-state machines. This is crucial for AI and robotics, as it ensures the resulting strategies can actually be programmed into a physical agent.
  • The "Negation" Trap: The paper highlights a subtle difficulty in mean-payoff games: you cannot simply negate weights to turn a minimization problem into a maximization one in infinite games. This is because the limit-average of a sequence may not behave symmetrically under negation.
This figure illustrates a simple two-state arena used to demonstrate why negating weights in mean-payoff games is not always strategically equivalent in infinite-duration games.

Key Results

  • Complexity: The central decision problem—determining if a game has a strict $\epsilon$-Nash equilibrium—is 2ExpTime-complete.
  • Hardness vs. Feasibility: While 2ExpTime sounds daunting, it is the same complexity class as standard LTL games. This means that adding quantitative mean-payoff objectives does not make the problem exponentially harder than the purely logical version.
  • Decidability: The authors prove that the problem remains decidable even when players are allowed to use infinite-memory strategies for their deviations, provided the equilibrium strategies themselves are finite-state.

Limitations and Future Work

  • Ordinary Equilibria: The current results specifically target strict $\epsilon$-Nash equilibria. The authors note that characterizing "ordinary" (non-strict) Nash equilibria in this combined setting remains an open and potentially more difficult challenge.
  • State Space Explosion: Because the complexity is doubly exponential in the size of the LTL formulas, practical implementations will likely need to focus on restricted fragments of LTL (like GR(1)) or employ heuristic search methods.
  • Memoryless Strategies: A promising direction for future work is investigating whether simpler, "memoryless" strategies are sufficient for certain types of game arenas, which could significantly reduce the computational burden.

Summary updated

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.
BibTeX
@article{gutierrez2021equilibria,
  author = {Julian Gutierrez and Aniello Murano and Giuseppe Perelli and Sasha Rubin and Thomas Steeples and Michael J. Wooldridge},
  title = {{Equilibria for games with combined qualitative and quantitative objectives}},
  journal = {Acta Informatica},
  year = {2021},
  doi = {10.1007/s00236-020-00385-4},
}

Loading related content...

Figure