Proposition 7, PDF p. 24 — offering each store its single-store optimum earns at least ½ of the optimal SQR-heter revenue, and ½ is tight
ProvedMultiStoreAssort.Approx.proposition7_half_approxConsider the heterogeneous multi-store model under sequential recommendation: stores with arrival fractions , ; products with revenues ; attraction values of product in store ; utility discounts with . Let be the (SQR-heter) revenue of a profile , let be its maximum over all profiles, and let be store 's single-store optimal assortment (the smallest revenue-ordered maximizer of ). The heuristic offers in every store and earns . Then:
- Half-approximation.
- Tightness. For every there is an instance with two stores and two products, satisfying all of the above assumptions, on which .
The result shows that the naive heuristic loses at most half of the optimal sequential revenue, and that sequential recommendation can earn up to twice the benchmark of operating every store separately.
Formalization Note. is never formed as a term: part 1 states for every profile . The paper says it "identifies an instance where the equality holds", but its instance attains only in the limit ; part 2 states this limit form. Part 2 also asserts that exists on the instance, so it is not vacuous, and it uses the paper's tie rule: on the instance store 2 has two single-store optima, and only the smallest one makes the bound tight. The positivity of revenues is a pinned hypothesis (the paper's revenues are prices; its proof drops a second-stage revenue term that is nonnegative only for nonnegative prices). When no revenue-ordered assortment exists, so part 1 is vacuous there, as in the paper, where is a set with .
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MultiStoreAssort_Approx_Model
namespace MultiStoreAssort.Approx
/-- Proposition 7 (p. 24): (1) offering each store `i` its single-store optimal assortment `S̃_i`
earns at least half the optimal (SQR-heter) revenue, `R^H_Q ≥ ½ R*_Q`; (2) the factor `½` is tight:
for every `δ > 0` there is an instance (two stores, two products) on which `R^H_Q < (½ + δ) R*_Q`. -/
theorem proposition7_half_approx :
(∀ (m n : ℕ) (lam : Fin m → ℝ) (r : Fin n → ℝ) (v : Fin m → Fin n → ℝ)
(c : Fin m → Fin m → Fin n → ℝ),
(∀ i, 0 ≤ lam i) → ∑ i, lam i = 1 → StrictAnti r → (∀ k, 0 < r k) →
(∀ i k, 0 < v i k) → (∀ i j k, 0 ≤ c i j k) → (∀ i k, c i i k = 0) →
∀ St : Fin m → Finset (Fin n), (∀ i, MultiStoreAssort.SMR.IsStilde r (v i) (St i)) →
∀ S : Fin m → Finset (Fin n), (1 / 2) * revQh lam r v c S ≤ revQh lam r v c St) ∧
(∀ δ : ℝ, 0 < δ →
∃ (lam : Fin 2 → ℝ) (r : Fin 2 → ℝ) (v : Fin 2 → Fin 2 → ℝ) (c : Fin 2 → Fin 2 → Fin 2 → ℝ),
(∀ i, 0 ≤ lam i) ∧ ∑ i, lam i = 1 ∧ StrictAnti r ∧ (∀ k, 0 < r k) ∧
(∀ i k, 0 < v i k) ∧ (∀ i j k, 0 ≤ c i j k) ∧ (∀ i k, c i i k = 0) ∧
(∃ St : Fin 2 → Finset (Fin 2), ∀ i, MultiStoreAssort.SMR.IsStilde r (v i) (St i)) ∧
∀ St : Fin 2 → Finset (Fin 2), (∀ i, MultiStoreAssort.SMR.IsStilde r (v i) (St i)) →
∃ S : Fin 2 → Finset (Fin 2), revQh lam r v c St < (1 / 2 + δ) * revQh lam r v c S) := by sorry
end MultiStoreAssort.Approx
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.