Lemma 1 — removing one product does not lower per-product revenue
ProvedProductFraming.Nest.lemma_1assortment-optimizationchoice-modelp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-framing
Let be a choice model satisfying Assumption A1 and let the revenues be nonnegative, . For every set with there is a product such that
that is, .
The paper cites this result from Davis, Topaloglu and Williamson (2015). It guarantees that step 2 of NEST() can always be carried out.
Formalization Note The hypothesis is added: the paper speaks of unit revenues, and the lemma fails for negative ones (for , , , the left side is and the right side ). is S.erase i, and cardinalities are cast to before subtracting.
Preamble
import Mathlib import Definitions.Def_ProductFraming_Nest_Model
Formal statement
namespace ProductFraming.Nest
open Finset
/-- Lemma 1 (Davis et al. 2015; Gallego, Li, Truong, Wang 2020, p. 8): for any `S` with `|S| ≥ 2`
there is `i ∈ S` with `R(S \ {i}) / (|S| − 1) ≥ R(S) / |S|`. The hypothesis `0 ≤ r` is added
(the lemma fails for negative revenues). -/
theorem lemma_1 (n : ℕ) (r : Fin n → ℝ) (hr : ∀ i, 0 ≤ r i) (P : Fin n → Finset (Fin n) → ℝ)
(hP : IsChoiceModel P) (hA1 : SatisfiesA1 P) (S : Finset (Fin n)) (hS : 2 ≤ S.card) :
∃ i ∈ S, R r P S / (S.card : ℝ) ≤ R r P (S.erase i) / ((S.card : ℝ) - 1) := 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. 8, Lemma 1 (Davis et al. 2015)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.