Random combinatorial assignment
We study a model of combinatorial assignment of indivisible objects without money and exploit the power of random assignment rules compared to deterministic ones. We introduce a new notion of "expected competitive equilibrium from equal incomes". In an ECEEI, agents receive random, near-equal budgets of tokens, select their optimal lotteries over objects, and markets clear in expectation. Compared to the celebrated (deterministic) approximate CEEI (Budish 2011), ECEEI (i) is symmetric (i.e., gives the same expected allocation to the same types); (ii) is ex-ante Pareto-efficient; (iii) controls good-by-good (rather than overall) ex-post constraint violations; and (iv) is computationally faster. Moreover, we show how to apply ECEEI for online assignment where a naive repeated application of ACEEI does not yield a desirable outcome because the approximation error in market-clearing compounds quickly over time. Our ECEEI-based online mechanism is (i) group strategy-proof up to one object; (ii) envy-free up to one object for almost all agents; (iii) approximately market-clearing in almost all periods with high probability when the market is large and arrivals are random. Applications include refugee resettlement, daycare assignment, and airport slot allocation.