Delayed Prices, Private Agents: Stability and Privacy Cost of Price-Based Coordination Over Slow Networks

Many coordination problems, such as scheduling electric-vehicle charging under a shared transformer limit, are solved without anyone revealing their plans. Agents exchange only a "shadow price," a number that rises when a shared resource is overused. Each agent privately picks its own consumption in response. This keeps departure times, battery sizes and preferences hidden. The analyses of these schemes, however, assume that prices reach every agent instantly.

On a real network, prices arrive late. Agents then respond to stale prices, and the next price corrects for demand that has already moved. This is a delayed negative-feedback loop, the textbook recipe for oscillation. This note argues that the delay does more than threaten stability. Through a single tuning knob, the price step size, it also raises the privacy cost of coordinating. To survive delay, the price must move more cautiously. Cautious prices need more rounds to converge. Every extra round of released prices spends more of the privacy budget and gives an eavesdropper more trajectory to reconstruct private data from. We propose to measure this coupling, derive its shape, and test whether delay compensation can break it at no extra privacy cost. The compensation uses only prices that have already been published.

Core Claim

Consider the dual update in Dual decomposition for multi-agent distributed optimization with coupling constraints. That paper has agents exchange only dual variables, keeps primal decisions private, and reaches dual consensus on a 100-vehicle charging benchmark. Linearize it around the optimum, with a step size $\gamma$ and aggregate demand sensitivity $h>0$. With a delay of $k$ rounds, the price error $e$ then obeys

$$e_{t+1} = e_t - \gamma h \, e_{t-k}.$$

For this scalar delay-difference equation it is known that $e_t \to 0$ if and only if

$$0 < \gamma h < 2\sin\!\left(\frac{\pi}{2(2k+1)}\right),$$

so the largest stable step shrinks roughly as $\pi/(2k)$. This is the discrete analogue of the result in Dynamics of Analog Neural Networks with Time Delay. That paper showed that delay turns negative-feedback modes, harmless without delay, into Hopf oscillations once gain times delay crosses a threshold. Dual ascent on a coupling constraint is exactly such a negative-feedback mode.

Convergence takes on the order of $1/(\gamma h)$ rounds, so the number of rounds grows roughly linearly with the delay $k$. Now suppose prices carry Gaussian noise for formal differential privacy, meaning a guarantee that the released prices change little in distribution when one agent's private data changes. Under standard composition, the total privacy loss then grows with the number of rounds. Delay therefore translates directly into privacy spent. Our claim has two parts. The first is that this chain (delay, then smaller safe step, then more rounds, then more leakage) holds quantitatively on realistic heterogeneous-delay networks. The second is that a price predictor built purely from already-released prices recovers most of the lost step size. Differential privacy is preserved under post-processing, so such a predictor is privacy-free by construction.

Relation to Prior Work

Two papers supply the coordination method we build on and motivate the gap. Dual decomposition for multi-agent distributed optimization with coupling constraints exchanges only dual variables over time-varying graphs. A Fully Distributed Approach for Plug-in Electric Vehicle Charging does the same peer-to-peer with a consensus-plus-innovation update. Both assume synchronous, delay-free rounds, and the second explicitly leaves delays as future work. Neither gives a formal privacy guarantee against someone reading the price history. We keep their mechanism and add both missing elements.

Delay theory supplies the analysis. Dynamics of Analog Neural Networks with Time Delay gives critical-delay criteria, but only for uniform delays. We extend the question to long-tailed, heterogeneous link delays, where closed forms are unavailable and numerical spectral analysis is needed. The work on delayed predictive coding in Alpha oscillations and traveling waves: Signatures of predictive coding? shows that delayed error-correcting loops ring at a period set by the delay. We use this as a qualitative warning: privacy noise injected near that period is amplified rather than averaged out. We measure this amplification rather than assume it.

The privacy literature constrains the design. Differential Privacy for Stackelberg Games shows that naive noise destroys feasibility of coupled physical constraints, and restores feasibility with an optimization-based "fidelity" projection. We use that projection as a baseline component, not as our contribution. Privacy Leakage of Search-Based Multi-Agent Planning Algorithms measures leakage as the shrinkage of the set of private models consistent with what was communicated. We adapt this idea into an empirical reconstruction attack on price trajectories.

The closest work joining delay and multi-agent coordination is DACOM: Learning Delay-Aware Communication for Multi-Agent Reinforcement Learning. It learns how long to wait for late messages among fully cooperative agents sharing raw embeddings, and has no privacy model. QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits does combine delay with local differential privacy. However, it works in memoryless bandits, where delay adds only an additive regret penalty and there is no feedback loop to destabilize. Our setting is the one both leave out: a continuous feedback loop whose stability and privacy cost are governed by the same parameter.

Research Program

The work has three parts. The first is analysis. We extend the scalar bound above to the multi-constraint, heterogeneous-delay case by linearizing around the optimum and computing the spectrum of the delayed closed-loop operator. The operator's modes correspond to active coupling constraints, and on this benchmark only a few constraints are active (3 of 48 in Falsone et al.). From this spectrum we obtain two quantities. One is the largest stable step. The other is a noise-amplification factor: the closed-loop variance of demand per unit of injected price noise. This factor diverges as the step approaches the stability boundary.

