E¢ cient Sequential Assignmentwith Incomplete InformationAlex Gershkov and Benny Moldovanu 5.5.2008AbstractWe study the welfare maximizing assignment of several heterogenous, commonlyranked objects to impatient agents with privately known characteristics who arrivesequentially according to a Poisson or renewal process. We focus on two cases: 1.There is a deadline after which no more objects can be allocated; 2. The horizonis potentially in…nite and there is time discounting. We …rst characterize all im-plementable allocation schemes and show that the dynamically e¢ cient allocationfalls in this class. We then obtain several properties of the welfare maximizing pol-icy using stochastic dominance measures of increased variability and majorizationarguments. These results yield upper/lower bounds on e¢ ciency for large classe sof distributions of agents’characteristics or of distributions of inter-arrival timesfor which explicit solutions cannot be obtained in closed form. We also propose re-distribution mechanisms that 1) implement e¢ cient allocation 2) satisfy individualrationality 3) never run a budget de…cit 4) may run a budget surplus that vanishesasymptotically. Some of the present results previously appeared in a discussion paper entitled "The Dynamic Assign-ment of Heterogeneous Objects: A Mechanism Des ign Approach". We are grateful for …nancial supportfrom the German Science Foundation, and from the Max Planck Research Prize. Gershkov, Moldovanu:Department of Economics, University of Bonn, Lennestr. 37, 53113 Bonn. [email protected],[email protected] IntroductionWe study e¢ cient, individual rational and budget-balanced schemes for the followingdynamic mechanism design problem: the designer wants to assign a …xed, …nite set ofheterogenous objects to a sequence of randomly arriving agents with privately knowncharacteristics. Monetary transfers are feasible. The objects are substitutes, and eachagent derives utility from at most one object. Moreover, all agents share a commonranking over the available objects, and values for objects have a multiplicative structureinvolving the agents’ types and objects’ qualities. In one formulation we assume thatthere is a deadline by which all objects must be sold, in another we assume a discountedin…nite horizon (in both scenarios, time is a continuous variable).Examples of such settings include the dynamic allocation of limited resources amongincoming projects, the allocation of limited research facilities among research units (e.g.,telescope time), the assignment of dormitory rooms to potential tenants, and the alloca-tion of available positions to arriving candidates. The yield-management literature hasanalyzed the simpler models of allocating identical objects (e.g., seats on an aeroplane,or hotel rooms) from the point of view of revenue-maximization1. Our model also sharesseveral common features to the classical job search models2. The main di¤erence is thatin that literature it is usually assumed that the stream of the job o¤ers is generated by anon-strategic player, without private information. Hence, implementation issues do notarise there.3Compared to a static setting, the new trade-o¤ is between an assignment today andthe valuable option of assigning it in the future, possibly to an agent who values it more.Since the arrival process of agents is stochastic, the "future" on which the option valuedepends may never materialize (if there is a deadline) or it may be farther away in time,and thus discounted.First, we characterize all dynamically implementable deterministic allocation policies.1See McAfee and te-Velde [14], and Gershkov and Moldovanu [9] for several reference to that largeliterature2For extensive surveys of the search literature see Lippman and McCall [13] , and Mortensen [15]3Other di¤erences are: the job search model corresponds here to the one object case, and samplinghas an explicit cost.2Such policies are described by partitions of the set of possible agent types: an arrivingagent gets the best available object if his type lies in the highest interval of the partition,the second best available object if his type lies in the second highest interval, and so on.These intervals may depend on the p oint in time of the arrival, and on the compositionof the set of available objects at that point in time. For implementable allocation poli-cies we derive the associated menus of prices (one menu for each point in time, and foreach subset of remaining objects) that implement it, and show that these menus havean appealing recursive structure: each agent who is assigned an object has to pay thevalue he displaces in terms of the chosen allocation. It allows us to verify the imple-mentability of the dynamically e¢ cient allocation policy under Poisson arrivals, whichhas been characterized for the complete information case - via a system of di¤erentialequations - by Albright [1]4. Since that policy is deterministic, Markovian and has theform of a partition, it can be implemented also in our private information frameworkby the dynamic price schedules identi…ed above, which coincide then with a dynamicversion of the Vickrey-Clarke-Groves mechanism. Dolan [7] used a dynamic version ofthe Vickrey-Clarke-Groves mechanism in order to achieve welfare maximization in queueswith random arrivals and with incomplete information about the agents’characteristics.Dynamic extensions of VCG schemes (for much more general situations than those con-sidered here) have recently attracted a lot of interest - see for example Athey and Segal [3],Bergemann and Välimäki [4], and Parkes and Singh [17]. Gershkov and Moldovanu[10]analyze the limitations encountered in a framework where the designer needs also to learnabout the distribution of agents’characteristics.A somewhat surprising feature is that the cuto¤ curves de…ning the intervals in thetime-dependent partitions that characterize the dynamic welfare maximizing policy inour model depend only on the cardinality of the set of available objects, but not on theexact composition of that set. This is due here to the multiplicative structure of theagents’valuations for objects.4Derman, Lieberman and Ross [6] introduced the basic assignment model in a framework with a…nite number of periods (time is discrete), and one arrival per period. An early pap er that uses optimalstopping theory to characterize the e¢ cient assignment of a single object to