How to Use Prices for Efficient Online Matching [link available soon]
Abstract: Many matching markets feature unknown, dynamic arrivals of agents that must match immediately. A caseworker must match an abused child to a foster home, a hospital must assign a patient in critical condition to a room, or a city must place a homeless individual into a shelter. We design an online matching algorithm---the Sequential Equilibrium Mechanism (SEM)---that approximates large market equilibria to match arriving agents to objects. SEM is asymptotically efficient, fair, and strategy-proof with probability one. Our application plans to deploy a field experiment where real caseworkers match vulnerable children to host homes, and we currently provide simulation evidence that SEM can substantially improve welfare.
A Dynamic Matching Framework for Faster Child Adoptions [link]
Abstract: Caseworkers in foster care systems match waiting children to adoptive homes. We use dynamic matching market design to characterize a class of mechanisms that incentivize expedient matches that homes can accept or decline. We design mechanisms satisfying fairness and limited strategy-proofness. They also avoid costly patience. Our empirically-based simulations suggest the mechanisms could increase adoptions by at least 25% versus the status quo. A naive dynamic extension of Deferred Acceptance does not attain these benefits. Our mechanisms sidestep direct preference elicitation by predicting preferences, and they are robust to prediction error.
A Market Approach for Online Task Allocation (draft available upon request)
Abstract: Online task allocation is a the problem of allocating stochastically arriving tasks to a fixed set of known agents. We model a mechanism that opens a pseudomarket where agents receive fiat money to purchase probabilities of a task contingent on the task arriving in a future period. Our Dynamic Pseudo-Market (DPM) mechanism allocates tasks through constructing quasiequilibria in the pseudomarket. It is ex-ante efficient. Our quasiequilibria concept imposes lump-sum taxes on the fiat budget to ensure that DPM is ex-ante efficient and asymptotically ex-post balanced, meaning that agents complete (weighted) equal numbers of tasks in the limit. In addition: we establish prophet inequalities showing that DPM is ex-post efficient, beating other greedy mechanisms.