The Dynamic Assignment of Heterogenous Objects: A Mechanism Design Approach

We study the allocation of several heterogenous, commonly ranked objects to impatient agents with privately known characteristics who arrive sequentially according to a Poisson or renewal process. We analyze and compare the policies that maximize either welfare or revenue. We focus on two cases: 1. There is a deadline after which no more objects can be allocated; 2. The horizon is potentially infinite and there is time discounting. We first characterize all implementable allocation schemes, and we compute the expected revenue for any implementable, deterministic and Markovian allocation policy. These properties are shared by the welfare and revenue maximizing policies. Moreover, we show that these policies do not depend on the characteristics of the available objects at each point in time. The revenue-maximizing allocation scheme is obtained by a variational argument which sheds somewhat more light on its properties than the usual dynamic programming approach. We also obtain several properties of the welfare maximizing policy using stochastic dominance measures of increased variability and majorization arguments. These results yield upper/lower bounds on efficiency/revenue for large classes of distributions of agents' characteristics or of distributions of inter-arrival times for which explicit solutions cannot be obtained in closed form.