Richard M. Karp Distinguished Lecture — Algorithmic Opportunities in Matching Markets

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). 

New opportunities for developing fundamental algorithmic tools for matching markets arise from ideas obtained within Algorithmic Game Theory; I will first describe these. The rest of the talk will be devoted to a very specific market, the Adwords market, in which results from "pure theory" obtained three decades ago led to algorithms that are used widely by search engine companies and have had a massive (multi-billion dollar) impact.

Light refreshments will be served before the lecture at 3:30 p.m.