Potential-Aligned Robust Beamforming for Selfish Unsplittable Routing

Wireless mesh networks are increasingly shared by traffic that nobody controls centrally. Examples include drone swarms from different operators, tenants of a sliced network, and sessions that pick their own path through relays. Each such session wants a single path, not a split one, because splitting a session across paths with different delays reorders packets and breaks stateful middleboxes. At the same time, how much capacity each wireless link offers is not fixed. It depends on how the network operator points its antenna beams and tunes any reflecting surfaces, and the operator only knows the radio channels approximately. This produces a two-sided loop. Sessions pick routes based on how fast links look, and the operator re-tunes beams based on where sessions went. Nobody has asked whether this loop settles down, or how inefficient its resting points are. The one convergence result we have for single-path selfish routing assumes fixed, deterministic link delays. The imperfectly known radio channel breaks exactly that assumption.

We propose a specific operator design and argue it is the right one. The operator should tune beams to minimize the same "potential" quantity that the selfish sessions are implicitly minimizing, rather than the sum-rate or total-delay objectives used in wireless design. It should also publish worst-case latencies computed from its channel-uncertainty set, rather than nominal estimates or noisy measurements. The first choice makes the joint session-and-operator system a potential game. The standard iterative beam optimizers, which improve their objective at every step, then plug in and provably converge. The second choice turns robust beamforming into a stable, trustworthy signal to users. It is an information-design device that removes the oscillations noisy channel feedback would otherwise cause.

Core Claim

Model each session as an atomic, unit-size player that must pick one path. A player is "atomic" when it is a single decision-maker large enough to matter individually. Every wireless link $e$ has a latency $\ell_e(n_e; c_e)$ that rises with the number of sessions $n_e$ on it and falls with its capacity $c_e$. The capacity $c_e(w,\Phi)$ is set by the operator's active beamformers $w$ and the phase shifts $\Phi$ of any reconfigurable intelligent surface (RIS), a passive panel whose elements reflect signals with tunable phase. Interference couples the links: a beam chosen for one link changes the signal quality on others. Game theory in this area normally bars that kind of non-separable dependence. The paper that bounds selfish routing under fairness envelopes, Reconciling Selfish Routing with Social Good, and the SINR-free latency models in A Strategic Routing Framework and Algorithms for Computing Alternative Paths both assume separable, deterministic costs.

The structural observation behind this proposal is that the coupling lives entirely inside the operator's variable. For any fixed $(w,\Phi)$, the sessions play an ordinary congestion game, with the Rosenthal potential

$$P(n; w,\Phi) = \sum_e \sum_{j=1}^{n_e} \ell_e\big(j;\, c_e^{\mathrm{rob}}(w,\Phi)\big),$$

where $c_e^{\mathrm{rob}}$ is the worst-case capacity of link $e$ over the channel-error ellipsoid $\|\Delta H\|_F \le \epsilon$. If the operator's beam update never increases $P$, then every unilateral path switch and every operator step both decrease a common function. The joint dynamics therefore reach an $\eta$-equilibrium in finitely many improvement steps, where $\eta$ is the minimum improvement a session requires before switching. Alternating optimization and block minorization-maximization are exactly the monotone optimizers the RIS literature already uses. Examples include Beamforming Design with Fast Convergence for IRS-Aided Full-Duplex Communication and the mirror-ascent method of Weighted Sum-Rate Maximization for Multi-Hop RIS-Aided Multi-User Communications. Monotone improvement is all the argument needs, so global optimality of the non-convex beam problem is never required.

The same structure also gives an efficiency guarantee. Suppose social cost $C$ and potential satisfy $P \le C \le \alpha P$ for every capacity vector. That holds whenever each $\ell_e$ is non-decreasing in $n_e$, for example with $\alpha = 2$ when latency is linear in load. Because the sandwich holds for every $(w,\Phi)$, the joint potential minimizer costs at most $\alpha$ times the joint routing-plus-beamforming optimum. This is a Price of Stability bound: the price of stability compares the best equilibrium to the optimum. The bound carries over unchanged from fixed-capacity games to games with endogenous, interference-coupled, non-convex capacities.

