Stable Matchings

LECTURER CANDIDATE

We will discuss the stable matching problem: Given two sets of agents (entities with preferences), our goal is to pair them off, while respecting the preferences of everyone involved. Algorithms for this problem have been used to match students to high schools, doctors to hospitals, and TAs to courses among many other applications. Stable matchings have proven so useful that the popularizers of the problem and the associated algorithms were awarded the 2012 Nobel Prize.
We will discuss a beautifully-simple algorithm for solving the problem; if time permits we may very briefly discuss some questions about stable matchings that are the subject of active research.

We will assume only a basic familiarity with programming and proofs (completion of EECS 203 would suffice); much of the talk will be accessible even without that background.

Biography:
Robbie Weber is a fifth-year Ph.D. student at the University of Washington. He spends most of his time TAing and teaching a wide array of theoretical and theory-adjacent computer science courses (9 different courses so far). When he finds time for research, it lies broadly in algorithm design for graph problems and in answering combinatorial questions. He is advised by Shayan Oveis Gharan and Anna Karlin.