NeurIPS 2026 (Accepted, according to the acceptance list supplied with the task) Optimization nonlinear pricing budget constraints piecewise-linear convex functions linear programming extreme-point sparsity

Non-Linear Pricing Restores Tractability for a Data Seller¶

Conference: NeurIPS 2026 (Accepted, according to the acceptance list supplied with the task)
arXiv: 2609.36589
Area: Optimization & Theory (data markets and algorithmic game theory)
Keywords: nonlinear pricing, budget constraints, piecewise-linear convex functions, linear programming, extreme-point sparsity

TL;DR¶

With known linear buyer valuations and budgets and separate pricing for each dataset, allowing nonlinear prices turns the previously APX-hard optimal linear-pricing problem into a polynomial-time LP and guarantees an optimum with at most as many total kinks as buyers; instances constructed from California Housing also exhibit revenue ratios of at most 1.1 and at most 10 total kinks.

Background & Motivation¶

A data seller seeks maximum total revenue from multiple budget-constrained buyers, but buyers do not purchase indefinitely simply because data is inexpensive. They purchase data to improve predictions, account for its informational value, subtract payments, and respect their budgets. The paper follows a precision-gain model based on Gaussian priors and additive Gaussian noise: precision is reciprocal variance, and the gain from additional data can be represented as a linear combination of the purchased dataset fractions. The seller therefore has a buyer–dataset valuation matrix, while each buyer solves a budget-constrained net-utility maximization problem.

The earlier Revenue-optimal pricing for budget-constrained buyers in data markets permits only one fixed unit price per dataset. Changing a price changes both the datasets buyers want and how they distribute their budgets; this restricted problem is already APX-hard. A richer price-function space might appear harder to search, but the paper identifies the single-price restriction as part of the difficulty. One linear price struggles to serve low- and high-valuation buyers simultaneously, whereas a segmented price can offer a low-marginal-price prefix followed by a more expensive remainder for high-valuation buyers.

This is an academic data-trading model, not financial investment advice. Data is non-rivalrous: the same dataset can be sold to multiple buyers, with no inventory constraint limiting their aggregate purchased fractions. The authors also argue that duplicate identities buying cheap prefixes receive overlapping records rather than additional information. That explanation depends on record overlap and delivery rules; it is not a general anti-collusion mechanism. Core Idea: prove that every admissible separable price can be replaced without revenue loss by a piecewise-linear convex price with slopes drawn from buyer valuations, then optimize the continuous lengths of those slope segments through a linear program.

Method¶

Overall Architecture¶

The inputs are \(n\) buyers, \(m\) datasets, nonnegative valuations \(\tau_{i,j}\), and budgets \(b_i\); the outputs are total-payment functions for purchased fractions \(x\in[0,1]\) of each dataset. Prices are common to all buyers and add separately across datasets, with zero payment for buying nothing. The seller may use monotone, lower-continuous functions. The authors define lower-continuous as equality with the local lower limit, meaning lower semicontinuity rather than ordinary continuity of every admissible input price.

A buyer values a bundle at \(\sum_{j=1}^{m}\tau_{i,j}x_j\) and has net utility equal to that value minus total payment. The buyer first maximizes net utility within the budget. When multiple bundles are optimal, revenue is defined using the largest payment among them: seller-favorable tie-breaking. This must not be replaced by directly maximizing buyer expenditure, which would not establish that the buyer wants the resulting bundle.

The analysis and algorithm center on four designs. The budget-exhaustion relation handles the coupling between budgets and demand; convexification and slope discretization establish that PLC (piecewise-linear convex) prices suffice; the shard-length LP finds globally optimal prices; and extreme-point sparsity explains why an optimum remains nearly linear. This is an analysis of mechanism and optimization structure, not a neural-network training pipeline, so no network-style framework diagram is used.

Key Designs¶

1. Budget-exhaustion relation: distinguish optimal net utility from maximum payment

