Proposition 1 —
ProvedProductFraming.Nest.proposition_1approximation-algorithmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-framing
In the product framing model with , a choice model and a page-count law on , let and let be any run of NEST(). Then the expected revenue of the framing the run displays satisfies
Taking the best gives , the lower bound that is compared with Theorem 2.
Formalization Note The statement holds for every run, and needs neither A1, A3 nor a sign condition on . .
Preamble
import Mathlib import Definitions.Def_ProductFraming_Nest_Model import Definitions.Def_ProductFraming_Nest_Algorithm
Formal statement
namespace ProductFraming.Nest
open Finset
/-- Proposition 1 (Gallego, Li, Truong, Wang 2020, p. 9):
`V^{NEST(y)} ≥ (U(y)/y) E[min(X, y)]` for all `y ∈ [m]` and every run of NEST(y). -/
theorem proposition_1 (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) :
∀ y ∈ Icc 1 m, ∀ S : ℕ → Finset (Fin n), IsNestRun p r P y S →
U p r P y / (y : ℝ) * Emin m lam (y : ℝ) ≤ VNest m r P lam y S := 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. 9, Proposition 1 (proof pp. 34–35)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.