Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Explicit binary pricing decision problem and polynomial-time hardness

Definition
FBMSP_Hardness

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

market-segmentationoperations-researchpricing

This bundle gives an explicit binary encoding of rational finite pricing instances, including the number of price slots and revenue threshold. Valid data have distinct nonnegative predicted means with positive normalized masses and a common finite mean-zero error law. Purchase is inclusive at the posted price; seller prices may be arbitrary nonnegative reals. Realized valuations are not required to be nonnegative.

NP is defined by a polynomially bounded certificate and a finite Turing-machine verifier with polynomial transition count. Polynomial many-one reductions use the same actual machine model. The target language restricts the number of listed error atoms by fixed constants CndCn^dCnd. No arbitrary encoding convention or unspecified computational oracle is used to assert hardness.

Definition code
import Mathlib
import Mathlib.Computability.TuringMachine.Computable

/-!
# A binary-input decision problem for FBMSP hardness

These definitions specify the computational content of Theorem 1 of
Cui and Hamilton, *Optimal Feature-Based Market Segmentation and Pricing*,
DOI 10.1287/opre.2022.0490.

The input distribution is finite and rational.  The seller may nevertheless
choose arbitrary nonnegative REAL prices.  The number of allowed prices is
part of the binary input, not a fixed constant.  A single common shock
distribution is used for all customer means, expressing independence.

NP and polynomial many-one reductions are defined using Mathlib's finite
TM2 machines and a polynomial bound on their actual transition count.
No arbitrary `Encodable` instance, unspecified computational oracle, or
unbounded-time computable reduction is used.
-/

namespace FBMSP

abbrev BinaryString := List Bool

abbrev BinaryLanguage := Set BinaryString

/-- A pair of binary strings with one explicit separator symbol.  Its length
is exactly `x.length + w.length + 1`. -/
def verifierPairEncoding (xw : BinaryString × BinaryString) : List (Option Bool) :=
  xw.1.map some ++ none :: xw.2.map some

/-- A Boolean decision is encoded by its single Boolean output symbol. -/
def verifierOutputEncoding (b : Bool) : List Bool := [b]

/-- Standard certificate definition of NP: a total polynomial-time TM2
verifier and a polynomial bound on the number of witness bits.  Verifier time
is measured in the length of the explicitly delimited input/witness pair. -/
def InNP (L : BinaryLanguage) : Prop :=
  ∃ (V : BinaryString × BinaryString → Bool) (p : Polynomial ℕ),
    Nonempty (Turing.TM2ComputableInPolyTime
      verifierPairEncoding verifierOutputEncoding V) ∧
    ∀ x : BinaryString,
      x ∈ L ↔ ∃ w : BinaryString, w.length ≤ p.eval x.length ∧ V (x, w) = true

/-- A many-one reduction computed by a finite TM2 machine in polynomially
many transitions, measured in the source string's bit length. -/
def PolyManyOneReduction (A B : BinaryLanguage) : Prop :=
  ∃ f : BinaryString → BinaryString,
    Nonempty (Turing.TM2ComputableInPolyTime
      (fun x : BinaryString => x) (fun x : BinaryString => x) f) ∧
    ∀ x : BinaryString, x ∈ A ↔ f x ∈ B

/-- Every NP language polynomial-time many-one reduces to the target. -/
def NPHard (L : BinaryLanguage) : Prop :=
  ∀ A : BinaryLanguage, InNP A → PolyManyOneReduction A L

/-- A self-delimiting bitstring: `length` one-bits, one zero-bit, then the
payload.  The unary part encodes the BIT LENGTH, not the represented integer.
Consequently a natural number occupies O(log n) bits. -/
def marketEncodeBits (bs : BinaryString) : BinaryString :=
  List.replicate bs.length true ++ false :: bs

/-- Little-endian base-two digits with an explicit bit-length prefix. -/
def marketEncodeNat (n : ℕ) : BinaryString :=
  marketEncodeBits ((Nat.digits 2 n).map (fun d => decide (d = 1)))

/-- A sign bit followed by the self-delimiting binary absolute value. -/
def marketEncodeInt (z : ℤ) : BinaryString :=
  decide (z < 0) :: marketEncodeNat z.natAbs

/-- Canonical rational numerator and positive denominator, each using the
explicit integer/natural binary encoding above. -/
def marketEncodeRat (q : ℚ) : BinaryString :=
  marketEncodeInt q.num ++ marketEncodeNat q.den

