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

Sample Complexity of Multi-Item Profit Maximization

Historically, mechanism design has rested on the assumption that the seller knows the distribution over buyers’ values. In practice, a description of this distribution is typically unavailable. In “Generalization Guarantees for Multi-Item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms,” we assume only sample access to this distribution. When using 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 question: 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 across many mechanisms: Profit is piecewise linear in the mechanism’s parameters for any set of buyers’ values. We prove new bounds for mechanism classes not yet studied in the sample-based mechanism design literature and match or improve over best-known guarantees for many classes.