  We consider the problem of learning stable matchings in a fully decentralized
and uncoordinated manner. In this problem, there are $n$ men and $n$ women,
each having preference over the other side. It is assumed that women know their
preferences over men, but men are not aware of their preferences over women,
and they only learn them if they propose and successfully get matched to women.
A matching is called stable if no man and woman prefer each other over their
current matches. When all the preferences are known a priori, the celebrated
Deferred-Acceptance algorithm proposed by Gale and Shapley provides a
decentralized and uncoordinated algorithm to obtain a stable matching. However,
when the preferences are unknown, developing such an algorithm faces major
challenges due to a lack of coordination. We achieve this goal by making a
connection between stable matchings and learning Nash equilibria (NE) in
noncooperative games. First, we provide a complete information game formulation
for the stable matching problem with known preferences such that its set of
pure NE coincides with the set of stable matchings, while its mixed NE can be
rounded in a decentralized manner to a stable matching. Relying on such a
game-theoretic formulation, we show that for hierarchical markets, adopting the
exponential weight (EXP) learning algorithm for the stable matching game
achieves logarithmic regret with polynomial dependence on the number of
players, thus answering a question posed in previous literature. Moreover, we
show that the same EXP learning algorithm converges locally and exponentially
fast to a stable matching in general matching markets. We complement this
result by introducing another decentralized and uncoordinated learning
algorithm that globally converges to a stable matching with arbitrarily high
probability, leveraging the weak acyclicity property of the stable matching
game.