Because the published latencies use $c^{\mathrm{rob}}$, the latency a session actually experiences is at most the published one. What remains open, and what the experiments measure, is how far local equilibria fall from this bound (the empirical Price of Anarchy) and how much the robustness margin $\epsilon$ costs.

Research Program

The theory component formalizes the claims above for three cases. The first is unit sessions on general graphs. The second is confluent routing, where paths may merge but never diverge again. We use the confluent case as a special case to reconnect with A Scalable Game-theoretic Approach to Urban Evacuation Routing and Scheduling and Islam et al.. Those papers proved polynomial-time convergence under deterministic costs, and we ask whether the polynomial bound survives an operator that re-tunes beams between moves. The third is a negative construction. We will show that if the operator instead maximizes weighted sum-rate, or if sessions react to per-round measured latencies drawn from the true, unknown channel, a small interference-coupled instance cycles.

The motivation for this negative result comes from the herding findings of Predictive Trip Planning - Smart Routing in Smart Cities and Combining Car-to-Infrastructure Communication and Multi-Agent Reinforcement Learning in Route Choice. Both show that reacting to shared, fluctuating information shifts bottlenecks rather than resolving them. Information Design for Regulating Traffic Flows under Uncertain Network State showed that a deliberately designed signal beats both no information and full information on a two-route network. Our robust published latency is a physically grounded version of such a signal on general graphs with atomic, unsplittable players.

We will also treat a family of operator objectives, $P + \beta(C - P)$. It interpolates between the potential, which guarantees stability, and social cost, which is more efficient but loses the potential structure. This lets us trace how much efficiency is traded for convergence.

The algorithm component builds the operator's step as robust alternating optimization. With surface phases fixed, the worst-case SINR constraints become linear matrix inequalities through the S-lemma, following Distributed Robust Multicell Coordinated Beamforming With Imperfect CSI: An ADMM Approach. We reuse its distributed ADMM decomposition across base stations and its worst-case-interference slack variables. With beams fixed, the unit-modulus phases are updated by a minorization step on the potential, adapting Weighted Sum-Rate Maximization for Multi-Hop RIS-Aided Multi-User Communications. That paper explicitly assumes perfect channel knowledge and fixed routes; we remove both assumptions.

Because the semidefinite relaxation is not guaranteed to return rank-one solutions, which the ADMM paper also flags, the operator step accepts a candidate only if its Gaussian-randomized rank-one extraction does not increase $P$. Otherwise it keeps the previous beams, which preserves monotonicity by construction.

Baselines

The naive reference point is shortest-path routing on nominal, fixed beams, with no re-optimization. Sessions take the path that looks fastest under beams designed once for uniform load from the estimated channel. It shows what one gets by doing nothing and anchors every gain we report.

The strongest existing competitor is a decoupled pipeline built from the best available pieces. Sessions route selfishly by best response. After each routing round, the operator runs the robust ADMM beamformer of Distributed Robust Multicell Coordinated Beamforming With Imperfect CSI: An ADMM Approach with its standard power-minimization or sum-rate-style objective, and sessions react to the resulting latencies. This is the pipeline a wireless engineer would assemble today, and it already contains the robustness ingredient. The only differences from our method are the operator's objective and the signal published to users, so it isolates our contribution. For reference, that paper reports that non-robust designs targeting 20 dB SINR fall as low as 5 dB, that its robust design is about 5 dBm more power-efficient than earlier restrictive approximations, and that it reaches the centralized solution in 20 to 50 iterations. We found no reported result on Lacuna for any joint selfish-routing-plus-beamforming system, so no published number exists for the end-to-end comparison.

The upper reference is the centralized joint optimum. It is computed on small instances by enumerating or branch-and-bounding path choices, with multi-start robust alternating optimization for beams at each routing. This is the denominator of both the Price of Anarchy and the Price of Stability.

