Events - Colloquia & Seminars

CCIS Colloquium Fall 2005

Random popular matchings

Speaker: Mohammad Mahdian (Microsoft Research, Redmond)

Date: Tuesday, November 29, 2005

Talk: 12:00 pm, 366 WVH

Abstract

We consider matching markets where a centralized authority must find a matching between the agents on one side of the market, and the items on the other side. Such settings occur, for example, in mail-based DVD rental services such as NetFlix or in certain job markets. A popular matching is defined as a matching that is preferred by a majority of the agents to any other matching. The main drawback of this solution concept is that popular matchings sometimes do not exist. We partially address this issue by proving that in a probabilistic setting where preference lists are drawn at random and the number of items is more than the number of agents by a small multiplicative factor, popular matchings almost surely exist. More precisely, we prove that there is a threshold (~=1.42) such that as the number of items divided by the number of agents passes this threshold, the probability of existence of a popular matching goes from zero to one asymptotically. Our proof uses a characterization result by Abraham et al., and a number of tools from the theory of random graphs.

Biography

Mohammad Mahdian has received his PhD from MIT in June 2004, and has since been a postdoctoral researcher at Microsoft Research in Redmond. His research interests include algorithms and game-theoretic aspects of computing.