The menu-size complexity of revenue approximation

DOI10.1016/j.geb.2021.03.001zbMath1497.91072arXiv1604.06580OpenAlexW2950569841WikidataQ114174561 ScholiaQ114174561MaRDI QIDQ2155903

Moshe Babaioff, Yannai A. Gonczarowski, Noam Nisan

Publication date: 15 July 2022

Published in: Games and Economic Behavior, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

auctionmechanism designcommunication complexityrevenue maximizationapproximate revenue maximizationmenu size

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Microeconomic theory (price theory and economic markets) (91B24) Auctions, bargaining, bidding and selling, and other market models (91B26) Mechanism design theory (91B03)

Related Items (10)

On symmetries in multi-dimensional mechanism design ⋮ Buy-many mechanisms are not much better than item pricing ⋮ The menu-size complexity of revenue approximation ⋮ On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer ⋮ Approximate revenue maximization with multiple items ⋮ Bayesian auctions with efficient queries ⋮ A simple mechanism for a budget-constrained buyer ⋮ Optimal mechanisms for selling two items to a single buyer having uniformly distributed valuations ⋮ The Complexity of Contracts ⋮ Selling multiple correlated goods: revenue maximization and menu-size complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Haggling over substitutes
• Multidimensional incentive compatibility and mechanism design
• Selling two goods optimally
• The menu-size complexity of revenue approximation
• Bundling as an optimal selling mechanism for a multiple-good monopolist
• Sampling and Representation Complexity of Revenue Maximization
• Optimal Auction Design
• Maximal revenue with multiple goods: Nonmonotonicity and other observations
• Simple mechanisms for subadditive buyers via duality
• On revenue maximization for selling multiple independently distributed items
• Bounding the menu-size of approximately optimal auctions via optimal-transport duality
• An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications

This page was built for publication: The menu-size complexity of revenue approximation