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.