Learning Simple Auctions

Abstract

We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of "simple" auctions. Our framework captures all of the most prominent examples of "simple" auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The technique we propose is to break the analysis of auctions into two natural pieces. First, one shows that the set of allocation rules have large amounts of structure; second, fixing an allocation on a sample, one shows that the set of auctions agreeing with this allocation on that sample have revenue functions with low dimensionality. Our results effectively imply that whenever it's possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior (given a polynomial number of samples).

References in corpus (2)

• Sampling and Representation Complexity of Revenue Maximization
• Ironing in the Dark

Cited by in corpus (21)

• Revenue Optimization with Approximate Bid Predictions
• Machine Learning-powered Iterative Combinatorial Auctions
• A Sample Complexity Measure with Applications to Learning Optimal Auctions
• Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
• Learning Multi-item Auctions with (or without) Samples
• Semi-parametric dynamic contextual pricing
• Guarantees for Tuning the Step Size using a Learning-to-Learn Approach
• Explicit shading strategies for repeated truthful auctions
• A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts
• Thresholding at the monopoly price: an agnostic way to improve bidding strategies in revenue-maximizing auctions
• Third-Party Data Providers Ruin Simple Mechanisms
• Auction learning as a two-player game
• Learning Utilities and Equilibria in Non-Truthful Auctions
• Online Revenue Maximization for Server Pricing
• Information Elicitation for Bayesian Auctions
• Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
• Robust Learning of Optimal Auctions
• Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization
• The Sample Complexity of Up-to-$\epsilon$ Multi-Dimensional Revenue Maximization
• Learning Optimal Reserve Price against Non-myopic Bidders
• Tight Revenue Gaps among Multi-Unit Mechanisms