[Colloq] Colloq Spkr Tomorrow @ Noon

[Chantal Cardona]

**

* *

*College** of **Computer** and Information Science Colloquium*

 

Presents:

*Mohammad Mahdian*

*(Microsoft Research, Redmond)*

 

Who will speak on:

*Random Popular Matchings*

* *

*/Tuesday, November 29, 2005/**//*

*/12:00Noon /*

*/366 West Village H/*

*/Northeastern University/*

*/ /*

_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.

 

_Bio_:

 

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.