The menu-size complexity of revenue approximation

• 成果类型: Article
• 署名作者: Babaioff, Moshe; Gonczarowski, Yannai A.; Nisan, Noam; Nisan, Noam
• 署名单位: Hebrew University of Jerusalem; Hebrew University of Jerusalem
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2021.03.001
• 发表日期: 2022
• 页码: 281-307
• 关键词: Mechanism design; revenue maximization; Approximate revenue maximization; Menu size; auction; communication complexity

摘要

Consider a monopolist selling n items to an additive buyer whose item values are drawn from independent distributions F-1, F-2, ..., F-n possibly having unbounded support. Unlike in the single-item case, it is well known that the revenue-optimal selling mechanism (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. Also known is that simple mechanisms with a bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, whether an arbitrarily high fraction of the optimal revenue can be extracted via a bounded menu size remained open. We give an affirmative answer: for every n and epsilon > 0, there exists C = C(n, epsilon) s.t. mechanisms of menu size at most C suffice for obtaining (1 - epsilon) of the optimal revenue from any F-1, ..., F-n. We prove upper and lower bounds on the revenue-approximation complexity C(n, epsilon) and on the deterministic communication complexity required to run a mechanism achieving such an approximation. (C) 2021 Elsevier Inc. All rights reserved.