The sample complexity of revenue maximization

DOI10.1145/2591796.2591867zbMATH Open1315.91026arXiv1502.00963OpenAlexW2164143329MaRDI QIDQ5259558FDOQ5259558

Authors: Tim Roughgarden, Richard Cole 

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue. Our basic model is a single-item auction in which bidders' valuations are drawn independently from unknown and non-identical distributions. The seller is given $m$ samples from each of these distributions "for free" and chooses an auction to run on a fresh sample. How large does m need to be, as a function of the number k of bidders and eps > 0, so that a (1 - eps)-approximation of the optimal revenue is achievable? We prove that, under standard tail conditions on the underlying distributions, m = poly(k, 1/eps) samples are necessary and sufficient. Our lower bound stands in contrast to many recent results on simple and prior-independent auctions and fundamentally involves the interplay between bidder competition, non-identical distributions, and a very close (but still constant) approximation of the optimal revenue. It effectively shows that the only way to achieve a sufficiently good constant approximation of the optimal revenue is through a detailed understanding of bidders' valuation distributions. Our upper bound is constructive and applies in particular to a variant of the empirical Myerson auction, the natural auction that runs the revenue-maximizing auction with respect to the empirical distributions of the samples. Our sample complexity lower bound depends on the set of allowable distributions, and to capture this we introduce alpha-strongly regular distributions, which interpolate between the well-studied classes of regular (alpha = 0) and MHR (alpha = 1) distributions. We give evidence that this definition is of independent interest.

Full work available at URL: https://arxiv.org/abs/1502.00963

Recommendations

• Making the Most of Your Samples
• Revenue maximization with a single sample
• Sampling and Representation Complexity of Revenue Maximization
• The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization
• The sample complexity of auctions with side information

zbMATH Keywords

sample complexityMyerson's auction

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Theory of Cryptography
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower bounds in differential privacy
• Iterative Constructions and Private Data Release
• Differential privacy and the fat-shattering dimension of linear queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Title not available (Why is that?)
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• Title not available (Why is that?)
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the sample complexity for private learning and private data release
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (29)

• The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization
• Settling the sample complexity of single-parameter revenue maximization
• Improved two sample revenue guarantees via mixed-integer linear programming
• Canadian traveller problem with predictions
• Applications of \(\alpha \)-strongly regular distributions to Bayesian auctions
• Optimal multi-unit mechanisms with private demands
• From pricing to prophets, and back!
• Incentive-compatible learning of reserve prices for repeated auctions
• Vickrey auctions for irregular distributions
• Full surplus extraction from samples
• Pricing with samples
• Improving multi-armed bandit algorithms in online pricing settings
• The Limitations of Optimization from Samples
• Robust auctions for revenue via enhanced competition
• Revenue-maximizing auctions: a bidder's standpoint
• Making the Most of Your Samples
• Bayesian auctions with efficient queries
• Multi-scale online learning: theory and applications to online auctions and pricing
• Near-optimal auctions on independence systems
• The sample complexity of auctions with side information
• Revenue maximization with a single sample
• Regret-minimizing Bayesian persuasion
• On the optimal fixed-price mechanism in bilateral trade
• A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders
• Learning in repeated auctions
• Sampling and Representation Complexity of Revenue Maximization
• Performance bounds for optimal sales mechanisms beyond the monotone hazard rate condition
• Pricing to maximize revenue and welfare simultaneously in large markets
• Brief Announcement: Bayesian Auctions with Efficient Queries.

Uses Software

• SuLQ

This page was built for publication: The sample complexity of revenue maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259558)