/-- A binary element count followed by self-delimiting element encodings. -/
def marketEncodeList {α : Type} (enc : α → BinaryString) (xs : List α) : BinaryString :=
  marketEncodeNat xs.length ++ xs.flatMap enc

/-- Concrete finite rational input.  Validity conditions are kept separate
so malformed strings and malformed numerical inputs are rejected. -/
structure RationalMarketInput where
  means : List ℚ
  weights : List ℚ
  shocks : List ℚ
  shockWeights : List ℚ
  segments : ℕ
  threshold : ℚ

/-- Every field is encoded explicitly; no Cantor-pairing or arbitrary
type-level encoding can distort the input-size measure. -/
def encodeRationalMarket (I : RationalMarketInput) : BinaryString :=
  marketEncodeList marketEncodeRat I.means ++
  marketEncodeList marketEncodeRat I.weights ++
  marketEncodeList marketEncodeRat I.shocks ++
  marketEncodeList marketEncodeRat I.shockWeights ++
  marketEncodeNat I.segments ++ marketEncodeRat I.threshold

/-- The means form the actual finite support: they are distinct and all have
strictly positive probability.  Shock probabilities may be zero; the support
bound used below bounds the entire supplied shock list and hence its support.
No assumption that every realized valuation is nonnegative is imposed. -/
def ValidRationalMarket (I : RationalMarketInput) : Prop :=
  0 < I.means.length ∧
  I.means.Nodup ∧
  (∀ x ∈ I.means, 0 ≤ x) ∧
  I.weights.length = I.means.length ∧
  (∀ w ∈ I.weights, 0 < w) ∧
  I.weights.sum = 1 ∧
  0 < I.shocks.length ∧
  I.shockWeights.length = I.shocks.length ∧
  (∀ w ∈ I.shockWeights, 0 ≤ w) ∧
  I.shockWeights.sum = 1 ∧
  ((I.shocks.zip I.shockWeights).map (fun z => z.1 * z.2)).sum = 0 ∧
  1 ≤ I.segments

/-- Expected revenue from assigning each feature-mean atom to one of the
offered prices.  Purchase occurs at valuation greater than or equal to price.
Matching list lengths in `ValidRationalMarket` ensure the `getD` defaults are
never used for the masses in a valid instance. -/
noncomputable def rationalMarketRevenue (I : RationalMarketInput)
    (prices : Fin I.segments → ℝ)
    (assignment : Fin I.means.length → Fin I.segments) : ℝ := by
  classical
  exact ∑ i : Fin I.means.length,
    (I.weights.getD i.val 0 : ℝ) *
      ∑ j : Fin I.shocks.length,
        (I.shockWeights.getD j.val 0 : ℝ) *
          (if prices (assignment i) ≤ (I.means.get i : ℝ) + (I.shocks.get j : ℝ)
           then prices (assignment i) else 0)

/-- The exact threshold decision problem; prices range over all nonnegative
reals, and unused price slots are allowed. -/
def MeetsPricingThreshold (I : RationalMarketInput) : Prop :=
  ∃ (prices : Fin I.segments → ℝ)
      (assignment : Fin I.means.length → Fin I.segments),
    (∀ j, 0 ≤ prices j) ∧
      (I.threshold : ℝ) ≤ rationalMarketRevenue I prices assignment

/-- Canonical encodings of yes-instances whose noise representation has at
most `C * n^d` atoms, where `n` is the number of distinct customer means.
Strings not encoding such valid inputs are outside the language. -/
def pricingLanguageWithShockBound (C d : ℕ) : BinaryLanguage :=
  {bits | ∃ I : RationalMarketInput,
    encodeRationalMarket I = bits ∧
    ValidRationalMarket I ∧
    I.shocks.length ≤ C * I.means.length ^ d ∧
    MeetsPricingThreshold I}

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 1, p.14; proof pp.39–42 (ec5–ec8).
Read-back

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

