MS&E 319: Matching Theory

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 (tpollner@stanford.edu)
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.)

Course description:
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.

Reading material:
Lecture notes or links to papers & surveys will be available on the class webpage. The following textbook is recommended:

L. Lovasz, M.D. Plummer, Matching Theory, 1986.

Course load and grading:
Two homework assignments (25% each) and research project (50%).

Lectures:

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).
Lectures 7, 8, 9: Online Matching in Adversarial Models
- 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.
- 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.
Lectures 10, 11: Online Matching in Bayesian Models
- We discussed prophet inequalities for matching in adversarial and random arrival orders. See the handwritten notes.
Lectures 12, 13: Stochastic Matching
- The paper introduced the stochastic matching problem and gave a 0.5-approximation for it. There is also a proof that its approximation is no better than 5/6, and several discussions about applications of the model.
- Papers here and here giving the improved algorithm with a (1-eps)-approximation guarantee.
Lectures 14, 15: Applications of Matching Theory
- School choice: Itai Ashlagi's slides on mechanisms for matching without money, and applications to school choice in SFUSD.
- Ridesharing: See the papers on Maximum Weight Online Matching with Deadlines and Online Hypergraph Matching with Delays, both inspired by ridesharing applications.
Lecture 16: EDCS and Dynamic Matching
- EDCS were first introduced in this paper on dynamic matching by Bernstein and Stein. It has since been used for a number of computational models, such as streaming, Massive Parallel Computation, and more. A simple analysis of these matching sparsifiers was given in this SOSA19 paper. This includes the example application to communication complexity mentioned in class, and a few others. The use of EDCS for dynamic matching appeared in a number of papers (here, here, here, here and here), with the last of these papers probably giving the sleekest algorithm and analysis using this sparsifier.
Lecture 17: Fast algorithms for matching
- An O(n log n) randomized algorithm for computing a perfect matching in regular bipartite graphs; see here.
Lecture 18: The matching polynomial and its roots
- See the class notes from previous years and also these lecture notes by Daniel Spielman.

Homework:

You can find last year's course homepage here.