Efficient Combinatorial Assignment (with Thành Nguyen and Shai Vardi)

We characterize all ordinally efficient allocations in the combinatorial assignment setting in which agents have ordinal preferences over bundles of indivisible resources. Our Competitive Equilibrium from Random Incomes (CERI) assigns a random budget of tokens to each agent, finds the distribution of optimal bundles, and computes prices that clear the market in expectation. We show that an allocation is ordinally efficient if and only if it is a CERI allocation. When distributions of token budgets are continuous a CERI exists. Any CERI can be implemented as a lottery over approximately ex-post efficient allocations. When token budget distributions are identical a CERI allocation is ordinally envy-free, and when they are on a sufficiently small support, a CERI allocation is ex-post envy-free up to one good. Using our characterization and new techniques, we develop mechanisms that are (asymptotically) strategyproof, efficient and envy-free. CERI therefore fully captures difficult tradeoffs between efficiency, equity and incentive compatibility in combinatorial assignment and can be practically used for a variety of applications including course allocation, daycare assignment, allocation of food donations to food banks, and refugee resettlement.