Binary strings are finite lists of Boolean symbols, including the empty list, and binary languages are arbitrary sets of such strings. An input/witness pair (x,w)(x,w)(x,w) is encoded over the three-symbol alphabet consisting of the two Boolean symbols and a separator by the symbols of xxx, one separator, and the symbols of www, of length ∣x∣+∣w∣+1|x|+|w|+1∣x∣+∣w∣+1; a Boolean decision is encoded as the singleton list containing that Boolean. A language LLL is in NP as defined here if there are a total Boolean function V(x,w)V(x,w)V(x,w), a polynomial ppp with natural coefficients, and a polynomial-time computation of VVV on this pair encoding such that, for every binary string xxx, x∈Lx\in Lx∈L if and only if there exists a binary string www with ∣w∣≤p(∣x∣)|w|\leq p(|x|)∣w∣≤p(∣x∣) and V(x,w)=trueV(x,w)={\rm true}V(x,w)=true. The machine guarantee is for all correctly encoded pairs; there is no stated behavior requirement on other strings over the three-symbol alphabet. A polynomial-time computation here means existence of a TM2 stack machine with finitely many stacks, control labels, and internal states, designated input and output alphabets identified with the indicated symbol types, and a polynomial with natural coefficients bounding its number of TM2 step transitions in the encoded input length. One such step executes the statement at the current control label through its next jump or halt. The required computation starts with the encoded input on the input stack, other stacks empty and the designated initial internal state, and reaches the designated halted configuration with the encoded output on the output stack, other stacks empty and that initial internal state restored. A polynomial many-one reduction from AAA to BBB is a total function fff on binary strings with such a polynomial-time computation using the identity encodings for both input and output, satisfying x∈Ax\in Ax∈A if and only if f(x)∈Bf(x)\in Bf(x)∈B for every binary string xxx. A language is NP-hard as defined here when every language satisfying the preceding NP definition has such a reduction to it. A rational market input is just a record of four rational lists, a natural number of slots, and a rational threshold before any validity conditions are applied. The encoding used is the following exact bit encoding: a bit list bbb is encoded as ∣b∣|b|∣b∣ one-bits, one zero-bit, then bbb; a natural number uses this encoding of its little-endian base-two digits, with 000 having an empty digit list and hence encoding as one zero-bit; an integer uses a sign bit, true exactly when it is negative, followed by the natural encoding of its absolute value; a rational uses the integer encoding of its canonical numerator followed by the natural encoding of its positive denominator; and a list uses the natural encoding of its length followed by the encodings of its elements. A market encoding concatenates, in order, the encoded mean list, mean-weight list, shock list, shock-weight list, number of price slots, and rational threshold. A valid market consists of lists of rational means μ0,…,μn−1\mu_0,\ldots,\mu_{n-1}μ0​,…,μn−1​ and rational weights w0,…,wn−1w_0,\ldots,w_{n-1}w0​,…,wn−1​ with n≥1n\geq1n≥1, pairwise distinct nonnegative means, strictly positive weights, and ∑iwi=1\sum_iw_i=1∑i​wi​=1; lists of rational shocks e0,…,es−1e_0,\ldots,e_{s-1}e0​,…,es−1​ and rational weights q0,…,qs−1q_0,\ldots,q_{s-1}q0​,…,qs−1​ 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 slots k≥1k\geq1k≥1; and an arbitrary rational threshold τ\tauτ. The two mean lists have equal lengths and the two shock lists have equal lengths. Means need not be sorted; shocks need not be distinct, shock weights may vanish, and no condition μi+ej≥0\mu_i+e_j\geq0μi​+ej​≥0 is imposed. It meets the threshold when there exist nonnegative real prices p0,…,pk−1p_0,\ldots,p_{k-1}p0​,…,pk−1​ 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} for which τ≤∑iwi∑jqjpa(i)1{pa(i)≤μi+ej}\tau\leq\sum_iw_i\sum_jq_j p_{a(i)}\mathbf 1_{\{p_{a(i)}\leq\mu_i+e_j\}}τ≤∑i​wi​∑j​qj​pa(i)​1{pa(i)​≤μi​+ej​}​. The same shock list and probabilities are used at every mean. The prices need not be rational or distinct, unused slots are allowed, and the assignment depends on the mean index but not the shock index. Outside the validity predicate, revenue still uses finite sums over the supplied mean and shock lists, with a missing mean weight or shock weight replaced by 000 and extra weights ignored; the threshold predicate itself does not include market validity. If there are no means, revenue is 000 for every available assignment; if there are means but zero slots, no assignment exists. For natural C,dC,dC,d, the shock-bounded pricing language consists exactly of strings equal to the specified encoding of some valid market that meets its threshold and whose supplied shock-list length satisfies s≤Cnds\leq Cn^ds≤Cnd. This bounds the entire shock list, including repeated shocks and zero-weight entries. Strings with no such encoded witness are outside the language. The language definition allows C=0C=0C=0, in which case it is empty because valid markets require s≥1s\geq1s≥1; it also allows d=0d=0d=0, in which case the bound is s≤Cs\leq Cs≤C. Thresholds need not be positive; every otherwise admissible market with τ≤0\tau\leq0τ≤0 meets the threshold by taking all prices to be zero.

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