| |
|
| |
|
Mohammad Mahdian
Microsoft Research Theory Group
Marriage, Honesty, and Stability
April 13, 2006 10:00am
Abstract:
Many centralized two-sided markets, such as the medical residency market, 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, as we will show in this talk, in a certain probabilistic setting, truthfulness is (in some sense) the best strategy for the participants. We show this by proving that in our setting the set of stable marriages is small. We derive several corollaries of this result. First, we show that, with high probability, in a stable marriage mechanism, the truthful strategy is the best response for a given player when the other players are truthful. Then we analyze equilibria of the deferred acceptance stable marriage game. We show that the game with complete information has an equilibrium in which a $(1-o(1))$ fraction of the strategies are truthful in expectation. In the more realistic setting of a game of incomplete information, we will show that the set of truthful strategies form a $(1+o(1))$-approximate Bayesian-Nash equilibrium. Our results have implications in many practical settings and were inspired by experimental observations in a paper of Roth and Peranson (1999) concerning the National Residency Matching Program.
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.