Quick links

Matching Markets

Date and Time
Tuesday, April 20, 2010 - 4:30pm to 5:30pm
Computer Science Small Auditorium (Room 105)
CS Department Colloquium Series
Avinatan Hassidim, from MIT
Sanjeev Arora
Matching markets appear in many different scenarios, from college admissions to job search. In the simplest, the deferred acceptance of Gale and Shapley provides a stable solution (also known as a stable marriage) to these problems. It also has the desirable property that for the ``proposing side" it is a dominant strategy to behave truthfully.

In this talk, I will focus on a couple of more involved matching markets. The first will be assigning doctors to residencies when there are two body problems. We will discuss the Match, show impossibility results, and present new matching algorithms that satisfy the above properties in a large market . The second will be Internet ad auctions with budgets, where we match between advertisers and slots on the web-page.

Based on Joint works with Itai Ashlagi, Mark Braverman, Ron Lavi and Moshe Tennenholtz

Follow us: Facebook Twitter Linkedin