David Delacrétaz
Ph.D. Candidate – Department of Economics – The University of Melbourne

Working Papers

Stability in Matching Markets with Sizes

Abstract: Matching markets such as day care, tuition exchange, couples problems and refugee resettlement involve agents of different sizes. The size of an agent is the amount of capacity that he uses. In matching markets where all agents have the same size, there exists an agent-optimal stable matching. This structure disappears when agents have different sizes: the set of stable matchings may not contain an agent-optimal element and may even be empty. In this paper, we study a matching market where the size of an agent is either one or two. We propose a novel and constructive algorithm to find an agent-undominated stable matching whenever one exists. We introduce a novel relaxation of stability: size-stability. Size-stable matchings are non-wasteful but allow size-two agents to envy multiple size-one agents. We show that the set of size-stable matchings is nonempty. We adapt our algorithm to find a size-stable matching that is undominated from the point of view of size-two agents, thus compensating them for envying size-one agents. In the process, we outline a new trade-off between eliminating waste and bounding envy: at any non-wasteful matching, an agent may envy arbitrarily many other agents.

Two-Sided Allocation Problems, Decomposability, and the Impossibility of Efficient Trade 

Joint with Simon Loertscher, Leslie Marx, and Tom Wilkening
Revise and ResubmitJournal of Economic Theory

Abstract: Previous literature has shown that private information is a transaction cost that prevents efficient reallocation in two-sided setups with bilateral trade or homogeneous goods. We derive conditions under which the impossibility of efficient trade extends to rich environments in which buyers and sellers have multi-dimensional private types, accommodating many-to-many trades and heterogeneous objects. If agents can be decomposed into unit constituents, the allocation problem can be represented as an assignment game and impossibility obtains through a generalization of Shapley’s (1962) result that buyers and sellers are complements. We introduce a general family of payoff functions that ensures decomposability and thus impossibility.

Refugee Resettlement

Joint with Scott Duke Kominers and Alexander Teytelboym
Media coverage: BloombergNews Deeply
Application: Refugees’ Say

Abstract: Over 100,000 refugees are permanently resettled from refugee camps to hosting countries every year. Nevertheless, refugee resettlement processes in most countries are ad hoc accounting for neither the priorities of hosting communities nor the preferences of refugees themselves. Building on models from two-sided matching theory, we introduce a new framework for matching with multidimensional constraints that models refugee families’ needs for multiple units of different services, as well as the service capacities of local areas. We propose several refugee resettlement mechanisms that can be used by hosting countries under various institutional and informational constraints. Our mechanisms can improve match efficiency, incentivize refugees to report where they would like to settle, and respect priorities of local areas thereby encouraging them to accept more refugees overall. Beyond the refugee resettlement context, our model has applications ranging from the allocation of daycare slots to the incorporation of complex diversity constraints in public school assignment.

Essentially Stable Matchings

Joint with Peter Troyan and Andrew Kloosterman

Abstract: We propose a solution to the trade-off between Pareto efficiency and stability in matching markets. We define a matching to be essentially stable if any claim initiates a chain of reassignments that ultimately results in the initial claimant losing the object she claimed to a third agent. Our definition is not only compatible with Pareto efficiency but also is practical, since explaining why claims are not valid is straightforward. We study the essentially stable set and show that it shares some, though not all, of the structure possessed by the stable set. We classify popular Pareto efficient mechanisms using our definition: those based on Shapley and Scarf’s TTC mechanism are not essentially stable while Kesten’s EADA mechanism is. Our analysis points to a trade-off among essential stability, Pareto efficiency, and strategyproofness: mechanisms exist that satisfy any two of these properties but no mechanism achieves all three.

Work in Progress

Uncontrolled Immigration and Refugee Matching
Joint with Ellen Muir