Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Uncoordinated twosided matching markets
 SIAM Journal on Computing 40 (2011), No.1, pp.92106 ISSN: 00975397 ISSN: 10957111 

 English 
 Journal Article 
 Fraunhofer ITWM () 
Abstract
Various economic interactions can be modeled as twosided markets. A central solution concept for these markets is stable matchings, introduced by Gale and Shapley. It is well known that stable matchings can be computed in polynomial time, but many reallife markets lack a central authority to match agents. In those markets, matchings are formed by actions of selfinterested agents. Knuth introduced uncoordinated twosided 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 they 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 twosided markets. We also extend the results for the better response dynamics to the best response dynamics; i.e., we present a cycle of best responses and prove that the r andom 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 matroid twosided markets with reallife applications for which we prove that the random best response dynamics converges in expected polynomial time.