Theorem 2: the LP-stitched assortment is best among candidate combinations
ProvedConstrNestedLogit.Stitch.theorem_2For each nest , let be a finite collection of candidate assortments. Suppose is an optimal solution of linear program (4), which minimizes subject to and for every . In each nest, choose a candidate that maximizes . Then
Thus one LP optimum and independent nestwise maximizations select a highest-revenue combination from the supplied candidate collections.
Formalization Note Optimality in (4) means feasibility and minimum over every feasible LP pair; feasibility alone does not suffice. The paper's candidates lie in , but no property of those sets is used in this comparison. Products are zero-indexed, , , all product weights are positive, and . Revenues need not be ordered or nonnegative.
import Mathlib import Definitions.Def_NestedLogitVariants_LP_Model
namespace ConstrNestedLogit.Stitch
/-- Theorem 2, p. 12: the candidate combination selected at an optimum of (4)
maximizes expected revenue among all candidate combinations. -/
theorem theorem_2 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ}
(I : NestedLogitVariants.LP.Instance ι n)
(A : ι → Finset (Finset (Fin n)))
(z : ℝ) (y : ι → ℝ) (S_hat : ι → Finset (Fin 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)
(hlp : NestedLogitVariants.LP.LP4Optimal I (fun i => (A i : Set (Finset (Fin n)))) z y)
(hmem : ∀ i, S_hat i ∈ A i)
(hmax : ∀ i S, S ∈ A i →
NestedLogitVariants.LP.nestWeight I i S * (NestedLogitVariants.LP.R I i S - z) ≤
NestedLogitVariants.LP.nestWeight I i (S_hat i) *
(NestedLogitVariants.LP.R I i (S_hat i) - z)) :
∀ S : ι → Finset (Fin n), (∀ i, S i ∈ A i) →
NestedLogitVariants.LP.revenue I S ≤ NestedLogitVariants.LP.revenue I S_hat := by sorry
end ConstrNestedLogit.Stitch
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.