Sampling and Representation Complexity of Revenue Maximization

Abstract

We consider (approximate) revenue maximization in auctions where the distribution on input valuations is given via "black box" access to samples from the distribution. We observe that the number of samples required -- the sample complexity -- is tightly related to the representation complexity of an approximately revenue-maximizing auction. Our main results are upper bounds and an exponential lower bound on these complexities.

References in corpus (2)

• Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
• Bayesian Optimal Auctions via Multi- to Single-agent Reduction

Cited by in corpus (13)

• Approximate Revenue Maximization with Multiple Items
• Learning Simple Auctions
• Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")
• The Pseudo-Dimension of Near-Optimal Auctions
• Mixture Selection, Mechanism Design, and Signaling
• Learning Multi-item Auctions with (or without) Samples
• The Sample Complexity of Revenue Maximization
• Ironing in the Dark
• Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments
• Exponential Weight Functions for Quasi-Proportional Auctions
• A Simple Mechanism for a Budget-Constrained Buyer
• Monopoly pricing with buyer search
• Learning Optimal Reserve Price against Non-myopic Bidders