A binding budget does not automatically make a buyer spend it all. Appendix A.2 constructs a nonconvex single-dataset price for a buyer with per-unit value 2 and budget 1.3 who purchases fraction 0.4 and pays only 0.4. Further purchases initially reduce net utility, and the budget is insufficient to cross that loss and reach the preferable full bundle. With unlimited budget, the same buyer purchases the whole dataset and pays 1.5. This counterexample shows that simply truncating unlimited-budget expenditure at the budget is invalid for general prices.

For continuous prices and concave net utility, the authors prove a budget-exhaustion theorem. Linear valuation minus convex pricing satisfies the required concavity, giving:

\[ r(\mathbf p\mid\tau_i,b_i)=\min\{b_i,\ r(\mathbf p\mid\tau_i,\infty)\}. \]

If the maximum payment of an unlimited-budget optimal demand is within the budget, that demand is already affordable. Otherwise, interpolate between a budget-feasible optimal bundle and an unlimited-budget optimal bundle. Price continuity yields a point costing exactly the budget, and net-utility concavity ensures that it remains optimal within the budget. The conclusion is that an optimal demand consistent with the revenue definition spends the budget, not that every optimal demand must do so. This relation lets later proofs analyze unlimited-budget demand before truncating revenue, without incorrectly assigning an independent full budget to each dataset.

2. Convexification and slope discretization: reduce the function space to finite slope sets

The first step replaces a price by its lower convex envelope. Although the envelope is cheaper at some bundles, revenue does not decrease. With linear valuations, an unlimited-budget buyer cannot optimally choose a point strictly above the envelope: the bundle can be represented as a convex combination of contact points, at least one of which offers higher net utility. Finite budgets require more than this intuition. Appendix A.3 combines the budget-exhaustion relation with a case split on whether unlimited-budget revenue after convexification reaches the budget, establishing that each buyer's revenue contribution does not decrease.

The second step aligns each dataset's convex marginal-price slopes with its buyer-valuation set. Slopes below the maximum valuation round upward to the nearest candidate; a tail exceeding the maximum valuation is capped at that largest candidate. The definition in Appendix A.5 handles this tail, which the main text's upward-rounding description leaves uncovered. Because the candidate set includes every buyer's marginal valuation, the rightmost demand threshold cannot move left, and the corresponding unlimited-budget payment cannot decrease. Budget exhaustion then preserves the revenue guarantee under finite budgets. Purchased fractions under finite budgets need not remain identical.

For multiple datasets, the essential property is separability, not independently granting the buyer's full budget to each dataset. The convex envelope of a separable price equals the sum of its component envelopes; unlimited-budget net-utility demand decomposes by component, and revenue adds. The structural theorem therefore guarantees a separable PLC replacement for any separable monotone lower-continuous price, with no buyer's revenue contribution reduced and with slopes drawn only from that dataset's buyer valuations. Some intermediate convexification results allow nonseparable functions, but the final algorithm is optimal within separable pricing, not arbitrary cross-dataset bundle pricing.

3. Shard-length LP: turn price design into continuous resource allocation

Once the slopes are fixed, only their segment lengths remain to be chosen. Let \(z_{t,j}\) be the fraction of dataset \(j\) charged at slope \(\tau_{t,j}\). Ordering positive lengths by increasing slope reconstructs a convex price. Lengths sum to 1 for each dataset and may be zero; adjacent segments with equal valuations can be merged.

With unlimited budget, a buyer purchases segments whose marginal prices do not exceed the buyer's marginal valuation. Equality relies on seller-favorable tie-breaking. Potential payment is thus the sum of price times length over shards satisfying \(\tau_{t,j}\leq\tau_{i,j}\), capped by the total budget. Revenue variables \(r_i\) implement these two upper bounds, producing the LP in the paper's equation (3):

