CSP Seminar

Scarf’s Lemma and Stable Matchings

Rakesh Vohra

University of Pennsylvania
Friday, December 01, 2017
10:00am - 11:00am
1013 Dow

Add to Google Calendar

About the Event

The elegance and simplicity of Gale and Shapley's deferred acceptance algorithm (DA) has made it the algorithm of choice for determining stable matchings in a variety of settings. Each setting has imposed new demands on the algorithm. Among them are to how to handle complementarities and distributional constraints. The simplicity of the DA algorithm makes it difficult to accommodate these new considerations except in special cases. In this talk I outline an alternative approach based on Scarf’s lemma for tackling such problems. It is based on joint work with Thanh Nguyen.


Professor Vohra is a leading global expert in mechanism design, an innovative area of game theory that brings together economics, engineering and computer science. His economics research in mechanism design focuses on the best ways to allocate scarce resources when the information required to make the allocation is dispersed and privately held, an increasingly common condition in present-day environments. His work has been critical to the development of game, auction and pricing theory — for example, the keyword auctions central to online search engines — and spans such areas as operations research, market systems and optimal pricing mechanisms. He formerly taught at Northwestern University, where he was the John L. and Helen Kellogg Professor of Managerial Economics and Decision Sciences in the Kellogg School of Management, with additional appointments in the Department of Economics and the Department of Electrical Engineering and Computer Science. He taught from 1985 to 1998 in the Fisher College of Business at Ohio State University. He earned a Ph.D. in mathematics in 1985 from the University of Maryland, an M.Sc. in operational research in 1981 from the London School of Economics and a B.Sc. (Hon.) in mathematics in 1980 from University College London. He came to Penn as part as of the Penn Integrates Knowledge program that President Amy Guttmann established in 2005 as a University-wide initiative to recruit exceptional faculty members whose research and teaching exemplify the integration of knowledge across disciplines. His appointment is shared with the Department of Electrical and Systems Engineering in the School of Engineering and Applied Science.

Additional Information

Sponsor(s): ECE - Systems

Faculty Sponsor: Vijay Subramanian

Open to: Public