Hard Capacity Sharing in Zero-Sum Routing Games on Series-Parallel Networks

When two parties compete over the same physical network, their choices constrain each other. Examples include a transport operator routing commuters while an adversary floods or blocks lanes, or two fleets sharing road capacity. Every unit one party sends down a link is a unit the other cannot use. Such games are "zero-sum" (one side's gain is exactly the other's loss). Zero-sum games are normally the easy case of multi-agent learning: every equilibrium has the same value, and simple algorithms find it. That ease disappears once actions are coupled. Finding even a feasible pair of randomized strategies under hard, per-realization constraints is NP-hard in a single-state two-player zero-sum game (Anytime-Constrained Equilibria in Polynomial Time). Correlated equilibria stop being a shortcut, because computing them becomes PPAD-complete (Bernasconi et al.). Separately, work on cooperative network games shows that series-parallel networks make capacity-constrained problems tractable. Series-parallel networks are graphs built by repeatedly placing links in sequence or side by side. On these graphs, strong equilibria always exist and integer allocation programs have no integrality gap (Do Capacity Constraints Constrain Coalitions?, Market Design for Capacity Sharing in Networks). Nobody in this literature has asked whether the same topology rescues the competitive, zero-sum case.

This note proposes to answer that question, starting from one simple observation. Suppose the two players randomize independently and every realized pair of routings must respect link capacity. Then the coupled constraint is equivalent to a per-link reservation split: each player may use, in any strategy it plays with positive probability, at most its reserved share of each link. This rewrites the hard coupled game as two layers. The outer layer is a coupled choice of reservations. The inner layer is an ordinary zero-sum game with independent action sets, which is well understood. The main conjecture is that on series-parallel networks the outer layer can be solved by recursion over the graph's series/parallel decomposition tree, with cost linear in the number of links. The second claim concerns scale. Departure-time choice, meaning a copy of the network for each time period with every copy joined in parallel at the origin and destination, keeps the graph series-parallel. So the method extends to space-time routing over a full day at cost linear in (links × periods).

Core Claim

Let $f_i(e)$ be the integer flow player $i$ sends on link $e$, and let $c(e)$ be the link's capacity. Player $i$ plays a mixed strategy $x_i$ over feasible routings with support $S_i$. The anytime (almost-sure) coupled constraint requires $f_1(e)+f_2(e)\le c(e)$ for every $f_1\in S_1$, $f_2\in S_2$. Because the players randomize independently, the joint support is the product $S_1\times S_2$. The constraint therefore holds exactly when

$$R_1(e)+R_2(e)\le c(e)\quad\text{for all links } e,\qquad R_i(e)=\max_{f\in S_i} f(e),$$

where $R_i(e)$ is player $i$'s reservation on link $e$, the largest flow it ever sends there. This step is exact for any edge-additive packing constraint and any graph. The topology question arises in the next step. A player's best response is feasible only inside the capacity the opponent leaves free, so the game is a zero-sum pseudo-game: a game in which each player's allowed actions depend on the other's choice. In such a game, equilibria may fail to exist, and when they exist they may have different values. The unique-value property that makes zero-sum games easy is not guaranteed to survive.

The proposal makes three testable claims. The first is that on series-parallel networks, the set of throughput levels a player can achieve under a reservation vector composes cleanly: series links combine by minimum, parallel links by sum. This should make three problems solvable in time polynomial in the size of the decomposition tree: the outer reservation problem, feasibility of a joint profile, and computation of an equilibrium. Here "equilibrium" means a generalized Nash equilibrium: a strategy pair such that neither player can gain by deviating to any strategy that stays feasible given the other's choice. The second claim is that on series-parallel networks all such equilibria share one value. The third is that on networks containing the Braess graph as a substructure, which is the structure Do Capacity Constraints Constrain Coalitions? shows breaks strong equilibria, existence or value uniqueness can fail. On those networks the NP-hardness of Anytime-Constrained Equilibria should reappear through a reduction.

I do not yet know whether the second claim holds for all series-parallel networks. It may hold only for the narrower Series-of-Parallel-Paths class, which is the class where Feldman and Geri's characterization is tight. Finding out which class it holds for is part of the work.

