Theorem 1, p. 13 — if (αx̂, βŷ) is feasible for (3), the assortment of (5) earns within a factor α: αẐ ≥ Z* ≥ Ẑ
ProvedNestedLogitVariants.LP.theorem_1Assume . Let be candidate collections of assortments for the nests, let be an optimal solution of the linear program (4), and for every nest let be an optimal solution of
If is feasible for the linear program (3) for some real and , then, writing and for the optimal value of problem (2),
So the revenue of the assortment stitched together from the candidate collections deviates from the optimum by no more than a factor of . This is the general approximation framework of the paper: the performance guarantees of Theorems 7, 10, 11 and 12 are obtained by exhibiting candidate collections for which is feasible for (3).
Formalization Note is for an arbitrary optimal assortment (one always exists, since there are finitely many assortments). The hypothesis is added: the paper allows , but the theorem is false then. Take one nest with , , one product with , and candidates ; then is optimal for (4), solves (5), is feasible for (3) with , and . The paper's derivation divides by , which vanishes in this instance. No sign condition is placed on or . 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
/-- Theorem 1, p. 13. Let `(x̂, ŷ)` be an optimal solution of (4) and `Ŝ_i` an optimal solution of
(5), `max_{S_i ∈ A_i} V_i(S_i)^{γ_i} (R_i(S_i) − x̂)`, for every nest `i`. If `(α x̂, β ŷ)` is
feasible for (3), then `α Ẑ ≥ Z* ≥ Ẑ` with `Ẑ = Π(Ŝ_1, …, Ŝ_m)` and `Z* = Π(S*)` for any optimal
`S*` of (2). Pinned `0 < v_0`: the statement is false for `v_0 = 0` (one nest, `v_{10} = 0`,
`γ_1 = 1`, `r_{11} = v_{11} = 1`, `A_1 = {∅, {1}}`, `x̂ = 1`, `Ŝ_1 = ∅`, `α = β = 1`). -/
theorem theorem_1 {ι : 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))
(α β : ℝ) (hfeas : LP3Feasible I (α * xh) (β • yh)) :
∀ Sstar, IsOptimal I Sstar →
revenue I Sstar ≤ α * revenue I Sh ∧ revenue I Sh ≤ revenue I Sstar := by sorry
end NestedLogitVariants.LP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.