# New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 59 references that are in the map.
- First posted on arXiv 22 Feb 2023.

## Builds on (most cited first, 25 of 25)

- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximization](https://mlsanity.com/paper/1808.02458/) (2018)
- [Learning-to-learn non-convex piecewise-Lipschitz functions](https://mlsanity.com/paper/2108.08770/) (2021)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022)
- [Ironing in the Dark](https://mlsanity.com/paper/1511.06918/) (2015)
- [Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments](https://mlsanity.com/paper/1610.09976/) (2016)
- [A Sample Complexity Measure with Applications to Learning Optimal Auctions](https://mlsanity.com/paper/1704.02598/) (2017)
- [Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms](https://mlsanity.com/paper/1705.00243/) (2017)
- [Multi-scale Online Learning and its Applications to Online Auctions](https://mlsanity.com/paper/1705.09700/) (2017)
- [Sampling and Representation Complexity of Revenue Maximization](https://mlsanity.com/paper/1402.4535/) (2014)
- [Online Optimization of Smoothed Piecewise Constant Functions](https://mlsanity.com/paper/1604.01999/) (2016)
- [Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")](https://mlsanity.com/paper/1304.6116/) (2013)
- [Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues](https://mlsanity.com/paper/1705.08430/) (2017)

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

- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Efficiently Learning the Graph for Semi-supervised Learning](https://mlsanity.com/paper/2306.07098/) (2023)
- [Learning to Price Homogeneous Data](https://mlsanity.com/paper/2407.05484/) (2024)
- [Learning to Price with Persuasion](https://mlsanity.com/paper/2608.16699/) (2026)

## Abstract (arXiv)

We advance a recently flourishing line of work at the intersection of learning theory and computational economics by studying the learnability of two classes of mechanisms prominent in economics, namely menus of lotteries and two-part tariffs. The former is a family of randomized mechanisms designed for selling multiple items, known to achieve revenue beyond deterministic mechanisms, while the latter is designed for selling multiple units (copies) of a single item with applications in real-world scenarios such as car or bike-sharing services. We focus on learning high-revenue mechanisms of this form from buyer valuation data in both distributional settings, where we have access to buyers' valuation samples up-front, and the more challenging and less-studied online settings, where buyers arrive one-at-a-time and no distributional assumption is made about their values. We provide a suite of results with regard to these two families of mechanisms. We provide the first online learning algorithms for menus of lotteries and two-part tariffs with strong regret-bound guarantees. Since the space of parameters is infinite and the revenue functions have discontinuities, the known techniques do not readily apply. However, we are able to provide a reduction to online learning over a finite number of experts, in our case, a finite number of parameters. Furthermore, in the limited buyers type case, we show a reduction to online linear optimization, which allows us to obtain no-regret guarantees by presenting buyers with menus that correspond to a barycentric spanner. In addition, we provide algorithms with improved running times over prior work for the distributional settings. Finally, we demonstrate how techniques from the recent literature in data-driven algorithm design are insufficient for our studied problems.