Proposition 9, PDF p. 29 — the SMR optimum of Theorem 6 earns at least half the optimal revenue of the SQR joint problem (15)
ProvedMultiStoreAssort.Pricing.proposition9_halfIn the setting of Theorem 6 (, , , , , , and the solution of the markup equation), consider the joint problem under sequential recommendation, whose objective is of (15): a store- customer first sees , and only if she buys nothing is she shown .
Proposition 9. The optimal solution of problem (13) from Theorem 6, namely and , achieves at least half of the optimal revenue of (15): for every profile , every real price matrix and every best-store rule ,
The single-store optimal solution is therefore a -approximation for the joint assortment and pricing problem under sequential recommendation, extending Proposition 7 of the paper to endogenous prices.
Formalization Note "The optimal solution to problem (13)" is read as the solution constructed in Theorem 6 (the proof in App. E.2 bounds the optimal value of (15) by twice , which is what that solution earns in (15)). "The optimal revenue in (15)" is expressed as a bound over all profiles, real prices and tie-breaking rules, not through a supremum.
import Mathlib import Definitions.Def_MultiStoreAssort_Pricing_Model
namespace MultiStoreAssort.Pricing
open Finset
theorem proposition9_half {m n : ℕ} (lam : Fin m → ℝ) (α β : Fin m → Fin n → ℝ)
(c : Fin m → Fin m → Fin n → ℝ) (hlam : ∀ i, 0 ≤ lam i) (hlam1 : ∑ i, lam i = 1)
(hα : ∀ i k, 0 < α i k) (hβ : ∀ i k, 0 < β i k) (hc : ∀ i j k, 0 ≤ c i j k)
(hcii : ∀ i k, c i i k = 0) (θ : Fin m → ℝ) (hθ : ∀ i, IsTheta (α i) (β i) (θ i)) :
∀ (S : Fin m → Finset (Fin n)) (P : Fin m → Fin n → ℝ) (l l' : Fin m → Fin n → Fin m),
IsBestStore α β c P S l →
rev15 lam α β c S P l ≤
2 * rev15 lam α β c (fun _ => Finset.univ) (fun i k => θ i + 1 / β i k) l' := by sorry
end MultiStoreAssort.Pricing
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.