§2, p. 12 — at an optimum of (4) the first constraint binds and x̂ = Π(Ŝ_1, …, Ŝ_m)
ProvedNestedLogitVariants.LP.lp4_opt_bindingAssume . Let be an optimal solution of the linear program (4) with candidate collections , and for every nest let be a member of the collection of nest that maximizes over that collection. Then
So the expected revenue of the assortment stitched together from the maximizers is exactly the optimal value of (4).
Formalization Note The hypothesis is added. The page allows , but its step "solving for " divides by , which can vanish then, and the conclusion fails: one nest, , , one product with , candidates ; then and is a maximizer, but . The standing assumptions are those of §1: , , revenues ordered , together with the disclosed pins (the page allows zero-weight padding products, under which Proposition 2 of the paper fails), (revenues are prices) and (the page has ; its convention when fails at ).
import Mathlib import Definitions.Def_NestedLogitVariants_LP_Model
namespace NestedLogitVariants.LP
/-- §2, p. 12: at an optimal solution `(x̂, ŷ)` of (4), the first constraint binds with the
maximizers `Ŝ_i` of (5): `v_0 x̂ = ∑_i V_i(Ŝ_i)^{γ_i} (R_i(Ŝ_i) − x̂)`, and hence
`x̂ = Π(Ŝ_1, …, Ŝ_m)`. Pinned `0 < v_0` (the step "solving for x̂" divides by
`v_0 + ∑_i V_i(Ŝ_i)^{γ_i}`, which can vanish when `v_0 = 0`). -/
theorem lp4_opt_binding {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing) (hv0 : 0 < I.v0)
(A : ι → Set (Finset (Fin n))) (xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I A xh yh)
(Sh : ι → Finset (Fin n)) (hSmem : ∀ i, Sh i ∈ A i)
(hSmax : ∀ i, ∀ S ∈ A i,
nestWeight I i S * (R I i S - xh) ≤ nestWeight I i (Sh i) * (R I i (Sh i) - xh)) :
I.v0 * xh = ∑ i, nestWeight I i (Sh i) * (R I i (Sh i) - xh) ∧ xh = revenue I Sh := by sorry
end NestedLogitVariants.LP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.