Communications and Signal Processing Seminar

Scarfs Lemma and Stable Matchings

Rakesh VohraProfessorUniversity of Pennsylvania

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.

Sponsored by

ECE - Systems

Faculty Host

Vijay Subramanian