Matching Markets

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