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

Maria-Florina Balcan (), Tuomas Sandholm () and Ellen Vitercik ()
Additional contact information
Maria-Florina Balcan: School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Tuomas Sandholm: School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; and Optimized Markets, Inc., Pittsburgh, Pennsylvania 15213; and Strategic Machine, Inc., Pittsburgh, Pennsylvania 15213; and Strategy Robot, Inc., Pittsburgh, Pennsylvania 15213
Ellen Vitercik: Management Science and Engineering Department, Stanford University, Stanford, California 94304; and Computer Science Department, Stanford University, Stanford, California 94304

Operations Research, 2025, vol. 73, issue 2, 648-663

Abstract: 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.

Keywords: Market; Analytics; and; Revenue; Management; machine learning theory; profit maximization; revenue maximization; combinatorial auctions (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0026 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:648-663

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().