Fall 2019

Algorithms for Stable Matchings in Models with Choice Functions

Monday, Mar. 1, 2021 10:40 am11:10 am

Add to Calendar


Yuri Faenza (Columbia University)



We present an algorithm for optimizing a linear function over the set of stable matchings when preferences of the agents are expressed via choice functions that are substitutable, consistent, and quota-filling. Alkan proved that, in this model, the set S of stable matching forms a distributive lattice. Using Birkhoff's representation theorem, S can therefore be represented as the family of closed sets of a poset. Generalizing the approach by Irving, Leather, and Gusfield (1987), we explain how to use this auxiliary poset to solve our original optimization problem. More generally, we discuss the problem of optimizing a linear function over the elements of a distributive lattice.

Joint work with Xuan Zhang (Columbia University)