\[ \begin{aligned} \max_{z,r}\quad &\sum_{i=1}^{n}r_i\\ \text{s.t.}\quad &r_i\leq b_i &&\forall i,\\ &r_i\leq\sum_{j=1}^{m}\sum_{t=1}^{n}\tau_{t,j}\mathbf 1\{\tau_{t,j}\leq\tau_{i,j}\}z_{t,j} &&\forall i,\\ &\sum_{t=1}^{n}z_{t,j}=1 &&\forall j,\\ &z_{t,j}\geq0 &&\forall t,j. \end{aligned} \]

The objective pushes each revenue variable to the smaller upper bound. This is therefore not merely a relaxed revenue bound: it exactly implements revenue from buyer demand. The LP has \(nm+n\) variables and polynomial size in the buyer and dataset counts. After finding prices, optimal buyer bundles can be recovered through fractional knapsack over the shards. Cross-dataset budget allocation accounts for value relative to payment, while cheaper shards of a given dataset precede more expensive ones. Saying that all nonnegative-net-utility shards are desirable does not mean their purchase order is arbitrary under a finite budget.

The displayed source LP does not explicitly include \(r_i\geq0\), whereas the following proof treats revenue as nonnegative when discussing a bounded feasible region. The display above preserves that difference rather than pretending it is absent. Optimal revenue is nonnegative, and an explicit nonnegativity constraint is consistent with the variables' interpretation.

4. Extreme-point sparsity: concentrate nonlinearity in relatively few datasets

A general optimal LP solution can assign positive lengths to many shards. The guarantee is that an optimal basic feasible solution exists with at most \(m+n\) positive lengths. Every dataset needs at least one positive-length segment; only segments beyond these \(m\) baseline segments can create interior kinks. After equal slopes are merged, total kinks across all datasets are at most \(n\), and at least \(\max(0,m-n)\) datasets are priced entirely linearly.

The bound follows from counting tight constraints at an extreme point, not from a sparsity regularizer. If \(k\) constraints from the two buyer-revenue upper-bound families are tight and the length matrix has \(d\) positive entries, the length-sum and zero-entry constraints supply enough additional tight constraints to yield \(d\leq m+(k-n)\leq m+n\). Thus, when datasets greatly outnumber buyers, allowing nonlinear pricing does not require complicated prices for every dataset.

The authors also construct a single-dataset instance with \(n\) buyers. Buyer \(i\) has value \(i\) and budget \(i(i+1)/(2n)\), with every slope segment assigned length \(1/n\). Its unique optimal length solution has \(n-1\) kinks, so the general upper bound cannot be substantially improved in order. This is worst-case structural evidence, not a claim that observed markets usually contain that many kinks.

A Worked Example¶

The sharding interpretation in Appendix A.8 gives three marginal prices: unit price 10 for the first 0.4 fraction, 25 for the next 0.4, and 65 for the final 0.2. Buying fraction 0.6 means taking the whole first shard and half the second. Calculated from the displayed source price, payment is \(10\times0.4+25\times0.2=9\). It is not \(25\times0.6\), because the PLC price retains the inexpensive prefix.

For an illustrative demand calculation derived from this price, consider a buyer with per-unit value 25 and budget 9. The first shard increases net utility, the second adds no further net utility, and the third reduces it. Among affordable bundles maximizing net utility, seller-favorable tie-breaking selects fraction 0.6 and payment 9. This shows both why the LP's valuation threshold includes equality and why the budget caps the entire bundle.

In the cached Example 5, the plin parameters are written as (0.4,0.4), whereas the subsequent segment intervals, payment formula, and shard sizes correspond to breakpoints 0.4 and 0.8. This inconsistency is retained explicitly. The example uses the internally consistent latter shard description rather than silently repairing the parameter expression as an exact author formula.

Key Experimental Results¶

Main Results¶

The experiments do not benchmark prediction SOTA for a new learning algorithm. They construct data markets from California Housing and examine optimal-price revenue and complexity. The source dataset has 20,640 rows and 9 numeric columns. Median house value is the target known to all buyers; the remaining input columns form 4 seller datasets: income, housing structure, demographics, and location. A random 80% of rows forms the training set, and the remaining test rows are sorted by latitude and distributed across buyers to represent regional prediction interests.

