Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7, PDF p. 24 — offering each store its single-store optimum earns at least ½ of the optimal SQR-heter revenue, and ½ is tight

Proved
MultiStoreAssort.Approx.proposition7_half_approx

by mikedeng1 · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsassortment-optimizationmultinomial-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-recommendation

Consider the heterogeneous multi-store model under sequential recommendation: mmm stores with arrival fractions λi≥0\lambda_i\ge0λi​≥0, ∑iλi=1\sum_i\lambda_i=1∑i​λi​=1; nnn products with revenues r1>r2>⋯>rn>0r_1>r_2>\dots>r_n>0r1​>r2​>⋯>rn​>0; attraction values vik>0v_{ik}>0vik​>0 of product kkk in store iii; utility discounts cijk≥0c^k_{ij}\ge0cijk​≥0 with ciik=0c^k_{ii}=0ciik​=0. Let R(S)R(\boldsymbol S)R(S) be the (SQR-heter) revenue ∑iλi∑krkpikQ(S)\sum_i\lambda_i\sum_kr_kp^Q_{ik}(\boldsymbol S)∑i​λi​∑k​rk​pikQ​(S) of a profile S=(S1,…,Sm)\boldsymbol S=(S_1,\dots,S_m)S=(S1​,…,Sm​), let RQ∗R^*_QRQ∗​ be its maximum over all profiles, and let S~i\tilde S_iS~i​ be store iii's single-store optimal assortment (the smallest revenue-ordered maximizer of ∑k∈Srkvik/(1+∑k∈Svik)\sum_{k\in S}r_kv_{ik}/(1+\sum_{k\in S}v_{ik})∑k∈S​rk​vik​/(1+∑k∈S​vik​)). The heuristic offers S~i\tilde S_iS~i​ in every store iii and earns RQH=R(S~1,…,S~m)R^H_Q=R(\tilde S_1,\dots,\tilde S_m)RQH​=R(S~1​,…,S~m​). Then:

  1. Half-approximation.
RQH ≥ 12RQ∗.R^H_Q\ \ge\ \tfrac12R^*_Q.RQH​ ≥ 21​RQ∗​.
  1. Tightness. For every δ>0\delta>0δ>0 there is an instance with two stores and two products, satisfying all of the above assumptions, on which RQH<(12+δ)RQ∗R^H_Q<(\tfrac12+\delta)R^*_QRQH​<(21​+δ)RQ∗​.

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. RQ∗R^*_QRQ∗​ is never formed as a term: part 1 states 12R(S)≤RQH\frac12R(\boldsymbol S)\le R^H_Q21​R(S)≤RQH​ for every profile S\boldsymbol SS. The paper says it "identifies an instance where the equality holds", but its instance attains 12\frac1221​ only in the limit ϵ→0\epsilon\to0ϵ→0; part 2 states this limit form. Part 2 also asserts that S~i\tilde S_iS~i​ 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 n=0n=0n=0 no revenue-ordered assortment exists, so part 1 is vacuous there, as in the paper, where S~\tilde SS~ is a set {1,…,k}\{1,\dots,k\}{1,…,k} with k∈[n]k\in[n]k∈[n].

Preamble
import Mathlib
import Definitions.Def_ChoiceCDLP_MNL_mnlObjective
import Definitions.Def_MultiStoreAssort_Approx_Model
Formal statement
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
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. 24, §7.1, Proposition 7; proof Online Supplement Appendix D.2, PDF pp. 46–47
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 14, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me