Proposition 4.4: with Poisson show demands, the expected net revenue G(x) of (4.21) is component-wise concave and submodular in the overbooking levels x
ProvedRevenueManagement.joint_overbooking_concave_submodularoperations-researchoverbookingpoissonrevenue-managementsubmodularitytransportation-problem
In the substitutable-capacity model with nonnegative capacities and show demands independent across classes, , the expected net revenue of (4.21) has decreasing first differences in every direction: for all levels and all classes , . With this is component-wise concavity in , and with submodularity in .
Formalization Note The book prints $G(x) = p^\top(x-y) - \mathbb E[s^\top(x - Z(x))]
- \mathbb E[V(Z(x), C)]V+\mathbb E[V(Z(x), C)]$.
Preamble
import Definitions.Def_RevenueManagement_overbooking
Formal statement
namespace RevenueManagement
theorem joint_overbooking_concave_submodular {n m : ℕ} (h : Fin n → Fin (m + 1) → ℝ)
(Cap : Fin (m + 1) → ℝ) (hCap : ∀ i, 0 ≤ Cap i) (p s q : Fin n → ℝ) (hq : ∀ j, 0 ≤ q j)
(y x : Fin n → ℕ) (i j : Fin n) :
expNetRevenue h Cap p s q y (x + Pi.single i 1 + Pi.single j 1) -
expNetRevenue h Cap p s q y (x + Pi.single i 1) ≤
expNetRevenue h Cap p s q y (x + Pi.single j 1) - expNetRevenue h Cap p s q y x := by sorry
end RevenueManagement
Source
Kalyan T. Talluri and Garrett J. van Ryzin, The Theory and Practice of Revenue Management, Kluwer/Springer 2004, DOI 10.1007/b139000, p. 164, Proposition 4.4 ('the function G(x) defined by (4.21) is component-wise concave in each xj and submodular in x. That is, letting ej denote the jth unit vector, for all j, the first differences G(x + ej) − G(x) are decreasing')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.