Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8: the heuristic equilibrium of no-search assortment planning is never deeper than optimal, x∗≤xox^*\le x^ox∗≤xo

Proved
AssortSearch.HeurEq.theorem_8

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

assortment-planningconsumer-searchmultinomial-logitoperations-researchp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

A retailer carries the xxx most popular of nnn product variants with preferences v1≥⋯≥vn>0v_1\ge\dots\ge v_n>0v1​≥⋯≥vn​>0 (no-purchase preference v0>0v_0>0v0​>0), margins with mj≥mkm_j\ge m_kmj​≥mk​ whenever vj≥vkv_j\ge v_kvj​≥vk​ and an operational cost ccc that is concave and increasing on [0,1][0,1][0,1] with c(0)≥0c(0)\ge0c(0)≥0. Consumers behave according to the independent assortment search model with constant λ>0\lambda>0λ>0, but the retailer plans with the traditional no-search MNL model, re-estimating preferences from the sales of each assortment it carries.

Let x∗x^*x∗ be a heuristic equilibrium of this process: 1≤x∗≤n1\le x^*\le n1≤x∗≤n and x∗x^*x∗ maximises the predicted profit π(⋅∣v^(x∗))\pi(\cdot\mid\hat v(x^*))π(⋅∣v^(x∗)) over the depths 0,…,n0,\dots,n0,…,n. Let xox^oxo be an optimal assortment, π(xo)=max⁡0≤x≤nπ(x)\pi(x^o)=\max_{0\le x\le n}\pi(x)π(xo)=max0≤x≤n​π(x), such that every deeper assortment is strictly worse: π(x)<π(xo)\pi(x)<\pi(x^o)π(x)<π(xo) for xo<x≤nx^o<x\le nxo<x≤n. Then

x∗≤xo.x^*\le x^o.x∗≤xo.

The heuristic equilibrium never contains more variants than the optimal assortment: a retailer that ignores consumer search risks choosing an assortment that is too narrow, never one that is too deep.

Formalization Note Independent assortment model only; the paper dismisses the overlapping case with "the similar process", which would also need the search threshold Uˉ(x)\bar U(x)Uˉ(x) to be monotone. The paper speaks of "the optimal assortment", presuming uniqueness; the strict-deeper condition on xox^oxo is implied by uniqueness, and without it the conclusion can fail for a shallower optimum. c(0)≥0c(0)\ge0c(0)≥0 is added (the positivity step needs it). x∗≥1x^*\ge 1x∗≥1 is part of the equilibrium: at x∗=0x^*=0x∗=0 nothing is observed. Optimality of xox^oxo is over depths, as in the paper's proof.

Preamble
import Mathlib
import Definitions.Def_AssortSearch_HeurEq_Model
Formal statement
namespace AssortSearch.HeurEq

open RetailVariety.Structure

/-- Theorem 8 (p. 23), independent assortment model: the heuristic equilibrium resulting from
the iterative application of the no-search assortment planning model never contains more variants
than the optimal assortment, `x* ≤ x^o`. Here `x^o` maximises the true profit over the depths
`0, …, n` and every deeper depth is strictly worse (implied by the uniqueness of "the optimal
assortment" that the paper presumes). The heuristic equilibrium has `x* ≥ 1`; at `x* = 0`
nothing is observed and the claim would be trivial. -/
theorem theorem_8 {n : ℕ} (lam : ℝ) (m : Fin n → ℝ) (c : ℝ → ℝ)
    (v : Fin n → ℝ) (v0 : ℝ)
    (hv : ∀ i, 0 < v i) (hanti : Antitone v) (hv0 : 0 < v0) (hlam : 0 < lam)
    (hm : ∀ j k : Fin n, v k ≤ v j → m k ≤ m j)
    (hcc : ConcaveOn ℝ (Set.Icc 0 1) c) (hcm : MonotoneOn c (Set.Icc 0 1))
    (hc0 : 0 ≤ c 0)
    (xstar xo : ℕ) (heq : IsHeuristicEquilibrium lam m c v v0 xstar)
    (hopt : IsOptimalDepth lam m c v v0 xo)
    (hdeeper : ∀ x : ℕ, xo < x → x ≤ n → trueProfit lam m c v v0 x < trueProfit lam m c v v0 xo) :
    xstar ≤ xo := by sorry

end AssortSearch.HeurEq
Source
Cachon, Terwiesch & Xu, Retail Assortment Planning in the Presence of Consumer Search, working paper (Dec. 20, 2002), p. 23 (PDF 25), Theorem 8 (independent assortment model; proof pp. 23–24)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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