On the characterization and existence of constrained correlated equilibria in Markov games
July 04, 2025
Abstract
Markov games with coupling constraints model constrained dynamical decision-making involving self-interested agents, where the feasibility of an individual agent’s strategy depends on the joint strategies of the others. Such games arise in numerous real-world applications involving safety requirements and budget caps, for example, in environmental management, electricity markets, and transportation systems. In unconstrained dynamical decision-making, the correlated equilibrium has emerged as a desired solution concept, due to its computational tractability and amenability to learning algorithms. Understanding how coupling constraints shape correlated equilibria is a crucial step towards computing solutions in constrained Markov games. In this paper, we formalize and characterize the notion of constrained correlated equilibria for Markov games, defined as feasible joint policies where any unilateral deviation is either unprofitable or infeasible. Building on this characterization, we further study existence conditions of constrained correlated equilibria. In particular, we provide a novel existence proof of such equilibria in Markov games with coupling constraints.
1 Introduction↩︎
Many real-world systems involve multiple self-interested agents that interact with each other in a dynamic environment. Such multi-agent systems can be framed as Markov games, also referred to as stochastic games [1], which extend normal-form games to dynamic settings. With the rapid rise of multi-agent reinforcement learning, Markov games have become a central framework for studying coordination, competition, and learning among agents. While multi-agent reinforcement learning has achieved impressive success in handling complex and high-dimensional systems [2], [3], safety concerns arise when applying it to real-world systems, where agents often face coupling constraints—that is, the feasibility of each agent’s strategy depends on the joint actions of all others.
Prominent examples arise in environmental management [4], where countries must jointly ensure that greenhouse emissions are below some threshold, in electricity markets [5], where transmission capacity constraints must be satisfied, or in transportation systems [6], where vehicles must avoid collisions with other vehicles. Such multi-agent systems can be framed as Markov games with coupling constraints [7], representing a direct generalization of constrained Markov decision processes to the multi-agent setting [8]–[10]. To analyze constrained multi-agent decision making, it is crucial to characterize constrained equilibrium notions for this class of games and prove its existence.
The generalized Nash equilibrium was first introduced in [11] for normal-games as a natural extension of its unconstrained counterpart, the Nash equilibrium [12]. Several works have since emerged to study the generalized Nash equilibrium, including its characterization and existence in various game settings, ranging from constrained normal-form games [11], [13]–[20] to constrained Markov games [21]–[25]. However, without further assumptions, computing a generalized Nash equilibrium is intractable [26], a property it inherits from the Nash equilibrium.
To circumvent intractability of Nash equilibria in normal form games, past works have turned to weaker equilibrium notions. In particular, a correlated equilibrium [27], [28] is a strict generalization of Nash equilibria which can be computed and learned efficiently [29]–[33]. In Markov games, tractability of correlated equilibria has also recently been established [34]. However, to date, equilibrium notions in constrained Markov games have received little attention. This motivates studying the constrained correlated equilibrium which was recently introduced by [35]–[38].
In constrained Markov games, a constrained correlated equilibrium is a feasible policy such that any unilateral modification is either unprofitable or leads to an infeasible outcome. Different classes of modifications—deterministic versus stochastic—give rise to alternative equilibrium formulations. In particular, stochastic modifications form a more general class of modifications, and therefore define a stronger equilibrium concept. Characterizing constrained correlated equilibria under these different classes of modifications remains an open research problem. In the unconstrained setting, both for normal-form and Markov games, it was shown that restricting to the subset of deterministic modifications yields an equivalent formulation of a correlated equilibrium. However, in the presence of constraints, such a restriction leads to a weaker equilibrium notion [35]. As the structure and characterization of constrained correlated equilibria in terms of possible modifications remain only partially understood, we are led to the following question:
Which classes of modification yield equivalent notions of constrained correlated equilibria?
Beyond characterization, an important question concerns the existence of constrained correlated equilibria. For Markov games with playerwise coupling constraints, [21] establishes the existence of a constrained Nash equilibrium.1 As constrained Nash equilibria are also constrained correlated equilibria [37], existence of the former implies existence of a constrained correlated equilibrium. However, the above existence proof relies on a so-called strong Slater’s condition, which requires that every agent can modify its policy so that any joint policy is strictly feasible. This is often unrealistic; for example, in multi-agent robotic systems, this would require each vehicle to guarantee collision avoidance with all other vehicles, regardless of their actions. Motivated by this limitation, a natural question is whether the strong Slater condition can be relaxed. This is challenging due to the generality of playerwise coupling constraints, where each agent must independently ensure feasibility. Unfortunately, constrained correlated equilibria may fail to exist without this condition (see Example 1 in Section 4). To overcome this, we focus on common coupling constraints, where all agents share the same constraints. Such settings naturally arise in applications with shared resource or safety requirements, including environmental management, power grids, and transportation networks. For normal-form games with common coupling constraints, [36] proves the existence of a constrained correlated equilibrium assuming a jointly feasible policy exists, which is a much weaker condition than the strong Slater’s condition. However, they only consider deterministic modifications and, as discussed above, this leads to a weaker notion of a constrained correlated equilibrium. Motivated by the above, the second question we address in this paper is the following:
Under what conditions does a constrained correlated equilibrium exist in Markov games with coupling constraints?
Contributions Our paper addresses the characterization and existence of constrained correlated equilibria in finite-horizon Markov games with finite state and action spaces. For clarity, we summarize our results alongside existing results on characterization and existence in both normal-form and Markov games in Table [table]. Our main contributions are as follows:
We show that constrained correlated equilibria are equivalently characterized by restricting to convex combinations of deterministic modifications (Theorem 1). More importantly, we leverage this result to establish our existence result.
For Markov games with common coupling constraints, we establish the existence of constrained correlated equilibria under a significantly weakened Slater-type condition (Theorem 2). Together with the characterization result above, this shows that the strong Slater’s condition is primarily an artifact of playerwise coupling constraints. Moreover, our result is new even for normal-form games, which are a special case of Markov games.
4pt
@p0.17p0.15XX@ Equilibrium & Aspect & Normal-form games & Markov games
& & Deterministic modifications [28] & Deterministic modifications [35]
(lr)2-4 & Existence & [27] & [39]
& &
(lr)2-4 & Existence &
Notation Let \(\mathbb{N}\) and \(\mathbb{R}\) denote the sets of natural and real numbers, respectively. For any \(m \in \mathbb{N}\), we define \([m] := \{1, \dots, m\}\). We denote by \(x_{m:n}\) the sequence \(\{x_m, x_{m+1}, \dots, x_n\}\). Let \(\mathbf{1}_n\) denote the all-ones vector of dimension \(n\). Given a finite set \(\mathcal{X}\), we denote the indicator function by \(\mathbb{1}_{\mathcal{X}}(x)\). Furthermore, the probability simplex over \(\mathcal{X}\) is denoted by \(\Delta({\mathcal{X}})\) and the cardinality of \(\mathcal{X}\) is denoted by \(|\mathcal{X}|\). Given any two finite sets \(\mathcal{X}\) and \(\mathcal{Y}\) in \(2^{\mathbb{R}^d}\), we define the Minkowski sum of the sets \(\mathcal{X}\) and \(\mathcal{Y}\) as \(\mathcal{X}+ \mathcal{Y} =\{x+y\mid x\in\mathcal{X},\,y\in\mathcal{Y}\}\). Given a point-to-set mapping \(f:\mathcal{X} \to 2^{\mathcal{Y}}\), we say that \(f\) is upper semi-continuous on \(\mathcal{X}\) if, for every \(x_0\in\mathcal{X}\) and every neighborhood \(N_Y\) of \(f(x_0)\), there exists a neighborhood \(N_{x_0}\) of \(x_0\) such that \(f(x)\subseteq N_Y,\, \forall x\in N_{x_0}\). We further say that \(f\) is upper semi-compact if it is upper semi-continuous and \(f(x)\) is compact for every \(x\in\mathcal{X}\) [40].
2 A finite-horizon Markov game with coupling constraints↩︎
A finite-horizon Markov game with coupling constraints is given by the tuple \(\{\mathcal{N}, H, \mathcal{S}, \{\mathcal{A}^i\}_{i\in\mathcal{N}}, P, \rho,\{r^i\}_{i\in\mathcal{N}}, \{g^{i,j}\}_{i\in\mathcal{N},j\in[J]}, \{c^{i,j}\}_{i\in\mathcal{N},j\in[J]}\}\), where \(\mathcal{N}=[N]\) denotes the set of players and \(H\in\mathbb{N}\) denotes a finite horizon. The set \(\mathcal{S}\) denotes a finite state space and each player \(i\in\mathcal{N}\) has a finite action space \(\mathcal{A}^i\). Let \(a=(a^1,\ldots, a^N)\in\mathcal{A}\) denote the joint action profile, where \(\mathcal{A} =\Pi_{i=1}^N A^i\) is the joint action space. Similarly, let \(a^{-i}=(a^1,\ldots,a^{i-1},a^{i+1},\ldots,a^N)\in\mathcal{A}^{-i}=\Pi_{j\neq i}\mathcal{A}^j\) denote the joint action profile of all players except player \(i\). The transition kernel is denoted by \(P := \{P_t\}_{t\in[H-1]}\), where \(P_t : \mathcal{S} \times \mathcal{A} \rightarrow \Delta(\mathcal{S})\). Specifically, \(P_t(s_{t+1} |s_t, a_t)\) denotes the probability of transitioning from state \(s_t \in \mathcal{S}\) to state \(s_{t+1} \in \mathcal{S}\) under the joint action \(a_t \in \mathcal{A}\). The initial state distribution is denoted by \(\rho\in\Delta(\mathcal{S})\).
Furthermore, each player \(i \in \mathcal{N}\) has a reward function \(r^i := \{r^i_t\}_{t \in [H]}\), where \(r^i_t : \mathcal{S} \times \mathcal{A} \rightarrow [0,1]\). Additionally, each player has \(J\) constraint functions \(g^{i,j} := \{g^{i,j}_t\}_{t \in [H]}\) for \(j \in [J]\), where \(g^{i,j}_t : \mathcal{S} \times \mathcal{A} \rightarrow [0,1]\). The threshold with respect to each player \(i\)’s constraints \(g^{i,j}\) is denoted by \(c^{i,j}\in\mathbb{R}\). We refer to the set of constraints \(\{g^{i,j}\}_{j\in[J]}\) as playerwise coupling constraints since each player has its own set of constraints that depend on the joint action profile. If, however, the constraint functions and threshold values are equal across all players, i.e., \(g^{i,j}=g^j\) and \(c^{i,j}=c^j\) for all \(j\in[J]\) and \(i\in\mathcal{N}\), then we refer to these types of constraints as common coupling constraints, as each player is subject to the same set of constraints. For shorthand, we refer to Markov games with coupling constraints as constrained Markov games.
Game dynamics For \(t \in[H]\), let \(\pi_t : \mathcal{S} \rightarrow \Delta(\mathcal{A})\) denote a mapping from each state \(s \in \mathcal{S}\) to a distribution over the joint action space \(\mathcal{A}\) at timestep \(t\). We define \(\pi := \{\pi_t\}_{t \in [H]}\) as a Markovian policy, and denote the set of all such policies by \(\Pi_M\).
In a constrained Markov game, an initial state \(s_1\) is drawn from the initial distribution \(\rho\), i.e., \(s_1 \sim \rho\in\Delta(\mathcal{S})\). At each timestep \(t\), the players select a joint action \(a_t\sim \pi_t(\cdot\,\lvert\, s_t)\) based on policy \(\pi\in\Pi_M\) and each player receives a reward \(r_t^i(s_t,a_t)\) and a set of constraints \(\{g_t^{i,j}(s_t,a_t)\}_{j\in[J]}\). Then, the state \(s_t\) transitions to a new state \(s_{t+1} \sim P_t(\cdot\,\lvert\, s_t, a_t)\). The expected cumulative reward over the horizon \(H\) of player \(i\) is defined as: \[\begin{align} V^{r^i}(\pi) := \mathbb{E}_{\substack{ s_1 \sim \rho,\, a_t \sim \pi_t(\cdot | s_t), s_{t+1} \sim P_t(\cdot | s_t, a_t) }} \left[ \sum_{t=1}^{H} r^i_t(s_t, a_t) \right]. \end{align}\] and its expected cumulative constraint value over the horizon \(H\) is defined as: \[\begin{align} V^{g^{i,j}}(\pi) := \mathbb{E}_{\substack{ s_1 \sim \rho,\, a_t \sim \pi_t(\cdot | s_t), s_{t+1} \sim P_t(\cdot | s_t, a_t) }} \left[ \sum_{t=1}^{H} g^{i,j}_t(s_t, a_t) \right], \,\forall j \in[J]. \end{align}\] The transition dynamics \(P\) and policy \(\pi\in\Pi_M\) induce a distribution over state-action pairs, the so-called state-action occupancy measure, given by: for all \(t\in[H]\) and \((s_t,a_t)\in\mathcal{S}\times\mathcal{A}\), \[\begin{align} d_1^\pi(s_1,a_1) &= \rho(s_1)\pi_1(a_1\lvert s_1) ,\\ d_t^\pi(s_t,a_t) &=\sum_{(s_{t-1},a_{t-1})\in\mathcal{S}\times \mathcal{A}}\!\!\!\!\!\!\!\!\!d_{t-1}^\pi(s_{t-1},a_{t-1}) P_{t-1}(s_t\lvert s_{t-1},a_{t-1})\pi_t(a_t\lvert s_t). \end{align}\] The reward function and constraint functions can then equivalently be expressed as: \[\begin{align} &V^{r^i}(\pi) = \sum_{t=1}^H \sum_{(s_t,a_t)\in\mathcal{S}\times \mathcal{A}} d_t^\pi(s_t,a_t) r_t^i(s_t,a_t),\label{eq:reward95constraint95via95occupancy}\\ &V^{g^{i,j}}(\pi) = \sum_{t=1}^H \sum_{(s_t,a_t)\in\mathcal{S}\times \mathcal{A}} d_t^\pi(s_t,a_t) g_t^{i,j}(s_t,a_t), \,\forall j\in[J].\nonumber \end{align}\tag{1}\] In a constrained Markov game, each player \(i\) is subject to constraints of the form: \[\begin{align} \label{eq:i-feasible95set} V^{g^{i,j}}(\pi)\geq c^{i,j},\,\forall j\in[J]. \end{align}\tag{2}\] A policy \(\pi\) is said to be \(i\)-feasible if Inequality 2 above holds for every \(j\in[J]\). We denote the set of \(i\)-feasible policies by: \[\begin{align} \mathcal{C}_\pi^i:=\{\pi\in\Pi_M\mid V^{g^{i,j}}(\pi)\geq c^{i,j},\, \forall j\in[J]\}.\label{eq:i-feasible} \end{align}\tag{3}\] Furthermore, a policy \(\pi\) is called feasible if it is \(i\)-feasible for all \(i\in\mathcal{N}\). We denote the set of feasible policies by: \[\begin{align} \!\! \!\mathcal{C}_\pi:=\{\pi\in\Pi_M \mid V^{g^{i,j}}(\pi)\geq c^{i,j}, \forall j\in[J],\forall i\in\mathcal{N}\}.\label{eq:feasible95set} \end{align}\tag{4}\] Observe that \(\mathcal{C}_\pi=\bigcap_{i\in\mathcal{N}}\mathcal{C}_\pi^i\). For Markov games with common coupling constraints, we note that \(\mathcal{C}_\pi^i\) reduces to \(\mathcal{C}_\pi\) for all \(i\in\mathcal{N}\) since each player has the same set of constraints.
3 Constrained correlated equilibria↩︎
An important solution concept in Markov games is the correlated equilibrium. The constrained correlated equilibrium generalizes this notion to constrained Markov games. Before giving a formal definition, we introduce the Markovian stochastic modification.
Definition 1. A Markovian stochastic modification of player \(i\) is a collection of maps \(\phi^i =\{\phi_t^i\}_{t=1}^{H}\) with: \[\begin{align} \phi_t^i: \mathcal{S} \times \mathcal{A}^i\to \Delta(\mathcal{A}^i),\quad\forall t\in[H]. \end{align}\] Denote the set of such modifications by \(\Phi_M^i\). At each timestep \(t\), denote \(\hat{a}_t^i\) as player \(i\)’s action induced by policy \(\pi_t\). Given the current state \(s_t\) and player \(i\)’s action \(\hat{a}_t^i\), a stochastic modification \(\phi_t^i\) randomly maps \(\hat{a}_t^i\) to another action \(a_t^i\).
A modified policy \(\phi^i\circ\pi:=\{\phi_t^i\circ\pi_t\}_{t=1}^H\) is, for all \(t\in[H]\), all \(a_t\in\mathcal{A}\), and all \(s_t\in\mathcal{S}\), defined as: \[\begin{align} (\phi_t^i\circ\pi_t)(a_t\lvert s_t) =\sum_{\hat{a}_t^i\in\mathcal{A}^i} \phi_t^i( a_t^i\lvert s_t, \hat{a}_t^i)\pi_t((\hat{a}_t^i,a_t^{-i})\lvert s_t). \end{align}\] At each timestep \(t\), an action profile \((\hat{a}_t^i,a_t^{-i})\) is sampled from \(\pi_t\). Then \(\phi_t^i\) modifies \(\hat{a}_t^i\) to another \(a_t^i\) at random.
In the above definition, if \(\Delta(\mathcal{A}^i)\) is replaced by \(\mathcal{A}^i\), then we refer to \(\phi^i=\{\phi_t^i\}_{t=1}^H\) as a Markovian deterministic modification and denote the set of such modifications by \(\Phi_{M,det}^i\). We are now ready to introduce the constrained correlated equilibrium.
Definition 2 (Constrained correlated equilibrium). A Markovian policy \(\pi\in\Pi_M\) is a constrained correlated equilibrium if \(\pi\) is feasible, namely, \(\pi\in\mathcal{C}_\pi\), and if for any player \(i \in \mathcal{N}\) the following holds: \[\begin{align} \label{eq95notionCE} V^{r^i}(\pi) \ge \max_{\text{\phi^i\in\Phi_{M}^i is i-feasible}}V^{r^i}(\phi^i \circ \pi). \end{align}\qquad{(1)}\] In the maximization above, \(\phi^i\) is said to be \(i\)-feasible if the modified policy \(\phi^i\circ\pi\) is \(i\)-feasible, namely, \(\phi^i\circ\pi\in\mathcal{C}_\pi^i\), where \(\mathcal{C}_\pi^i\) is defined in Equation 4 .
In a constrained correlated equilibrium, for each player, any deviation via a stochastic modification \(\phi^i_M\) is either unprofitable or leads to an infeasible policy.
In unconstrained normal-form games, restricting the search for profitable deviations from the set of stochastic modifications \(\Phi_M^i\) to the subset of deterministic modifications \(\Phi_{M,\mathrm{det}}^i\) yields an equivalent notion of correlated equilibrium. For any joint policy \(\pi\), computing the best deviation for player \(i\), namely \(\max_{\phi^i \in \Phi_M^i} V^{r^i}(\phi^i \circ \pi)\), is a linear program over the simplex of \(\Phi_M^i\), whose extreme points correspond to \(\Phi_{M,\mathrm{det}}^i\). Hence, an optimal deviation can always be chosen deterministic. In contrast, this equivalence fails in normal-form games with coupling constraints, and therefore also in Markov games with coupling constraints. In this case, the search is restricted to feasible modifications in \(\Phi_M^i\), and the extreme points of the feasible set no longer correspond to \(\Phi_{M,\mathrm{det}}^i\). In particular, [35] establishes that restricting to \(\Phi_{M,\mathrm{det}}^i\) leads to a strictly weaker notion of constrained correlated equilibrium.
Nevertheless, we next introduce a class of modifications that preserves equivalence for constrained correlated equilibria.
Theorem 1. The following two statements are equivalent:
Policy \(\pi\) is a constrained correlated equilibrium as per Definition 2.
Policy \(\pi\) is feasible, and for every player \(i \in \mathcal{N}\), the following holds: for any \(\alpha \in \Delta(K^i)\), where \(K^i := |\Phi_{M,\mathrm{det}}^i|\), satisfying \(\sum_{k=1}^{K^i} \alpha_k V^{g^{i,j}}(\phi^i(k)\circ \pi) \geq c^{i,j}, \, \forall j \in [J]\), we have \[V^{r^i}(\pi)\geq \sum_{k=1}^{K^i} \alpha_k V^{r^i}(\phi^i(k)\circ \pi).\]
We say that \(\alpha\) is \(i\)-feasible* if \(\alpha\in\{\alpha\in\Delta(K^i)\mid\sum_{k=1}^{K^i} \alpha_k V^{g^{i,j}}(\phi^i(k)\circ\pi) \geq c^{i,j},\,\forall j \in [J]\}\).*
Theorem 1 shows that, in Definition 2, Inequality ?? can be verified over convex combinations of Markovian deterministic modifications in \(\Phi^i_{M,\mathrm{det}}\), rather than over all stochastic modifications in \(\Phi_M^i\). In normal-form games, stochastic deviations can be restricted to deterministic ones because the objective is linear and the set is a simplex. In the presence of constraints, however, the feasible set of deviations is no longer a simplex, and optimal deviations may require randomization. Theorem 1 shows that it nevertheless suffices to consider mixtures over deterministic modifications. In particular, \(\Phi_{M,\mathrm{det}}^i\) is finite, with cardinality \(|\Phi_{M,\mathrm{det}}^i| = H|S||\mathcal{A}^i|^{|\mathcal{A}^i|}\), whereas \(\Phi_M^i\) is infinite. Hence, it suffices to optimize over a mixture \(\alpha \in \Delta(K^i)\) for each player. This reformulation is also central to the existence result in Theorem 2.
The full proof of above is given in Appendix 7, and we outline a proof sketch below.
3.0.0.1 Proof sketch
Our goal is to reduce each player’s deviation problem to a single-agent finite-horizon MDP whose policies correspond to all possible modifications of player \(i\). Once this reduction is established, we can invoke the standard result that any stochastic policy in a finite-horizon MDP is equivalent to a convex combination of deterministic policies [41]. To construct this MDP, we encode everything observable to player \(i\) at time \(t\) into the state, namely \((s_t, a_t^i)\), where \(s_t\) is the environment state and \(a_t^i\) is the recommended action. The key idea is that the action in this MDP corresponds to a modification of the recommendation. Concretely, at state \((s_t, a_t^i)\), player \(i\) selects a modified action \(\hat{a}_t^i \sim \phi_t^i(\cdot \mid s_t, a_t^i)\). Given \((s_t, a_t^i)\) and the chosen modification \(\hat{a}_t^i\), the remaining players act according to the original policy, i.e., \(a^{-i} \sim \pi_t((\cdot,a_t^i) \mid s_t)\), and the environment transitions as \(s_{t+1} \sim P_t(\cdot \mid s_t, (\hat{a}_t^i, a_{-i}))\). To ensure independence from \(\pi\), we sample the next step recommended action \(a_{t+1}^i\) uniformly from \(\mathcal{A}^i\), treating it as an exogenous component of the augmented state. This defines a transition kernel \(\bar P_t^\pi((s_{t+1}, a_{t+1}^i)\mid (s_t, a_t^i), \hat{a}_t^i)\) (see Equation 14 ), where the randomness over \(a_t^{-i}\) is integrated out. Figure 1 illustrates the main idea of the proof sketch.
4 Existence of constrained correlated equilibria↩︎
We now turn to our main result on the existence of constrained correlated equilibria. In this section, we study sufficient conditions under which such equilibria exist in constrained Markov games.
Assumption 1 (Strong Slater’s condition). For any player \(i \in \mathcal{N}\) and any policy \(\pi \in \Pi_M\), there exists a modification \(\phi^i \in \Phi_M^i\) such that \[V^{g^{i,j}}(\phi^i \circ \pi) > c^{i,j}, \qquad \forall j\in[J].\]
Assumption 1 implies the Slater-type condition used in [21], which establishes the existence of constrained Nash equilibria under playerwise coupling constraints. Therefore, the analysis in that paper also yields existence of constrained correlated equilibria.
The strong Slater’s condition requires that each player can unilaterally modify the joint policy \(\pi\) so that the resulting policy \(\phi^i\circ\pi\) is strictly feasible for all of that player’s constraints. This requirement is often restrictive, as it asks each player to independently enforce feasibility of coupled constraints. Nevertheless, it plays a crucial role in ensuring existence: as the following example illustrates, even in normal-form games, such an assumption may be necessary to guarantee existence for playerwise coupling constraints.
Example 1. Consider a two-player normal-form game in which each player has action space \(\mathcal{A}^1=\mathcal{A}^2=\{1,2\}\). We denote the players by \(P1\) and \(P2\). The reward functions \((r^1,r^2)\) and the player-wise constraint functions \((g^{1,1},g^{2,1})\) are:
The constraint thresholds are \(c^{1,1}=\frac{1}{2},\,c^{2,1}=\frac{1}{3}\). It is straightforward to verify that the strong Slater’s condition (Assumption 1) does not hold. For example, consider the policy \(\pi((a^1,a^2)) = \mathbb{1}_{(a^1,a^2)=(2,2)}\). Any modification for \(P1\) results in \(\phi^1 \circ \pi((a^1,a^2)=(1,1)) = 0\), which is \(1\)-infeasible. Similarly, \(P2\) has no \(2\)-feasible modification.
Moreover, no constrained correlated equilibrium exists in this game. For any feasible policy \(\pi \in \mathcal{C}_\pi\), the best \(2\)-feasible modification for \(P2\) is \(\phi^2(\tilde{a}^2 | a^2) = \mathbb{1}_{\tilde{a}^2=2}\) for all \(a^2 \in \{1,2\}\), meaning that \(P2\) always switches to play \(a^2=2\). This modification strictly increases \(P2\)’s reward while remaining \(2\)-feasible (\(\phi^2 \circ \pi \in \mathcal{C}^2_\pi\)), thereby violating the equilibrium condition.
The above example shows that, under playerwise coupling constraints, constrained correlated equilibria may fail to exist without additional assumptions. In contrast, many real-world applications involve common coupling constraints—such as transportation systems with collision-avoidance requirements (see a simplified abstraction in the example below), where existence can still be guaranteed even when Assumption 1 is violated. Since our existence result is novel even for normal-form games, we illustrate the key ideas through simple normal-form examples below.
Example 2. Consider a two-player normal-form game in which each player has action space \(\mathcal{A}^1=\mathcal{A}^2=\{Stop, Go\}\).2 The reward functions \((r^1,r^2)\) and the common constraint function \(g^1\) are given below:
The constraint threshold is \(c^1 = 1\), which forbids the joint action \((\mathrm{Go}, \mathrm{Go})\). It is straightforward to verify that the strong Slater’s condition (Assumption 1) does not hold, since there exists no strictly feasible policy satisfying \(\pi((\mathrm{Go}, \mathrm{Go})) < 0\). However, a constrained correlated equilibrium exists in this game. For example, the policy \(\pi((\mathrm{Go}, \mathrm{Stop})) = \pi((\mathrm{Stop}, \mathrm{Go})) = 0.5\) is feasible and satisfies the equilibrium conditions.
Motivated by this observation, we now show that the strong Slater’s condition can be relaxed under common coupling constraints in Markov games, where \(g^j = g^{i,j}\) and \(c^j = c^{i,j}\) for all \(i \in \mathcal{N}\) and all \(j \in [J]\). Observe that in this setting the terms \(i\)-feasible and feasible defined in Equation 3 are equivalent, and the set of feasible policies \(\mathcal{C}_\pi\) defined in Equation 4 reduces to: \[\begin{align} \mathcal{C}_{\pi} := \{\pi \in \Pi_M \mid V^{g^j}(\pi) \geq c^j, \, \forall j \in [J]\}.\label{eq:cpi} \end{align}\tag{5}\] Now, we present a relaxation of Assumption 1.
Assumption 2. For any player \(i \in \mathcal{N}\) and any policy \(\pi\in\Pi_M\) on the boundary of \(\,\mathcal{C}_\pi\), i.e., \(\pi \in \{\pi \in \Pi_M \mid \exists j \in [J]\,\,s.t.\,\, V^{g^j}(\pi) = c^j\}\), there exists an \(\alpha\in\Delta(K^i)\) with positive weights, namely \(\alpha_k>0\) for all \(k\in[K^i]\), such that: \[\sum_{k=1}^{K^i}\alpha_kV^{g^j}(\phi^i(k)\circ\pi)\ge c^j,\,\forall j\in[J],\] where \(\phi^i(k)\in\Phi^i_{M,det}\).
The above assumption applies only to policies on the boundary of the feasible set. For such policies, it requires the existence of a strictly positive convex combination of deterministic modifications \(\phi^i(k)\in\Phi_{M,\mathrm{det}}^i\) such that the resulting modified policy remains feasible. In the special case of normal-form games, this condition can be interpreted as requiring that feasibility can be preserved by fully randomized modifications, namely \(\phi^i(\hat{a}^i \mid a^i) > 0\) for all \(\hat{a}^i, a^i \in \mathcal{A}\). In particular, Assumption 2 imposes a regularity condition on the boundary of the feasible set. Moreover, it is strictly weaker than Assumption 1: the latter implies the former, but the converse does not hold (see Appendix 9).
We are now ready to state our main theorem on the existence of constrained correlated equilibria under our relaxed assumption.
Theorem 2. Consider a Markov game with common coupling constraints. Let Assumption 2 hold. Then, there exists a policy \(\pi\in\Pi_M\) which is a constrained correlated equilibrium.
We begin by highlighting the main technical ingredients of our approach and then provide the full proof in Section 5.2.
4.1 Proof elements and connections to past work↩︎
Our goal is to prove equilibrium existence by applying Kakutani’s fixed-point theorem [43] (see Appendix 8) to a suitable best-response correspondence. To do so, we need to address two main challenges.
The first challenge is to choose an appropriate domain for the fixed-point map. The feasible policy set \(\mathcal{C}_\pi\) is generally nonconvex [44], and therefore cannot be used directly. We instead work with the feasible occupancy-measure set \[\begin{align} \mathcal{C}_d = \left\{ d^\pi \in \bigcup_{t\in[H]}\Delta(\mathcal{S}\times\mathcal{A}) \mid \pi\in\mathcal{C}_\pi \right\}, \label{eq:c95d} \end{align}\tag{6}\] which is convex and compact [21]. This gives us a suitable domain on which to define the fixed-point correspondence.
The second challenge is to characterize each player’s best feasible deviation. In constrained Nash equilibria with playerwise coupling constraints [21], deviations are taken over the full policy space. In our setting, however, the common coupling constraints impose a shared feasible region across all players. Hence, feasible deviations can be characterized relative to the common set \(\mathcal{C}_d\). The remaining task is to identify each player’s optimal feasible deviation within this set.
A direct optimization over stochastic modifications is difficult, because the space of such modifications is infinite-dimensional and nonconvex. We overcome this difficulty using Theorem 1, which shows that optimizing over all stochastic modifications is equivalent to optimizing over convex combinations of finitely many deterministic modifications. Starting from an occupancy measure \(d\in\mathcal{C}_d\), we first map it to the set of policies that induce it through the correspondence \(\Gamma:\mathcal{C}_d\to 2^{\mathcal{C}_\pi}\), defined in Equation 7 ; that is, each \(\pi\in\Gamma(d)\) satisfies \(d^\pi=d\). For each such policy \(\pi\) and each player \(i\), we then compute player \(i\)’s best feasible modification by solving the linear program 8 , as justified by Theorem 1. The optimal solutions induce a set of feasible occupancy measures \(A_i(\pi)\subseteq\mathcal{C}_d\), defined in Equation 9 , whose upper semi-compact 3 is established in Lemma 2.
We aggregate these best feasible modifications across all players to define the best-response correspondence \[f:\mathcal{C}_d\to 2^{\mathcal{C}_d}.\] This correspondence maps each feasible occupancy measure to the occupancy measures induced by players’ best feasible modifications. The preceding regularity properties ensure that \(f\) satisfies the conditions of Kakutani’s fixed-point theorem. Therefore, there exists a fixed point \(d^*\in f(d^*)\), and any policy \(\pi^*\in\Gamma(d^*)\) is a constrained correlated equilibrium. Figure 2 illustrates the main idea of the proof sketch.
While Appendix 9 shows that Assumption 2 relaxes Assumption 1, both assumptions remain difficult to verify numerically for a given Markov game.
5 Proof of Theorem 2↩︎
In this section, we establish key properties of the mappings used to construct the fixed-point correspondence, ensuring that Kakutani’s conditions are satisfied. We then prove Theorem 2.
5.1 Preliminary results↩︎
For a given state-action occupancy measure \(d \in \mathcal{C}_d\), we define the corresponding feasible Markovian policy \(\pi\) via the point-to-set mapping \(\Gamma:\mathcal{C}_d\rightarrow 2^{\mathcal{C}_\pi}\) as follows: for every timestep \(t\in[H]\), state \(s \in \mathcal{S}\) and action \(a\in\mathcal{A}\), \[\begin{align} \pi_t(a| s) = \begin{cases} \frac{d_t(s, a)}{\sum_a d_t(s, a)}, & \text{if } \sum_a d_t(s, a) \neq 0, \\ \text{arbitrary distribution}, & \text{otherwise.} \end{cases}\label{eq95defgamma} \end{align}\tag{7}\]
Given a player \(i\) and a feasible policy \(\pi\in\mathcal{C}_\pi\), consider the problem of finding the best feasible modification for player \(i\): \[\begin{align} \max_{\phi^i}\quad & V^{r^i}(\phi^i\circ\pi) \\ \text{s.t.}\quad & V^{g^j}(\phi^i\circ\pi)\ge c^j,\, \forall j\in[J],\\ & \phi^i \in \Phi^i_M . \end{align}\] By the proof of Theorem 1, this problem can be interpreted as finding an optimal policy in an auxiliary constrained MDP with an augmented state space. However, directly solving constrained MDPs over policy space is generally non-convex [44]. To obtain a tractable formulation, we invoke Theorem 1, which shows that optimizing over feasible stochastic modifications \(\phi^i\in\Phi_M^i\) is equivalent to optimizing over feasible mixtures of deterministic modifications. Let \(\Phi^i_{M,\mathrm{det}}=\{\phi^i(k)\}_{k=1}^{K^i}\), where each \(\phi^i(k)\) is a deterministic modification. Then the best feasible modification can be obtained by solving the following linear program: \[\begin{align} \max_{\alpha}\;&\sum_{k=1}^{K^i}\alpha_k V^{r^i}(\phi^i(k)\circ\pi) \\ \text{s.t. } &\sum_{k=1}^{K^i}\alpha_k V^{g^j}(\phi^i(k)\circ\pi)\ge c^j,\,\forall j\in[J], \label{lp}\\ &\alpha\in \Delta(K^i). \end{align}\tag{8}\] Let \(\Omega^i(\pi):\mathcal{C}_\pi \to 2^{\Delta(K^i)}\) be the set of optimal solutions of 8 , and let \(\Psi^i(\pi):\mathcal{C}_\pi \to \mathbb{R}\) denote the optimal value of 8 . These mappings \(\Omega^i(\pi)\) and \(\Psi^i(\pi)\) satisfy the following properties:
Lemma 1. Let Assumption 2 hold. Then, the following holds: for any \(i \in \mathcal{N}\),
The optimal set \(\Omega^i(\pi)\) is convex and upper semi-compact in \(\pi\in\mathcal{C}_\pi\).
The optimal value \(\Psi^i(\pi)\) is continuous in \(\pi\in\mathcal{C}_\pi\).
We provide a proof in Appendix 8.2. The two properties demonstrate compactness and (upper semi-)continuity of the mappings \(\Omega^i(\pi)\) and \(\Psi^i(\pi)\). To connect the solution set \(\Omega^i(\pi)\) of 8 to the set of feasible state-action occupnacy measures \(\mathcal{C}_d\), we define a linear transformation which maps any \(\pi\in\mathcal{C}_\pi\) to \(d\in\mathcal{C}_d\): \[\begin{align} A^i(\pi) \!:= \!\!\bigcup_{\alpha \in \Omega^i(\pi)} \!\!\bigg\{\sum_{k\in[K^i]} \alpha_k d_t^{\phi^i(k)\circ\pi}(s,a)\bigg\}_{t\in[H],\,(s,a)\in\mathcal{S}\times\mathcal{A}}.\label{eq:def95A95i} \end{align}\tag{9}\]
The following lemma, for which we provide a proof in Appendix 8.3, shows that \(A^i(\pi)\) defines a valid mapping to \(\mathcal{C}_d\) and is upper semi-compact.
Lemma 2. For any player \(i\in\mathcal{N}\) and policy \(\pi\in\mathcal{C}_\pi\), the point-to-set mapping \(A^i(\pi):\mathcal{C}_\pi\rightarrow 2^{\mathcal{C}_d}\) is upper semi-compact.
5.2 Proof↩︎
Proof. Consider the point-to-set map \(f:\mathcal{C}_d \to 2^{\mathcal{C}_d}\) given by: \[\begin{align} f(d):= \bigcup_{i\in\mathcal{N}} f^i(\Gamma(d)), \label{eq:def95f} \end{align}\tag{10}\] where for each player \(f^i:\mathcal{C}_\pi \to 2^{\mathcal{C}_d}\) is a point-to-set map defined as: \[\begin{align} f^i(\pi):=\big( 1 - \frac{\Psi^i(\pi)- V^{{r}^{i}}(\pi)}{2H}\big) d^\pi+ \frac{\Psi^i(\pi)- V^{{r}^{i}}(\pi)}{2H} A^i(\pi). \end{align}\]
First, we will show that for all \(i\in\mathcal{N}\) the point-to-set map \(f^i\) is a valid mapping into \(2^{\mathcal{C}_d}\) and then that \(f^i\) is upper semi-compact.
\(f^i\) is a valid mapping: By assumption \(\pi\in\mathcal{C}_\pi\) and thus by definition \(d^\pi\in\mathcal{C}_d\). By Lemma 2, it holds that \(A^i(\pi)\subseteq\mathcal{C}_d\). Furthermore, it follows that for all \(\pi\in\mathcal{C}_{\pi}\): \[\begin{align} &\Psi^i(\pi)- V^{{r}^{i}}(\pi) =\max_{\alpha\in\Delta(K^i) \text{ is feasible}} \sum_{k=1}^{K^i} \alpha_k V^{r^i}(\phi^i(k)\circ\pi)-V^{{r}^{i}}(\pi)\ge 0.
\end{align}\] The above term can be upper-bounded by: \(\Psi^i(\pi)- V^{{r}^{i}}(\pi)\le \Psi^i(\pi) \le H\). Hence, \[\begin{align} 1\ge 1 - \frac{\Psi^i(\pi)- V^{{r}^{i}}(\pi)}{2H} \ge
1-\frac{H}{2H}=\frac{1}{2}.
\end{align}\] By convexity of \(\mathcal{C}_d\) [21], the convex combination of \(d^\pi\) and \(d^i\in A^i(\pi)\) belongs to \(\mathcal{C}_d\). Therefore, \(f^i\) is a valid mapping into \(2^{\mathcal{C}_d}\).
\(f^i\) is upper semi-compact: By Lemmas 1 and 2, \(\Psi^i(\pi)\) is a continuous real-valued function and \(A^i(\pi)\) is upper semi-compact in \(\pi\in\mathcal{C}_\pi\). Furthermore, \(V^{{r}^{i}}(\pi)\) and \(d^\pi\) are continuous functions since both can be represented as polynomial functions of \(\pi\). Since for every \(\pi\in\mathcal{C}_\pi\), \(f^i(\pi)\) is a compact set it follows that \(f^i\) is upper semi-compact
for all \(\pi\in\mathcal{C}_\pi\).
Next, we will show that the point-to-set map \(f:\mathcal{C}_d \to 2^{\mathcal{C}_d}\) is a valid mapping into \(2^{\mathcal{C}_d}\) and that \(f\) is
upper semi-compact.
\(f\) is a valid mapping and upper semi-compact: The mapping \(f\) is well defined as a correspondence from \(\mathcal{C}_d\) into \(2^{\mathcal{C}_d}\), since \(\Gamma\) maps \(\mathcal{C}_d\) into \(2^{\mathcal{C}_\pi}\) and each \(f^i\) maps \(\mathcal{C}_\pi\) into \(2^{\mathcal{C}_d}\).
For any \(d\in\mathcal{C}_d\), the set \(\Gamma(d)\) is compact: by construction, it is a union over \(t\in[H]\) and \(s\in\mathcal{S}\) whose components are either singletons or simplices \(\Delta(\mathcal{A})\), all of which are compact. Moreover, upper semi-continuity of \(\Gamma\) in \(d\) follows from [21]. Hence, \(\Gamma\) is upper semi-compact.
Since the composition of two upper semi-compact correspondences is again upper semi-compact [40], it follows that \(f^i\!\circ\Gamma\) is upper semi-compact for every \(i\in\mathcal{N}\). Finally, because \(f(d)=\bigcup_{i\in\mathcal{N}} f^i(\Gamma(d))\) and the finite union of upper semi-compact correspondences is upper semi-compact [40], we conclude that \(f\) is upper semi-compact on \(\mathcal{C}_d\).
Finally, we will show that for mapping \(f\), a fixed point \(d^*\in f(d^*)\) exists and that any corresponding policy \(\pi^*\in\Gamma(d^*)\) is a
constrained correlated equilibrium.
Existence of a constrained correlated equilibrium: Since \(\mathcal{C}_d\) is a compact and convex set [21], and \(f(d)\) is upper semi-compact, Kakutani’s fixed point theorem guarantees the existence of a fixed point \(d^*\) of \(f\) such that \[\begin{align}
d^*\in f(d^*). \label{eq95fix}
\end{align}\tag{11}\] Consider any policy \(\pi\in\Gamma(d^*)\). By Equation 11 , for any \(i\in\mathcal{N}\), we have that:
\[\begin{align} d^\pi\in\big( 1 - \frac{\Psi^i(\pi)- V^{{r}^{i}} (\pi)}{2H}\big) d^\pi + \frac{\Psi^i(\pi)- V^{{r}^{i}}(\pi)}{2H} A^i(\pi).\label{eq95fix95d}
\end{align}\tag{12}\]
To prove \(\pi\) is a constrained correlated equilibrium, by Theorem 1, we have to show that for any player \(i\) and any feasible \(\alpha\), the following holds: \[\begin{align} &V^{r^i}(\pi)\geq\max_{\text{\alpha\in \Delta(K^i) is i-feasible }} \sum_{k=1}^{K^i} \alpha_k V^{r^i}(\phi^i(k)\circ\pi), \end{align}\] This is equivalent to showing that \(\Psi^i(\pi)\le V^{{r}^{i}}(\pi)\), since \(\Psi^i(\pi)\) is the optimal solution returned by solving 8 . We prove this by contradiction. Assume that there exists a player \(i\in\mathcal{N}\) and a feasible \(\alpha \in\Delta(K^i)\) such that: \[\begin{align} \sum_{k=1}^{K^i} \alpha_k V^{r^i}(\phi^i(k)\circ\pi)> V^{r^i}(\pi). \end{align}\] Combining the above inequality with Equation 12 , we have \(d^\pi\in A^i(\pi)\) and by construction of \(A^i(\pi)\) it follows that: \(V^{r^i}(\pi) = \Psi^i(\pi)\), which is a contradiction. We conclude that any policy \(\pi\in\Gamma(d^*)\) is a constrained correlated equilibrium. ◻
Discussion Theorem 2 establishes the existence of constrained correlated equilibria in Markov games with common coupling constraints under a weakened Slater-type condition. The key insight is that, under common coupling constraints, feasibility becomes a shared property across players, which allows us to replace the strong Slater requirement with a boundary regularity condition. Importantly, this relaxation substantially broadens the class of games for which equilibrium existence can be guaranteed. It applies, for instance, to settings such as collision-avoidance games, where feasibility may naturally be required only near the constraint boundary, rather than uniformly over the entire policy space.
6 Conclusion and future work↩︎
In this paper, we studied constrained correlated equilibria in finite-horizon Markov games with coupling constraints. To this end, we first showed that constrained correlated equilibria can be characterized by convex combinations of Markovian deterministic modifications (Theorem 1). Leveraging this characterization, we prove the existence of a constrained correlated equilibrium under common coupling constraints using a weakened Slater-type assumption.
These considerations suggest several directions for future work. First, the existence result may be extended to infinite-horizon Markov games, which would require generalizing Theorem 1 to that setting. Second, it would be of interest to consider Markov games with countable state spaces and action sets, which calls for extending the upper semi-continuity arguments (Lemmas 1 and 2). Another promising direction is to investigate whether common coupling constraints can avoid the computational intractability known for constrained correlated equilibria with playerwise coupling constraints [45].
7 Proof for Theorem 1↩︎
Proof. For any player \(i \in \mathcal{N}\) and any policy \(\pi\in\Pi_M\), we construct a finite-horizon MDP defined by the tuple: \[\begin{align} \label{eq:MDP2} \left\{\bar{\mathcal{S}}\cup\{b\}, \mathcal{A}^i, H, \bar{P}^\pi, \bar{\rho}\right\}.\end{align}\tag{13}\] The state space is given by \(\bar{\mathcal{S}}\cup\{b\}\), where \(\bar{\mathcal{S}}:= \mathcal{S} \times \mathcal{A}^i\) and \(b\) is an auxiliary state. Each element of \(\bar{\mathcal{S}}\) takes the form \(\bar s=(s,a^i)\). The time horizon \(H\) is the same as in the original Markov game. The action space \(\mathcal{A}^i\) corresponds to player \(i\)’s action set in the original Markov game. The transition kernel is denoted by \(\bar{P}^\pi := \{\bar{P}_t^\pi\}_{t \in [H-1]}\), where each \(\bar{P}_t^\pi : \bar{\mathcal{S}} \times \mathcal{A}^i \to \Delta(\bar{\mathcal{S}} \cup \{b\})\) is defined as follows: \[\begin{align} \bar{P}_t^\pi \left( (s_{t+1},a_{t+1}^i) \mid (s_t,a_t^i),\hat{a}_t^i \right) =& \frac{1}{|\mathcal{A}^i|} \sum_{a_t^{-i}}P_t(s_{t+1} \mid s_t, (\hat{a}_t^i,a_t^{-i})) \pi_t((a_t^i,a_t^{-i}) \mid s_t),\\ \bar{P}_t^\pi \left( b \mid (s_t,a_t^i),\hat{a}_t^i \right) = &1 - \sum_{a_t^{-i}}\pi_t((a_t^i,a_t^{-i}) \mid s_t).\label{eq95deftransition} \end{align}\tag{14}\] We define \(b\) to be an absorbing state, such that the transition kernel satisfies \(\bar{P}_t^\pi \left( b \mid b \right) = 1\). By Lemma 3 in Appendix 7.1, we verify that \(\bar P_t^\pi\) defines a valid probability distribution over \(\Delta(\bar{\mathcal{S}} \cup \{b\})\) for all \(t \in [H-1]\).
Moreover, we define the initial distribution for all \(\bar s_1\in\bar{\mathcal{S}}\cup\{b\}\) as: \[\begin{align} \bar{\rho}(\bar s_1)=\begin{cases} \frac{\rho(s_1)}{|\mathcal{A}^i|}, \,&\text{if }\bar s_1=(s_1,a_1^i)\in\bar{\mathcal{S}},\\ 0, \,&\text{otherwise}. \end{cases} \end{align}\] It is straightforward to verify that \(\bar{\rho} \in \Delta(\bar{\mathcal{S}}\cup\{b\})\). Therefore, the constructed 13 is well-posed. We further note that any Markovian stochastic modification \(\phi^i\in\Phi^i_{M}\), constitutes a valid policy in the 13 . By Lemma 4 in Appendix 7.1, for all \((s_h, (\hat{a}_h^i,a_h^{-i})) \in \mathcal{S} \times \mathcal{A}\) and \(h\in[H]\) it holds that: \[\begin{align} d_h^{\phi^i\circ \pi}&({s}_h, (\hat{a}_h^i, a_h^{-i})) =|\mathcal{A}^i|^h\sum_{a_h^i}\bar d_h^{\phi^i}((s_h,a_h^i),\hat{a}_h^i) \pi_h((a_h^i,a_h^{-i})|s_h), \label{eq95equidistribution} \end{align}\tag{15}\] where \(\bar d_h^{\phi^i}(\cdot)\) denotes the state-action occupancy measure at timestep \(h\) of the 13 .
Meanwhile, we leverage that Markovian stochastic policies and convex combinations of Markovian deterministic policies are equivalent in terms of the state-action occupancy measures they induce in the 13 (see [41]). Namely, there exists a vector \(\alpha\in\Delta(K^i)\) such that: \[\begin{align} \label{eq:connection95stochastic95deterministic} \bar d_t^{\phi^i}((s_t, a_t^i), \hat{a}_t^i) = \sum_{k=1}^{K^i} \alpha_k \, \bar d_t^{ \phi^i(k)}(( s_t, a_t^i), \hat{a}_t^i), \end{align}\tag{16}\] for all \((s_t, a_t^i) \in \bar{\mathcal{S}}\), all \(\hat{a}_t^i \in \mathcal{A}^i\), and all \(t\in[H]\), where each \(\phi^i(k) \in \Phi^i_{M,det}\) is a Markovian deterministic policy of the 13 . Note that since Equation 16 holds with equality, the reverse statement is also true. Namely, given a vector \(\alpha\in\Delta(K^i)\), there exists a \(\phi^i\in\Phi_{M}^i\) such that Equation 16 holds.
Combining Equations 16 and 15 , we conclude that Markovian stochastic policies and convex combinations of Markovian deterministic policies are equivalent in terms of the state-action occupancy measures they induce in the original Markov game. Since the reward \(V^{r^i}\) and the constraint functions \(V^{g^{i,j}}\) are linear functions of the state-action occupancy measure as seen in Equation 1 , this implies the equivalence in Theorem 1. ◻
7.1 Supporting results for Theorem 1↩︎
Lemma 3. For \(\bar P^\pi:=\{\bar P^\pi_t\}_{t\in[H-1]}\) defined in 13 , \(\bar P^\pi_t\) is a valid probability distribution in \(\Delta(\bar{\mathcal{S}}\cup \{b\})\) for all \(t\in[H-1]\).
Proof. For any given timestep \(t\in[H-1]\), state \(\bar{s}_t=(s_t,a_t^i)\in\bar{S}_t\), and action \(\hat{a}_t^i\in\mathcal{A}_i\), it holds that: \[\begin{align} &\sum_{\bar s_{t+1}\in\bar{\mathcal{S}}_{t+1}\cup\{b\}}\bar{P}_t^\pi(\bar{s}_{t+1}|\left(s_t,a_t^i\right),\hat{a}_t^i)\\ =&\sum_{s_{t+1}}\sum_{a_{t+1}^i}\bar{P}_t^\pi ( (s_{t+1},a_{t+1}^i) \!\mid \!(s_t,a_t^i),\hat{a}_t^i )\!+\! \bar{P}_t^\pi( b \!\mid\! (s_t,a_t^i),\hat{a}_t^i )\\ =& \frac{1}{|\mathcal{A}^i|} \sum_{s_{t+1}}\sum_{a_{t+1}^i}\sum_{a_t^{-i}}P_t(s_{t+1} \mid s_t, (\hat{a}_t^i,a_t^{-i})) \pi_t((a_t^i,a_t^{-i}) \mid s_t)+1 - \sum_{a_t^{-i}}\pi_t((a_t^i,a_t^{-i}) \mid s_t)\\ =&1. \end{align}\] Furthermore, for the auxiliary state \(b\) and timestep \(t\in[H-1]\), it holds that: \[\begin{align} &\sum_{\bar s_{t+1}\in\bar{\mathcal{S}}_{t+1}\cup\{b\}}\bar{P}_t^\pi\left(\bar{s}\mid b\right)=\bar P_t^\pi(b \mid b) = 1. \end{align}\] We conclude that \(\bar{P}_t^\pi\) is a valid probability distribution in \(\Delta(\bar{\mathcal{S}}_{t+1}\cup\{b\})\). ◻
Lemma 4. For any player \(i\in\mathcal{N}\), Markovian policy \(\pi\in\Pi_M\), and Markovian stochastic modification \(\phi^i \in\Phi_{M}^i\), the state-action occupancy measure of the modified policy \(\phi^i\circ\pi\) equals: \[\begin{align} &d_h^{\phi^i\circ \pi}({s}_h, (\hat{a}_h^i, a_h^{-i})) = |\mathcal{A}^i|^h\sum_{a_h^i}\bar d_h^{\phi^i}((s_h,a_h^i),\hat{a}_h^i) \pi_h((a_h^i,a_h^{-i})|s_h), \label{eq95occ95ori} \end{align}\qquad{(2)}\] for all \((s_h, (\hat{a}_h^i,a_h^{-i})) \in \mathcal{S} \times \mathcal{A}\) and \(h\in[H]\), where \(\bar d_h^{\phi^i}(\cdot)\) denotes the state-action occupancy measure at timestep \(h\) of 13 .
Proof. We prove the above lemma by induction.
Base case: For \(h=1\), we have that for any \((s_1,(\hat{a}_1^i,a_1^{-i}))\in \mathcal{S}\times\mathcal{A}\) the following holds: \[\begin{align}
&|\mathcal{A}^i| \sum_{a_1^{i}} \bar{d}_1^{\phi^i}((s_1,a_1^i),\hat{a}_1^i)\pi_1((a_1^i,a_1^{-i}) \mid s_1)\\ \overset{(i)}{=}& |\mathcal{A}^i| \sum_{a_1^{i}}\bar{\rho}(s_1,a_1^i) \phi^i_1(\hat{a}^i_1|s_1,a_1^i)\pi_1((a_1^i,a_1^{-i}) \mid s_1)\\
\overset{(ii)}{=}&\sum_{a_1^{i}} \rho(s_1)\phi_1^i(\hat{a}^i_1|s_1,a_1^i )\pi_1((a_1^i,a_1^{-i}) \mid s_1)\\ =& d_1^{\phi^i\circ \pi}({s}_1, (a_1^{-i},\hat{a}_1^i)),
\end{align}\] where in step \((i)\) we express \(\bar{d}_1^{\phi^i}\) by the dynamics of 13 . In step \((ii)\) we plug in
the definition of \(\bar{\rho}\).
Induction step: Assume that Equation ?? holds for all \((s_h, (a_h^{-i},\hat{a}_h^i)) \in \mathcal{S} \times \mathcal{A}\) and all \(h \in [t-1]\), then we show that Equation ?? also
holds for \(t\). We can rewrite \(\bar{d}_t^{\phi^i}\) as: \[\begin{align} &\bar{d}_t^{\phi^i}((s_t,a_t^i),\hat{a}_t^i)\\
\overset{(i)}{=}&\phi^i_t(\hat{a}_t^i|s_t,a_t^i)\sum_{ \bar s_{t-1}}\sum_{\bar a_{t-1}^i}\sum_{\hat{a}_{t-1}^i}\bar{d}_{t-1}^{\phi^i}((\bar s_{t-1},\bar a_{t-1}^i),\hat{a}_{t-1}^i)\bar{P}_{t-1}^\pi(s_t,a_t^i|(\bar s_{t-1},\bar
a_{t-1}^i),\hat{a}_{t-1}^i)\\ \overset{(ii)}{=}&|\mathcal{A}^i|^{-1}\phi^i_t(\hat{a}_t^i|s_t,a_t^i)\sum_{ \bar s_{t-1}}\sum_{\bar a_{t-1}^i}\sum_{\hat{a}_{t-1}^i}\sum_{\bar a_{t-1}^{-i}}\bar{d}_{t-1}^{\phi^i}((\bar s_{t-1},\bar
a_{t-1}^i),\hat{a}_{t-1}^i)\\ &\times \pi_{t-1}((\bar a_{t-1}^i,\bar a_{t-1}^{-i}) \mid \bar s_{t-1}) P_{t-1}(s_t|\bar s_{t-1},(\hat{a}_{t-1}^i,\bar a_{t-1}^{-i}))\\ \overset{(iii)}{=}&|\mathcal{A}^i|^{-t}\phi^i_t(\hat{a}_t^i|s_t,a_t^i)\sum_{ \bar
s_{t-1}}\sum_{\hat{a}_{t-1}^i}\sum_{\bar a_{t-1}^{-i}}d_{t-1}^{\bar\phi^i\circ\pi}(\bar s_{t-1},(\hat{a}_{t-1}^i,\bar a_{t-1}^{-i})) \\ & \times P_{t-1}(s_t|\bar s_{t-1},(\hat{a}_{t-1}^i,\bar a_{t-1}^{-i})).
\end{align}\] In step \((i)\), we express the state-action distribution using the transition dynamics, in step \((ii)\), we apply the definition of \(\bar{P}^\pi_{t-1}\), and in step \((iii)\), we apply Equation ?? which holds by induction for timestep \(t-1\). Using the above equation, we obtain: \[\begin{align} &|\mathcal{A}^i|^t\sum_{a_t^i}\bar{d}_t^{\phi^i}((s_t,a_t^i),\hat{a}_t^i) \pi_t((a_t^i,a_t^{-i})|s_t)\\ =&\sum_{a_t^i}\phi^i_t(\hat{a}_t^i|s_t,a_t^i)\sum_{ \bar s_{t-1}}\sum_{\hat{a}_{t-1}^i}\sum_{\bar
a_{t-1}^{-i}}d_{t-1}^{\bar\phi^i\circ\pi}(\bar s_{t-1},(\hat{a}_{t-1}^i,\bar a_{t-1}^{-i})) P_{t-1}(s_t|\bar s_{t-1},(\hat{a}_{t-1}^i,\bar a_{t-1}^{-i}))\\ & \times \pi_t((a_t^i,a_t^{-i})|s_t)\\ =&d_t^{\phi^i\circ\pi}(s_t,(\hat{a}_t^i,a_t^{-i})),
\end{align}\] where the last step follows by the definition of state-action occupancy measure. ◻
8 Supporting results for Theorem 2↩︎
For completeness, we first state Kakutani’s fixed point theorem. Then, we provide a proof of Lemma 1 in Section 8.2, and a proof of Lemma 2 in Section 8.3.
8.1 Kakutani’s fixed point theorem↩︎
Theorem 3 (Kakutani’s Fixed Point [43]). Let \(X\) be a non-empty, compact, and convex subset of a finite-dimensional Euclidean space. Let \(F: X \to 2^X\) be an upper semi-continuous set-valued function. Then, there exists at least one fixed point \(x^*\) such that \(x^* \in F(x^*)\).
8.2 Proof of Lemma 1↩︎
In Lemma 5, we begin by establishing the sensitivity analysis of the linear program 8 , namely: the upper semi-continuity of its optimal solution set and the continuity of its optimal value with respect to any variability of policy \(\pi\) in 8 . These results will then be used to prove Lemma 1.
8.2.0.1 Sensitivity analysis of \(LP^i(\pi)\)
We recall the linear program 8 : find \(\alpha\in \Delta({K^i})\) with \(\Phi^i_{M,det}=\{\phi^i(k)\}_{k=1}^{K^i}\) such that: \[\begin{align} \max_{\alpha\in\mathbb{R}^{K^i}}\;&\sum_{k=1}^{K^i}\alpha_k V^{r^i}(\phi^i(k)\circ\pi) \nonumber\\ \text{s.t. } &\sum_{k=1}^{K^i}\alpha_k V^{g^j}(\phi^i(k)\circ\pi)\ge c^j,\, \forall j\in[J], \tag{17}\\ &\sum_{k=1}^{K^i}\alpha_k=1,\tag{18}\\ &\alpha_k\ge 0,\,\forall k\in [K^i].\tag{19} \end{align}\] For a more compact notation, we recast the above LP such that \(\xi(\alpha)\leq 0\) captures the inequality constraints 17 and 19 and \(\psi(\alpha)=0\) captures the equality constraints 18 . Denote by \[H(\xi,\psi)=\{\alpha\in\mathbb{R}^{K^i}\;\lvert\;\xi(\alpha)\leq 0\, \text{ and }\, \psi(\alpha)=0\}\] the set of feasible solutions and by \[\begin{align} M(\pi\mid H(\xi,\psi)) =&\bigg\{\alpha\in H(\xi,\psi) \mid \alpha\in\arg\max_{\alpha'\in H(\xi,\psi)}\sum_{k=1}^{K^i}\alpha_k' V^{r^i}(\phi^i(k)\circ\pi)\bigg\}\\ \subseteq & H(\xi,\psi) \end{align}\] the set of maximizers of the above 8 .
Next, consider a sequence of policies \(\{\pi_n\}\) and let \(LP_n^i\), \(\xi_n\), and \(\psi_n\) be defined as above, where \(\pi\) is replaced by \(\pi_n\). We make the following assumption which ensures that \(LP^i\) and \(LP_n^i\) are feasible and therefore the problem is well-posed.
Assumption 3. We assume that both \(H(\xi,\psi)\) and \(H(\xi_n,\psi_n)\) are non-empty.
We furthermore consider the following assumption:
Assumption 4. Assume the following holds:
For all \(j \in [J]\), if there exists a strictly infeasible \(\alpha \in \Delta(K^i)\), i.e., \[\sum_{k=1}^{K^i} \alpha_k V^{g^j}(\phi^i(k) \circ \pi) < c^j,\] then it holds that there does not exist any \(\beta \in \mathbb{R}\) such that: \[\{ V^{g^j}(\phi^i(k) \circ \pi) \}_{k=1}^{K^i} = \beta \mathbf{1}_{K^i}.\]
There exists a feasible \(\alpha\in\Delta(K^i)\) with positive weights such that: \[\sum_{k=1}^{K^i}\alpha_kV^{g^j}(\phi^i(k)\circ\pi)\ge c^j,\,\forall j\in[J],\] where \(\alpha_k>0\) for all \(k\in[K^i]\).
Lemma 5. Let Assumptions 3 and 4 hold. Assume that \(\pi_n \to \pi\) pointwise as \(n \to \infty\), then the following is satisfied:4
\(\lim\inf_{n\rightarrow\infty} M(\pi_n\mid H(\xi_n,\psi_n))\subseteq M(\pi\mid H(\xi,\psi))\).
\(\lim\sup_{n\rightarrow\infty} M(\pi_n\mid H(\xi_n,\psi_n))\subseteq M(\pi\mid H(\xi,\psi))\).
The optimal values of \(LP_n^i\) converge to the optimal values of \(LP^i\).
The key step in the proof is to verify a rank condition for the active constraints, which is ensured by Assumptions 3 and 4. This prevents degeneracy and allows us to apply standard sensitivity results for linear programs. We now provide the full proof below.
Proof.
Denote by \(I=\{m\in[J+K^i])\;\lvert\;\xi_m(\alpha)=0,\, \forall \alpha\in H(\xi,\psi)\}\) the set of those inequality constraints 17 and 19 that are actually equality constraints for all feasible points. Note that this set depends only on the limiting \(LP^i\). In the following, we will show that: \[\begin{align} \label{eq:rank95condition} {\lim}\sup_{n\rightarrow\infty} rank(\xi_{n,I},\psi_n)\leq rank(\xi_I,\psi). \end{align}\tag{20}\] Suppose for now that Inequality 20 holds, then, by [46] it follows that either \(\lim_{n\rightarrow\infty} H(\xi_n,\psi_n)=H(\xi,\psi)\) or \(H(\xi_n,\psi_n)\) is empty infinitely often. By Assumption 3 the set \(H(\xi_n,\psi_n)\) is non-empty for all \(n\) and therefore, by [46] it follows that \(\lim_{n\rightarrow\infty} H(\xi_n,\psi_n)=H(\xi,\psi)\). Thus, the conditions of [46] are satisfied and applying it we obtain that \(\lim\inf_{n\rightarrow\infty} M(\pi_n\mid H(\xi_n,\psi_n))\subseteq M(\pi\mid H(\xi,\psi))\). This concludes the proof of the first point.
We are now left with showing that Inequality 20 indeed holds.
Consider \(rank(\psi)\) and \(rank(\psi_n)\): Since \(\psi_n=\psi =\sum_{k=1}^{K^i}\alpha_k-1\), therefore: \[rank(\psi)=rank(\psi_n)=1.\]
Consider \(rank(\xi_I)\) and \(rank(\xi_{n,I})\): Consider \(\xi:\mathbb{R}^{K^i}\rightarrow\mathbb{R}^{J + K^i}\) with: \[\begin{align} & \xi_j(\alpha)=c^j - \sum_{k=1}^{K^i}\alpha_k V^{g^j}(\phi^i(k)\circ\pi)\leq 0,\,\forall j\in[J],\\ & \xi_k(\alpha)= -\alpha_k\leq 0, \, \forall k\in\{J+1,\dots,J+K^i\}. \end{align}\] Without loss of generality, we assume that \(rank(\{\xi_j\}_{j\in[J]})=J\) since otherwise the redundant constraints can be removed. Note that removing redundant constraints from 8 does not affect \(LP^i_n\) since \(I=\{m\in[J+K^i]\;\lvert\;\xi_m(\alpha)=0,\, \forall \alpha\in H(\xi,\psi)\}\) depends only on the limiting 8 . Next, we divide the satisfaction of each constraint \(\xi_j\) for \(j \in [J]\) into three distinct cases:
For all \(\alpha \in \Delta(K^i)\), we have \(\xi_j(\alpha) = 0\).
For all \(\alpha\in\Delta(K^i)\), we have \(\xi_j(\alpha)\geq 0\). Furthermore, there exists a feasible \(\alpha\in\Delta(K^i)\) and a strictly infeasible solution \(\alpha'\in\Delta(K^i)\), i.e., \(\xi_j(\alpha)=0\) and \(\xi_j(\alpha')>0\), respectively.
There exists a strictly feasible solution \(\alpha \in \Delta(K^i)\) such that \(\xi_j(\alpha) < 0\), hence \(j \notin I\).
In case (a), the constraint can be removed from the linear program 8 as it does not affect the feasible set. Without loss of generality, assume that there are \(J_1 \in [J]\) constraints \(\{ \xi_j \}\) for \(j \in [J_1]\) satisfying condition (b), and the remaining \(J - J_1\) constraints \(\{ \xi_j \}\) for \(j = J_1 + 1, \dots, J\) satisfy condition (c). Therefore, we have \([J_1]\subseteq I\).
For the additional inequality constraints \(\xi_k\), where \(k = J+1, \dots, J + K^i\), Assumption 4 guarantees the existence of a feasible \(\alpha \in \Delta(K^i)\) with positive weights, implying again that \(I = [J_1]\).
Suppose that \((\xi_I, \psi)\) has full rank, i.e., \(\mathrm{rank}(\xi_I, \psi) = J_1 + 1\). Then, the following inequality holds: \[\mathrm{rank}(\xi_{n, I}, \psi_n) \leq \mathrm{rank}(\xi_I, \psi), \quad \forall n,\] since \(\mathrm{rank}(\xi_{n, I}, \psi_n) \leq J + 1\). Hence, Inequality 20 is satisfied.
Now, we show that \(\mathrm{rank}(\xi_I, \psi) = J_1 + 1\). Any linear mapping \((\xi_I, \psi): \mathbb{R}^{K^i} \to \mathbb{R}^{J_1 + 1}\) can be represented as \(\alpha^\top M - (1, c)^\top\), where \(M \in \mathbb{R}^{(J_1+1) \times K^i}\) is defined as: \[M := \begin{bmatrix} 1 & \dots & 1 \\ V^{g^1}(\phi^i(1) \circ \pi) & \dots & V^{g^1}(\phi^i(K^i) \circ \pi) \\ \vdots & \ddots & \vdots \\ V^{g^{J_1}}(\phi^i(1) \circ \pi) & \dots & V^{g^{J_1}}(\phi^i(K^i) \circ \pi) \end{bmatrix}.\] By Assumption 4, we have \(\mathrm{rank}(M) = J_1 + 1\), which concludes the proof.
The proof follows from the first point and the same arguments as in [47].
The proof follows from the first point and the same arguments as in [47].
◻
We now use Lemma 5 to establish Lemma 1. In particular, the upper semi-continuity of the solution set implies the upper semi-continuity of \(\Omega^i(\pi)\), while the convergence of optimal values ensures continuity of the associated value mappings. It remains to verify that the assumptions of Lemma 5 hold uniformly over all \(\pi \in \mathcal{C}_\pi\), which follows directly from Assumption 2.
Proof. We will prove the properties one by one:
Convexity and compactness are standard results of linear programming [48]. Upper semi-continuity of \(\Omega^i(\pi)\) follows from Lemma 5, if we can verify that the conditions of the lemma are satisfied:
Assumption 3:
This holds since for any feasible policy \(\pi\) the identity is a feasible modification.
Assumption 4:
We need to verify that Assumption 4 holds for all \(\pi\in\mathcal{C}_\pi\) and all \(i\in\mathcal{N}\).
For any policy lying in the interior of \(\mathcal{C}_\pi\), the identity modification \(\phi^i(\mathrm{id}) \in \Phi^i_{\mathrm{M,det}}\) always ensures \(V^{g^j}(\phi^i(\mathrm{id}) \circ \pi) > c^j\). Now, pick any \(\alpha' \in \Delta(K^i)\) such that \(\alpha'_k > 0\) for all \(k \in [K^i]\), and define \(\alpha'' := (1 - \varepsilon)\mathbf{1}_{\mathrm{id}} + \varepsilon \alpha'\), where \(\mathbf{1}_{\mathrm{id}}\) is the canonical basis vector whose position of \(1\) corresponds to the identity modification. By choosing \(\varepsilon > 0\) sufficiently small, it follows that \(\sum_{k=1}^{K^i} \alpha''_k V^{g^j}(\phi^i(k) \circ \pi) > c^j\) with \(\alpha''_k > 0\) for all \(k \in[K^i]\).
For policies on the boundary of \(\mathcal{C}_\pi\), if there exists a strictly infeasible \(\alpha \in \Delta(K^i)\) such that \[\sum_{k=1}^{K^i} \alpha_k V^{g^j}(\phi^i(k) \circ \pi) < c^j.\] Then, there must exist at least one modification \(\phi^i(k)\) for which \(V^{g^j}(\phi^i(k) \circ \pi) < c^j\). On the other hand, under the identity modification \(\phi^i(\mathrm{id})\), we have \(V^{g^j}(\phi^i(\mathrm{id}) \circ \pi) = c^j\). Thus, there does not exist any \(\beta\in\mathbb{R}\) such that \(\{V^{g^j}(\phi^i(k)\circ\pi)\}_{k=1}^{K^i}=\beta\mathbf{1}_{K^i}\). Hence, together with Assumption 2, Assumption 4 is satisfied.
Continuity result of \(\Psi^i(\pi)\) in \(\pi\) follows from the third point of Lemma 5. Note that the assumptions of Lemma 5 have been verified above.
◻
8.3 Proof of Lemma 2↩︎
Proof. Consider any element \(d^i=\{d^i_t\}_{t\in[H]} \in A^i(\pi)\), defined as: \[\begin{align} d_t^i(s,a) := \sum_{k=1}^{K^i} \alpha_k d_t^{\phi^i(k)\circ\pi}(s,a), \,\forall(s,a)\in\mathcal{S}\times \mathcal{A}, \,\forall t\in[H],\label{eq:help1} \end{align}\tag{21}\] where \(\alpha\in\Omega^i(\pi)\). For all \(\pi'\in\Gamma(d^i)\), we have that: \[\begin{align} V^{g^j}(\pi') =& \sum_{t=1}^{H}\sum_{s_t,a_t}d_t^{i}(s_t,a_t) g_t^j(s_t,a_t) \\ \overset{(i)}{=}& \sum_{t=1}^{H}\sum_{s_t,a_t}\sum_{k=1}^{K^i} \alpha_k d_t^{\phi^i(k)\circ\pi}(s_t,a_t) g_t^j(s_t,a_t) \\ =& \sum_{k=1}^{K^i} \alpha_k\sum_{t=1}^{H}\sum_{s_t,a_t} d_t^{\phi^i(k)\circ\pi}(s_t,a_t) g_t^j(s_t,a_t) \\ =& \sum_{k=1}^{K^i} \alpha_k V^{g^j}(\phi^i(k)\circ\pi) \\ \overset{(ii)}{\geq}& c^j, \end{align}\] where \((i)\) uses Equation 21 and \((ii)\) holds since \(\alpha\) is a solution of \(\Omega^i(\pi)\). Thus, \(d^i \in \mathcal{C}_d\), implying that \(A^i(\pi):\mathcal{C}_\pi \to 2^{\mathcal{C}_d}\). Note that \(\sum_{k=1}^{K^i} \alpha_k d_t^{\phi^i(k)\circ\pi}(s,a)\) is polynomial in \(\pi\) for all \(t\in[H]\) and \((s,a)\in\mathcal{S}\times\mathcal{A}\) and thus continuous in \(\pi\). Furthermore, Lemma 1 together with the fact that \(A^i(\pi)\) is a linear transformation of \(\Omega^i(\pi)\) with respect to \(\pi\) ensures that \(A^i(\pi)\) maps to a convex and compact set in \(2^{\mathcal{C}_d}\), and is upper semi-continuous for any \(\pi \in \mathcal{C}_\pi\). ◻
9 Assumption relationship↩︎
In this section, we show that Assumption 1 implies Assumption 2.
Suppose Assumption 1 holds. Then, for any \(i \in \mathcal{N}\) and any policy \(\pi \in \Pi_M\), there exists a modification \(\phi_0^i \in \Phi_M^i\) such that \[V^{g^j}(\phi_0^i \circ \pi) > c^j, \qquad \forall j \in [J].\] By Theorem 1, there exists \(\bar{\alpha} \in \Delta(K^i)\) such that \[\sum_{k=1}^{K^i} \bar{\alpha}_k V^{g^j}(\phi^i(k)\circ \pi) = V^{g^j}(\phi_0^i \circ \pi) > c^j, \qquad \forall j \in [J].\] Let \(\alpha^{\mathrm{unif}}_k = 1/K^i\) for all \(k \in [K^i]\), and define \[\alpha^\varepsilon = (1-\varepsilon)\bar{\alpha} + \varepsilon \alpha^{\mathrm{unif}}.\] Then \(\alpha^\varepsilon_k > 0\) for all \(k \in [K^i]\). Since the above inequalities are strict and there are finitely many constraints, choosing \(\varepsilon > 0\) sufficiently small yields \[\sum_{k=1}^{K^i} \alpha^\varepsilon_k V^{g^j}(\phi^i(k)\circ \pi) \ge c^j, \qquad \forall j \in [J].\] Therefore, Assumption 2 holds. In particular, this conclusion applies to all policies on the boundary, i.e., \(\pi \in \mathcal{C}_\pi\).
References↩︎
Playerwise coupling constraints refer to settings where each agent has individual constraints that may depend on other agents’ policies.↩︎
This game is standard and models two vehicles approaching an intersection with these actions [42].↩︎
A correspondence \(g\) is upper semi-compact if it is upper semi-continuous and \(g(x)\) is compact for every \(x\in\mathcal{X}\) [40]. See the notation section for the definition of upper semi-continuity.↩︎
Pointwise convergence of \(\pi_n\) to \(\pi\) ensures that for any \(i \in \mathcal{N}\), \(j \in [J]\), and \(k \in [K^i]\): \(V^{r^i}(\phi^i(k) \circ \pi_n) \to V^{r^i}(\phi^i(k) \circ \pi)\) and \(V^{g^j}(\phi^i(k) \circ \pi_n) \to V^{g^j}(\phi^i(k) \circ \pi)\) pointwise as \(n \to \infty\).↩︎