Theorem 2 — the clairvoyant bound
ProvedProductFraming.Nest.theorem_2p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-framingupper-bound
In the product framing model with products, pages of capacity , revenues , a choice model and a page-count law on , let be the optimal revenue of an assortment of at most products. Then the optimal expected revenue of problem (1) is at most the revenue of a seller who knows in advance:
This upper bound, which is easy to compute, is the benchmark against which the approximation ratios of the paper are proved.
Formalization Note No assumption beyond the model of §3 is used (no A1, A3, or sign condition on ).
Preamble
import Mathlib import Definitions.Def_ProductFraming_Nest_Model
Formal statement
namespace ProductFraming.Nest
open Finset
/-- Theorem 2 (Gallego, Li, Truong, Wang 2020, p. 7): the clairvoyant bound `E[U(X)] ≥ V^OPT`. -/
theorem theorem_2 (n m p : ℕ) (hm : 1 ≤ m) (hp : 1 ≤ p) (r : Fin n → ℝ)
(P : Fin n → Finset (Fin n) → ℝ) (hP : IsChoiceModel P) (lam : ℕ → ℝ) (hlam : IsPageLaw m lam) :
Vopt n m p r P lam ≤ ∑ x ∈ Icc 1 m, lam x * U p r P x := by sorry
end ProductFraming.Nest
Source
Gallego, Li, Truong, Wang, Approximation Algorithms for Product Framing and Pricing, Operations Research (2020), DOI 10.1287/opre.2019.1875, authors' accepted manuscript, p. 7, Theorem 2 (proof p. 34)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.