Online Supplement A, pp. 33–34 — the claim ŷ_i ≥ V_i(S*_i)^γ_i (R_i(S*_i) − ẑ)
ProvedConstrNestedLogit.UpperBound.claimConsider the nested logit model with no-purchase weight , preference weights , arbitrary revenues , dissimilarity parameters and no within-nest no-purchase weight. Let be space requirements and capacities with for every product (the paper's standing assumption, p. 8), and let be finite sets of vectors such that every vector of is feasible for the linear programming relaxation of the knapsack problem (10) of nest , and for every some vector of is optimal for that relaxation at . Let be an assortment with for every nest. If is a feasible solution of the linear program (13) built on the sets , then
This is the claim at the heart of the proof of Proposition 7; summing it over the nests and using the first constraint of (13) gives the upper bound.
Formalization Note The paper states the claim for an optimal solution of (13) and an optimal assortment of problem (1); the statement here is for every feasible and every feasible assortment, which is what the proof uses. Positivity of , and is added; is the paper's standing assumption (p. 8); is the paper's model.
import Mathlib import Definitions.Def_NestedLogitVariants_General_Model import Definitions.Def_NestedLogitVariants_General_Relaxation import Definitions.Def_ConstrNestedLogit_UpperBound_Relaxation import Definitions.Def_ConstrNestedLogit_UpperBound_LP13 open NestedLogitVariants.General
namespace ConstrNestedLogit.UpperBound
/-- Online Supplement A, the claim in the proof of Proposition 7 (pp. 33–34): if the vectors `X i`
are feasible for the linear programming relaxation of (10) and include an optimal solution of that
relaxation for every `u ≥ 0`, then every feasible solution `(z, y)` of the linear program (13)
satisfies `y_i ≥ V_i(S_i)^{γ_i} (R_i(S_i) − z)` for every nest `i` and every assortment
`(S_1, …, S_m)` that satisfies the space constraints. -/
theorem claim {ι : Type*} [Fintype ι] {n : ℕ} (I : Instance ι n)
(hvnp : ∀ i, I.vnp i = 0) (hv0 : 0 < I.v0) (hv : ∀ i j, 0 < I.v i j)
(hγ : ∀ i, 0 < I.γ i ∧ I.γ i ≤ 1)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (X : ι → Finset (Fin n → ℝ))
(hw : ∀ i j, 0 < w i j) (hwc : ∀ i j, w i j ≤ c i)
(hX : IsRelaxSolutionFamily I w c X)
(S : ι → Finset (Fin n)) (hS : ∀ i, SpaceFeasible w c i (S i))
(z : ℝ) (y : ι → ℝ) (hzy : LP13Feasible I X z y) :
∀ i, nestWeight I i (S i) * (R I i (S i) - z) ≤ y i := by sorry
end ConstrNestedLogit.UpperBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.