Proof of Proposition 7, PDF p. 47 — every profile earns at most twice the sum of single-store optima
ProvedMultiStoreAssort.Approx.second_inequalityIn the heterogeneous multi-store model ( stores with arrival fractions , ; products with revenues ; attraction values ; utility discounts with ), let be the (SQR-heter) revenue of a profile . For each store let be an optimal solution of store 's single-store problem
Then for every profile ,
Each store's revenue under splits into a first stage (the store's own assortment) and a second stage (the other stores' products, with discounted attraction values); each part is at most . Applied to an optimal profile of (SQR-heter) this is the second and third inequality of the proof of Proposition 7, .
Formalization Note. The statement only uses that each is an optimal solution of (D.1), not the paper's tie rule, and it is stated for every profile instead of an optimal one; both are generalizations covered by the paper's argument. The positivity of the revenues is pinned, as in the rest of the mission.
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MultiStoreAssort_Approx_Model
namespace MultiStoreAssort.Approx
/-- Second and third inequalities of the proof of Proposition 7 (Online Supplement p. 15): if each
`St i` is an optimal solution of store `i`'s single-store problem (D.1), then every profile `S`
earns at most twice `∑_i λ_i ∑_{k ∈ S̃_i} r_k v_{ik} / (1 + ∑_{k ∈ S̃_i} v_{ik})` under (SQR-heter). -/
theorem second_inequality {m n : ℕ} (lam : Fin m → ℝ) (r : Fin n → ℝ) (v : Fin m → Fin n → ℝ)
(c : Fin m → Fin m → Fin n → ℝ)
(hlam : ∀ i, 0 ≤ lam i) (hlam1 : ∑ i, lam i = 1) (hr : StrictAnti r) (hrpos : ∀ k, 0 < r k)
(hv : ∀ i k, 0 < v i k) (hc : ∀ i j k, 0 ≤ c i j k) (hcii : ∀ i k, c i i k = 0)
(St : Fin m → Finset (Fin n)) (hSt : ∀ i, MultiStoreAssort.SMR.IsOptSingle r (v i) (St i)) :
∀ S : Fin m → Finset (Fin n),
revQh lam r v c S ≤ 2 * ∑ i, lam i * MultiStoreAssort.SMR.single r (v i) (St i) := by sorry
end MultiStoreAssort.Approx
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.