Research Program

The first strand is theory, built on the reservation decomposition. On a series-parallel decomposition tree, each node's feasible flow region under a reservation vector should be summarized by a single number, its maximum throughput. This summary is the zero-integrality-gap property that Market Design for Capacity Sharing in Networks exploits in the cooperative setting, reused here as a method. We will then show that the zero-sum payoff restricted to reservations is concave-convex along the tree when the payoff is throughput-based. That property would give existence through a minimax argument at each node.

The feasible-initialization problem left open by both Nash Equilibria in Games with Playerwise Concave Coupling Constraints and An Online Feasible Point Method becomes a greedy pass up the tree that splits each block's capacity. This is a concrete instance of the "contractibility along topological paths" idea sketched as Gap 4 in the source material. On the negative side, we will attempt to embed the single-state hardness instance of Anytime-Constrained Equilibria into a routing game on a Braess-containing graph.

The second strand is an algorithm for learning in this game. The outer reservation layer is a small coupled game over the $|E|T$ reservation variables, where $T$ is the number of time periods. We solve it with an interior-point update that keeps reservations strictly inside capacity using a log-barrier, adapted from Jordan and Kamgarpour. Their convergence proof covers potential games and explicitly leaves zero-sum games open. Here the barrier is applied only to the outer layer, which the tree structure is meant to make concave-convex, so their proof technique has a chance of carrying over.

The inner layer is an unconstrained zero-sum game. We run optimistic gradient descent-ascent on it, an update rule that extrapolates one step ahead to damp the cycling of plain gradient methods. It has known last-iterate guarantees in the tabular case (Wei et al.). We deliberately avoid plain multiplicative weights, whose day-to-day iterates are chaotic in zero-sum games (Cheung and Piliouras). Any realized routing respects its reservation, so capacity is never violated during learning, only at convergence or otherwise.

The third strand covers the space-time regime and its boundary. The spatio-temporal graph literature scales by factorizing a monolithic space-time graph, whose pairwise cost grows as $O(N^2T^2)$ for $N$ locations and $T$ periods, into separate spatial and temporal operators (Fully-Connected Spatial-Temporal Graph for Multivariate Time-Series Data, TESTAM). Here the factorization is not learned. It comes from the network itself: departure-time choice places period copies in parallel, and the decomposition tree gives an exact $O(|E|T)$ computation. We will then add waiting at intermediate nodes, which breaks the series-parallel property of the time-expanded graph. This tests whether tractability degrades gradually or collapses. It matches the open question in the file about "mild cycle structures."

Baselines

The naive reference point is a soft-penalty game. We add $\lambda\max(0,f_1(e)+f_2(e)-c(e))$ to the payoff, run the same optimistic gradient method on the flat joint game, and tune $\lambda$ over a grid with the same compute budget. Beating it means our method matches or improves the final constrained Nash gap with zero realized capacity violations. The penalty method should show nonzero violations during learning, as Anytime-Constrained Equilibria argues it must.

The strongest exact competitor is the polynomial-time $\epsilon$-approximation scheme of Anytime-Constrained Equilibria in Polynomial Time. It builds an AND/OR feasibility tree, augments the state with accumulated costs, and solves a linear program at each stage game. It is the only method in the file with guarantees for zero-sum games under anytime coupled constraints. We run it with its published structure on identical instances, sweeping $\epsilon$, under the same wall-clock limit. No reported runtime or accuracy result was found on Lacuna for this scheme on routing instances, so the comparison must be generated here. Beating it means equal or lower exploitability at networks and horizons where its augmented state, which grows as $(1/\epsilon)^n$, exhausts memory.

The strongest scalable learned competitor is GAPNet from Infinite Horizon Markov Economies. It trains a generator network against an adversarial deviation tester to minimize exploitability in pseudo-games. We give it the same network parameterization budget and the same number of gradient steps. The file reports it scaling to 20 consumers and 20 commodities and "significantly" outperforming a neural projection method, but no numeric exploitability is reported on Lacuna. Beating it means lower final exploitability together with feasibility at every iterate, which GAPNet does not guarantee.

