Lemma 14, p. 17 — maximum availability in the m-unit system: A_m(q) = r_max·G_{m−1}/G_m ≥ m/(m+n−1)
ProvedSharedVehicleApprox.Pricing.lemma_14approximation-ratioavailabilityclosed-queueing-networkp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , and let be a vector of traffic intensities, with some . Write , , and let be the product-form law (4), on . Then the maximal availability under satisfies
This is the pullback step of the framework: by Lemma 12, is the ratio of the -unit to the infinite-unit objective, so the bound transfers infinite-unit guarantees to the -unit system.
Differences from the source:
- generalization: "for any state-independent pricing policy q", with r = r(q) = w(q)/µ(q) → any r with r_j ≥ 0 for all j and r_j > 0 for some j; reason: every traffic intensity vector r(q) (w an invariant distribution, µ_i > 0) is nonnegative with a positive entry, so the statement specializes to r(q)
- encoding: A_m(q), the maximum availability of the m-unit system under q → max_i of the availabilities under productForm (r_j^y) m, the law (4); reason: by Theorem 2 the stationary law of q is (4) with r = r(q); the ratio is stated with m ≥ 1 since G_{m−1} needs it
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 14, p. 17: for `m ≥ 1` and every nonnegative vector `r` of traffic intensities with
some positive entry, the maximal availability under the product-form law (4) is
`A_m = r_max · G_{m−1} / G_m`, and it is at least `m / (m + n − 1)`. -/
theorem lemma_14 {n m : ℕ} [NeZero n] (hm : 1 ≤ m) (r : Fin n → ℝ) (hr : ∀ j, 0 ≤ r j)
(hpos : ∃ j, 0 < r j) :
univ.sup' univ_nonempty (fun i => availability m (productForm (fun j y => r j ^ y) m) i) =
rmax r * G r (m - 1) / G r m ∧
(m : ℝ) / ((m : ℝ) + n - 1) ≤ rmax r * G r (m - 1) / G r m := by sorry
end SharedVehicleApprox.Pricing
Source
Banerjee, Freund & Lykouris, Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework, arXiv:1608.06819v4, p. 17 (PDF 18), Lemma 14; proof pp. 17–18 (PDF 18–19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.