Uncoordinated Two-Sided Markets
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin,
and Berthold Vöcking
Various economic interactions can be modeled as two-sided markets.
A central solution concept to these markets are stable matchings,
introduced by Gale and Shapley. It is well known that stable matchings
can be computed in polynomial time, but many real-life markets lack a
central authority to match agents. In those markets, matchings are formed
by actions of self-interested agents. Knuth introduced uncoordinated
two-sided markets and showed that the uncoordinated better response
dynamics may cycle. However, Roth and Vande Vate showed that the random
better response dynamics converges to a stable matching with probability
one, but did not address the question of convergence time.
In this paper, we give an exponential lower bound for the convergence
time of the random better response dynamics in two-sided markets. We also
extend these results to the best response dynamics, i.e., we present
a cycle of best responses, and prove that the random best response
dynamics converges to a stable matching with probability one, but its
convergence time is exponential. Additionally, we identify the special
class of correlated two-sided markets with real-life applications for
which we prove that the random best response dynamics converges in
expected polynomial time.