EconCS Seminar

 

Lecturer: 

Dr. Assaf Romm (Hebrew University)

Title: 

Partial two-sided matching (the hard part)

Abstract: 

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 the existence of a maximal safe matching and provide an algorithm that converges to it in polynomial time. We also uncover the structure of the set of safe matchings, showing that it relies on a tree-like structure of independent tiers of agents.

Note: This paper was overviewed on the Israeli AGT day. In this talk I will quickly repeat the settings, but this time actually show the model, the results, and the proofs.

Location: 

Room 130, Feldman Building, Edmond J. Safra Campus.

Click here to add the EconCS Seminar to your Google Calendar