PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-Linear Pricing Restores Tractability for a Data Seller

Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma, Jiaxin Song

arXiv:2609.36589v1cs.GT

TL;DR

The paper asks how a monopolistic seller should price datasets for budget-constrained buyers, building on prior work on linear pricing [CGSS26b]. It studies general monotone, lower-continuous pricing and shows that an optimal PLC solution is computable in polynomial time, with at most n kinks across datasets.

  • Problem

    The paper studies how a monopolistic seller should price multiple datasets to maximize revenue from buyers who choose bundles under budget constraints.

    Source: §1 · p. 1

  • Method

    It proves an optimal solution exists among PLC pricing functions and formulates the resulting optimization as a linear program.

    Source: §1 · p. 2, §1.2 · pp. 3–4

  • Results

    At most n kinks are needed across all pricing functions, and an optimal PLC solution can be computed in polynomial time.

    Source: §1.2 · pp. 3–4

  • Takeaways & Limitations

    When datasets significantly outnumber buyers, most datasets are priced linearly in the revenue-maximizing scheme.

    Source: §1.2 · p. 4

    The pricing model considers functions required to be monotone and lower-continuous.

    Source: §1 · p. 2, §1.1 · p. 3

Abstract

from arXiv · show

We consider a data seller who designs pricing mechanisms over multiple datasets to maximize revenue from budget-constrained buyers. The seller offers multiple datasets and assigns each a pricing function that maps the quantity purchased to a total payment. The goal is to design these pricing functions to maximize revenue, anticipating that buyers---who trade off accuracy gains against cost---choose bundles optimally subject to their budget constraints. Prior work [Chaudhury et al., 2026] studies such optimal pricing under the restriction that each dataset is assigned a linear price, and shows that computing optimal linear prices is computationally intractable. In contrast, we allow each dataset to be priced via a general function and show that this additional flexibility can not only increase the revenue but also restore tractability, yielding a surprising simultaneous improvement in economic performance and computational efficiency. Even when pricing functions are only required to be monotone and lower-continuous, optimal pricing admits a highly structured and simple form: each pricing function is piecewise linear and convex (PLC), and the optimal solution can be computed in polynomial time. Moreover, the total number of kinks across all pricing functions is bounded by the number of buyers. Consequently, when datasets significantly outnumber buyers, most pricing functions are effectively linear. We further empirically study the structure of optimal pricing by analyzing the number of kinks and the revenue gap between optimal nonlinear pricing and optimal linear pricing on simulations generated from a real dataset.

1 Introduction

The paper studies how a monopolistic data seller should price datasets for budget-constrained buyers, and considers pricing functions beyond the linear prices studied in prior work [CGSS26b]. It shows that optimal pricing can be computed in polynomial time using structured PLC functions, with at most n kinks across all datasets.

1 Introduction

  • General pricing can increase revenue by up to a factor of two and makes revenue maximization tractable, unlike the APX-hard linear-pricing problem studied by [CGSS26b].The paper models buyers as choosing utility-maximizing dataset bundles subject to their budgets.Source: §1 · pp. 1–2

1.1 Our Model

  • Buyers value bundles by their prediction-accuracy gains and choose fractions of datasets to maximize utility within their budgets; pricing functions are required to be monotone and lower-continuous.Lower continuity ensures a utility-maximizing demand bundle exists.Source: §1.1 · pp. 2–3, §1 · p. 2

1.2 Our Contributions

  • Revenue-maximizing pricing functions can be found in polynomial time: an optimal solution exists with PLC prices, and segment lengths let the seller formulate the problem as a linear program.Each PLC function’s left derivative at any x in (0, 1] is drawn from the buyers’ dataset-informativeness values τi,j.Source: §1.2 · pp. 3–4
  • At most n kinks are needed across all pricing functions, so when datasets significantly outnumber buyers, most datasets are priced linearly.On instances built from a real-world dataset, experiments found both the linearity gap and kink count substantially smaller than in specially constructed worst-case examples.Source: §1.2 · p. 4

1.3 Related Work

  • Related work spans data valuation, data-sharing incentives, and monopolistic data selling, with prior studies differing in assumptions about information, price discrimination, dataset modification, and budget constraints.The paper points to [Pei20] for a survey of data pricing.Source: §1.3 · p. 4

2 Technical Overview

The overview transforms separable monotone, lower-continuous pricing into piecewise-linear convex (PLC) pricing and optimizes it with a linear program. The resulting pricing is computable in polynomial time and has at most n kinks across all datasets.

2.1 The Model

  • Buyers choose affordable bundles to maximize net utility, while the seller chooses monotone pricing to maximize total revenue.The overview considers separable prices, with each dataset priced independently.Source: §2.1 · p. 5

