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.
NSTL
Elsevier
