The Math of Coordination: Why Hundreds of Polluters Can Now Be Modeled at Once

Five-hundred players, each with a private motive, are nudging a single shared state — the planet's atmosphere, say — in different directions. One wants to pump emissions and pocket the profit. Another wants to scrub the air and charge for it. Left to themselves, they fight. But there is a way to give every one of them a strategy that, if all follow it, none of them wants to abandon. That is a Nash equilibrium — the mathematical shadow of "no one has a cheaper move."

The catch has always been price. For decades, the standard machinery for finding such equilibria in games that unfold over time — the famous Riccati equations of linear-quadratic differential games — grew quadratically in cost as the problem got bigger. Double the number of state variables and the computation roughly quadruples. That is fine for a three-player toy. For a realistic model of a couple hundred polluters, it collapses.

A team led by Alba Gurpegui at Lund University and Monika Tomar and Takashi Tanaka at Purdue has found a way around that wall. In a new paper on a class of games they call "linear regulator" games, the equilibrium computation scales linearly with the state dimension — not quadratically (Gurpegui et al.). That is the difference between a problem that grows like a square and one that grows like a line, and for large-scale games involving many interacting agents — pollution, epidemiology, population dynamics — it turns an infeasible computation into a tractable one. This is the kind of scaling shift that separates a theorem that sits in a journal from a method that actually gets used.

The trade-off, as with most real progress, is not free. The strategies that emerge are piecewise-constant: each player's action slams between its upper and lower bound like a thermostat, rather than gliding smoothly. That makes the math harder in a different way, and the paper spends much of its effort taming exactly that awkwardness.

The Science

Before the game, there was a single player. The authors build directly on a body of work on the "linear regulator" (LR) optimal control problem: one decision-maker trying to minimize a linear cost over a finite horizon, with dynamics that are positive — meaning the state variables (populations, pollutant stocks, disease counts) can never go negative — and with inputs constrained to lie inside a cone defined by the state itself.

This sounds abstract, but the structure is everywhere in the real world. Positivity is not an assumption the modelers chose for convenience; it is intrinsic to the quantities they care about. A population cannot be negative. A stock of pollution cannot be negative. An epidemic count cannot be negative. Linear costs, meanwhile, arise naturally when profit from emitting and the cost of controlling emissions both grow in proportion to how much is involved — double the activity, double the cost and benefit. That is precisely the shape of many pollution and resource problems.

The key insight from the prior single-player work: under two structural assumptions, the optimal control can be written explicitly. The first (Assumption 1) demands that the dynamics preserve positivity. The second (Assumption 2) guarantees each player's cost is nonnegative and bounded below. When both hold, the optimal policy takes a bang-bang form: each input sits at one of its extreme allowed values, flipped by the sign of an "input gradient."

The new paper extends this single-player recipe to a general-sum game with $N>1$ players, each with their own cost functional. This is not a zero-sum fight where one player's gain is another's loss. Each player has a genuinely different objective, captured by their own vectors $s_i$ and $r_i$, and their own constraint matrix $E_i$. The dynamics are shared:

$$\dot{x}(t)=Ax(t)+\sum _{i=1}^N{B}_i{u}_i(t),x(0)=x_0,$$

with each player $i$ obeying $|u_i|\le E_{i}x$. Each player $i$ minimizes their own cost

$$C_i={\int }_t^T\left(s_i^{\top }x(\tau )+r_i^{\top }{u}_i(\tau )\right)d\tau .$$

The equilibrium concept is feedback Nash equilibrium (a set of state-feedback laws such that no player can reduce their own cost by unilaterally deviating, no matter what state the system is in). Feedback equilibria are prized because they are strongly time-consistent: players can react to state deviations even if someone deviated in the past, which makes them robust in a way that open-loop equilibria are not.

The result is a verification theorem (Theorem 2): if one can find absolutely continuous functions $p_i(t)$ satisfying a coupled system of vector-valued ODEs (equation 6 in the paper), with appropriate sign conditions on the input gradients, then the feedback laws constructed from those $p_i$'s constitute a feedback Nash equilibrium. The cost each player pays is $p_i(0{)}^{\top }{x}_0$.