2.2 Structural Theorem

  • For separable MLC prices, a revenue-nondecreasing transformation yields continuous, convex, piecewise-linear components whose slopes come from buyers’ valuations.The structural theorem applies to buyers with linear valuations and budgets.Source: §2.2 · p. 6

2.2.1 Step 1: Convexification

  • Replacing an MLC price by its convex envelope does not reduce revenue and produces a monotone, continuous, convex price.The proof intuition relates utility-maximizing bundles under the original price to those under its convex envelope.Source: §2.2.1 · pp. 6–7

2.2.2 Step 2: Piecewise-Linearization

  • For one dataset, rounding marginal prices up to a finite set containing the buyer’s value preserves or increases revenue and yields a PLC price.With multiple buyers, the relevant slope set consists of their valuations; the paper then applies this discretization per dataset.Source: §2.2.2 · pp. 7–8

2.2.3 Composing the Transformations

  • For multiple datasets, separability lets the authors compose the transformations componentwise, extending the structural result beyond the single-dataset discretization step.The composition uses each dataset’s buyer-valuation thresholds.Source: §2.2.3 · p. 8

2.3 Finding the Optimal PLC Pricing Using an LP

  • The LP represents PLC prices through segment lengths and maximizes buyer expenditure, yielding a revenue-maximizing separable price in polynomial time.A buyer purchases while budget remains and marginal utility exceeds marginal price.Source: §2.3 · pp. 8–9
  • At most n kinks occur across the optimal prices, so at least max(0, m − n) datasets are linear; when m ≫ n, nearly all are linear.The paper gives an example with n − 1 kinks, making the upper bound nearly tight.Source: §2.3 · p. 9

2.4 Linearity Gap

  • A constructed instance has linearity gap 2 − 1/n: nonlinear pricing serves poor and rich buyers with low-priced data followed by a high-priced remainder.Linear pricing must choose between a low price for all buyers and a high price for the rich buyer alone.Source: §2.4 · p. 10

3 Empirics

The California Housing experiments find a small linearity gap and few observed pricing-function kinks, while the appendix outlines proofs behind general-pricing results.

3 Empirics

  • Using California Housing, they split inputs into four feature groups, assign geographic test regions to buyers, and value datasets by ridge-regression precision gains under linearized valuations.Source: §3 · pp. 10–11
  • Budgets scale with buyers’ total marginal valuations and Beta-distributed factors; the experiments vary n from 1 to 100 and construct 16 instances per n.Source: §3 · p. 11, Figure 4 · p. 11
  • They solve for nonlinear prices with an LP and observe kinks, comparing against brute-force optimal linear prices only when n≤20.The linear-price algorithm is from [CGSS26b].Source: §3 · p. 11
  • The empirical linearity gap is at most 1.1, below the demonstrated 2−1/n example bound; Figure 4 summarizes 16 instances per n.The figure’s line is the mean; its darker and lighter shaded regions show the first-to-third quartiles and the minimum-to-maximum range, respectively.Source: Figure 4 · p. 11, §3 · p. 11
  • The authors conjecture that linear pricing recovers at least half the revenue of optimal nonlinear pricing because the linearity gap is at most 2.Source: §3 · p. 11
  • At most 10 kinks were observed, compared with n−1 in a worst-case example.The authors say the observed kink count can be much smaller than the worst case.Source: §3 · p. 12

A Details on Revenue Maximization under General Pricing

A.1 MLC Pricing

A buyer’s utility-maximizing bundle need not exist for every pricing function; monotone lower-continuous pricing rules out that failure.

A.1 MLC Pricing

  • In Example 2, the buyer’s supremum net utility is 0.5, but no affordable bundle attains it, leaving the demand set empty.At x=0.5, net utility is 0, while values just below 0.5 approach 0.5 without reaching it.Source: §A.1 · p. 16
  • The example’s discontinuous price is identified as the source of nonexistence; monotone lower-continuous pricing guarantees a utility-maximizing affordable bundle.Source: §A.1 · pp. 16–17
  • Lower continuity can be assumed without loss of revenue: at a discontinuity, a slightly smaller bundle can retain nearly the same value at a substantially lower price.Source: §A.1 · p. 17

A.2 Budget Exhaustion

Under concavity of net utility, a budgeted buyer spends the lesser of the budget and unbudgeted revenue; convexity is essential for this equality.

