Constrained Markov Potential Games

Definition

Constrained Markov Potential Games are constrained Markov games whose agents’ unilateral reward improvements align with a shared potential function, while feasible policies must satisfy coupled safety or resource constraints over the joint policy.

Why It Matters

CMPGs isolate a tractable-looking but still delicate safe-MARL class. The potential structure lets equilibrium search use coordinated unilateral improvements, but coupled constraints mean single-agent CMDP intuitions, especially Lagrangian strong duality, do not automatically transfer.

Formalism / Key Objects

• In a Markov potential game, each agent i has value V_i^r(pi) and there is a potential Phi such that for unilateral deviations

$$V_i^r({\pi }_i,{\pi }_{-i})-V_i^r({\pi }_i^{\prime },{\pi }_{-i})=\Phi ({\pi }_i,{\pi }_{-i})-\Phi ({\pi }_i^{\prime },{\pi }_{-i}).$$

• A CMPG adds cost functions and thresholds. The feasible set is

$${\Pi }_C=\{\pi \in \Pi \mid V^{c_j}(\pi )\le {\alpha }_j,j=1,\dots ,k\}.$$

• A feasible policy pi* is an epsilon-Nash policy when each agent’s feasible unilateral improvement is at most epsilon:

$$\underset{{\pi }_i\in {\Pi }_C^i({\pi }_{-i}^{\ast })}{\max }{V}_i^r({\pi }_i,{\pi }_{-i}^{\ast })-V_i^r({\pi }^{\ast })\le ϵ.$$

• Potential maximization over feasible policies,

$${\pi }^{\ast }\in \arg \underset{\pi \in {\Pi }_C}{\max }\Phi (\pi ),$$

yields a Nash policy, but solving this optimization directly can be intractable.

• Lagrangian relaxation modifies rewards as r_i - sum_j lambda_j c_j, but strong duality can fail in CMPGs, so a dual solution may not be safe or optimal for the constrained game.
• Coordinate-Ascent for CMPGs records the CA-CMPG and CA-CMPG-E algorithms for directly searching over feasible joint policies.

Connections

• Alatur2024 - Provably Learning Nash Policies in Constrained Markov Potential Games introduces the class and CA-CMPG/CA-CMPG-E algorithms.
• Stochastic Games are the unconstrained sequential-game baseline: CMPGs add potential alignment and coupled feasibility constraints on top of Markov-game dynamics.
• Coordinate-Ascent for CMPGs collects the main constrained optimization, duality, convergence, and sample-complexity statements.
• Safe Reinforcement Learning supplies the constraint-satisfaction motivation, while Strategic Reasoning supplies the Nash-equilibrium lens.
• Constrained Markov Decision Processes are the single-agent ancestor; CMPGs show why coupled multi-agent feasibility can break CMDP duality intuitions.
• Gu2022 - Multi-Agent Constrained Policy Optimisation studies a neural safe-MARL trust-region route for constrained Markov games without the potential-game restriction.
• Shielding is an alternative safety mechanism: it filters actions by construction rather than learning an equilibrium inside a constrained feasible set.
• Decision Theory is relevant because CMPGs make trade-offs among individual objectives, feasibility constraints, and equilibrium notions explicit.

Common Confusions

• A CMPG need not be fully cooperative; agents can have different reward functions as long as unilateral reward changes align with a potential.
• Strong duality for single-agent CMDPs does not imply strong duality for CMPGs.
• An approximate feasible policy is not enough for the convergence argument if intermediate policies can leave the feasible set.

Key Sources

• Alatur2024 - Provably Learning Nash Policies in Constrained Markov Potential Games
• Gu2022 - Multi-Agent Constrained Policy Optimisation
• Coordinate-Ascent for CMPGs