Theorem 3.2 — revenue-ordered assortments earn
ProvedRevenueOrdered.UDPmin.revenue_ordered_ratio_boundapproximation-algorithmsassortment-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management
Let be a regular discrete choice model on a finite nonempty product set , and a revenue function whose distinct values are ; put . Then the revenue-ordered value , , satisfies
That is, revenue-ordered assortments approximate the optimum to within a factor , .
This is the guarantee that Corollary 4.7 transfers to uniform pricing through Theorem 4.6.
Formalization Note The approximation factor is stated in product form, , rather than as a ratio. This item restates, for this mission's own copy of the model, the goal theorem of mission I of the series (RevenueOrdered.Ratio.revenue_ordered_ratio_bound).
Preamble
import Mathlib import Definitions.Def_RevenueOrdered_UDPmin_Model
Formal statement
namespace RevenueOrdered.UDPmin
/-- Theorem 3.2 (Berbeglia–Joret, arXiv:1606.01371v3, p. 8), for an arbitrary regular choice
model: `OPT ≤ (∑_{i=1}^{k} (r_i − r_{i−1})/r_i) · RO` and `∑_{i=1}^{k} (r_i − r_{i−1})/r_i ≤
1 + ln(r_k/r_1)`, with `r_0 := 0`. -/
theorem revenue_ordered_ratio_bound {C : Type*} [Fintype C] [DecidableEq C] [Nonempty C]
(P : C → Finset C → ℝ) (hP : IsRegular P) (r : C → ℝ) (hr : ∀ x, 0 < r x) :
RevenueOrdered.Ratio.opt P r ≤ ratioSum r * ro P r ∧
ratioSum r ≤ 1 + Real.log (rMax r / rMin r) := by sorry
end RevenueOrdered.UDPmin
Source
Berbeglia & Joret, Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments, arXiv:1606.01371v3, p. 8, Theorem 3.2 (proof pp. 8–9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.