A.2 Budget Exhaustion

  • Without convex pricing, a buyer with budget 1.3 chooses quantity 0.4 and spends 0.4, despite being budget-constrained.In the example, for budgets at least 1.5 the buyer chooses the whole dataset and pays 1.5.Source: §A.2 · pp. 17–18
  • If an unbudgeted revenue-maximizing bundle costs no more than b, the budgeted and unbudgeted demand sets and revenues coincide.Source: §A.2 · p. 18
  • For general budgeted pricing, revenue is bounded above by min(b, r(p | τ, ∞)); the theorem makes this bound tight under its concavity condition.Source: §A.2 · pp. 18–19
  • When net utility is concave, budgeted revenue equals min(b, r(p | τ, ∞)), so a buyer whose unbudgeted optimum costs more than b exhausts the budget.Source: §A.2 · pp. 18–19

A.3 Convexifying the Pricing Function

Convexifying a pricing function does not reduce revenue and yields a monotone, continuous, convex function. For a single dataset, the buyer’s revenue-maximizing demand point is identified by a rate-equalization rule.

A.3 Convexifying the Pricing Function

  • A bundle priced strictly above its convex hull can be represented by a convex combination of bundles where the prices coincide, so a buyer prefers one of those bundles.This gives the argument for why convexification does not decrease revenue.Source: §A.3 · p. 19
  • Replacing a pricing function by its convex hull preserves or increases revenue and produces a monotone, continuous, convex price.The convex hull is the largest convex function lying below the original pricing function.Source: §A.3 · pp. 19–20

A.4 Rate Equalization

  • For a single dataset and an infinite-budget buyer, the rightmost point where the pricing function’s left derivative is at most the buyer’s value per unit maximizes revenue in the demand set.At that point, revenue equals the price of the bundle.Source: §A.4 · p. 21

A.5 Piecewise-Linearization

Piecewise-linearizing a convex price at buyer valuation rates preserves or increases revenue. Separability lets the analysis of aggregate prices and buyer choices reduce to their dataset components.

A.5 Piecewise-Linearization

  • With multiple buyers, rounding marginal prices to buyer valuation rates makes the price piecewise linear; non-convex prices need not tolerate such increases without revenue loss.The paper’s example shows revenue falling from 1.5 to 0.4 after a price increase on a non-convex function.Source: §A.5 · p. 22
  • Discretizing a monotone, continuous, convex price into a piecewise-linear function preserves or increases revenue for a buyer with a linear valuation and budget.The discretized price remains monotone, continuous, and convex.Source: §A.5 · p. 23

A.6 Separability

  • For separable functions, convexification acts componentwise, and optimizing the aggregate is equivalent to optimizing its components independently.The aggregate is monotone, lower-continuous, or convex exactly when its components have the corresponding property.Source: §A.6 · pp. 23–24

A.7 Proof of the Structural Theorem

The structural theorem replaces any separable monotone, lower-continuous pricing function with one that gives every buyer at least as much revenue and has a restricted piecewise-linear convex form.

A.7 Proof of the Structural Theorem

  • The construction convexifies each dataset’s price and discretizes it at the distinct buyer valuation rates, preserving or increasing each buyer’s revenue.The resulting component prices are monotone, continuous, convex, and piecewise linear.Source: §A.7 · p. 25
  • For every buyer, the replacement pricing function yields at least the original revenue, and each dataset’s component is monotone, continuous, convex, and piecewise linear.Its left derivative at any positive quantity belongs to the set of buyers’ valuations for that dataset.Source: §A.7 · p. 25

A.8 The Sharding Interpretation

A piecewise-linear price can be interpreted as linear prices on successive shards of one dataset. Buyers do not use the extra freedom to purchase shards out of order.

A.8 The Sharding Interpretation

  • Although separate shards could be purchased out of order, buyers purchase the cheapest shard first because their per-unit value is the same across shards.The example’s 0.6 fraction consists of the first shard and half of the second.Source: §A.8 · p. 26
  • A piecewise-linear price is equivalent to splitting a dataset into shards, each with its own size and per-unit price.The example has shard sizes 0.4, 0.4, and 0.2, priced at 10, 25, and 65 per unit, respectively.Source: §A.8 · p. 26
  • After finding the revenue-maximizing price, the corresponding buyer allocation can be computed efficiently as fractional knapsack over the shards.The stated allocation objective first maximizes net utility and then the amount paid.Source: §A.8 · p. 26

A.9 Number of Kinks in LP

An optimal basic feasible solution has at most n total kinks across its PLC pricing functions, and an example shows this bound is nearly tight. The appendix also compares the pricing analysis to auction-theory ironing, noting important differences in scope and implementation.

