Section 4.3.1 — the externality decomposition of
ProvedKellyStochasticNetworks.queueing_network_delay_derivConsider an open network of queues in which a route is a set of queues a customer must traverse. Queue has service rate , customers on route arrive at rate , and the mean sojourn time at queue is with , which is the behaviour of a network of /M/1 queues. If a unit delay of a customer on route costs , the mean cost per unit time is
Suppose every queue is stable, . Then is differentiable in the arrival rate on route , with
This is an exact derivative, not an approximation, and its two terms separate the private cost from the externality: one extra customer on route is delayed at each queue on its route, and it also delays every other customer passing through those queues. The decomposition is what licenses shifting traffic towards routes with smaller derivatives, and it is the same accounting that makes a marginal-cost toll align selfish routing with the social optimum.
Formalization Note The derivative in is stated as an ordinary derivative of the function obtained by varying the -th coordinate of and holding the others fixed, so no partial-derivative API is presupposed. Sums over the queues of a route are written as sums over all queues weighted by the incidence matrix, whose entries are or . The stability hypothesis is what keeps every denominator away from zero.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop
namespace KellyStochasticNetworks
theorem queueing_network_delay_deriv {J R : ℕ} (A : Fin J → Fin R → ℝ) (w ν : Fin R → ℝ)
(φ : Fin J → ℝ) (hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(hstab : ∀ j, (∑ r', A j r' * ν r') < φ j) (r : Fin R) :
HasDerivAt (fun t : ℝ => queueingCost A w (Function.update ν r t) φ)
(∑ j, A j r * (w r / (φ j - ∑ r', A j r' * ν r')
+ ∑ r', A j r' * (ν r' * w r') / (φ j - ∑ r'', A j r'' * ν r'') ^ 2))
(ν r) := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.