On the complexity of dynamic mechanism design

• 成果类型: Article
• 署名作者: Papadimitriou, Christos; Pierrakos, George; Psomas, Alexandros; Rubinstein, Aviad
• 署名单位: Columbia University; Purdue University System; Purdue University; Stanford University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2022.01.024
• 发表日期: 2022
• 页码: 399-427
• 关键词: Dynamic auctions; revenue maximization; complexity

摘要

We introduce a simple dynamic mechanism design problem in which the designer offers two items in two consecutive stages to a single buyer. The buyer's joint distribution of valuations for the two items is known, and the buyer knows the valuation for the current item, but not for the one in the future. The designer seeks to maximize expected revenue, and the mechanism must be deterministic, truthful, and ex-post individually rational. We show that finding the optimum deterministic mechanism in this situation - arguably one of the simplest meaningful dynamic mechanism design problems imaginable - is NP-hard. We also prove several positive results, including a polynomial-time linear programming based algorithm for the revenue optimal randomized mechanism (even for many buyers and many stages). We prove strong separations in revenue between non-adaptive, adaptive, and randomized mechanisms, even when the valuations in the two stages are independent.(c) 2022 Elsevier Inc. All rights reserved.