A.9 Number of Kinks in LP

  • An optimal basic feasible solution has at most n total kinks across the PLC pricing functions.An example with n −1 kinks shows the bound is nearly tight.Source: §A.9 · p. 26
  • A one-dataset instance with buyer i valuing the dataset at i and budget i(i + 1)/2n has a unique LP optimum with z_i,1 = 1/n.The construction demonstrates the near-tightness example’s specific instance.Source: §A.9 · p. 26

B Comparison to Ironing Techniques

  • The authors interpret their pricing analysis as analogous to auction-theory ironing, but their procedure covers multiple datasets and buyers and is captured by a linear program.They contrast this with Myerson’s single-item setting and the difficulty of extending it to multiple-item auctions.Source: B Comparison to Ironing Techniques · p. 27
  • Unlike the complex integral expression that may determine Myerson’s payments, the paper’s pricing functions are piecewise linear with derivatives taken only from buyers’ values.The authors describe this structure as easier to implement in practical settings.Source: B Comparison to Ironing Techniques · p. 27

C Details on Real and Convex Analysis

This appendix collects standard results from real and convex analysis used elsewhere in the paper. It reviews extended real numbers and convergence of sequences, among other topics.

C Details on Real and Convex Analysis

  • The appendix gathers mostly standard results from real and convex analysis, including material on monotone functions, convexity, and left derivatives of convex functions.The authors state that most results are well-known.Source: C Details on Real and Convex Analysis · pp. 27–28

C.1 Extended Real Numbers

  • The extended real number system adds −∞ and ∞ to the reals, and the appendix defines supremum and infimum for sets in that system.It also states conventions for arithmetic involving infinities.Source: §C.1 · p. 28

C.2 Convergence of Sequences

  • The appendix defines sequence convergence and boundedness, states that bounded sequences have convergent subsequences, and notes that most proofs are omitted as standard.It also defines closed sets through limits of convergent sequences.Source: §C.2 · p. 29

C.3 Monotonicity and Continuity

This section defines monotonicity and lower continuity and develops consequences for optimization over budget-feasible sets. It establishes support and closedness properties and gives an existence result for a utility-maximizing feasible choice.

C.3 Monotonicity and Continuity

  • A function is MLC when it is both monotone and lower-continuous; monotonicity means coordinatewise larger inputs cannot lower the function value.The appendix permits extended-real codomains for monotone functions, which is useful in Appendix A.4.Source: §C.3 · p. 30
  • For any sequence in the unit cube, the appendix constructs a monotone sequence dominated by the original sequence that converges to the same limit.For an MLC function, its values along this constructed sequence have supremum equal to the function value at the limit.Source: §C.3 · pp. 30–31
  • An MLC function’s sublevel set is either empty or closed.This closedness is used to show that a continuous utility function attains its maximum over the budget-feasible set when the price function is MLC and p(0) = 0.Source: §C.3 · p. 31

C.4 Convex Sets

This appendix section introduces convex sets and convex hulls and records basic properties used in the paper’s analysis.

C.4 Convex Sets

  • A set is convex if every strict convex combination of two of its points remains in the set.The appendix defines the convex hull as the set of finite convex combinations of points from the original set.Source: §C.4 · pp. 31–32
  • Convex hulls preserve set inclusion, while the convex hull of an intersection is contained in the intersection of the convex hulls.Source: §C.4 · p. 32
  • For a closed and bounded set in finite-dimensional Euclidean space, its convex hull is closed and bounded.The appendix attributes this result to Theorem 17.2 in.Source: §C.4 · p. 32

C.5 Convex Functions

The appendix develops properties of convex hulls of monotone lower-continuous functions, characterizes left derivatives of convex functions, and relates separable functions to their components.

C.5 Convex Functions

  • For monotone lower-continuous functions, the convex hull of the epigraph is closed; the proof reduces this to the bounded part below f(1).The bounded portion is the convex hull of the epigraph intersected with the bounded region [f(0), f(1)].Source: §C.5 · pp. 33–34
  • The convex hull of a function lies below it, is convex, preserves monotonicity, and is continuous when the original function is monotone and lower-continuous.For a monotone lower-continuous function, its epigraph's convex hull is closed, and the infimum defining the convex hull is attained.Source: §C.5 · pp. 34–35

C.6 Left Derivative of Convex Functions

  • A convex function's left derivative is monotone and left-continuous, is nonnegative when the function is monotone, and adds across sums of convex functions.The supremum of points where the left derivative is nonpositive identifies the function's rightmost global minimum.Source: §C.6 · pp. 36–37

C.7 Separable Functions

  • For h(x, y) = f(x) + g(y), monotonicity, lower- and upper-continuity, and convexity hold exactly when they hold for both components.The maximizers of h are the Cartesian product of the maximizers of f and g.Source: §C.7 · pp. 38–39
Loading 2609.36589v1…