On the computational complexity of optimal simple mechanisms

DOI10.1145/2840728.2840736MaRDI QIDQ2800549zbMATH OpenOpenAlexFDO

Authors Aviad Rubinstein

Publication date 15 April 2016

Published in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

revenue maximizationmechanism designPTASsimple mechanisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: We consider a monopolist seller facing a single buyer with additive valuations over n heterogeneous, independent items. It is known that in this important setting optimal mechanisms may require randomization [HR12], use menus of infinite size [DDT15], and may be computationally intractable [DDT14]. This has sparked recent interest in finding simple mechanisms that obtain reasonable approximations to the optimal revenue [HN12, LY13, BILW14]. In this work we attempt to find the optimal simple mechanism. There are many ways to define simple mechanisms. Here we restrict our search to partition mechanisms, where the seller partitions the items into disjoint bundles and posts a price for each bundle; the buyer is allowed to buy any number of bundles. We give a PTAS for the problem of finding a revenue-maximizing partition mechanism, and prove that the problem is strongly NP-hard. En route, we prove structural properties of near-optimal partition mechanisms which may be of independent interest: for example, there always exists a near-optimal partition mechanism that uses only a constant number of non-trivial bundles (i.e. bundles with more than one item).

Recommendations

• On the complexity of simple and optimal deterministic mechanisms for an additive buyer
• The complexity of optimal mechanism design
• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• Optimal mechanisms with simple menus

Cited in

(10)

• Near-optimal asymmetric binary matrix partitions
• The complexity of optimal mechanism design
• On the complexity of simple and optimal deterministic mechanisms for an additive buyer
• A note on the tight simplification of mechanisms
• Computing simple mechanisms: Lift-and-round over marginal reduced forms
• Explicitly simple near-tie auctions
• A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders
• Simple complexity from imitation games
• scientific article; zbMATH DE number 3961285 (Why is no real title available?)
• Optimal mechanisms with simple menus

This page was built for publication: On the computational complexity of optimal simple mechanisms

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