§2, p. 11 — problem (2) is equivalent to the linear program (3): its optimal value is Z*
ProvedNestedLogitVariants.LP.lp3_value_eqConsider an instance of the nested logit assortment problem with at least one nest and at least one product, and let be an optimal assortment of problem (2), so . Then is the optimal value of the linear program (3):
that is, is feasible for (3) with a suitable , and every feasible is at least . No positivity of is assumed; the paper notes that (3) continues to apply when .
This is the linear-programming representation on which the approximation framework of the paper rests.
Formalization Note The minimum is stated with IsLeast on the set of feasible . At least one nest and one product are assumed: with no nests, or no products, and , every is feasible for (3) and the claim fails, a degenerate instance the paper does not consider. 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. 11: problem (2) is equivalent to the linear program (3). If `S*` is an optimal
assortment, then `Z* = Π(S*)` is the least `x` for which some `y` makes `(x, y)` feasible for
(3), i.e. the optimal value of (3) is `Z*`. No positivity of `v_0` is assumed: the page states that
(3) "continues to apply when the preference weight `v_0` of the no purchase option is zero".
`Nonempty ι` and `0 < n` (at least one nest and one product) exclude the empty instance, in which
with `v_0 = 0` every `x` is feasible for (3). -/
theorem lp3_value_eq {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing) [Nonempty ι] (hn : 0 < n)
(Sstar : ι → Finset (Fin n)) (hopt : IsOptimal I Sstar) :
IsLeast {x | ∃ y, LP3Feasible I x y} (revenue I Sstar) := by sorry
end NestedLogitVariants.LP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.