Sampling and Representation Complexity of Revenue Maximization

DOI10.1007/978-3-319-13129-0_22MaRDI QIDQ2936993zbMATH OpenOpenAlexFDO

Authors Shaddin Dughmi, Li Han, Noam Nisan

Publication date 7 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexity of samplesrevenue-maximizing 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)

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.

Recommendations

• The sample complexity of revenue maximization
• 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
• Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
• Revenue maximization with a single sample
• Approximating the revenue maximization problem with sharp demands
• Approximating the revenue maximization problem with sharp demands

Cited in

(11)

• The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization
• Improved two sample revenue guarantees via mixed-integer linear programming
• A simple mechanism for a budget-constrained buyer
• Settling the sample complexity of single-parameter revenue maximization
• Selling multiple correlated goods: revenue maximization and menu-size complexity
• The sample complexity of revenue maximization
• Approximate revenue maximization with multiple items
• A simple and approximately optimal mechanism for a buyer with complements
• The Limitations of Optimization from Samples
• Buy-many mechanisms are not much better than item pricing
• On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer

This page was built for publication: Sampling and Representation Complexity of Revenue Maximization

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