Optimal Dynamic Allocation: Simplicity Through Information Design.

agents, who have privately known preferences, arrive over time. This problem arises in various contexts with wait-lists, including public housing assignment, organ allocation and refugee reassignment. Wait-lists offer a natural way of rationing scarce resources, are simple to implement, and do not elicit much information. For example, patients decide only upon receiving an organ offer whether to accept it or not.It is natural to ask whether there is any loss from using wait-lists (instead of more sophisticated mechanisms that elicit refined preferences) to allocate scarce resources over time. This paper focuses on the allocation of resources that have a single-dimensional quality to agents who vary in their taste for quality. The model features agents and objects that arrive over time at possibly different constant rates. Objects vary horizontally in a single dimension of quality. Agents have single-dimensional private types that capture their preference for quality: an agent's value for an object is a supermodular function of the agent's type and the object's quality. An agent's payoff is her value for the (expected) object quality that she allocates minus her waiting cost, i.e., the cost she incurs while waiting for an object. The social planner's objective is to maximize social welfare, defined as the agents' average payoff. Due to the supermodularity of the utility function, a positive assortative assignment maximizes the agents' average utility, but not necessarily social welfare (which accounts for waiting costs). Because the agents have private types, we take a mechanism design approach. The goal is to design a direct revelation mechanism that maximizes social welfare over the space of all steady state direct revelation mechanisms. Our focus on large markets allows us to analyze a market with multiple agent types and object types (i.e., object qualities) and optimize over the space of all direct revelation mechanisms. This is in contrast to the previous studies in the dynamic matching literature that restrict attention to at most two types of agents and objects or, alternatively, considered a restricted class of mechanisms. Our two main contributions are the following: Characterization of the optimal incentive-compatible mechanism. The optimal mechanism is characterized by a finite set of disjoint queues. Every agent, upon arrival, is assigned to a queue based on her type as reported. Within each queue, objects are allocated to agents according to their waiting times: when an object becomes available, it is assigned to the agent with the earliest arrival time present in the queue; the assignment is definitive and cannot be declined. The objects are allocated to queues in a way such that, if two objects of distinct types are allocated to the same queue, then all objects with a type in between the two distinct types are also allocated to that queue. The same property holds for agents' types. The maximum number of queues required by the optimal mechanism is 2n + 1, where n is the number of distinct object types. In terms of methodology, we build our results upon the work of Kleiner et al. [2], who characterize the extreme points of a set of functions that are memorized by a reference function.We first transform the planner's problem into maximizing virtual payoff by choosing an interim allocation rule that satisfies monotonicity and a certain majorization condition that ensures feasibility. If the virtual payoff function is increasing, the optimal mechanism allocates objects in a greedy manner, creating one separate queue for each object type. Otherwise, the optimal mechanism pools together some of the adjacent object types, creating one queue for each interval of pooled object types. To characterize the optimal mechanism in the latter case, standard ironing techniques in mechanism design are not directly applicable, due to the concurrence of two complicating factors: the supermodularity of agents' values for objects and the capacity constraints of the heterogeneous object types. We take a different approach by applying Bauer's Maximum Principle [1], implying that the virtual payoff- maximizing allocation rule attains its maximum at an extreme point of the set of allocation rules that satisfy monotonicity and a certain majorization condition that ensures feasibility. We then use the extreme point characterization result of Kleiner et al. [2] to conclude that the interim allocation that maximizes virtual payoff has an interval structure, which is shown to correspond to a monotone disjoint queue mechanism. Implementation through first-come, first-served (FCFS) wait-list with deferrals using information design. One feature of the optimal mechanism characterized above is that agents cannot decline the object they are assigned to. In numerous applications, however, agents wait on a single wait-list and can decline an assignment while keeping their position on the list. We ask whether offering this flexibility to agents can result in efficiency loss. We show that the answer to this question is negative if the planner can design the information disclosed to agents about the objects. When objects' types are fully disclosed, higher-type objects are assigned to higher-type agents who value object quality more and, hence, are willing to wait longer for higher-quality objects. Therefore, waiting costs act as prices to clear the market, with higher-quality objects having higher prices. However, waiting costs are also sunk costs. An information disclosure policy that does not fully disclose the object types may allow for changing these prices such that efficiency gains from lower prices offset losses from the non-assortative assignment of objects to agents. We find an information disclosure policy that pools adjacent object types, which, under a FCFS wait-list with deferrals, implements the same outcome as the optimal mechanism. Agents decide whether to join the wait-list and objects are offered on a FCFS basis to the agents, who can decline offers while keeping their position on the wait-list. The information disclosure policy uses a set of intervals that partitions the range of object qualities and discloses to agents only the interval containing an object. The challenge in analyzing a single wait-list is accounting for the agents' strategic behavior who have to reason about the decisions of the other agents ahead of them on the list. We show that this dynamic game has a unique equilibrium when the information disclosure policy pools adjacent object types. In addition, there is such a disclosure policy under which the welfare at this equilibrium equals the welfare under the optimal disjoint queue mechanism. [ABSTRACT FROM AUTHOR]