The seminal, and Nobel-Prize-winning, work of Gale & Shapley (1962) started the field of matching markets. Bolstered by the Internet and mobile computing revolutions, today these markets occupy a sizable fraction of our economy (e.g., the Adwords market, Uber, Airbnb, Up-work) and have yielded effective solutions to important sociological challenges (e.g., markets for assigning students to schools, kidney exchange, and medical residents).

The discipline of algorithm design has had an umbilical connection to matching markets: At the birth of this field lies the highly sophisticated Gale-Shapley stable matching algorithm, whose quintessential game-theoretic property of incentive compatibility follows as a free gift from polynomial time solvability -- it was established two decades after the discovery of the algorithm by Dubins and Freedman.

This talk will provide a panoramic overview of this and other success stories in matching markets, such as a solution to the Adwords problem, which have sophisticated algorithms at their core. The talk will conclude with the general and powerful scheme of Hylland & Zeckhauser (1979) for running a one-sided matching market. Obtaining an efficient algorithm for this scheme is an outstanding 40-year-old open problem.

Vijay Vazirani received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. He has been a professor at Cornell and Georgia Tech and is currently Distinguished Professor at the University of California, Irvine. Vazirani has made seminal contributions to the theory of algorithms, in particular to the classical maximum matching problem, approximation algorithms and algorithmic game theory, as well as to complexity theory, in which he established, with Les Valiant, the hardness of unique solution instances of NP-complete problems. In 2001 he published what was widely regarded as the definitive book on Approximation Algorithms. His research on algorithms for the maximum matching problem spans four decades and on market equilibria spans two decades. His current research interest is algorithms for matching markets.