The second part is the mechanism. Each agent fits a low-order linear predictor to the stale price stream it has received and acts on the extrapolated price rather than the stale one. This is a Smith-predictor-style correction that uses only public information. A second variant also lets an agent correct for its own in-flight demand. That variant uses private state, but it only changes the agent's own action. Its effect on released prices therefore passes through the already-privatized aggregation step, and the formal guarantee still holds. We will verify this argument carefully.

The third part is accounting. Prices are released with Gaussian noise calibrated to per-vehicle sensitivity, and we track cumulative privacy loss with standard composition. Alongside the formal bound, we run an empirical attack. The attacker is a learned model that infers a target vehicle's departure time and battery size from the price trajectory. We report its accuracy gain over the prior, in the spirit of the min-entropy leakage measure of Stolba et al.

The operating regime matters and we fix it explicitly. The test case is receding-horizon real-time charging. Price rounds run within each 15-minute interval, and vehicles draw power continuously while prices are updated. In this regime stale prices produce real transformer load, which is where delay can hurt.

Baselines

The naive reference is uncoordinated charging, in which each vehicle charges at full rate on arrival. The cited PEV papers use this as the setting where transformer limits are violated. It defines the worst-case peak.

The strongest existing method is Falsone et al.'s dual decomposition, run unchanged over our delayed channels at its published step-size schedule. This is the method whose delay-free behavior is documented: dual consensus within 1000 iterations with 3 of 48 coupling constraints correctly identified as active. We also run CI-PEVCC from Carli et al., whose delay-free run reports relative error 0.0028 within about 2,000 iterations at 0.004 s per iteration. For neither method did we find any reported result under communication delay on Lacuna. We therefore establish those numbers ourselves.

The fairest and most dangerous competitor is the same dual decomposition with its step size retuned by grid search. The retuning is done for each delay distribution, to the best stable value. It gets the same tuning budget, number of random seeds, noise level and delay traces as our method.

For the privacy dimension, every method is also run with Gaussian-noised prices, with and without the fidelity projection of Differential Privacy for Stackelberg Games. In its own coupled-grid testbed that projection raised feasibility from 4.47% under naive Laplace noise to over 91%. A barrier-synchronized variant waits for all messages each round. It shows what delay-free iterations cost in wall-clock time.

The key ablation removes the predictor while keeping the retuned step. This isolates whether compensation, and not tuning, drives any gain. Beating the baselines means the following. At matched privacy loss and delay distribution, our method must reach the same cost suboptimality with fewer rounds and fewer transformer-limit violations. Alternatively, at matched rounds it must spend measurably less privacy budget and give lower attacker accuracy. The comparison is against the retuned-step baseline, not just the published schedule.

Why not just…?

Why not just shrink the step size until the loop is stable? This is the real threat. It is also exactly the phenomenon we claim has a hidden cost. The bound above says the safe step falls roughly as $1/k$, so rounds grow with delay, and privacy loss grows with rounds. The retuned-step baseline measures this directly. If its privacy loss at convergence barely grows with delay, for example because only a few slow modes matter, our central claim fails. We would then report that result rather than argue around it.

Why not just synchronize with barriers so every round is delay-free? In day-ahead scheduling, barriers are probably the right answer, and we will say so. In real-time operation, vehicles draw load between rounds. A round then lasts at least as long as the slowest link, so prices lag load by the same amount a barrier was meant to hide. DACOM reports that fixed waiting timers raised collision rates and lowered arrival rates in its intersection task (DACOM). That evidence comes from a different setting. Our barrier baseline tests whether the same cost appears as transformer violations.

Why not just add standard noise and project back to feasibility? Projection fixes feasibility of each released answer. It does nothing about the closed loop amplifying noise near its resonance, and nothing about the number of rounds. We run projection as an add-on to every method, so the experiment shows whether it alone closes the gap.

Proposed Experiments and Decisive Checks

The main testbed is the 100-vehicle MATSim Switzerland and Zurich winter-load charging setup used by both PEV papers. Delays are drawn per link from long-tailed distributions with means from zero to several rounds. A secondary check reuses the coupled IEEE 36-bus and gas testbed from the Stackelberg privacy paper, to see whether the trade-off survives a hierarchical structure.

We measure five things. They are the peak transformer overload, cost suboptimality relative to the centralized optimum, rounds and wall-clock time to a fixed tolerance, cumulative privacy loss, and attacker accuracy gain.

Three checks decide the project. The first is whether the predicted stability boundary, computed from the linearized spectrum, matches the empirical onset of price oscillation across delay distributions. The second is whether rounds-to-convergence and privacy loss for the retuned baseline grow with delay as predicted. The third is whether the post-processing predictor shifts the boundary enough to cut privacy loss at matched accuracy, without increasing attacker success.

If the first check fails, the analysis must be revised. If the second fails, the trade-off is not real. Only if both hold does the third test whether compensation is worth deploying.