Gale and Shapley's college admission problem and the concept of stability have been extensively studied, applied, and extended in the last decades. The input of the classical model is a set of students and schools, with students having a strictly ordered list of schools they would like to attend, and similarly schools having a strictly ordered list of students they are willing to admit, as well as the maximum number of seats available at each school (quota). The output is an assignment of students to schools that respects quotas and a concept of fairness known as stability. The goal of many extensions of this model is to obtain an assignment more favorable to students, often shifting the focus from stability to (constrained) Pareto efficiency (for students). In this talk, we show how to obtain an improved understanding of some of those extensions using tools, facts, and ideas from the classical theory of stable matchings. This allow us, in particular, to prove strong structural properties and obtain algorithms that perform faster in both theory and practice. Joint work with Xuan Zhang
Bio: Yuri Faenza is Assistant Professor in the Industrial Engineering and Operations Research (IEOR) department at Columbia University since 2016. He obtained a Ph.D. in Operations Research from the University of Rome (Italy), and has worked with various roles at the University of Padua (Italy) EPFL (Switzerland), and University of Brussels (Belgium). His research has been funded by several agencies, including the European Union and the National Swiss Science Foundation. His research interests lie in Discrete Optimization, including theory, algorithms and connections / applications to other areas.
Welcome to everyone!