Partial Two-Sided Matching

Over the last few decades market designers have been using two-sided stable matching theory to redesign centralized matching systems around the world and across many domains, including university admissions, matching for medical internships and residencies, school choice, and more. However, no theory and no algorithms are available to address the (common) case of partial participation in the centralized matching system. Motivated by this gap, and by a specific application (matching for Israeli law internships), we introduce the concept of safe matching - a relaxation of stability that is more suited to deal with scenarios in which the designer only has access to some of the agents. We prove structural results, including the existence of a maximal safe matching, and provide a polynomial-time algorithm that converges to a maximal safe matching.

(joint with Avinatan Hassidim and Ran I. Shorrer) 

Assaf Romm's homepage: https://assafromm.weebly.com