Lemma 3, p. 9 — availability in product-form networks: A_i,m = (Z_{m−1}/Z_m)·r_i when ρ_i(y) = r_i^y
ProvedSharedVehicleApprox.Pricing.lemma_3availabilityclosed-queueing-networkp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1product-form
Consider a product-form network with units, nodes and functions , whose law is
and off . If node has for all , then its availability is
With Theorem 2 this expresses the availabilities of a state-independent policy through the Gordon–Newell constants, .
Formalization Note The law is productForm ρ m of the reused closed-network module; it divides by , and Lean's makes both sides when .
Differences from the source:
- generalization: functions ρ_j : ℕ → ℝ_+ (nonnegative, p. 9) → arbitrary real functions ρ_j, Z_m possibly 0; reason: the identity holds for every real ρ_j (both sides are 0 when Z_m = 0), so it specializes to nonnegative ρ_j
- encoding: a product-form network whose stationary distribution is π(x) = Z_m⁻¹ Π_j ρ_j(x_j) → π := productForm ρ m; reason: the lemma uses the network only through this law
- encoding: m units, Z_{m−1} → hypothesis 1 ≤ m; reason: S_{n,m−1} and Z_{m−1} are defined only for m ≥ 1 (ℕ subtraction)
Preamble
import Mathlib import Definitions.Def_QueueingFundamentals_Networks_ClosedJackson import Definitions.Def_SharedVehicleApprox_Pricing_Model open Finset QueueingFundamentals.Networks Filter Topology
Formal statement
namespace SharedVehicleApprox.Pricing
/-- Lemma 3, p. 9: in a product-form network with `m ≥ 1` units and functions `ρ_j`, if
`ρ_i(y) = r_i^y` then the availability of node `i` under the product-form law
`π(x) = Z_m⁻¹ ∏_j ρ_j(x_j)` is `A_i,m = (Z_{m−1}/Z_m) · r_i`. -/
theorem lemma_3 {n m : ℕ} (hm : 1 ≤ m) (ρ : Fin n → ℕ → ℝ) (i : Fin n) (r : ℝ)
(hρ : ∀ y, ρ i y = r ^ y) :
availability m (productForm ρ m) i = normConst ρ (m - 1) / normConst ρ m * r := by sorry
end SharedVehicleApprox.Pricing
Source
Banerjee, Freund & Lykouris, Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework, arXiv:1608.06819v4, p. 9 (PDF 10), Lemma 3, Eq. (5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.