Theorem 1, p. 87 — on a product of subsets of ℝ, f is submodular iff f has decreasing differences
ProvedSubstOverbooking.Structure.theorem1_submodular_iff_decreasingDifferencesdecreasing-differenceslatticep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodularity
Let and , and let . Then is submodular on , i.e.
if and only if has decreasing differences on in the sense of Definition 1.
This equivalence, quoted by the paper from Sundaram (1996), is what turns the pairwise inequality (7) into submodularity of the expected net revenue.
Formalization Note. The paper states the theorem for an arbitrary . As printed it is false: on decreasing differences holds trivially (only zero increments stay in ), while the lattice inequality compares with and fails for suitable . The statement is therefore made for product sets , which covers every set the paper applies it to ( and ). Submodularity of is supermodularity of (platform SupermodularOn).
Preamble
import Mathlib import Definitions.Def_SubstOverbooking_Structure_Setting import Definitions.Def_Supermodularity_Monotonicity_SupermodularOn
Formal statement
namespace SubstOverbooking.Structure
theorem theorem1_submodular_iff_decreasingDifferences {n : ℕ} (T : Fin n → Set ℝ)
(f : (Fin n → ℝ) → ℝ) :
Supermodularity.Monotonicity.SupermodularOn (fun s => - f s) (Set.pi Set.univ T) ↔
DecreasingDifferencesOn f (Set.pi Set.univ T) := by sorry
end SubstOverbooking.Structure
Source
Karaesmen & van Ryzin, Overbooking with Substitutable Inventory Classes, Operations Research 52(1):83–104 (2004), p. 87, Theorem 1 (after Sundaram 1996)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.