标题： 去中心化、无需通信和协调的结构匹配市场学习 显示英文标题

标题： 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.