Carrying Feasibility Forward: Anytime-Safe Equilibrium Play in Receding Horizon Games

When several self-interested agents share a physical resource, such as prosumers drawing on one feeder line or robots sharing free space, each agent's choice changes which choices remain legal for the others. Game theorists call this a generalized Nash equilibrium problem: a game in which each player's feasible action set depends on what the other players do. To control such a system over time, you re-solve this game over a short look-ahead window at every time step, execute only the first move, and repeat. This is receding horizon control, the same loop that model predictive control (MPC) uses. The difficulty is that solving each stage game exactly is slow, and if you stop the solver early you may execute an action that breaks a shared constraint.

This note proposes a way to make every intermediate solver iterate safe to execute. Each agent runs a few steps of a decentralized barrier-gradient method, a method that keeps iterates strictly inside the feasible set by adding a $-\log$ penalty that blows up at the constraint boundary. The method is always warm-started from the previous step's plan, shifted forward one step and padded with a locally known safe terminal action. The receding horizon loop then supplies, for free, the strictly feasible starting point that safe decentralized equilibrium learning otherwise needs and that is NP-hard to find in general. Because the iterates never leave the interior, agents can stop after any number of iterations, or inject exploration noise confined to an interior ellipsoid, without a single violation. Each agent only exchanges messages with the agents it shares constraints with, so the per-agent cost per control tick scales with its number of constraint neighbors rather than with the joint action space.

Core Claim

Two existing lines of work almost meet but leave a gap between them. Jordan and Kamgarpour give a decentralized interior-point learning algorithm for games with playerwise concave coupling constraints whose iterates stay feasible throughout and reach an $\epsilon$-equilibrium in $\mathcal{O}(\epsilon^{-3})$ iterations. Their setting is stateless, convergence is proven only for potential games, and the algorithm assumes a strictly feasible starting point. Hall et al. (2022) and Hall et al. (2024) supply the dynamic side. They compute a variational equilibrium of a coupled-constraint game at every step of a receding horizon and prove closed-loop stability, through a potential-game equivalence with economic MPC under symmetric pricing and through a matrix-inequality certificate for strongly monotone games. They assume each stage game is solved to convergence by a coordinated solver, and they do not consider exploration.

Our claim is that these two ingredients can be joined so that each fills the other's hole. The receding horizon shift provides the feasible start that the barrier method needs. The barrier method's interior iterates provide the anytime safety that lets the receding horizon loop run with truncated, decentralized solves. Concretely, at tick $t$ agent $i$ holds a planned action sequence $u_i$ over horizon $K$, and runs $k$ local updates

$$u_i \leftarrow u_i - \eta_i \nabla_{u_i}\Big[J_i(u_i, u_{-i}; x_t) - \mu \sum_{c \in \mathcal{C}_i} \log g_c(u; x_t)\Big],$$

Here $J_i$ is agent $i$'s cost given current state $x_t$, the $g_c \ge 0$ are the coupling constraints that involve agent $i$, $\mu$ is the barrier weight, and $\eta_i$ is an adaptive step size chosen so the step never crosses the boundary, as in Jordan and Kamgarpour. After the first action is executed, the plan is shifted and a safe terminal action is appended. That plan is the starting point at tick $t+1$.

The new questions concern the closed loop. We ask when the shifted plan remains strictly feasible after the state update, how far the truncated iterate trails the exact stage-game equilibrium, and whether that tracking error stays bounded or accumulates. We call the guarantee we seek recursive strict feasibility under truncation.

Research Program

The theoretical part has three pieces.

The first is a recursive feasibility lemma. Assume each agent has a local terminal action that, jointly with everyone else's, satisfies every coupling constraint with margin $\delta$; for a battery this is holding charge at base load, for a vehicle it is stopping. Assume also that the state disturbance moves each constraint by less than the barrier margin of the shifted plan. Under these conditions the warm start is strictly feasible at every tick. This is the standard terminal-set argument from MPC, carried over to coupled game constraints.

