Sign pattern of : nonpositive, then nonnegative
ProvedAssortSearch.MNLQC.derivative_signLet , , margins , and an operational cost that is concave and increasing on and differentiable on . Fix an assortment and . Let be the profit change from adding with preference under the MNL model without search.
Then changes sign at most once, from nonpositive to nonnegative. Either
or there is a threshold such that
The paper derives this from (6) and the monotonicity of the numerator, and concludes from it that is quasi-convex.
Formalization Note The paper says "there is at most one such that ". Read literally this is false when the numerator vanishes on a whole interval, for instance with linear and every margin equal to , when is constant. The statement is therefore the single-crossing form, which is what the paper's argument shows. Differentiability of on is added because the paper differentiates . Mathlib's deriv is used, and it is the true derivative at every by (6).
import Mathlib import Definitions.Def_RetailVariety_Structure_Model import Definitions.Def_AssortSearch_MNLQC_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.