Bounding the menu-size of approximately optimal auctions via optimal-transport duality

DOI10.1145/3188745.3188786zbMATH Open1430.91045arXiv1708.08907OpenAlexW2962924022MaRDI QIDQ5230282FDOQ5230282

Authors: Yannai A. Gonczarowski 

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: The question of the minimum menu-size for approximate (i.e., up-to-$varepsilon$) Bayesian revenue maximization when selling two goods to an additive risk-neutral quasilinear buyer was introduced by Hart and Nisan (2013), who give an upper bound of $O(frac1varepsilo{n}^4)$ for this problem. Using the optimal-transport duality framework of Daskalakis et al. (2013, 2015), we derive the first lower bound for this problem - of $Omega(frac1sqrt[4]varepsilon)$, even when the values for the two goods are drawn i.i.d. from "nice" distributions, establishing how to reason about approximately optimal mechanisms via this duality framework. This bound implies, for any fixed number of goods, a tight bound of $Theta(logfrac1varepsilon)$ on the minimum deterministic communication complexity guaranteed to suffice for running some approximately revenue-maximizing mechanism, thereby completely resolving this problem. As a secondary result, we show that under standard economic assumptions on distributions, the above upper bound of Hart and Nisan (2013) can be strengthened to $O(frac1varepsilo{n}^2)$.

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

Recommendations

• Optimal mechanisms with simple menus
• The menu complexity of ``one-and-a-half-dimensional mechanism design
• Duality and optimality of auctions for uniform distributions

zbMATH Keywords

dualitylower boundrevenue maximizationupper boundauctionapproximate revenue maximizationmenu size

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cited In (4)

• The complexity of contracts
• Selling multiple correlated goods: revenue maximization and menu-size complexity
• The menu complexity of ``one-and-a-half-dimensional mechanism design
• Buy-many mechanisms are not much better than item pricing

This page was built for publication: Bounding the menu-size of approximately optimal auctions via optimal-transport duality

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