Theorem 3 —
ProvedProductFraming.Nest.theorem_3Consider the product framing problem with products, pages of capacity , nonnegative revenues , a choice model satisfying Assumption A1, and a page-count law on that is NBUE (Assumption A3). For each let be any run of NEST() (with an exact solution of problem (2), i.e. A2 with ), and let be the best expected revenue among the framings these runs display. Then
This is the main result of the paper on product framing: NEST earns at least of the optimal expected revenue, although problem (1) is NP-hard.
Formalization Note The guarantee is stated for every choice of the runs, since the algorithm's choices are arbitrary; that runs exist is a separate milestone. The hypothesis is added (unit revenues; Lemmas 1 and 2 need it). A2 is used with , as in the paper; with the paper states that the bound scales by , which is not formalized. Pages are 1-based and "not displayed" is page .
import Mathlib import Definitions.Def_ProductFraming_Nest_Model import Definitions.Def_ProductFraming_Nest_Algorithm
namespace ProductFraming.Nest
open Finset
/-- Theorem 3 (Gallego, Li, Truong, Wang 2020, p. 10): under A1, A2 with `ε = 0` and A3,
`V^{NEST} ≥ (6/π²) V^{OPT}`, for every choice of the NEST(y) runs `runs y`, `y ∈ [m]`. The
hypothesis `0 ≤ r` is added. -/
theorem theorem_3 (n m p : ℕ) (hm : 1 ≤ m) (hp : 1 ≤ p) (r : Fin n → ℝ) (hr : ∀ i, 0 ≤ r i)
(P : Fin n → Finset (Fin n) → ℝ) (hP : IsChoiceModel P) (hA1 : SatisfiesA1 P)
(lam : ℕ → ℝ) (hlam : IsPageLaw m lam) (hA3 : IsNBUE m lam)
(runs : ℕ → ℕ → Finset (Fin n)) (hruns : ∀ y ∈ Icc 1 m, IsNestRun p r P y (runs y)) :
6 / Real.pi ^ 2 * Vopt n m p r P lam ≤ VNEST hm r P lam runs := by sorry
end ProductFraming.Nest
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.