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

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

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)

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

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)