Proof of Theorem 2, p. 88 — sample-path concavity: V₀((k₁+k₂, l)) − V₀((k₁, l)) ⩾ V₀((k₁+k₂+k₃, l)) − V₀((k₁+k₃, l))
ProvedSubstOverbooking.Structure.samplePath_concaveconcavityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1transportation-problem
Fix and capacities (). For every , every class and all ,
The increments of along one coordinate are nonincreasing. This is the pointwise inequality which, after taking expectations, gives the componentwise concavity (6) of .
Formalization Note. The paper uses this at integer realizations for ; it is stated here for real nonnegative points and general (with playing the role of ), which contains the paper's case.
Preamble
import Mathlib import Definitions.Def_SubstOverbooking_Structure_Setting
Formal statement
namespace SubstOverbooking.Structure
theorem samplePath_concave {n m : ℕ} (a : Fin n → Fin (m + 1) → ℝ) (c : Fin (m + 1) → ℝ)
(hc : ∀ j, j ≠ 0 → 0 ≤ c j) (z : Fin n → ℝ) (hz : ∀ k, 0 ≤ z k) (i : Fin n)
(k₂ k₃ : ℝ) (hk₂ : 0 ≤ k₂) (hk₃ : 0 ≤ k₃) :
V0 a c (z + Pi.single i (k₂ + k₃)) - V0 a c (z + Pi.single i k₃) ≤
V0 a c (z + Pi.single i k₂) - V0 a c z := by sorry
end SubstOverbooking.Structure
Source
Karaesmen & van Ryzin, Overbooking with Substitutable Inventory Classes, Operations Research 52(1):83–104 (2004), p. 88, proof of Theorem 2, display before 'Taking expectations'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.