论文标题
结构化匹配市场中的分散，沟通和无协调的学习
Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
论文作者
论文摘要
我们在双面匹配市场的背景下研究竞争环境中在线学习的问题。特别是，市场的一方，代理商必须通过重复互动来了解他们在另一端的偏好，同时与其他代理商竞争成功的比赛。我们提出了一类分散的，通信和无协调的算法，代理商可以使用这些算法在结构化匹配的市场中达到其稳定的匹配。与先前的工作相反，拟议的算法仅根据代理商自己的游戏历史做出决定，并且不需要对公司的偏好进行预知。我们的算法是通过从嘈杂的观察中分解学习偏好的统计问题来构建的，这是从竞争公司竞争的问题中构建的。我们表明，在对代理商和公司的基本偏好的现实结构假设下，提出的算法产生了一种遗憾，这种遗憾在时间范围内大多数对数增长。我们的结果表明，在匹配市场的情况下，竞争并不一定会严重影响分散，沟通和协调的无用在线学习算法的表现。
We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent's own history of play and requires no foreknowledge of the firms' preferences. Our algorithms are constructed by splitting up the statistical problem of learning one's preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. Our results show that, in the case of matching markets, competition need not drastically affect the performance of decentralized, communication and coordination free online learning algorithms.
