Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Consecutive-block Bellman recurrence and oracle cost schedule

Definition
FBMSP_DynamicProgram

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

market-segmentationoperations-researchpricing

This bundle defines a finite maximum, the consecutive-block Bellman recurrence, and an inductive relation witnessing a partition and its score. Its first parameter counts additional slots beyond an initial block; a KKK-price problem uses K−1K-1K−1. Empty blocks are permitted and should have zero score in the pricing application.

The cost layer counts nonempty block-oracle queries, Bellman candidate evaluations in a bottom-up table, arbitrary declared oracle charges, and reconstruction steps. These counts describe a specified memoized evaluation schedule. They do not claim that naive recursive evaluation has quadratic cost or that arbitrary real-valued oracle operations have unit bit complexity.

Definition code
import Mathlib

noncomputable section
open scoped BigOperators
namespace FBMSP

/-- A maximum over the integers 0,...,n. -/
def prefixMax (f : ℕ → ℝ) : ℕ → ℝ
  | 0 => f 0
  | n + 1 => max (prefixMax f n) (f (n + 1))

/-- k additional block slots, hence k+1 slots in total, on [a,a+n). -/
def intervalDP (W : ℕ → ℕ → ℝ) : ℕ → ℕ → ℕ → ℝ
  | 0, a, n => W a (a + n)
  | k + 1, a, n =>
      prefixMax (fun i => intervalDP W k a i + W (a + i) (a + n)) n

inductive IntervalValue (W : ℕ → ℕ → ℝ) : ℕ → ℕ → ℕ → ℝ → Prop
  | one (a n : ℕ) : IntervalValue W 0 a n (W a (a + n))
  | append {k a n i : ℕ} {v : ℝ} (hi : i ≤ n)
      (hv : IntervalValue W k a i v) :
      IntervalValue W (k + 1) a n (v + W (a + i) (a + n))

/-- Nonempty interval queries, counted by right endpoint. -/
def blockOracleCalls : ℕ → ℕ
  | 0 => 0
  | n + 1 => blockOracleCalls n + (n + 1)

/-- Bottom-up table schedule: k extra layers, columns 0,...,n, i+1 cuts
at column i. This is not the cost of naive recursive evaluation. -/
def tableCandidateEvaluations (k n : ℕ) : ℕ := k * blockOracleCalls (n + 1)

/-- One query costs m including the price and attained value; a Bellman
candidate is one arithmetic/comparison unit. Empty intervals cost zero. -/
def tableWork (k n m : ℕ) : ℕ :=
  m * blockOracleCalls n + tableCandidateEvaluations k n

/-- Actual declared charges of the primitive price-and-value oracle,
enumerating each nonempty interval exactly once by its right endpoint. -/
def oracleCharges (charge : ℕ → ℕ → ℕ) : ℕ → ℕ
  | 0 => 0
  | n + 1 => oracleCharges charge n + ∑ a ∈ Finset.range (n + 1), charge a (n + 1)

/-- Cost of the memoized schedule with K slots: oracle precomputation,
Bellman candidates for K-1 extra layers, and K backtracking steps. -/
def segmentationWork (charge : ℕ → ℕ → ℕ) (K n : ℕ) : ℕ :=
  oracleCharges charge n + tableCandidateEvaluations (K - 1) n + K

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 . Proof of Theorem 2, pp.43–44 (ec9–ec10), Eq. (EC.6).
Read-back

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

