Teacher: Yuri Faenza
Credit: 1
Duration: July 7th to July 11th, only in 2025
Language: English
Room: CM 1 221
Summary
Starting with the work of Conway and Knuth in the 1970s, many advances in the theory of stable matchings, a solution concept originally introduced by Gale and Shapley in the 1960s, have been framed in terms of the underlying lattice structure. In this course, we will explore these developments.
Content
The lecture component of the course is divided into 4 classes of 1.5 hours each:
- Introduction to stable matchings
- Definitions
- Properties
- Examples
- Distributive lattice structure
- Linear optimization over stable matchings via their distributive lattice structure and Birkhoff’s representation theorem
- The poset of rotations
- Linear optimization via reduction to minimum cut
- Further applications and extensions of the distributive lattice structure
- Affine representability and the stable matching polytope
- Von Neumann-Morgenstern Stability
- Models with quota-filling choice functions
- Non-distributive lattice structure of stable matchings in path-independent models and its algorithmic consequences
- Models with path-independent choice functions and their lattices
- Stable matchings and antimatroids
In the exercise component (4 classes of 1.5 hours each), students will be asked to work on problems related to each of the lectures.
The project component will require the students to get familiar with topics beyond the content of the class, and to present them to the rest of the class.