The proof is elegant and worth pausing on. For a fixed opponent strategy, each player's subproblem becomes an optimal control problem of the LR type. The candidate value function $V_i(\tau ,x)=p_i(\tau {)}^{\top }x$ is shown to be the value function for that subproblem, and the bang-bang feedback law is shown to be the pointwise minimizer of the running cost integral. Symmetrically, the same holds for every other player. Hence no one wants to move — a Nash equilibrium.

The figure shows the phase diagram of a worked example with two players and scalar states, illustrating the "switching surfaces" ${\Sigma }_1=\{p_1=1\}$ and ${\Sigma }_2=\{p_2=1\}$ across which each player's feedback law toggles.

What They Found

Three results stand out.

First, the linear scaling. The authors frame this directly against the Riccati-based approach of linear-quadratic differential games, where the equilibrium is characterized by coupled matrix Riccati equations whose dimensions scale quadratically with the state dimension. Here, the equilibria are characterized by vector-valued ODEs — the $p_i$'s are vectors, not matrices. The number of unknowns grows linearly with the state dimension. This is the headline computational result, and it is what makes the method viable at scale.

Second, the switching structure. Because the feedback gains are piecewise-constant, saturating at their constraint bounds, the ODE system is piecewise affine rather than smooth. On each interval where every input gradient stays nonzero, the matrices $K_i$ are constant, and the system reduces to a plain affine ODE with unique solution (Remark 2). The hard part is what happens at the switching boundaries — and especially what happens when a gradient vanishes on an interval of positive measure.

This is where the mathematics gets genuinely delicate, and where the paper is refreshingly honest about its limits. Theorem 2 requires that input gradients be nonzero almost everywhere. But Example 1 shows a configuration where one player's gradient vanishes on an interval of positive length. There, the feedback gain $K_2$ is not uniquely determined, different choices of $K_2$ produce different trajectories for the other player's $p_1$ through the coupling term, and the solution fails to be unique. The dynamics then are better described by a differential inclusion — a set-valued generalization of an ODE — which the authors explicitly declare beyond the scope of this work. It is a notable boundary: one player's non-uniqueness propagates to another's equation.

Third, the infinite horizon. Under an $E$-stabilizability assumption — roughly, that there exists a feedback law within the constrained input class that makes the closed loop stable — the infinite-horizon equilibrium collapses from coupled ODEs into coupled algebraic equations (equation 3). This is the stationary analogue: instead of integrating backward in time, one solves a system of algebraic equations for constant value vectors $p_i$, and the optimal cost is $p_i^{\top }{x}_0$. Moreover, that algebraic system can be reformulated as a linear program, which unlocks all of LP's mature scalability machinery.

To actually compute the finite-horizon equilibria, the authors propose Algorithm 1: a fully implicit Backward Euler scheme with an active-set iteration. The subtlety is that the discrete "active set" $S_i(t)=\text{diag}(\text{sign}(r_i+B_i^{\top }{p}_i(t)))$ depends on the implicitly unknown $p_i(t)$, so the algorithm iterates between solving for the $p$-vector and updating the control signs, detecting cycling via repeated sign patterns and accepting the iterate only if the discrete residual falls below tolerance — otherwise it terminates and can be rerun with a smaller time step.

Why This Changes Things

The paper's own illustration is a large-scale pollution game, and that choice is not incidental. Environmental regulation is, structurally, a general-sum game with positive dynamics: the state is the pollutant stock (nonnegative by nature), each firm's cost is linear (profit from emitting, cost of abatement), and inputs are constrained. Yet most existing differential-game treatments of such problems are limited to small numbers of players precisely because of the quadratic scaling of Riccati-based methods.

