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, as we will show in this paper, in a
probabilistic setting where the preference lists of one side of the
market are composed of only a constant (independent of the the size of
the market) number of entries, each drawn from an arbitrary
distribution, the number of participants that have more than one
stable partner is vanishingly small. This proves (and generalizes) a
conjecture of Roth and Peranson. 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. We also 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 the work of Roth and Peranson on the National
Residency Matching Program.
Copyright. All Rights Reserved.