Generalization Guarantees for Multi-Item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms

We study multi-item profit maximization when there is an underlying distribution over buyers’ values. In practice, a full description of the distribution is typically unavailable, so we study the setting where the mechanism designer only has samples from the distribution. If the designer uses the samples to optimize over a complex mechanism class—such as the set of all multi-item, multibuyer mechanisms—a mechanism may have high average profit over the samples, but low expected profit. This raises the central question of this paper: How many samples are sufficient to ensure that a mechanism’s average profit is close to its expected profit? To answer this question, we uncover structure shared by many pricing, auction, and lottery mechanisms: For any set of buyers’ values, profit is piecewise linear in the mechanism’s parameters. Using this structure, we prove new bounds for mechanism classes not yet studied in the sample-based mechanism design literature and match or improve over the best-known guarantees for many classes. Finally, we provide tools for optimizing an important tradeoff: More complex mechanisms typically have higher average profit over the samples than simpler mechanisms, but more samples are required to ensure that average profit nearly matches expected profit.

Funding: This material is based on work supported by the National Science Foundation [Grants CCF-1422910, CCF-1535967, CCF-1733556, CCF-1910321, IIS-1617590, IIS-1618714, IIS-1718457, IIS-1901403, RI-2312342, SES-1919453 and a Graduate Research Fellowship]; the Army Research Office [Awards W911NF2010081, W911NF1710082, and W911NF2210266]; Office of Naval Research [Award N00014-23-1-2876]; the Defense Advanced Research Projects Agency [Cooperative Agreement HR00112020003]; Vannevar Bush Faculty Fellowship; an Amazon [Research Award]; a Microsoft Research [Faculty Fellowship]; an Amazon Web Services [Machine Learning Research Award]; a Bloomberg [Data Science research grant]; an International Business Machines Corporation [PhD Fellowship]; and a fellowship from Carnegie Mellon University's Center for Machine Learning and Health.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2021.0026.