On the complexity of dynamic mechanism design

Christos Papadimitriou, George Pierrakos, Alexandros Psomas and Aviad Rubinstein

Games and Economic Behavior, 2022, vol. 134, issue C, 399-427

Abstract: 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.

Keywords: Dynamic auctions; Revenue maximization; Complexity (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825622000306
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:134:y:2022:i:c:p:399-427

DOI: 10.1016/j.geb.2022.01.024

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().