# Revenue Maximization for Query Pricing

arXiv: https://arxiv.org/abs/1909.00845 · HTML: https://mlsanity.com/paper/1909.00845/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2019.

## Built on by (most cited first, 11 of 11)

- [Data Pricing in Machine Learning Pipelines](https://mlsanity.com/paper/2108.07915/) (2021)
- [Variance reduced Shapley value estimation for trustworthy data valuation](https://mlsanity.com/paper/2210.16835/) (2022)
- [FL-Market: Trading Private Models in Federated Learning](https://mlsanity.com/paper/2106.04384/) (2021)
- [A Survey of Data Pricing for Data Marketplaces](https://mlsanity.com/paper/2303.04810/) (2023)
- [Addressing Budget Allocation and Revenue Allocation in Data Market Environments Using an Adaptive Sampling Algorithm](https://mlsanity.com/paper/2306.02543/) (2023)
- [Uncertainty Quantification of Data Shapley via Statistical Inference](https://mlsanity.com/paper/2407.19373/) (2024)
- [Differentially Private Online Item Pricing](https://mlsanity.com/paper/2305.11362/) (2023)
- [A Bargaining-based Approach for Feature Trading in Vertical Federated Learning](https://mlsanity.com/paper/2402.15247/) (2024)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [DaDaDa: A Dataset for Data Pricing in Data Marketplaces](https://mlsanity.com/paper/2607.08785/) (2026)
- [Rent-a-RAG: Embedding-Space Watermarks for Auditing Third-Party RAG](https://mlsanity.com/paper/2609.03749/) (2026)

## Abstract (arXiv)

Buying and selling of data online has increased substantially over the last few years. Several frameworks have already been proposed that study query pricing in theory and practice. The key guiding principle in these works is the notion of em arbitrage-freeness where the broker can set different prices for different queries made to the dataset, but must ensure that the pricing function does not provide the buyers with opportunities for arbitrage. However, little is known about revenue maximization aspect of query pricing. In this paper, we study the problem faced by a broker selling access to data with the goal of maximizing her revenue. We show that this problem can be formulated as a revenue maximization problem with single-minded buyers and unlimited supply, for which several approximation algorithms are known. We perform an extensive empirical evaluation of the performance of several pricing algorithms for the query pricing problem on real-world instances. In addition to previously known approximation algorithms, we propose several new heuristics and analyze them both theoretically and experimentally. Our experiments show that algorithms with the best theoretical bounds are not necessarily the best empirically. We identify algorithms and heuristics that are both fast and also provide consistently good performance when valuations are drawn from a variety of distributions.