Making the Most of Your Samples

DOI10.1137/16M1065719MaRDI QIDQ4641589zbMATH OpenOpenAlexWikidataFDO

Authors Yishay Mansour, Tim Roughgarden, Zhiyi Huang

Publication date 18 May 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

information theorypricingauctionssample complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution $D$. The seller has "data"' about $D$ in the form of $mge1$ i.i.d. samples, and the algorithmic challenge is to use these samples to obtain expected revenue as close as possible to what could be achieved with advance knowledge of $D$. Our first set of results quantifies the number of samples $m$ that are necessary and sufficient to obtain a $(1-epsilon)$-approximation. For example, for an unknown distribution that satisfies the monotone hazard rate (MHR) condition, we prove that $ildeTheta(epsilo{n}^{-3/2})$ samples are necessary and sufficient. Remarkably, this is fewer samples than is necessary to accurately estimate the expected revenue obtained by even a single reserve price. We also prove essentially tight sample complexity bounds for regular distributions, bounded-support distributions, and a wide class of irregular distributions. Our lower bound approach borrows tools from differential privacy and information theory, and we believe it could find further applications in auction theory. Our second set of results considers the single-sample case. For regular distributions, we prove that no pricing strategy is better than $frac12$-approximate, and this is optimal by the Bulow-Klemperer theorem. For MHR distributions, we show how to do better: we give a simple pricing strategy that guarantees expected revenue at least $0.589$ times the maximum possible. We also prove that no pricing strategy achieves an approximation guarantee better than $frace4approx.68$.

Recommendations

• A Note on the Re-Use of Samples
• scientific article; zbMATH DE number 651017
• scientific article; zbMATH DE number 5044792
• What you can do with coordinated samples
• The joy of sampling

Cites work

• scientific article; zbMATH DE number 3202900 (Why is no real title available?)
• A theory of the learnable
• Bayesian Mechanism Design
• Competitive auctions
• How Far Can We Go Beyond Linear Cryptanalysis?
• Making the Most of Your Samples
• Mechanism design with approximate valuations
• Neural Network Learning
• Optimal Selling Strategies under Uncertainty for a Discriminating Monopolist when Demands are Interdependent
• Optimal and Efficient Parametric Auctions
• Reducing mechanism design to algorithm design via machine learning
• Revenue maximization with a single sample
• The effectiveness of English auctions.
• The sample complexity of revenue maximization
• Vickrey auctions for irregular distributions

Cited in

(19)

• Optimal pricing for MHR distributions
• Improved two sample revenue guarantees via mixed-integer linear programming
• Settling the sample complexity of single-parameter revenue maximization
• Extreme value theorems for optimal multidimensional pricing
• The sample complexity of revenue maximization
• Applications of -strongly regular distributions to Bayesian auctions
• On the limitations of data-based price discrimination
• Pricing with samples
• Optimal auctions through deep learning: advances in differentiable economics
• Revenue-maximizing auctions: a bidder's standpoint
• Making the Most of Your Samples
• Multi-scale online learning: theory and applications to online auctions and pricing
• On the approximability of simple mechanisms for MHR distributions
• The sample complexity of auctions with side information
• Revenue maximization with a single sample
• A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders
• Extreme-value theorems for optimal multidimensional pricing
• Price asymptotics
• Learning in repeated auctions

This page was built for publication: Making the Most of Your Samples

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