Yuri Faenza: Stable matchings in choice function models: algorithms, polytopes, and school choice

Seminars - Occasional seminars
YURI FAENZA, Columbia University
12:00 - 13:00
Room 3-E4-SR03 (Rontgen) / Zoom



In the classical marriage model by Gale and Shapley, agents from one side of the market (such as students/workers/doctors/...) have a strict ordering of the agents from the other side of the market (schools/firms/hospitals/...), and vice-versa. The goal is to find a matching that satisfies a fairness condition known as stability. However, strict orders cannot model many preference patterns that arise in problems such as diversification of school cohorts, formation of teams, etc. Hence, much attention has recently been reserved to matching problems where preferences of agents have a more complex behavior, which can be described via certain choice functions. In the first part of this talk, I will investigate algorithmic properties of these models, showing that the classical combinatorial approach based on the distributive lattice of stable matchings and the description of the convex hull of stable matchings as an LP are intimately related. This approach may turn out to be of interest for other problems in discrete optimization as well. In the second part of the talk, I will show how certain choice functions can be used to model school admission criteria that take into account well-defined diversity and fairness concerns, and will show their practical relevance by applying them to data from specialized high schools in New York City.


Joint work with Swati Gupta (Georgia Tech) and Xuan Zhang (Meta).