Generalization guarantees for multi-item profit maximization: pricing, auctions, and randomized mechanisms (Q6974758)

This paper is part of a line of research that studies how learning theory can be used to design and analyze mechanisms from a generalization perspective. The authors study multi-item profit maximization when there is an underlying distribution over buyers' values. More precisely, the setting where the mechanism designer only has samples from the distribution is studied. 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?\N\NThe authors 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. Following this structure, 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 are proved.