Ridge regression is trained for each dataset, and the gain in reciprocal MSE on a buyer's region supplies \(\tau_{i,j}\). The authors explicitly use linearized valuations and do not establish additivity of the predictive gains from actual data combinations. Budgets scale total valuation by \(B_i\sim\operatorname{Beta}(\alpha_B,1)\) and \(f_{\max}\). Several \(n\in[1,100]\) values are selected, with 16 instances for each selected buyer count and parameter ranges \(f_{\max}\in[0.4,1.3]\) and \(\alpha_B\in[0.3,1]\).

Item	Reported result	Scope and interpretation
Data-market size	\(m=4\), several \(n\in[1,100]\), 16 instances per selected \(n\)	Simulated markets constructed from one real dataset, not multiple independent market datasets
Optimal nonlinear/linear revenue ratio	At most 1.1	Optimal linear baselines are computed only for \(n\leq20\); nonlinear revenue advantage is at most 10% within this comparison range
Total kinks across all prices	At most 10	Observation on the constructed LP instances, not 10 kinks per price function
Computation time	16 seconds, Apple M4, MacBook Air 2025	Aggregate time for the described computations, not single-instance latency or a controlled baseline speedup
Solver and implementation	HiGHS dual-simplex through SciPy; Python and NumPy	No learning-training throughput is reported, and no code-repository link is verified for this note

Optimal linear revenue is computed using the earlier \(O(n^{m}\cdot nm)\) brute-force algorithm, limiting that comparison to \(n\leq20\). Kink observations also cover the selected larger buyer counts. Figure 4 displays means, interquartile bands, and minimum–maximum bands. The cache contains no per-point values, so exact means or standard deviations for individual buyer counts cannot be filled in.

Ablation Study¶

There is no module-removal ablation. The table instead summarizes pricing restrictions and theoretical counterexample analyses without inventing experimental configurations.

Configuration or analysis	Verifiable result	Note
Linear prices only	APX-hardness established by earlier work	One slope per dataset; not a baseline with the same complexity as the paper's LP
Separable monotone lower-continuous prices	A revenue-preserving PLC replacement exists	Slopes come from buyer valuations, and a continuous-length LP solves the problem exactly
Optimal basic feasible solution	At most \(m+n\) positive lengths and at most \(n\) total kinks	At least \(\max(0,m-n)\) linear datasets; the same sparsity bound is not asserted for every optimum
Single-dataset worst-case structure	Unique optimum with \(n-1\) kinks	Values \(i\), budgets \(i(i+1)/(2n)\), and lengths \(1/n\)
Rich buyer and low-valuation buyers	Revenue ratio approaches \(2-1/n\)	Limit as \(\varepsilon\to0\) in Example 1, not exact equality for arbitrary finite \(\varepsilon\)
Budget counterexample with nonconvex pricing	At budget 1.3, payment 0.4; with unlimited budget, payment 1.5	Shows why the budget-exhaustion relation needs continuous prices and concave net utility

Key Findings¶

The linearity gap is optimal admissible-pricing revenue divided by optimal linear-pricing revenue. In this model it also equals the shard-length LP's integrality gap: integer length variables leave one slope with length 1 for each dataset.
Constructed examples approach a nearly twofold nonlinear revenue advantage, but comparable California Housing instances have ratios at most 1.1. This supports a small gap in the specific linearized simulation, not a conclusion about all real data markets.
Conjecture 1 proposes a linearity gap of at most 2. The value 2 is a conjectured upper bound, not a proved theorem. Established results concern pricing structure, polynomial-time solvability, and the revenue ratios and kink properties of particular instances.
The empirical maximum of 10 kinks contrasts with the worst-case \(n-1\) construction and suggests that simple segmented prices may suffice. The paper does not solve optimal pricing with a prespecified kink limit.

