Some discrete optimization problems in matching markets.

Abstract:  In the classical stable marriage problem, we are given two sets of agents – students and schools – with each student and school having a total order of agents from the opposite set. The goal is to form disjoint pairs of students and schools so that the resulting matching satisfies a fairness property known as stability. In their fundamental work, Gale and Shapley showed that a stable matching always exists and gave a fast algorithm to find one. These strong structural and algorithmic results propelled the application of the stable marriage model in several contexts, most notably for assigning students to public high schools in many cities in the United States. Although very successful, the marriage model however fails to capture features that have become of crucial importance both inside and outside academia, such as diversity in school cohorts, complex preference patterns, and the need to obtain larger, possibly mildly unstable, matchings. In this talk, I will first present some extensions of the concept of stability and of the marriage model and investigate them from an optimizer’s viewpoint. I will then focus in detail on recent work with Xuan Zhang (Columbia) on algorithms for stable matching models when the preference patterns of agents are described by choice functions. Our approach will allow us to deduce general sufficient conditions for efficiently optimizing linear functions over the elements of a distributive lattice.

Posted on Jun 14, 2021 in ACGO, Seminars