Motivation

A seller can often predict a customer's willingness to pay from observed features, yet may be limited to a small number of prices. The decisions are then coupled: the seller must choose both the customer groups and the price assigned to each group. Grouping customers first and optimizing prices afterward does not generally solve the joint problem. Cui and Hamilton study this joint optimization in Optimal Feature-Based Market Segmentation and Pricing, using the structure of a regression model with a common prediction error.

The central question is when that statistical structure makes optimal segmentation tractable. The main positive result is Theorem 2. The companion results describe hardness without the additional shape condition, approximation by greedy price-menu selection, and the value of allowing more segments. The source for the page-specific formalization is the October 22, 2025, 60-page manuscript available under SSRN 4151103.

Setting

Let $M=\mu(X)\ge0$ denote a predicted valuation and let $E$ denote a mean-zero error independent of the observed features. Realized valuation is $V=M+E$. The general model uses separate probability laws $\nu$ for $M$ and $\eta$ for $E$, with finite first moments. Independence is represented by the shared location family: every customer with predicted value $x$ has valuation law $x+E$.

The inclusive survival function is $S(t)=\Pr(E\ge t)$. At nonnegative price $p$, expected customer revenue is $r(x,p)=pS(p-x)$. Inclusive survival is essential when the error distribution has atoms. A finite price menu $P$ earns

$$F(P)=\int \max\bigl(\{0\}\cup\{r(x,p):p\in P\}\bigr)\,d\nu(x).$$

For a fixed menu, assigning every customer to a revenue-maximizing menu price optimizes its segmentation. Write $R_k=\sup_{|P|\le k}F(P)$, $R_\infty=\int\sup_{p\ge0}r(x,p)\,d\nu(x)$, and $R_k^0$ for the same finite-menu problem with zero error. The MHR condition is encoded for density-bearing error laws by log-concavity of survival on its positive domain, the formulation used in the proof of Lemma 2(b). This permits bounded support and zero purchase probabilities.

Formalization targets

Goal: Theorem 2, optimal computation

For $n$ distinct, sorted predicted values with positive probability masses, independent mean-zero MHR error, and a primitive oracle that returns an optimal block price and its attained revenue, construct a globally optimal policy with at most $k$ contiguous index blocks. Its revenue must equal the specified Bellman recurrence, and the reconstructed policy must dominate every assignment of types to $k$ arbitrary nonnegative prices. If each nonempty block-oracle call costs at most $m$, the specified memoized schedule has

$$T(n,k,m)=O\bigl(n^2(k+m)\bigr).$$

The draft states an explicit upper bound $5n^2(k+m)$ for oracle charges, Bellman candidate evaluations, and backtracking. This is an oracle-operation model for already sorted data; it is not a bit-complexity assertion about evaluating arbitrary real probabilities.

Companion results

Theorem 1 asserts NP-hardness even with finitely supported independent mean-zero noise of polynomial support size. Its target uses an explicit binary encoding of rational input data and polynomial-time finite Turing-machine reductions; $k$ is part of the input. Remark 2 targets normalized, monotone, submodular menu revenue and the greedy guarantee

$$F(G_k)\ge(1-e^{-1})\max_{A\subseteq P,\ |A|\le k}F(A).$$

A separate finite-support target shows that nonnegative realized valuations, together with zero, suffice as candidate prices. Theorem 4 states

$$R_\infty-R_k\le\frac{U-L}{k}$$

for any finite almost-sure prediction bounds $L\le M\le U$. Theorem 5 states diminishing increments,

$$R_{k+2}-R_{k+1}\le R_{k+1}-R_k,\qquad k\ge1,$$

under MHR error. These two targets retain general prediction distributions. Theorem 3 includes almost-sure nonnegative realized valuations. Corollary 2 uses this same setting and includes the factor two confirmed by the author during review.

Significance

Theorem 2 replaces a search over arbitrary segmentations with an optimal interval policy and a quadratic-size block table. The performance results explain how a small menu approaches feature-based personalized pricing and when the incremental value of another segment diminishes. The hardness and approximation targets delineate what remains possible when the MHR restriction is removed.

The draft makes ties, atoms, support endpoints, optimizer attainment, and computational costs explicit. Generic proofs of monotone finite-menu assignment under a TP2 revenue condition and Bellman optimality have been checked locally in the pinned Lean environment. The full paper theorems remain open formal proof obligations; well-formed statements are not completed proofs.

Mathematical difficulties and author-confirmed corrections

The interval argument needs an attaining assignment that is monotone despite ties and all-zero revenue rows. Division by survival probabilities would exclude legitimate bounded-support cases. The complexity claim also needs the block oracle's attained revenue, not merely its price. The hardness target requires an actual polynomial-time reduction and careful centering of the constructed error while preserving nonnegative predicted means.

The author confirmed two corrections on October 30, 2026. Theorem 3 now explicitly assumes $V=M+E\ge0$ almost surely. Corollary 2 now includes the factor two:

$$R_\infty-R_k\le2\sqrt{\frac{2\sigma(\mathbb E[M]+\sigma)}{k}}.$$

Corollary 2 retains the same nonnegative realized-valuation setting used in the corrected Theorem 3. Both results are definitive milestone targets in this draft. Two earlier draft records are retained as clearly labeled superseded copies, with their mathematical statements corrected as well; they are not milestones. The nonnegative-valuation assumption supports the proof's bound $R_\epsilon(x)\le x$. For Corollary 2, minimizing $2j\sigma/k+(\mathbb E[M]+\sigma)/j$ gives the corrected factor two. Formal proofs must still handle conditional truncation, boundary atoms, and zero variance.

Formalization scope

General revenue targets use probability measures on the real line, nonnegative integrable predictions, and integrable mean-zero error. The finite computational model uses strictly increasing predicted values and positive weights summing to one. At most $k$ price slots are allowed; repeated cuts represent unused slots. Index intervals include every type, including the largest support point. Least optimal prices implement a deterministic tie convention; no interior first-order condition or uniqueness assumption is imposed.

The definition layer contains no proof placeholders or new axioms. Real suprema and infima are defined from the feasible economic objects; their attainment and boundedness must be proved where needed. The MHR-to-TP2 bridge is a theorem target, not an assumption that deletes the analytic content. The Bellman recurrence, its partition relation, and its charged evaluation schedule are separate objects. The goal connects that recurrence to the original unrestricted assignment problem and an actual feasible reconstruction.

The general model, the rational binary-input hardness model, and the discrete candidate-price model are explicit interfaces. Their connecting lemmas, optimizer existence, the analytic MHR argument, interval-to-DP reconstruction, and the source's companion results remain available proof obligations. The optional derivative refinement of Lemma 1 and appendix extension/necessity theorems are outside this first proposal. Every uploaded item includes an independent read-back for comparison with its intended mathematical content.

Selected references

• Titing Cui and Michael L. Hamilton, Optimal Feature-Based Market Segmentation and Pricing, Operations Research 74(3), 1354–1370 (2026). DOI. Page citations refer to the October 22, 2025 manuscript, SSRN 4151103.
• Adrien Saumard and Jon A. Wellner, Log-concavity and strong log-concavity: a review, Statistics Surveys 8, 45–114 (2014), Section 11, cited in the source's proof of Lemma 2(b). DOI.