Skip to main content
Loading Events

« All Events

  • This event has passed.

Stable matchings: lattices, polytypes, and applications

April 15 @ 12:00 PM 1:00 PM

Room 1163 ME

Dr. Yuri Faenza, Columbia University

Abstract: In the classical matching 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. 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 this talk, we investigate algorithmic properties of these models, showing that the classical combinatorial approach based on the 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. If time allows, I will also discuss some applications of stable matchings in choice function models to affirmative action policies in New York City public high schools. 

Bio: Yuri Faenza is an associate professor in the IEOR department at Columbia University. He works in discrete optimization, operations research, matching theory, and their applications. His research has been funded by the NSF (including an NSF Career award), the ONR, and the Swiss NSF.