For any function f:N→Rf:\mathbb N\to\mathbb Rf:N→R, its prefix maximum at nnn is max⁡0≤i≤nf(i)\max_{0\leq i\leq n}f(i)max0≤i≤n​f(i), recursively initialized by f(0)f(0)f(0) and extended by taking the maximum with f(n+1)f(n+1)f(n+1); in particular a prefix of length parameter 000 contains the value at 000. For any function W:N2→RW:\mathbb N^2\to\mathbb RW:N2→R, define D0(a,n)=W(a,a+n)D_0(a,n)=W(a,a+n)D0​(a,n)=W(a,a+n) and, for natural ℓ,a,n\ell,a,nℓ,a,n, Dℓ+1(a,n)=max⁡0≤i≤n(Dℓ(a,i)+W(a+i,a+n))D_{\ell+1}(a,n)=\max_{0\leq i\leq n}\bigl(D_\ell(a,i)+W(a+i,a+n)\bigr)Dℓ+1​(a,n)=max0≤i≤n​(Dℓ​(a,i)+W(a+i,a+n)). The relation saying that vvv is an interval value at (ℓ,a,n)(\ell,a,n)(ℓ,a,n) is the relation generated by the following two rules: W(a,a+n)W(a,a+n)W(a,a+n) is a value at (0,a,n)(0,a,n)(0,a,n); and if i≤ni\leq ni≤n and vvv is a value at (ℓ,a,i)(\ell,a,i)(ℓ,a,i), then v+W(a+i,a+n)v+W(a+i,a+n)v+W(a+i,a+n) is a value at (ℓ+1,a,n)(\ell+1,a,n)(ℓ+1,a,n). Equivalently, its values are exactly ∑j=0ℓW(cj,cj+1)\sum_{j=0}^{\ell}W(c_j,c_{j+1})∑j=0ℓ​W(cj​,cj+1​) over natural nondecreasing cuts c0=ac_0=ac0​=a and cℓ+1=a+nc_{\ell+1}=a+ncℓ+1​=a+n. Thus ℓ\ellℓ counts additional slots beyond the first, for ℓ+1\ell+1ℓ+1 blocks in total; zero-length blocks are included. There is no assumption on WWW, including no assumption that W(a,a)=0W(a,a)=0W(a,a)=0, so at n=0n=0n=0 the sole value and the recurrence both equal (ℓ+1)W(a,a)(\ell+1)W(a,a)(ℓ+1)W(a,a). Define Q(0)=0Q(0)=0Q(0)=0 and Q(n+1)=Q(n)+(n+1)Q(n+1)=Q(n)+(n+1)Q(n+1)=Q(n)+(n+1), equivalently Q(n)=∑b=1nb=n(n+1)/2Q(n)=\sum_{b=1}^{n}b=n(n+1)/2Q(n)=∑b=1n​b=n(n+1)/2. The table candidate evaluation count at natural parameters (k,n)(k,n)(k,n) is kQ(n+1)=k(n+1)(n+2)/2kQ(n+1)=k(n+1)(n+2)/2kQ(n+1)=k(n+1)(n+2)/2. The table work at natural parameters (k,n,m)(k,n,m)(k,n,m) is T(k,n,m)=mQ(n)+kQ(n+1)T(k,n,m)=mQ(n)+kQ(n+1)T(k,n,m)=mQ(n)+kQ(n+1); this is an explicitly defined natural number and contains no machine, implementation, or measured-runtime relation. All these definitions allow zero parameters: Q(0)=0Q(0)=0Q(0)=0, the candidate count is 000 at k=0k=0k=0, and T(k,0,m)=kT(k,0,m)=kT(k,0,m)=k. For any charge function c:N2→Nc:\mathbb N^2\to\mathbb Nc:N2→N, define the total charge Oc(0)=0O_c(0)=0Oc​(0)=0 and Oc(n+1)=Oc(n)+∑a=0nc(a,n+1)O_c(n+1)=O_c(n)+\sum_{a=0}^{n}c(a,n+1)Oc​(n+1)=Oc​(n)+∑a=0n​c(a,n+1), equivalently Oc(n)=∑b=1n∑a=0b−1c(a,b)O_c(n)=\sum_{b=1}^{n}\sum_{a=0}^{b-1}c(a,b)Oc​(n)=∑b=1n​∑a=0b−1​c(a,b). Only nonempty intervals with endpoints between 000 and nnn occur in this sum; diagonal and out-of-range charges do not occur. For a natural number of slots KKK, the segmentation work is the defined number Oc(n)+(K−1)Q(n+1)+KO_c(n)+(K-1)Q(n+1)+KOc​(n)+(K−1)Q(n+1)+K, with natural subtraction K−1=max⁡(K−1,0)K-1=\max(K-1,0)K−1=max(K−1,0). Thus this expression adds the supplied interval charges, the candidate count for K−1K-1K−1 additional layers, and KKK; it imposes no connection between ccc and a computational implementation. At K=0K=0K=0 it equals Oc(n)O_c(n)Oc​(n), and at n=0n=0n=0 it equals max⁡(K−1,0)+K\max(K-1,0)+Kmax(K−1,0)+K.

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