Proof of Proposition 7, PDF p. 47 — the tightness instance: S̃ = {1}, ({1},{1}) earns 1, ({1},{2}) earns nearly 2
ProvedMultiStoreAssort.Approx.tightness_instanceassortment-optimizationmultinomial-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-recommendation
Fix and consider the instance with two stores and two products in which the arrival fractions are , , the revenues are and , the attraction values are and in both stores , and every utility discount is . Then:
- In both stores the smallest revenue-ordered optimal single-store assortment is (both and earn ; earns ).
- The heuristic profile earns exactly under (SQR-heter).
- The profile earns
which tends to as .
This is the instance showing that the factor of Proposition 7 cannot be improved.
Formalization Note. The paper says only that the two revenues are "close to 1" and "close to 2" when ; the exact values above are a direct computation from (10). The paper sets and leaves the other cross-store discounts unspecified; they are set to here, which does not affect the revenues because and the discounts are by assumption.
Preamble
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MultiStoreAssort_Approx_Model
Formal statement
namespace MultiStoreAssort.Approx
/-- The tightness instance of the proof of Proposition 7 (Online Supplement p. 15): two stores, two
products, `λ = (1, 0)`, revenues `(1 + 1/ε, 1)`, attraction values `(ε, 1/ε)` in both stores and all
utility discounts `0`. Then `S̃ = {1}` in both stores, the profile `({1}, {1})` earns exactly `1`, and
the profile `({1}, {2})` earns `1 + 1/((1 + ε)(1 + ε + ε²))`, which tends to `2` as `ε → 0`. -/
theorem tightness_instance (ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1) :
let lam : Fin 2 → ℝ := ![1, 0]
let r : Fin 2 → ℝ := ![1 + 1 / ε, 1]
let v : Fin 2 → Fin 2 → ℝ := fun _ => ![ε, 1 / ε]
let c : Fin 2 → Fin 2 → Fin 2 → ℝ := fun _ _ _ => 0
(∀ (i : Fin 2) (S : Finset (Fin 2)), MultiStoreAssort.SMR.IsStilde r (v i) S ↔ S = {0}) ∧
revQh lam r v c ![{0}, {0}] = 1 ∧
revQh lam r v c ![{0}, {1}] = 1 + 1 / ((1 + ε) * (1 + ε + ε ^ 2)) := by sorry
end MultiStoreAssort.Approx
Source
Liu, Chen, Liu & Wan, Simultaneous vs. Sequential: Optimal Assortment Recommendation in Multistore Retailing, authors' manuscript with Online and Additional Supplements (2024-09-17; MSOM DOI 10.1287/msom.2024.0761), PDF p. 47 (Online Supplement p. 15), Appendix D.2, proof of Proposition 7, tightness instance
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.