The linear scaling opens a door that was effectively shut. A model with, say, a few hundred interacting regions or firms — each with its own cost structure and its own constraints — becomes computationally plausible. That is the difference between a stylized two- or three-player toy and a model that could actually inform policy about how many regions will shirk on a shared pollution target if they believe everyone else holds the line.

There is a second, subtler payoff. Because the equilibrium value functions are linear ($V_i=p_i^{\top }x$), the marginal "price" of the state is a constant vector rather than a state-dependent matrix. That makes the equilibria interpretable: each entry of $p_i$ is a shadow price — the marginal cost to player $i$ of one more unit of state $j$. For a pollution game, that is literally the marginal social cost of one more unit of pollutant for each player. Policy-relevant quantities like these are much harder to read out of a Riccati matrix.

How equilibrium computation scales with state dimension

Label	Value
Linear-quadratic (Riccati)	100 relative computation
Linear regulator (this paper)	10 relative computation

Based on the paper's comparison: Riccati-based equilibria scale quadratically with the state dimension; the linear regulator formulation scales linearly (Gurpegui et al.).

There is also a philosophical note worth making about the shape of the optimal strategies. Bang-bang control — saturating at extremes rather than adjusting smoothly — is common in engineering (thermostats, bang-bang rocket attitude control) but less familiar to a general reader. In the pollution context it has a sharp meaning: the "right" strategy, in a Nash sense, is often not to emit a little less than you'd like, but to apply maximal control up to the constraint bound until the value function says stop. Equilibrium policy in these games is a set of switches, not a dial. That is both a computational blessing (fewer parameters) and a modeling challenge (real abatement does ramp smoothly).

Unknowns needed for equilibrium at state dimension n = 10

Label	Value
Linear regulator (vector ODEs)	10 unknowns
Linear-quadratic (matrix Riccati ODEs)	100 unknowns

Representative of the paper's central scalability claim: vector-valued ODEs (n unknowns) versus matrix Riccati equations (n^2 unknowns).

The caveats are real, and the authors do not hide them. The requirement that input gradients be nonzero almost everywhere is a genuine restriction: the paper shows what happens when it fails, and the behavior is genuinely non-unique. For now, the theory handles "switching at isolated time instants" cleanly and leaves the differential-inclusion regime as future work. Stabilizability in the infinite-horizon case is also assumed rather than always verified. And the paper treats the case where switches are isolated — the grazing case where a gradient rides at zero for a stretch remains open.

What's Next

The most natural next step is the one the authors flag themselves: the differential-inclusion case where a player's gradient vanishes on an interval, producing non-unique and possibly non-smooth equilibria. That is where the mathematics currently breaks, and it is also where real pollution games might plausibly live — there is no reason a gradient must stay away from zero. Understanding when the non-uniqueness matters, and whether some selection principle picks a "natural" equilibrium, would meaningfully extend the reach of the theory.

A second direction is algorithmic hardening. The active-set Backward Euler scheme is sound but not proven to converge globally; the authors accept an iterate only if a residual check passes, and may need to shrink the time step. A convergence theory — and ideally a Newton-style or interior-point method exploiting the LP reformulation of the stationary problem — would make large-scale deployment more reliable.

A third, more speculative thread concerns what the linear scaling enables in practice. The authors mention $E$-stabilizability, positivity, and the LP reformulation in the infinite-horizon case. If the full pipeline — model, equilibria, LP solve — behaves as advertised, then genuinely large $N$-player pollution and population games move from thought experiment to computable artifact. That is the kind of evolution that lets a theory graduate from the whiteboard to the policy briefing.

None of this is a cure-all. The constraints are structural: linear costs, positive dynamics, elementwise input bounds, and — in the finite horizon — the almost-everywhere-nonzero condition on gradients. Real systems have nonlinearities, stochasticity, and asymmetric information that this framework does not yet touch. But within its domain, the paper delivers something rare: a rigorous, verifiable characterization of multi-agent equilibrium that actually scales. In a world where the hardest strategic problems — climate, pandemics, migration — are exactly games among many self-interested agents sharing one positive state, a linear path through the fog is worth having.