Department of Computer, Control and Management Engineering

In the classical marriage model by Gale and Shapley, agents from one side of the market have a strict ordering of the agents from the other side of the market 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 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. I will show the practical relevance of those choice functions by applying them to data from specialized high schools admission in New York City. Based on joint work with Swati Gupta (GA Tech & MIT) and Xuan Zhang (Meta Research).