Non-Linear Pricing Restores Tractability for a Data Seller

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.