The sample complexity of revenue maximization
From MaRDI portal
Publication:5259558
DOI10.1145/2591796.2591867zbMATH Open1315.91026arXiv1502.00963OpenAlexW2164143329MaRDI QIDQ5259558FDOQ5259558
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 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
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theory of Cryptography
- The geometry of differential privacy: the small database and approximate cases
- 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
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- 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
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (24)
- Revenue-Maximizing Auctions: A Bidder’s Standpoint
- Improved two sample revenue guarantees via mixed-integer linear programming
- Canadian traveller problem with predictions
- Title not available (Why is that?)
- Optimal multi-unit mechanisms with private demands
- Pricing to Maximize Revenue and Welfare Simultaneously in Large Markets
- From pricing to prophets, and back!
- Full surplus extraction from samples
- Improving multi-armed bandit algorithms in online pricing settings
- The Limitations of Optimization from Samples
- Making the Most of Your Samples
- Bayesian auctions with efficient queries
- Near-optimal auctions on independence systems
- Applications of $$\alpha $$-Strongly Regular Distributions to Bayesian Auctions
- Learning in Repeated Auctions
- Regret-minimizing Bayesian persuasion
- On the optimal fixed-price mechanism in bilateral trade
- Robust Auctions for Revenue via Enhanced Competition
- A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders
- Incentive-Compatible Learning of Reserve Prices for Repeated Auctions
- Sampling and Representation Complexity of Revenue Maximization
- Pricing with Samples
- Performance bounds for optimal sales mechanisms beyond the monotone hazard rate condition
- Brief Announcement: Bayesian Auctions with Efficient Queries.
Uses Software
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)
