Qualitative Analysis of Concurrent Mean-payoff Games

Krishnendu Chatterjee, Rasmus Ibsen-Jensen

Abstract

Concurrent mean-payoff games model interactions where multiple agents act simultaneously to optimize long-run average rewards. This paper provides a comprehensive qualitative analysis of these games, establishing their determinacy and providing efficient algorithms for computing winning sets. We demonstrate that almost-sure and positive winning sets can be determined in quadratic time, $O(n \cdot |\delta|)$, matching the complexity of simpler reachability problems. A key contribution is the characterization of strategy complexity: while exact qualitative constraints may necessitate infinite memory, stationary randomized strategies suffice for achieving payoffs arbitrarily close to the maximum.

Introduction

In the study of multi-agent systems, concurrent games provide a robust framework for modeling simultaneous actions, such as those found in distributed network protocols or high-frequency trading. The mean-payoff objective, which evaluates the long-run average reward of a sequence of actions, is a standard performance metric. While quantitative analysis—finding the exact value of a game—is computationally intensive and sensitive to numerical precision, qualitative analysis offers a more robust perspective by asking whether a player can win with probability 1 (almost-sure winning) or with some positive probability.

Prior to this work, the computational complexity and memory requirements for qualitative analysis of concurrent mean-payoff games remained unresolved. This paper addresses these gaps, providing both algorithmic bounds and a detailed taxonomy of strategy types.

Methodology

The authors employ a combination of fixpoint logic and graph-theoretic algorithms to analyze the game structure. Concurrent moves are modeled as simultaneous choices by players, often represented as grids of transitions from a given state.

Example of a concurrent game state transition where players move simultaneously.

Key methodological components include:

  • Fixpoint Characterization: Winning sets are defined using nested fixpoint expressions in the $\mu$-calculus. A central innovation is the Allow-Stay-Progress (ASP) predecessor operator, which formalizes the requirement that a player must be able to remain within a "safe" set of states while ensuring eventual progress toward higher rewards.
  • Algorithmic Efficiency: By generalizing the "small-progress measure" algorithm, the authors improve the complexity of computing winning sets from a naive cubic-time approach to a quadratic-time solution ($O(n \cdot |\delta|)$).
  • Hardness Reductions: The paper uses gadget reductions from turn-based deterministic mean-payoff games to demonstrate that solving the quantitative version of these games in polynomial time would resolve a long-standing open problem in complexity theory.

Strategy Complexity and Determinacy

A major finding of this research is the "memory divide" between different qualitative constraints. The complexity of a winning strategy depends heavily on whether the goal is to meet an exact payoff threshold or to approach it in the limit.

Summary of strategy requirements for ensuring and spoiling strategies across different qualitative objectives.

As shown in the table above, ensuring an exact payoff typically requires Markov strategies (which depend on the current state and time) or even infinite memory. Conversely, for limit qualitative constraints—where the goal is to ensure a payoff arbitrarily close to a threshold—stationary randomized strategies are sufficient. These strategies are simpler as they do not depend on the history of the game.

The authors also prove that concurrent mean-payoff games are determined: for any given state, either Player 1 has a strategy to win, or Player 2 has a "spoiling" strategy to prevent that win with positive probability.

Key Results

  • Quadratic Time Algorithms: Almost-sure and positive winning sets can be computed in $O(n \cdot |\delta|)$ time, where $n$ is the number of states and $|\delta|$ is the size of the transition relation.
  • Patience Bounds: The "patience" required for stationary strategies—defined as the inverse of the smallest non-zero probability used—is shown to be double exponential in the number of states. The authors provide a lower bound confirming this is asymptotically optimal.
  • Computational Boundary: The results highlight a significant boundary between qualitative and quantitative analysis, showing that the former is as efficient as reachability, while the latter remains tied to the complexity of turn-based games.

Conclusion and Future Work

This paper establishes that qualitative analysis of concurrent mean-payoff games is computationally feasible and provides a complete characterization of the necessary strategies. Future research directions include extending these results to partial-observation settings, where players have incomplete information about the system state, and exploring multi-valued reward structures beyond the boolean case.

Summary updated

BibTeX
@article{chatterjee2015qualitative,
  author = {Krishnendu Chatterjee and Rasmus Ibsen-Jensen},
  title = {{Qualitative Analysis of Concurrent Mean-payoff Games}},
  journal = {Inf. Comput.},
  year = {2015},
  doi = {10.1016/j.ic.2015.03.009},
}
Figure