Stable matchings and lattices
MATH-702 / 1 credit
Teacher(s): Eisenbrand Friedrich, Invited lecturers (see below)
Language: English
Remark: We will assume that the audience has basic knowledge of algorithmic theory and previous exposure to classical optimization models (linear programming, integer programming) and algorithms
Frequency
Only this year
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:
1. Introduction to stable matchings
(a) Definitions
(b) Properties
(c) Examples
(d) Distributive lattice structure
2. Linear optimization over stable matchings via their distributive lattice structure and Birkhoff's representation theorem
(a) The poset of rotations
(b) Linear optimization via reduction to minimum cut
3. Further applications and extensions of the distributive lattice structure
(a) Affine representability and the stable matching polytope
(b) Von Neumann-Morgenstern Stability
(c) Models with quota-filling choice functions
4. Non-distributive lattice structure of stable matchings in path-independent models and its algorithmic consequences
(a) Models with path-independent choice functions and their lattices
(b) 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.
Note
Invited lecturer: Prof. Yuri Faenza
Keywords
Stable matchings, lattices, linear optimization
Learning Prerequisites
Required courses
Introductory courses in algorithms and optimization
Learning Outcomes
By the end of the course, the student must be able to:
- Explain , model, and solve stable matchings problems and related problems
In the programs
- Number of places: 15
- Exam form: Project report (session free)
- Subject examined: Stable matchings and lattices
- Courses: 6 Hour(s)
- Exercises: 6 Hour(s)
- Project: 10 Hour(s)
- Type: optional