We also include the interior-point method of Jordan and Kamgarpour applied directly to the flat coupled zero-sum game. The file reports that on its five-player routing game the Nash gap converged to zero with zero constraint violations, but in a potential game. Our prediction is that without the reservation layer it cycles or stalls in the zero-sum case.

Two ablations isolate the key ingredients. The first keeps the reservation decomposition but solves the outer layer with a generic linear program instead of the tree recursion; this isolates the contribution of topology. The second runs the tree recursion on Braess-containing graphs through an approximate decomposition; this should fail visibly if topology is doing the work.

Why not just…?

Why not just use soft penalties or Lagrange multipliers? Penalties allow infeasible iterates while learning. The approximations built on Lagrange multipliers in Stochastic Generalized Dynamic Games with Coupled Chance Constraints leave a persistent gap to exact feasibility. For physical capacity, meaning cars on a lane, a violated iterate is not acceptable. The soft-penalty baseline reports violation counts per episode, so this claim is measured rather than asserted.

Why not just solve one big linear program? This alternative is a real threat. If capacity only has to hold in expectation, the game with shared linear constraints is a convex-concave saddle problem, and a linear program solves it in polynomial time. Our claim concerns only the almost-sure, integer regime, where the hardness result of Anytime-Constrained Equilibria applies. We will run the expectation-constrained linear program and report how often its randomized routings violate capacity on realized draws. If that violation rate is negligible on real Bay Area instances, the practical case for this work narrows to the guarantee itself, and we will say so. For the almost-sure problem, flat enumeration is also hopeless at scale: the file reports a linear program solver handling only 11×11 games in the time SI-MWU solved 1500×1500 (Computing Equilibria in Games with Stochastic Action Sets).

Why not just split capacity equally, or in proportion to demand, and then play an ordinary zero-sum game? This fixed-split heuristic is the most dangerous alternative, because it uses our decomposition without the equilibrium outer layer. The inner game becomes one with independent action sets, which SI-MWU handles (Computing Equilibria in Games with Stochastic Action Sets). We will measure the exploitability of fixed-split profiles, meaning how much either player gains by renegotiating reservations. If that gain is small on series-parallel instances, the outer layer is unnecessary there, and the contribution shifts to the non-series-parallel boundary.

Why not just train a spatio-temporal graph network to predict flows? Forecasters such as TESTAM predict passive traffic and model neither strategic response nor hard feasibility. GAPNet is the fair learned stand-in and is included as a baseline.

Proposed Experiments

We use three families of instances. The first is synthetic: Series-of-Parallel-Paths, general series-parallel, and Braess-augmented graphs of growing size, where exact equilibria can be enumerated on small cases. The second is Bay Area road networks, with link capacities calibrated from PeMS sensors following Market Design for Capacity Sharing in Networks, extracted as series-parallel corridors plus non-series-parallel neighborhoods. Time-varying demand comes from PEMS-BAY (325 sensors) at 5-minute periods, with $T$ up to 288 for a full day. The third probes scale using the 1,843-link EXPY-TKY network. It provides speeds, not capacities, so capacities must be imputed; that caveat will be reported.

The metrics are constrained exploitability, the largest gain either player gets from a feasible deviation; the realized capacity-violation rate across all iterates; the value spread across equilibria found from different starting points; and runtime and memory as $|E|\cdot T$ grows.

The decisive checks are the following. First, on series-parallel instances, the value spread across restarts should be zero within tolerance, and runtime should grow linearly in $|E|T$. Second, on Braess-augmented graphs, we should find instances with nonzero value spread or no equilibrium, confirming that topology and not the algorithm drives tractability. Third, adding waiting at intermediate nodes should degrade the method, and plotting exploitability against the number of non-series-parallel blocks tells us whether that degradation is gradual or abrupt. Fourth, the fixed-split and expectation-constrained linear program comparisons determine whether the full construction earns its complexity. If either matches it on real Bay Area instances, the proposal's practical claim is falsified, while the topological theory would still stand.