Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sign pattern of hm′h^{m\prime}hm′: nonpositive, then nonnegative

Proved
AssortSearch.MNLQC.derivative_sign

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

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

Let v1,…,vn>0v_1,\dots,v_n > 0v1​,…,vn​>0, v0>0v_0 > 0v0​>0, margins m1,…,mn∈Rm_1,\dots,m_n \in \mathbb Rm1​,…,mn​∈R, and an operational cost ccc that is concave and increasing on [0,1][0,1][0,1] and differentiable on (0,1)(0,1)(0,1). Fix an assortment SSS and j∉Sj \notin Sj∈/S. Let hm(vj)=πjm(vj)−Lm(vj)h^m(v_j) = \pi_j^m(v_j) - L^m(v_j)hm(vj​)=πjm​(vj​)−Lm(vj​) be the profit change from adding jjj with preference vjv_jvj​ under the MNL model without search.

Then hm′h^{m\prime}hm′ changes sign at most once, from nonpositive to nonnegative. Either

hm′(vj)≤0for all vj>0,h^{m\prime}(v_j) \le 0 \quad \text{for all } v_j > 0,hm′(vj​)≤0for all vj​>0,

or there is a threshold a≥0a \ge 0a≥0 such that

hm′(vj)≤0  for 0<vj<a,hm′(vj)≥0  for vj>a.h^{m\prime}(v_j) \le 0 \ \text{ for } 0 < v_j < a, \qquad h^{m\prime}(v_j) \ge 0 \ \text{ for } v_j > a.hm′(vj​)≤0  for 0<vj​<a,hm′(vj​)≥0  for vj​>a.

The paper derives this from (6) and the monotonicity of the numerator, and concludes from it that hmh^mhm is quasi-convex.

Formalization Note The paper says "there is at most one vjv_jvj​ such that hm′(vj)=0h^{m\prime}(v_j) = 0hm′(vj​)=0". Read literally this is false when the numerator vanishes on a whole interval, for instance with c(q)=aq+bc(q) = aq + bc(q)=aq+b linear and every margin equal to aaa, when hmh^mhm is constant. The statement is therefore the single-crossing form, which is what the paper's argument shows. Differentiability of ccc on (0,1)(0,1)(0,1) is added because the paper differentiates ccc. Mathlib's deriv is used, and it is the true derivative at every vj>0v_j > 0vj​>0 by (6).

Preamble
import Mathlib
import Definitions.Def_RetailVariety_Structure_Model
import Definitions.Def_AssortSearch_MNLQC_Model
Formal statement
namespace AssortSearch.MNLQC

/-- Proof of Theorem 4 (p. 14): the sign pattern of `h^m′`. Either `h^m′ ≤ 0` on all of
`(0, ∞)`, or there is a threshold `a ≥ 0` with `h^m′ ≤ 0` on `(0, a)` and `h^m′ ≥ 0` on
`(a, ∞)`. (The paper states "at most one `v_j` such that `h^m′(v_j) = 0`", which fails when
the numerator of (6) vanishes on an interval; this is the sign-change form its argument
proves.) -/
theorem derivative_sign
    {n : ℕ} (m : Fin n → ℝ) (c : ℝ → ℝ) (v : Fin n → ℝ) (v0 : ℝ)
    (S : Finset (Fin n)) (j : Fin n)
    (hv : ∀ i, 0 < v i) (hv0 : 0 < v0)
    (hc_concave : ConcaveOn ℝ (Set.Icc 0 1) c) (hc_mono : MonotoneOn c (Set.Icc 0 1))
    (hj : j ∉ S)
    (hc_diff : DifferentiableOn ℝ c (Set.Ioo 0 1)) :
    (∀ x : ℝ, 0 < x → deriv (hm m c v v0 S j) x ≤ 0) ∨
      ∃ a : ℝ, 0 ≤ a ∧
        (∀ x : ℝ, 0 < x → x < a → deriv (hm m c v v0 S j) x ≤ 0) ∧
        (∀ x : ℝ, a < x → 0 ≤ deriv (hm m c v v0 S j) x) := by sorry

end AssortSearch.MNLQC
Source
Cachon, Terwiesch & Xu, Retail Assortment Planning in the Presence of Consumer Search, working paper (Dec. 20, 2002), p. 14 (PDF 16), proof of Theorem 4, last two sentences
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