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.