Sampling and Representation Complexity of Revenue Maximization

DOI10.1007/978-3-319-13129-0_22zbMATH Open1406.91171arXiv1402.4535OpenAlexW2146268012MaRDI QIDQ2936993FDOQ2936993

Authors: Shaddin Dughmi, Li Han, Noam Nisan 

Publication date: 7 January 2015

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

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.

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

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

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)

Cited In (11)

• 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
• A simple mechanism for a budget-constrained buyer
• The sample complexity of revenue maximization
• Selling multiple correlated goods: revenue maximization and menu-size complexity
• 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)