The complexity of optimal multidimensional pricing for a unit-demand buyer

DOI10.1016/j.geb.2018.03.016zbMath1400.91214OpenAlexW2797066271MaRDI QIDQ1651230

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

Publication date: 12 July 2018

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2018.03.016

zbMATH Keywords

algorithmsNP-completenesscomplexity theorydeterministic mechanism design

Mathematics Subject Classification ID

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

Related Items (5)

Generalized Permutahedra and Optimal Auctions ⋮ Auction Design with a Revenue Target ⋮ On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer ⋮ The rank pricing problem: models and branch-and-cut algorithms ⋮ Extreme value theorems for optimal multidimensional pricing

Cites Work

• Optimal mechanisms with simple menus
• Haggling over substitutes
• Reducing mechanism design to algorithm design via machine learning
• The power of randomness in Bayesian optimal mechanism design
• Multidimensional mechanism design: revenue maximization and the multiple-good monopoly
• A Property of Solutions to Linear Monopoly Problems
• Multi-parameter mechanism design and sequential posted pricing
• On the Complexity of Nash Equilibria and Other Fixed Points
• Uniform Budgets and the Envy-Free Pricing Problem
• Optimal Auction Design
• On revenue maximization for selling multiple independently distributed items
• A duality based unified approach to Bayesian mechanism design
• 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
• Simple and Nearly Optimal Multi-Item Auctions
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of optimal multidimensional pricing for a unit-demand buyer