Research map / Learning theory and algorithms / Submodular and game algorithms

Non-Linear Pricing Restores Tractability for a Data Seller

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Streaming submodular algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that revenue-maximizing pricing for a budget-constrained data seller can be found in polynomial time via an LP over piecewise-linear convex (PLC) pricing functions, with at most n kinks in total, and that the linearity gap is at most 2-1/n in the worst case and about 1.1 empirically.

Problem

Revenue maximization for a monopolistic data seller selling multiple datasets to budget-constrained buyers; prior work showed optimal linear pricing is APX-hard.

Approach

Allow general monotone lower-continuous pricing functions per dataset rather than linear prices; show an optimal solution exists that is piecewise linear convex with left derivatives drawn from buyers' valuations, which reduces the problem to a polynomial-size LP whose basic solutions have at most n kinks.

Key results

• Optimal nonlinear pricing is computed by a polynomial-size LP; a basic optimal solution has at most n kinks total (at most m+n positive z entries).
• Worst-case linearity gap example achieves 2 - 1/n, which is the largest demonstrated.
• On California Housing-based instances (n up to 100), the empirical linearity gap is at most 1.1 and the number of kinks is at most 10.

Surprising findings

• Moving from linear to general pricing makes revenue maximization tractable, whereas optimal linear pricing is APX-hard.
• Empirical linearity gap (at most 1.1) is far below the worst-case 2 - 1/n.

Limitations

• Valuations are linear in data fractions; nonlinear valuations are not handled, so experiments use a linearized instance.
• Linearity gap upper bound of 2 is only conjectured, not proven.
• Empirical study uses a single real dataset with simulated buyers and budgets.

Experimental setup

Datasets: California Housing

Metrics: linearity gap number of kinks revenue

Baselines: optimal linear pricing (brute-force over buyer valuations)

Builds on: Chaudhury et al. 2026 linear data pricing model value of data framework (accuracy gain via precision)

Closest papers by meaning

• Learning to price with resource constraints: from full information to machine-learned prices (NeurIPS 2025 · similarity 0.87)
• Learning to Price Homogeneous Data (NeurIPS 2024 · similarity 0.87)
• An Instrumental Value for Data Production and its Application to Data Pricing (ICML 2025 · similarity 0.86)
• Transfer Faster, Price Smarter: Minimax Dynamic Pricing under Cross-Market Preference Shift (NeurIPS 2025 · similarity 0.86)
• Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.85)
• Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.85)