Optimal Allocation without Money : An Engineering Approach

We study the allocation of heterogeneous services to agents without monetary transfers under incomplete information. Agents have private, multi-dimensional utilities over services, drawn from commonly known priors, which may depend on agents' observable information. The social planner's goal is to maximize a public objective. Potential applications include the allocation of seats to public schools, spaces in college dorms or courses, or spots in subsidized housing. For tractability, we take an "engineering'' approach, in which we first solve a simpler large market approximation, and show using real data that a corresponding finite market mechanism still yields good results. In the large market model, there are finitely many "types'' of agents, and a continuum of agents of each type. (Here, "type'' corresponds to agents' observation information.) For both cardinal and ordinal mechanisms, we characterize all mechanisms that are incentive compatible and Pareto optimality within type. Such characterizations reduce the mechanism design problem to a well-defined optimization problem with a few continuous variables. We apply this framework to real data from Boston 2012-2013 school choice reform. The goal is to design an optimal ordinal mechanism to assign students to public schools to maximize a linear combination of utilitarian and max-min welfare, subject to capacity and transportation constraints. We show how to optimally solve a large market model with over 868 types of students and 77 schools, translate the solution into the finite market setup and yield a feasible finite market mechanism, which significantly outperforms the baseline plan chosen by the city in terms of efficiency, equity, and predictability