§4.2, NEST(y) step 2 — a run of NEST(y) always exists
ProvedProductFraming.Nest.nest_run_existsapproximation-algorithmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-framing
Let be a choice model satisfying Assumption A1, let , and let . For every there are sets forming a run of NEST(): is an optimal solution of problem (2) with bound , and for ,
The paper asserts this right after the description of the algorithm ("Lemma 1 ensures that we can always find such a set "). It shows that the guarantee of Theorem 3, which is stated for every run, is not about an empty set of runs.
Formalization Note The hypothesis is added, as for Lemma 1.
Preamble
import Mathlib import Definitions.Def_ProductFraming_Nest_Model import Definitions.Def_ProductFraming_Nest_Algorithm
Formal statement
namespace ProductFraming.Nest
open Finset
/-- §4.2, NEST(y) step 2, p. 9 (Gallego, Li, Truong, Wang 2020): "Lemma 1 ensures that we can always
find such a set S(x)." Every NEST(y), `y ∈ [m]`, has a run. The hypothesis `0 ≤ r` is added. -/
theorem nest_run_exists (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) :
∀ y ∈ Icc 1 m, ∃ S : ℕ → Finset (Fin n), IsNestRun p r P 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, §4.2, NEST(y) step 2, p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.