On characterization and existence of a constrained correlated equilibria in Markov games

Tingting Ni, Anna M. Maddux, Maryam Kamgarpour

Introduction

In multi-agent systems such as autonomous vehicle navigation or electricity market bidding, agents must navigate complex environments while adhering to strict shared restrictions. These restrictions—ranging from safety protocols to budget caps—are modeled as Markov games with coupling constraints. In these games, the feasibility of one agent's action often depends on the collective behavior of the group.

While the Nash Equilibrium is the standard solution concept for competitive games, finding it in multi-agent Markov settings is often computationally intractable. To address this, researchers frequently turn to the Correlated Equilibrium (CE), a solution concept where agents coordinate their actions based on a shared signal. However, the constrained version of this equilibrium (CCE) remains poorly understood. This paper addresses two critical gaps in the theory of CCE: its mathematical characterization and the conditions required for its existence.

Characterizing Deviations: Simplifying the Search Space

A fundamental question in defining a CCE is determining what types of strategy deviations must be considered. In a correlated equilibrium, no player should want to deviate from a recommended policy. However, it was previously unclear whether agents could gain an advantage by using complex, history-dependent (non-Markovian) deviations.

The authors address this by constructing specialized auxiliary Markov Decision Processes (MDPs). By mapping different classes of policy modifications into these MDPs, they compare the state-action occupancy measures—the distribution of states and actions visited over time—induced by various deviations.

Key Finding: The authors prove in Theorem 3.3 that a CCE defined against complex, non-Markovian stochastic modifications is mathematically equivalent to one defined against simple Markovian modifications. This is a significant result for the development of future algorithms; it implies that researchers can restrict their search space to simpler strategies without losing the equilibrium's integrity, leading to more efficient computation.

The Existence Problem and the Slater Condition

Proving that an equilibrium actually exists in a constrained game is a significant mathematical challenge. Previous proofs relied on a "strong Slater's condition," an unrealistic assumption that every individual player has the power to unilaterally force the entire system into a strictly safe state.

The authors investigate whether this condition is truly necessary and find that the answer depends on how constraints are structured:

  1. Playerwise Constraints: If each player has unique constraints that depend on the actions of others, the authors demonstrate through a concrete 2-player game (Example 1) that the strong Slater's condition is indeed necessary. Without it, an equilibrium may not exist.
  2. Common Coupling Constraints: The paper's most significant breakthrough occurs here. If all players share the same constraints—such as a global emissions cap or shared physical boundaries—the mathematical landscape changes. In Theorem 4.3, the authors prove that a CCE is guaranteed to exist under a vastly relaxed, more realistic Slater-type condition.

Methodology

This research is purely theoretical, utilizing tools from game theory and mathematical optimization. The existence proof relies on Kakutani’s fixed-point theorem. Because searching over infinite stochastic modifications is difficult, the authors formulate the search for the best feasible deviation as a Linear Program (LP). By analyzing the geometry of feasible policies and the convexity of state-action occupancy measures, they establish the existence of an equilibrium point.

Limitations and Future Outlook

While this work provides a robust theoretical foundation for CCE, it has certain limitations:

  • Convexity Constraints: The existence proof relies heavily on the convexity of state-action occupancy measures. This property holds for Correlated Equilibria but does not apply to Constrained Nash Equilibria, meaning these techniques cannot be directly applied to Nash existence proofs.
  • Scope: The current proofs are limited to finite-horizon games with finite state and action spaces.

Future research directions include extending these existence results to infinite-horizon games and continuous state/action spaces. Additionally, the authors suggest investigating whether the "common coupling constraints" framework can help bypass the computational hurdles typically associated with finding equilibria in large-scale constrained games.

Summary updated

BibTeX
@misc{ni2025characterization,
  author = {Tingting Ni and Anna M. Maddux and Maryam Kamgarpour},
  title = {{On characterization and existence of a constrained correlated equilibria in Markov games}},
  year = {2025},
  eprint = {2507.03502},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.03502},
}
Figure