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

DOI10.1137/17M1136481MaRDI QIDQ5080487zbMATH OpenFDO

Authors Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Xiaorui Sun, Mihalis Yannakakis, D. 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)

Recommendations

• Pricing randomized allocations
• Pricing lotteries
• On the complexity of simple and optimal deterministic mechanisms for an additive buyer
• The complexity of optimal multidimensional pricing for a unit-demand buyer
• The complexity of optimal multidimensional pricing

Cites work

• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• Algorithms and Data Structures
• An \(n\)-to-\(1\) bidder reduction for multi-item auctions and its applications
• Approximate revenue maximization with multiple items
• Bundling as an optimal selling mechanism for a multiple-good monopolist
• Combination can be hard
• Extreme-value theorems for optimal multidimensional pricing
• Haggling over substitutes
• On profit-maximizing envy-free pricing
• On revenue maximization for selling multiple independently distributed items
• Optimal Auction Design
• Optimal mechanism for selling two goods
• PP is as Hard as the Polynomial-Time Hierarchy
• Pricing lotteries
• Sampling and Representation Complexity of Revenue Maximization
• Single-minded unlimited supply pricing on sparse instances
• Strong Duality for a Multiple-Good Monopolist
• The complexity of optimal mechanism design
• The complexity of optimal multidimensional pricing for a unit-demand buyer
• The power of randomness in Bayesian optimal mechanism design
• Uniform Budgets and the Envy-Free Pricing Problem

Cited in

(2)

• On symmetries in multi-dimensional mechanism design
• Heterogeneous demand responses to discrete price changes: an application to the purchase of lottery tickets

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

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