Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — Optimal segmentation and oracle computation

Proved
FBMSP.theorem2_computing_segmentation

by mikeh · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

market-segmentationoperations-researchpricing

Let n≥1n\ge1n≥1 predicted values μ1<⋯<μn\mu_1<\cdots<\mu_nμ1​<⋯<μn​ be nonnegative, with positive weights summing to one. Let the independent common error have a finite first moment, mean zero, and MHR. For each index block [a,b)[a,b)[a,b), an oracle supplies a nonnegative price attaining the block's maximum revenue. Its declared charge includes both the price and attained revenue, and is bounded by m≥1m\ge1m≥1 on every nonempty block.

For every k≥1k\ge1k≥1, there exist ordered cuts covering all nnn types and a monotone assignment realizing those cuts, such that the oracle prices yield exactly the Bellman value and dominate every assignment to kkk arbitrary nonnegative real prices. The specified bottom-up schedule, including precomputation and backtracking, satisfies

T(n,k,m)≤5n2(k+m).T(n,k,m)\le5n^2(k+m).T(n,k,m)≤5n2(k+m).

Formalization note. Empty blocks represent unused price slots. The last endpoint is nnn, so no type is omitted. This is an explicit oracle-operation cost model for sorted inputs, not a claim about the naive recursive evaluation or bit complexity of a continuous price oracle. The source's intended price-and-value oracle contract is made explicit.

Preamble
import Definitions.Def_FBMSP_Model
import Definitions.Def_FBMSP_DynamicProgram
Formal statement
namespace FBMSP

theorem theorem2_computing_segmentation
    {n k : ℕ} (hk : 1 ≤ k) (η : MeasureTheory.Measure ℝ)
    (hη : ValidNoise η) (hMHR : HasMHR η)
    (μ w : Fin n → ℝ) (hMarket : ValidFiniteMarket μ w)
    (o : ℕ → ℕ → ℝ) (ho : BlockOracle η μ w o)
    (charge : ℕ → ℕ → ℕ) (m : ℕ) (hm : 1 ≤ m)
    (hCost : ∀ a b, a < b → b ≤ n → charge a b ≤ m) :
    ∃ (c : Fin (k + 1) → ℕ) (a : Fin n → Fin k),
      ValidCuts n k c ∧ RealizesCuts a c ∧ Monotone a ∧
      finitePolicyRevenue η μ w a
        (fun j => o (c j.castSucc) (c j.succ)) =
          intervalDP (oracleScore η μ w o) (k - 1) 0 n ∧
      (∀ (a' : Fin n → Fin k) (p' : Fin k → ℝ),
        (∀ j, 0 ≤ p' j) →
        finitePolicyRevenue η μ w a' p' ≤
          finitePolicyRevenue η μ w a
            (fun j => o (c j.castSucc) (c j.succ))) ∧
      segmentationWork charge k n ≤ 5 * (n * n) * (k + m) := by sorry

end FBMSP
Source
Titing Cui and Michael L. Hamilton, Optimal Feature-Based Market Segmentation and Pricing, October 22, 2025 manuscript (60 PDF pages); Operations Research 74(3), 1354–1370 (2026). https://doi.org/10.1287/opre.2022.0490 ; https://ssrn.com/abstract=4151103 . Theorem 2, p.17; proof pp.43–44 (ec9–ec10), Eq. (EC.6).
Read-back

What the Lean code literally says, in plain math · gpt-6-astra

For all natural n,kn,kn,k with k≥1k\geq1k≥1, let η\etaη be a probability measure on R\mathbb RR with integrable identity function and ∫e dη(e)=0\int e\,d\eta(e)=0∫edη(e)=0, and write S(t)=η([t,∞))S(t)=\eta([t,\infty))S(t)=η([t,∞)). Assume also that η\etaη is absolutely continuous with respect to Lebesgue measure and that D={t:S(t)>0}D=\{t:S(t)>0\}D={t:S(t)>0} is convex and log⁡S\log SlogS is concave on DDD, meaning log⁡S(λs+(1−λ)t)≥λlog⁡S(s)+(1−λ)log⁡S(t)\log S(\lambda s+(1-\lambda)t)\geq\lambda\log S(s)+(1-\lambda)\log S(t)logS(λs+(1−λ)t)≥λlogS(s)+(1−λ)logS(t) for s,t∈Ds,t\in Ds,t∈D and 0≤λ≤10\leq\lambda\leq10≤λ≤1; zero survival values outside DDD are allowed. Let real arrays (μi,wi)0≤i<n(\mu_i,w_i)_{0\leq i<n}(μi​,wi​)0≤i<n​ satisfy n>0n>0n>0, μi<μj\mu_i<\mu_jμi​<μj​ whenever i<ji<ji<j, all μi≥0\mu_i\geq0μi​≥0, all wi>0w_i>0wi​>0, and ∑iwi=1\sum_iw_i=1∑i​wi​=1. For natural endpoints u,vu,vu,v and real ppp, put B(u,v,p)=∑0≤i<n, u≤i<vwipS(p−μi)B(u,v,p)=\sum_{0\leq i<n,\,u\leq i<v}w_i pS(p-\mu_i)B(u,v,p)=∑0≤i<n,u≤i<v​wi​pS(p−μi​). Let o:N2→Ro:\mathbb N^2\to\mathbb Ro:N2→R satisfy, for every u≤v≤nu\leq v\leq nu≤v≤n, o(u,v)≥0o(u,v)\geq0o(u,v)≥0 and B(u,v,p)≤B(u,v,o(u,v))B(u,v,p)\leq B(u,v,o(u,v))B(u,v,p)≤B(u,v,o(u,v)) for every nonnegative real ppp, and set W(u,v)=B(u,v,o(u,v))W(u,v)=B(u,v,o(u,v))W(u,v)=B(u,v,o(u,v)). Let ccost:N2→Nc_{\rm cost}:\mathbb N^2\to\mathbb Nccost​:N2→N be any charge function and m≥1m\geq1m≥1 any natural number such that ccost(u,v)≤mc_{\rm cost}(u,v)\leq mccost​(u,v)≤m for every u<v≤nu<v\leq nu<v≤n. Define D0(u,v)=W(u,u+v)D_0(u,v)=W(u,u+v)D0​(u,v)=W(u,u+v) and Dℓ+1(u,v)=max⁡0≤i≤v(Dℓ(u,i)+W(u+i,u+v))D_{\ell+1}(u,v)=\max_{0\leq i\leq v}\bigl(D_\ell(u,i)+W(u+i,u+v)\bigr)Dℓ+1​(u,v)=max0≤i≤v​(Dℓ​(u,i)+W(u+i,u+v)). There exist natural cuts 0=c0≤c1≤⋯≤ck=n0=c_0\leq c_1\leq\cdots\leq c_k=n0=c0​≤c1​≤⋯≤ck​=n and an assignment a:{0,…,n−1}→{0,…,k−1}a:\{0,\ldots,n-1\}\to\{0,\ldots,k-1\}a:{0,…,n−1}→{0,…,k−1} such that ca(i)≤i<ca(i)+1c_{a(i)}\leq i<c_{a(i)+1}ca(i)​≤i<ca(i)+1​ for every i<ni<ni<n, the assignment is nondecreasing in iii, and with pj=o(cj,cj+1)p_j=o(c_j,c_{j+1})pj​=o(cj​,cj+1​) one has ∑iwipa(i)S(pa(i)−μi)=Dk−1(0,n)\sum_iw_i p_{a(i)}S(p_{a(i)}-\mu_i)=D_{k-1}(0,n)∑i​wi​pa(i)​S(pa(i)​−μi​)=Dk−1​(0,n). Moreover, for every assignment a′a'a′ into these kkk slots and every real price vector p′p'p′ with all pj′≥0p'_j\geq0pj′​≥0, ∑iwipa′(i)′S(pa′(i)′−μi)≤∑iwipa(i)S(pa(i)−μi)\sum_iw_i p'_{a'(i)}S(p'_{a'(i)}-\mu_i)\leq\sum_iw_i p_{a(i)}S(p_{a(i)}-\mu_i)∑i​wi​pa′(i)′​S(pa′(i)′​−μi​)≤∑i​wi​pa(i)​S(pa(i)​−μi​). The same existential conclusion includes ∑v=1n∑u=0v−1ccost(u,v)+(k−1)∑b=1n+1b+k≤5n2(k+m)\sum_{v=1}^{n}\sum_{u=0}^{v-1}c_{\rm cost}(u,v)+(k-1)\sum_{b=1}^{n+1}b+k\leq5n^2(k+m)∑v=1n​∑u=0v−1​ccost​(u,v)+(k−1)∑b=1n+1​b+k≤5n2(k+m). This left side is the defined segmentation-work expression; the hypotheses bound the supplied charges but state no further relation between the charge function and the evaluation of ooo. Since k≥1k\geq1k≥1, natural subtraction k−1k-1k−1 has its usual integer value and the recurrence uses kkk blocks. Repeated cuts and empty blocks are allowed, including when k>nk>nk>n; empty block revenue is 000. The case n=0n=0n=0 is excluded by the market hypotheses, the oracle is unconstrained outside u≤v≤nu\leq v\leq nu≤v≤n, diagonal and out-of-range charges are unbounded but unused by the work expression, and no condition μi+e≥0\mu_i+e\geq0μi​+e≥0 is imposed.

Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikeh · Oct 30, 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