Highlights & Insights¶

A larger decision space can reduce computational difficulty. Linear pricing imposes the discrete choice of one slope per dataset, whereas nonlinear pricing permits continuous length allocation; the structural theorem ensures that this relaxation corresponds exactly to a legitimate optimal economic mechanism.
A budget constrains the buyer's total demand rather than independently capping each dataset. The budget-exhaustion theorem lets one-dimensional threshold arguments compose across datasets, providing the bridge to a global LP.
Simplicity comes from optimal-solution geometry rather than forcing prices to be linear in advance. Selecting a basic feasible solution supplies sparse segmentation, suggesting a route to implementable optima in other mechanism-design problems.

Limitations & Future Work¶

Linear additive valuation is a core boundary. The Gaussian precision model offers one justification, but real datasets can be correlated, complementary, and subject to diminishing returns. The experiments also deliberately linearize valuations, so the LP does not directly handle arbitrary nonlinear data utility.
The seller knows valuations and budgets, and buyers are assumed to maximize net utility exactly with seller-favorable tie-breaking. The paper does not resolve truthful elicitation of private information, valuation-estimation error, or unfavorable tie-breaking.
Optimality concerns a single seller's separable prices. It does not cover arbitrary bundle pricing, competing-seller equilibria, buyer externalities, resale, or collusion. Non-rivalrous data and overlapping-prefix delivery do not substitute for a proof of resistance to duplicate identities.
Empirics use only a 4-dataset market constructed from one data source, with linear-price comparisons restricted to \(n\leq20\). More valuation structures, more seller datasets, and price stability under parameter perturbations are useful extensions, not results already validated here.
The cached main-text Theorem 3 sketch says purchased quantities are unchanged and ends with an equality of the same revenue with itself; Appendix Lemma 9 instead reasons that the rightmost demand point does not move left. A.9 also contains summation limits inconsistent with its subsequent weighted derivation. This note follows clearly stated theorem conclusions without guessing repairs to damaged proof formulas.
The omitted explicit revenue nonnegativity constraint and Example 5's breakpoint-parameter conflict also warrant attention. These presentation issues are distinct from whether the general linearity gap is bounded by 2, which remains an explicitly open conjecture.

vs Revenue-optimal pricing for budget-constrained buyers in data markets (CGSS26b): Under the same budgeted-buyer and data-valuation background, the earlier paper restricts prices to linear unit prices and establishes hardness. This paper permits segmented prices and restores exact tractability through a structural theorem and LP, rather than merely offering a heuristic for the difficult linear problem.
vs Myerson ironing: Both smooth irregular structure, but classical ironing acts on virtual valuations or allocation rules in auctions, whereas this paper convexifies prices shared by all buyers. It is not a truthful private-information reporting mechanism for these known-valuation buyers.
vs competitive equilibrium and data-exchange economies: Work on data pricing via competitive equilibrium, oligopolistic markets, and exchange without monetary transfers studies equilibrium or stability. This paper fixes a single seller and maximizes revenue, without guaranteeing welfare or fairness optimality.
Research directions: Robust segmented prices with guarantees under valuation-estimation error, or complexity and approximation bounds under a fixed kink budget, follow naturally from the assumptions and sparse structure. These are suggested extensions, not algorithms supplied by the paper.

Rating¶

Novelty: 4/5. Connecting greater pricing flexibility to lower computational difficulty is the central structural contribution, beyond using an LP solver.
Experimental Thoroughness: 4/5. Proofs and real-data-derived simulations complement each other, but the data source is singular and linear-baseline comparisons have limited scale.
Writing Quality: 4/5. The main argument and appendix explanations are clear, although several cached formulas and proof-sketch statements need careful checking.
Value: 4/5. The mechanism is computable, interpretable, and admits a sparse optimum, with applicability bounded by linear valuations and known budgets.