On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer

DOI10.1137/17M1136481MaRDI QIDQ5080487

Ilias Diakonikolas, Xiaorui Sun, Mihalis Yannakakis, Anthi Orfanou, Xi Chen, Dimitris Paparas

Publication date: 31 May 2022

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

zbMATH Keywords

optimal mechanism designlottery pricingunit-demand buyer

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On symmetries in multi-dimensional mechanism design

Cites Work

• Unnamed Item
• Haggling over substitutes
• The complexity of optimal multidimensional pricing for a unit-demand buyer
• Approximate revenue maximization with multiple items
• The menu-size complexity of revenue approximation
• Pricing lotteries
• The power of randomness in Bayesian optimal mechanism design
• Bundling as an optimal selling mechanism for a multiple-good monopolist
• Optimal Mechanism for Selling Two Goods
• Sampling and Representation Complexity of Revenue Maximization
• PP is as Hard as the Polynomial-Time Hierarchy
• Uniform Budgets and the Envy-Free Pricing Problem
• Combination can be hard
• Single-minded unlimited supply pricing on sparse instances
• Optimal Auction Design
• Strong Duality for a Multiple-Good Monopolist
• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• On revenue maximization for selling multiple independently distributed items
• An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications
• The Complexity of Optimal Mechanism Design
• Algorithms and Data Structures
• Extreme-Value Theorems for Optimal Multidimensional Pricing

This page was built for publication: On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer