Matching Theory

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 other branches of mathematics, including game theory and algebraic graph theory. Those results are complemented with models and algorithms developed for modern applications in market design, online advertising, and ride sharing. May be repeated for credit. Prerequisite: 212, CS 261, or equivalent.