The second piece is a tracking bound for potential stage games. The barrier-regularized potential serves as a merit function. We expect the gap between the truncated iterate and the stage equilibrium to contract geometrically in $k$ per tick and to grow with how fast the stage problem drifts from tick to tick. This is the same structure as real-time-iteration MPC analyses: error contracts by a factor per tick and is pushed up by the drift between consecutive problems.

The third piece is exploration. When an agent's own dynamics or cost parameters are uncertain, it adds probing noise only inside the barrier's Dikin ellipsoid, the region around the current point that the log-barrier geometry guarantees lies inside a convex feasible set. This gives information-gathering perturbations that cannot cause violations. It addresses, for the coupled case, the problem flagged in Feasible Dual Policy Iteration: an agent that learns only safe behavior rarely visits states near the constraint boundary. Ellipsoid probing reaches toward the boundary while remaining feasible.

We scope the theory honestly. The Dikin ellipsoid argument needs convex playerwise feasible sets, and the convergence argument needs a potential structure. We therefore treat non-potential games, such as asymmetric tariffs, as an empirical question. We check them against the Hall 2024 certificate rather than claiming a guarantee.

Scalability comes from the sparsity of coupling, not from a new equilibrium concept. The general hardness results stand. Bernasconi et al. show that even correlated equilibria of generalized games are PPAD-complete, and the anytime-constrained equilibrium construction carries a $(1/\epsilon)^n$ state blow-up in the number of agents $n$. We sidestep this by targeting continuous, convex-coupled stage games solved locally by gradient play, where each agent's work per tick is linear in its number of constraint neighbors. We are not claiming to beat these lower bounds; they constrain which game class we can promise anything for.

Baselines

The naive reference point is uncoordinated per-agent MPC. Each agent optimizes its own horizon, treats the others' last announced plans as fixed, and is clipped by a simple local rule when it would exceed its share of a coupling constraint. This shows what ignoring the coupling costs in both violations and efficiency.

The strongest existing method on the dynamic coupled-constraint question is the receding horizon game of Hall et al. (2022), with the variational equilibrium solved to convergence at every tick. On Pecan Street data with 10 active prosumers it reports a 49% reduction in peak aggregate load and a 6% gain over day-ahead optimization. It also reports zero constraint violations when grid capacity drops by 60% for five hours. We will reproduce this setting exactly, using the same data window, agents, horizon, and prices. The number to beat on quality is matching that 49% peak reduction within a small tolerance. The number to beat on cost is running at a fraction of its per-tick computation, with the gap widening as agent count grows.

For safety during learning, the competitors are MAPPO-Lagrangian and MACPO. These are multi-agent constrained policy optimization methods that enforce expected cost budgets and report near-zero costs on Safe Multi-Agent MuJoCo; the file has no single numeric value for them. We will also run DeepSafeMPC, which puts a centralized SQP-based MPC filter over MAPPO proposals and reports a roughly 33% cost reduction relative to MAPPO alone. In navigation we run MAMPS, a greedy per-agent model predictive shield that reports a 100% safety rate in 3-agent and 4-agent particle scenarios but declining goal-reach as density rises. Learned baselines receive the same environment-step budget and the same hyperparameter search budget as our exploration variant. Optimization baselines receive the same wall-clock budget per tick. Beating them means zero violations during training where the learned methods incur nonzero ones, together with equal or better task return. Against MAMPS, beating it means higher goal-reach at equal safety rate at higher densities.

Two ablations isolate the key ingredient. The first, cold start, keeps the barrier solver and truncation but restarts each tick from a feasible point found by a separate first-phase solve. The second, unsafe truncation, keeps warm starting but replaces the barrier with a projected-gradient or penalty solver. If the shift-and-append warm start is what matters, cold start should be slower at equal $k$, and unsafe truncation should violate constraints whenever $k$ is small.

