MS&E 319: Matching Theory, Spring 2022
Location: Shiram 108, Tuesdays and Thursdays 1:30 - 3:00 PM.
Instructor: Amin Saberi
Office Hours: by appointment
Teaching Assistant: Tristan Pollner (firstname.lastname@example.org)
Office Hours: Tuesdays 12:30 - 1:30 PM, Huang
3rd floor. (You can also find me after class if you want to chat about the course.)
The theory of matching with its roots in the work of mathematical giants like Euler and Kirchhoff has played a central and catalytic role in combinatorial optimization for decades. More recently, the growth of online marketplaces for allocating advertisements, rides, or other goods and services has led to new interest and progress in this area.
The course starts with classic results characterizing matchings in bipartite and general graphs and explores connections with algebraic graph theory and discrete probability. Those results are complemented with models and algorithms developed for modern applications in market design, online advertising, and ride sharing.
Lecture notes or links to papers & surveys will be available on the class webpage. The following textbook is recommended:
Course load and grading:
Two homework assignments (25% each) and research project
- Week 1: Matching, determinant, and Pfaffian
- Matching and polynomial identity testing.
- Isolating lemma and matrix inversion, matching in RNC.
- See the notes for lectures 1 and 2, and the MVV paper.
- Week 2: Combinatorial and polyhedral characterizations
- Hall's marriage theorem and polyhedral formulation of perfect matching.
- Tutte's theorem, Edmonds's LP and the Blossom algorithm.
- The assignment problem and its dual, primal-dual and auction algorithms.
- See the lecture notes by Santosh Vempala, as well as by Michel Goemans on bipartite and non-bipartite matching. Also see Edmonds's Paths, Trees, and Flowers paper.
- Week 3: Stable Matching
- The deferred acceptance algorithm, proposer optimality, (lack of) incentive compatibility. See the slides.
- The polyhedral characterization and lattice structure (refer to this chapter of an upcoming book of Echenique, Immorlica, and Vazirani).
- Random order stable matchings (see the paper and blog post).
- Week 4: Online Matching
- Notes from class on online fractional bipartite matching. The water-filling algorithm and its optimality first appeared in this paper. For an analysis of the algorithm similar to the one seen in class, see these notes by Tim Roughgarden.
- The randomized pirmal-dual schema, applied to the RANKING algorithm, is from this sleek paper (see also discussion about impossibility of black-box rounding of online matchings). An economic interpretation of the same analysis appears here. The randomized rounding approach for bipartite vertex cover appears in, e.g., Section 2.2 here.
- Week 5: Online Algorithms (continued)
- The AdWords problem was introduced in this paper. The primal-dual based AdWords algorithm we saw appeared here. For a better-than-(1-1/e) competitive algorithm for online i.i.d. matching, see Section 3 of this paper.
- Handwritten notes on prophet inequalities and prophet secretary for matching via OCRS will be posted!
You can find last year's course homepage here.