EECS Main
>
Events
Event Details
|
MEET THE FACULTY: Nicole Immorlica4:00 - 5:00 p.m.
March 11, 2009
Ford ITW Auditorium
Nicole Immorlica
"Marriage, Honesty, and Stability"
This event was recorded on video | 
A story of romance, true love, and the future of health care.
Many centralized two-sided markets form a matching between participants by running a stable marriage algorithm. It is a well-known fact that no matching mechanism based on a stable marriage algorithm can guarantee truthfulness as a dominant strategy for participants. However, we show in a probabilistic setting where the preference lists of one side of the market are composed of only a constant number of entries, each drawn from an arbitrary distribution, the number of participants that have more than one stable partner is vanishingly small. As a corollary of this result, we show that, with high probability, the truthful strategy is the best response for a given player when the other players are truthful. Our results have implications in many practical settings and were inspired by the work of Roth and Peranson on the National Residency Matching Program.
A video of this presentation is available at this link. |
|
