Uncoordinated Two-Sided Matching Markets
Uncoordinated Two-Sided Matching Markets
复制标题
不协调的双边匹配市场
DOI：
10.1137/090753498
复制
发表时间：
2011
影响因子：
1.6
通讯作者：
Ackermann H
中科院分区：
文献类型：
--
作者：
Ackermann H
各种经济互动可以被建模为双边市场。这些市场的核心解决方案概念是稳定匹配，由Gale和Shapley引入。众所周知，稳定匹配可以在多项式时间内计算，但许多现实生活中的市场缺乏一个中央权威机构来匹配代理。在这些市场中，匹配是由自利行为人的行为形成的。高德纳引入了不协调双边市场，并表明不协调的更好的反应动态可能会循环。然而，Roth和Vande Vate证明了随机最优反应动态收敛于概率为1的稳定匹配，但没有解决收敛时间的问题，本文给出了双边市场中随机最优反应动态收敛时间的指数下界.我们还将更好的响应动态的结果扩展到最佳响应动态，即，给出了一个最佳对策循环，证明了随机最佳对策动态以概率1收敛到稳定匹配，但收敛时间是指数的。此外，我们确定了特殊类的相关拟阵双边市场与现实生活中的应用，我们证明了随机最佳响应动态收敛在预期的多项式时间。
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 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 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 matroid two-sided markets with real-life applications for which we prove that the random best response dynamics converges in expected polynomial time.