Discrete Mathematics and Optimization Seminar
MOHAMMAD MAHDIAN |
Microsoft Research
Monday February 21st at 2.30pm
Burnside 1205
Title. Marriage, Honesty, and Stability.
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.