Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix C — Finite candidate prices suffice

Proved
FBMSP.discrete_candidate_sufficiency

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

market-segmentationoperations-researchpricing

For a valid finite rational market with nnn prediction values and mmm error atoms, define

P={0}∪{μi+ej:μi+ej≥0}.P=\{0\}\cup\{\mu_i+e_j:\mu_i+e_j\ge0\}.P={0}∪{μi​+ej​:μi​+ej​≥0}.

Then every candidate is nonnegative, ∣P∣≤nm+1|P|\le nm+1∣P∣≤nm+1, and every policy using arbitrary nonnegative real prices is weakly dominated by a policy using only prices from PPP, with the same customer assignment and at most the same number of price slots.

This is the finite-support link needed to apply the finite-candidate greedy guarantee to unrestricted pricing. The statement proves a cardinality bound; a machine-level cost of exact arithmetic is not asserted.

Preamble
import Definitions.Def_FBMSP_DiscreteCandidates
Formal statement
namespace FBMSP

/-- Finite-support bridge for Remark 2 / Appendix C.  Every real-price policy
is dominated by a policy using realized nonnegative valuation breakpoints,
without changing its assignment.  Thus a finite-candidate optimization loses
no revenue in this discrete setting.  Draft statement; proof remains open.

The cardinality bound is explicit.  No computational runtime bound is
asserted here; exact-arithmetic evaluation costs require a separate model. -/
theorem discrete_candidate_sufficiency (I : RationalMarketInput)
    (hvalid : ValidRationalMarket I) :
    0 ∈ rationalCandidatePrices I ∧
    (∀ p ∈ rationalCandidatePrices I, 0 ≤ p) ∧
    (rationalCandidatePrices I).card ≤ I.means.length * I.shocks.length + 1 ∧
    ∀ (prices : Fin I.segments → ℝ)
      (assignment : Fin I.means.length → Fin I.segments),
      (∀ j, 0 ≤ prices j) →
      ∃ candidatePrices : Fin I.segments → ℝ,
        (∀ j, candidatePrices j ∈ rationalCandidatePrices I) ∧
        rationalMarketRevenue I prices assignment ≤
          rationalMarketRevenue I candidatePrices assignment := 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 . Appendix C, p.50 (ec16); Remark 3, p.18.
Read-back

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

Let III consist of rational mean and mean-weight lists (μi)i<n(\mu_i)_{i<n}(μi​)i<n​ and (wi)i<n(w_i)_{i<n}(wi​)i<n​ with n≥1n\geq1n≥1, distinct nonnegative means, strictly positive weights, and ∑iwi=1\sum_iw_i=1∑i​wi​=1; rational shock and shock-weight lists (ej)j<s(e_j)_{j<s}(ej​)j<s​ and (qj)j<s(q_j)_{j<s}(qj​)j<s​ with s≥1s\geq1s≥1, all qj≥0q_j\geq0qj​≥0, ∑jqj=1\sum_jq_j=1∑j​qj​=1, and ∑jejqj=0\sum_je_jq_j=0∑j​ej​qj​=0; a natural number of price slots k≥1k\geq1k≥1; and an arbitrary rational threshold. Each value list has the same length as its weight list. Define the finite real set CI={0}∪{μi+ej:0≤i<n, 0≤j<s, μi+ej≥0}C_I=\{0\}\cup\{\mu_i+e_j:0\leq i<n,\ 0\leq j<s,\ \mu_i+e_j\geq0\}CI​={0}∪{μi​+ej​:0≤i<n, 0≤j<s, μi​+ej​≥0}, with rational sums embedded in R\mathbb RR and repeated values identified. The assertion is that 0∈CI0\in C_I0∈CI​, all its elements are nonnegative, ∣CI∣≤ns+1|C_I|\leq ns+1∣CI​∣≤ns+1, and for every nonnegative real vector (pℓ)ℓ<k(p_\ell)_{\ell<k}(pℓ​)ℓ<k​ and every 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} there is a vector (pℓ′)ℓ<k(p'_\ell)_{\ell<k}(pℓ′​)ℓ<k​ with every pℓ′∈CIp'_\ell\in C_Ipℓ′​∈CI​ such that ∑iwi∑jqjpa(i)1{pa(i)≤μi+ej}≤∑iwi∑jqjpa(i)′1{pa(i)′≤μi+ej}\sum_iw_i\sum_jq_jp_{a(i)}\mathbf1_{\{p_{a(i)}\leq\mu_i+e_j\}}\leq\sum_iw_i\sum_jq_jp'_{a(i)}\mathbf1_{\{p'_{a(i)}\leq\mu_i+e_j\}}∑i​wi​∑j​qj​pa(i)​1{pa(i)​≤μi​+ej​}​≤∑i​wi​∑j​qj​pa(i)′​1{pa(i)′​≤μi​+ej​}​. The assignment is the same on both sides, and purchase at equality is included. The original prices may be arbitrary real numbers; the replacement prices are drawn from this finite set and may repeat or be assigned to no mean. Means need not be sorted; shocks may repeat and have zero weight, and all supplied mean-shock pairs contribute candidate sums regardless of weight. Negative realized values are allowed but do not become candidate prices. The threshold value is unrestricted and has no role in the conclusion; there is no bound on sss in this theorem, no assertion that the replacement prices maximize revenue, and no computation-time conclusion.

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