Stable matchings in choice function models: algorithms, polyhedra, and an application to school choice
Friday, 16 June, 2023 - 14:00
Aula Magna DIAG
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).
Bio: Yuri Faenza obtained his Ph.D. from the Sapienza University of Rome and is currently an associate professor in the IEOR department at Columbia University. He works in discrete optimization, operations research, matching theory, market design, and their applications. His research has been funded by the NSF (including an NSF Career award), the ONR, the Swiss NSF, and by a Meta Research Award. He is the current chair of Mixed-Integer Programming Society of the MOS.
gruppo di ricerca: