Monday February 21st at 2.30pm

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.