Many shared-resource systems, such as radios sharing a spectrum band, mobile users offloading to an edge server, or jobs sharing a GPU cluster, are run as games. Each self-interested agent chooses its own action to minimize its own cost. A price attached to the shared limit (total interference, total capacity) steers the agents toward an outcome that respects that limit. Existing algorithms for these games make one of two assumptions. Either every agent computes its exact best response each round, which is itself an optimization problem solved by an inner iterative solver, or every agent takes one crude gradient step. Real agents do neither. They run a solver for as long as their time budget allows and then act. This note asks how precisely an agent must solve its own problem each round, and proposes a stopping rule that each agent can check locally. The rule should keep the game converging to the price-respecting equilibrium while spending far less inner computation than exact best responses and far fewer communication rounds than single-step play.
The central object is a generalized Nash equilibrium: a joint action from which no agent wants to deviate, given that the shared constraint must hold. We target the variational version, in which all agents face the same constraint price. We study it in the setting where no central coordinator holds the price. Each agent keeps its own estimate of the price and agrees on it with neighbors by averaging over a communication graph, which is the fully decentralized form of dual decomposition. We also let each agent's private problem be non-convex, as in joint sensing and power control. We then add a proximal term, a quadratic penalty on moving far from the last action. This makes each inner problem well behaved without pretending the original game is convex.
Core Claim
We claim that in monotone but non-potential games with shared linear constraints, one scheme converges to the variational equilibrium at the rate of the exact-best-response scheme, measured in communication rounds. The scheme combines three pieces: a proximal best response solved inexactly, a relative stopping rule, and neighbor averaging of prices. Its total inner computation should be within a logarithmic factor of what the exact rate requires. When local costs are only weakly convex (non-convex, but with curvature bounded below), a large enough proximal weight still gives convergence, now to a stationary equilibrium, a point satisfying every agent's first-order optimality conditions rather than a guaranteed best response.
Concretely, at round $k$ agent $i$ approximately solves
$$\min_{x_i \in X_i}\; f_i(x_i, x^k_{-i}) + (\lambda^k_i)^\top A_i x_i + \tfrac{\tau}{2}\|x_i - x^k_i\|^2 .$$
Here $f_i$ is its private cost, $x^k_{-i}$ are the others' last actions, $\lambda^k_i$ is its local price estimate, $A_i x_i$ is its contribution to the shared constraint $\sum_i A_i x_i \le b$, and $\tau>0$ is the proximal weight. The agent stops its inner solver at a candidate $\tilde x_i$ once
$$r_i(\tilde x_i) \;\le\; \sigma\,\|\tilde x_i - x^k_i\| \;+\; \theta\,\|\lambda^k_i - \bar\lambda^k_{\mathcal N_i}\| .$$
In this rule, $r_i$ is the inner problem's stationarity residual, $\bar\lambda^k_{\mathcal N_i}$ is the average of its neighbors' prices, and $\sigma<1$ and $\theta\ge 0$ are fixed constants. The first term says an agent need not solve precisely while its action is still moving a lot. The second says it need not solve more precisely than its price estimate currently disagrees with its neighbors'. Both quantities shrink as the system converges, so the tolerance tightens automatically and nobody needs a global iteration counter.
The mechanism behind the claim is standard. Under monotonicity, the exact proximal best-response map together with price ascent is a proximal-point step on the joint variational inequality in actions and prices, and such steps are firmly nonexpansive. Inexact proximal-point steps with relative errors keep this property up to a controllable constant. Our work is to show that consensus disagreement enters the analysis as an additional structured error that can be charged against the same budget.
Relation to Prior Work
Four lines of work motivate this proposal. Joint Sensing and Power Allocation in Nonconvex Cognitive Radio Games treats interference prices as a "virtual player" and proves existence, uniqueness and convergence of best-response schemes via variational inequalities. It assumes exact best responses, and its guarantees hold only in low-to-medium interference. We keep its pricing structure but drop exactness, and we test whether the proximal term extends convergence into denser interference. Convergence Rate of Generalized Nash Equilibrium Learning in Strongly Monotone Games with Linear Constraints gives rates for payoff-only learning with a dual virtual player and Tikhonov regularization, but each step is a single perturbation, not a multi-step inner solve. We sit between these two extremes. Efficient Multi-User Computation Offloading for Mobile-Edge Cloud Computing shows that offloading is a potential game, one whose equilibria are the stationary points of a single shared function, and that it converges under better-response dynamics. It also assumes accurate best responses, and it serves us as a control case, discussed below.
The inexactness techniques come from optimization. Inexact first-order primal-dual algorithms ties inner tolerance to the outer iteration count to preserve optimal rates. We replace the counter with locally observable residuals, because decentralized agents do not share a clock. Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates treats local SGD steps as inexact dual gradients and proves convergence for any number of local steps. IDEAL matches communication and computation lower bounds with inexact inner solvers. Both require a single smooth, strongly convex objective, so neither applies to a game without a potential function.
The non-convex side constrains the design. Penalty Dual Decomposition and An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints reach KKT points in non-convex problems, but they grow the penalty parameter without bound and rely on a central coordinator. Growing penalties would destabilize neighbor averaging, which is why we use a fixed proximal weight and dual ascent instead. Decentralized Resource Allocation via Dual Consensus ADMM supplies the neighbor-only price-agreement machinery, which we reuse. Its agents solve exact quadratic or cone programs every iteration, and that per-step cost is precisely the one we aim to cut.
Research Program
The theory has three parts. First, for strongly monotone games with linear shared constraints and a connected communication graph, we prove linear convergence of actions and averaged prices to the variational equilibrium under the stopping rule. The rate constant should depend on $\sigma$, $\theta$, $\tau$ and the graph's mixing rate. We also bound the total inner iterations by the outer round count times a logarithmic factor. This form is expected because a strongly convex inner problem solved by a linearly convergent method needs $\log(1/\text{tolerance})$ steps, and the tolerance shrinks geometrically. Second, for merely monotone games we prove sublinear convergence of a gap measure. Third, for weakly convex local costs we take $\tau$ larger than the curvature deficit and prove convergence to a stationary equilibrium, provided the price-to-equilibrium map is single-valued near the limit. We will state that condition explicitly rather than hide it.
Alongside the proofs we build a reference implementation. Each agent runs projected gradient or L-BFGS as its inner solver. Prices are averaged on ring, random-geometric and barbell graphs, and a central variational-inequality solver computes ground-truth equilibria for evaluation only. All-time feasibility, as in Achieving violation-free distributed optimization under coupling constraints, is out of scope. We will nonetheless report the maximum intermediate violation, because selfish agents acting on stale prices could overshoot the shared limit.
Baselines
The naive reference point is uncoordinated play: each agent best-responds with its price fixed at zero. This measures how much the shared constraint is violated without pricing and what throughput or fairness selfish agents obtain. A second naive point is single-step projected primal-dual gradient play, in which each agent takes exactly one gradient step per communication round and prices move by consensus plus ascent. This is the first-order analogue of the one-step updates in Tatarenko and Kamgarpour, and it has the lowest inner cost per round.
The strongest existing method on this question is exact best response with distributed pricing, as in Scutari et al.. We run it with inner solves driven to a residual of $10^{-10}$ and with the same price-averaging protocol. On the cognitive radio setup, that paper reports convergence "in fewer than 20 iterations" and "a sum-throughput gain of up to 80%" over methods that do not optimize sensing parameters. We will first reproduce these figures on our implementation to calibrate. Our method beats this baseline if it reaches the same distance to equilibrium, with the same final throughput and constraint satisfaction, in no more than 1.5 times its communication rounds while using at least 3 times fewer total inner gradient evaluations. A second strong competitor is a fixed decaying-tolerance schedule, with tolerance proportional to $1/k^{p}$ in the spirit of Chambolle et al.. We tune $p$ and the initial tolerance on a held-out instance with the same tuning budget we give our own $\sigma$ and $\theta$. Beating it means matching its round count with fewer inner evaluations, without per-instance retuning, across graph and interference changes. The third competitor is fixed-$K$ local steps as in Local ADA, with $K$ swept over $\{1, 2, 5, 10, 20\}$ and the best value per setting reported, which gives that baseline an advantage.
Two ablations isolate the key ingredients. Setting $\theta=0$ removes the consensus-disagreement term and shows whether tying tolerance to price disagreement matters. Setting $\tau=0$ in the non-convex and high-interference regimes shows whether the proximal term is what buys stability there.
Why not just…?
Why not just solve each best response exactly? On small cognitive radio instances this may be perfectly adequate, and Scutari et al. report fast convergence. The cost appears when inner problems are large, such as many subcarriers or many jobs per agent. Chambolle et al. show that early precision buys no outer rate, and dual consensus ADMM illustrates the per-step burden of exact cone solves. Our experiments measure total inner work at matched accuracy as the number of subcarriers grows. If exact solving is within 1.5 times our cost at the largest size, the claim fails for that domain and we will say so.
Why not just take one gradient step per round? This is the real threat, because single-step primal-dual play is simple and its cost per round is minimal. The open question is whether it pays for that in communication. In optimization, Local ADA found that multiple local steps reduce communication. In games, extra inner steps could instead amplify the effect of acting on stale actions from others. The fixed-$K$ sweep with $K=1$ included settles this directly. If $K=1$ matches our method in rounds, the stopping rule is unnecessary and the contribution shrinks to the non-convex stability result.
Why not just treat the game as an optimization and use IDEAL or Local ADA? When the game has a potential function, as the offloading game of Chen et al. does, its equilibria are stationary points of that function. Existing inexact decentralized dual methods then apply, and we expect them to be competitive. We therefore include a continuous-relaxation offloading game as a control, where we predict no advantage for our method. The advantage should appear only when cross-interference is asymmetric and no potential exists. Showing this split is part of the result, not a caveat.
Proposed Experiments
The primary testbed is the frequency-selective interference-channel cognitive radio setup of Scutari et al.. It has 10 to 15 secondary users with a shared primary-user interference limit. We sweep cross-interference strength from their low regime into densities where their uniqueness guarantee no longer holds, and we sweep the number of subcarriers from 16 to 1024 to scale inner-problem size. The joint sensing and power problem gives weakly convex local costs.
The second testbed is a GPU-sharing game built on the Gavel traces and the POP codebase. Jobs are players with concave throughput utilities over heterogeneous accelerator types, subject to shared per-type capacity. The game is non-potential when jobs weight each other's slowdowns asymmetrically. Here the centralized POP solution provides a quality reference. POP reports staying "within 1.5% of the optimal solution quality," and we report our equilibrium's gap to the centralized social optimum alongside it. We do so knowing that an equilibrium need not match a social optimum, so the gap measures the cost of selfishness rather than solver error.
The third testbed is the potential-game control based on Chen et al., relaxed to continuous offloading fractions. Their reported "within 12-14% of the centralized global optimum" and "70 decision slots" for 50 users concern the discrete game and are cited only for context, not as a direct comparison. For inexact-best-response schemes on any of these testbeds, no reported result was found on Lacuna.
Metrics are the same across testbeds: distance to the centrally computed equilibrium, communication rounds, total inner gradient evaluations, maximum intermediate constraint violation, and final throughput or completion-time utility. Each configuration is run on 20 random instances and three graph topologies.
Three checks decide the proposal. First, in the non-potential cognitive radio and GPU games, the adaptive rule must dominate both exact best response and the best fixed-$K$ baseline on inner work at matched rounds. Second, beyond Scutari's interference regime, the variant with $\tau>0$ must converge where the $\tau=0$ ablation and exact best response oscillate. Third, in the potential-game control, we expect IDEAL or Local ADA applied to the potential to match our method. If they instead beat it clearly, the proximal game formulation carries an overhead that the non-potential gains must be weighed against.
References
- Joint Sensing and Power Allocation in Nonconvex Cognitive Radio Games: Nash Equilibria and Distributed Algorithms
- Convergence Rate of Generalized Nash Equilibrium Learning in Strongly Monotone Games with Linear Constraints
- Efficient Multi-User Computation Offloading for Mobile-Edge Cloud Computing
- Inexact first-order primal-dual algorithms
- Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates
- IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
- Penalty Dual Decomposition Method For Nonsmooth Nonconvex Optimization
- An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
- Decentralized Resource Allocation via Dual Consensus ADMM
- Achieving violation-free distributed optimization under coupling constraints
- Solving Large-Scale Granular Resource Allocation Problems Efficiently with POP