Why not just…?

Why not just use MAPPO-Lagrangian with coupling constraints as cost budgets? Lagrangian methods satisfy constraints in expectation and only at convergence, so violations during training are expected. Satisfying constraints in expectation also does not stop one agent from emptying another's feasible set at the next step, which is the core coupled-action problem identified by McMahan. Safety-Gymnasium reports that PPO-Lag's 98% reduction in violations in velocity tasks came with a 45% drop in reward, which illustrates the tuning tension. We will measure cumulative training violations directly. If MAPPO-Lagrangian reaches comparable return with violations near zero, our safety argument weakens to a matter of guarantees rather than of practical differences, and we will report it that way.

Why not just solve one centralized MPC over all agents? This is the most serious threat for convex coupling. A sparse centralized quadratic program can be fast even for many agents, so the general claim that the joint action space grows exponentially does not apply to continuous convex problems. Our answer rests on two points rather than on speed alone. First, centralized MPC computes a social optimum, not an equilibrium, and requires agents to reveal private costs; Franci et al. motivate decentralized equilibrium seeking for exactly this reason. Second, an interior-point solver stopped mid-run gives no feasibility guarantee unless it is warm-started inside the feasible set. We will report centralized sparse QP wall-clock as a function of $N$. If it is faster and the setting allows a central planner, we will say so plainly, and the contribution then narrows to the decentralized and private-cost regimes.

Why not just run the Jordan–Kamgarpour algorithm to convergence at every tick? That approach is safe but pays a full solve per tick and needs a fresh feasible start every time. Hall's contingency scenario, where capacity drops abruptly, is exactly where finding a new start is hard. The cold-start ablation and the iterations-to-tolerance comparison measure what warm starting saves.

Why not just use priority-based shielding? Wang et al. show that a passive avoider loses 98% of blocking encounters to a strategic planner. MAMPS shows goal-reach falling as density rises. The density sweep below tests whether equilibrium-aware truncated play avoids the agents freezing in place.

Proposed Experiments

The primary testbed is the Pecan Street demand-side management setting of Hall et al. We scale it from 10 to several hundred prosumers on a feeder tree, so that each line-capacity constraint couples only the households downstream of it. We sweep $k$ from 1 to 50 iterations per tick. We measure four things: violations of any line constraint, peak-load reduction, the tick-wise gap to the exactly solved variational equilibrium, and per-agent wall-clock and message count per tick.

We then switch to asymmetric tariffs, which break the potential structure. We record whether the truncated loop stays bounded, and whether this agrees with the Hall 2024 matrix-inequality certificate when that certificate is feasible.

The second testbed is a dynamic version of Jordan and Kamgarpour's network routing game, with link capacities shared across time.

The third is multi-agent particle navigation, using convexified collision constraints in the form of separating half-planes computed from the previous plan. We run 3 to 50 agents and compare against MAMPS on safety rate and goal-reach, starting with its 3-agent/3-obstacle and 4-agent/4-obstacle configurations. Exploration experiments use Safe Multi-Agent MuJoCo two-agent tasks from the MACPO codebase, with a shared velocity budget added as a coupling constraint. Agents learn their own dynamics parameters with Dikin-ellipsoid probing, and we compare against MACPO, MAPPO-Lagrangian, and DeepSafeMPC on training-time violations and return.

Three results decide the proposal. With $k=1$ and warm starting, the closed loop must show zero coupling violations across the scaled grid while staying within a few percent of the exact receding horizon game's 49% peak reduction; the unsafe-truncation ablation must violate at the same $k$. Per-agent time per tick must stay flat as $N$ grows at fixed coupling degree. Finally, the Hall contingency, where capacity drops 60% at once, tests the recursive feasibility lemma at its edge: the drop can exceed the barrier margin. We will report how often the shifted plan becomes infeasible and whether falling back to the terminal safe action restores the interior within one tick. A failure there would mark the precise limit of the approach.