All methods share the same topologies, channel draws, error radius $\epsilon$, the same per-round beam-iteration budget, and the same wall-clock limit. Beating the decoupled pipeline means three things: converging on every instance where it cycles; social cost no worse than its equilibria, when it does converge, at matched $\epsilon$; and a true-latency violation rate against published latency of zero, versus its positive rate.

Two ablations isolate the ingredients. The first keeps the robust channel model but changes the operator objective among potential, social cost, and sum-rate. The second keeps the potential objective but changes what is published: robust latency, nominal-estimate latency, or per-round measured latency.

Why not just…?

Why not just have the operator compute the joint system optimum and tell sessions which path to take? If sessions obeyed, this would be correct and we would not need a game. The setting here is sessions owned by parties who can deviate. For road traffic, AlphaRoute: Large-Scale Coordinated Route Planning via Monte Carlo Tree Search and Reconciling Selfish Routing with Social Good motivate restricting recommendations to equilibrium or near-equilibrium plans, because system-optimal plans impose detours that users reject. We will report the gap between our equilibria and the centralized optimum directly, so a reader can see what compliance would buy.

Why not just keep sum-rate beamforming and hope best-response routing settles anyway? This is the real threat. Coupled systems often converge in practice without a guarantee. The decoupled baseline tests it directly. If it converges on nearly all realistic instances with similar cost, our contribution shrinks to a guarantee plus a latency certificate. We will report this outcome honestly, and then search adversarially, via the small cycling constructions, for how rare the failures are.

Why not just publish nominal latencies with a fixed dB safety margin instead of solving a robust program? A uniform margin is stable and cheap. But a fixed margin cannot track the direction of the channel error. Leakage from zero-forcing depends on the specific interference geometry, which is why the ADMM paper sees a 20 dB target collapse to 5 dB for non-robust designs. We add the uniform-margin variant to the signal ablation, tuned so that its average published latency matches ours. The comparison is its violation rate and its cost against ours.

Why not just solve a fractional (splittable) routing problem and round? Splitting is not permitted for these sessions, as Rachelson et al. and Doriguzzi-Corin et al. show for packet reordering and stateful middleboxes. Approximation Algorithms for Minimizing Congestion in Demand-Aware Networks also shows that unsplittable congestion on mixed fixed and reconfigurable links cannot be approximated better than $\Omega(c_{\max}/c_{\min})$. Beamforming makes this capacity ratio large. Rounding also gives no equilibrium property to the rounded outcome. We still include randomized rounding of the fractional robust optimum as a centralized reference.

Proposed Experiments

We will run the multicell layouts used by the ADMM paper, 2 to 8 coordinated cells under Rayleigh fading. Each cell gets relay nodes, and some layouts add an RIS, so that sessions have multiple multi-hop paths. We will also use the aerial layout of Distributionally Robust Optimization for Aerial Multi-Access Edge Computing via Cooperation of UAVs and HAPs: 1 km by 1 km, drones at 100 m, a high-altitude platform at 20 km, with drones acting as relays for competing ground sessions. For scale, Jellyfish random regular graphs of 40 to 180 nodes from the demand-aware network paper serve as mesh topologies, with synthetic wireless channels placed on their edges. We will sweep the channel-error radius $\epsilon$, the number of sessions, and the number of RIS elements.

The decisive checks are three. First, the fraction of instances on which each method's dynamics cycle rather than converge, together with the number of switches until convergence. Our claim predicts zero cycling for the potential-aligned design, and positive cycling for sum-rate or measured-latency variants on interference-heavy layouts. Second, the empirical Price of Anarchy and Price of Stability against the centralized optimum on instances small enough to enumerate. The theory predicts the stability ratio stays below $\alpha$ even as coupling grows. Third, the rate at which true realized latency exceeds published latency, and the social-cost price of robustness as $\epsilon$ grows. Together these trace the curve between conservative-but-trustworthy and aggressive-but-unreliable signals.

The claim is refuted if any of three things happens. The potential-aligned operator fails to converge. The decoupled robust pipeline matches it in both convergence and cost across the sweep. Or the social-cost cost of potential alignment, measured through the $\beta$ interpolation, turns out large compared with its stability benefit.