Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
复制标题
结构化匹配市场中的去中心化、无沟通和协调的学习
DOI：
10.48550/arxiv.2206.02344
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
S. Sastry
中科院分区：
文献类型：
--
作者：
C. Maheshwari;Eric V. Mazumdar;S. Sastry
我们在双边匹配市场的背景下研究了竞争环境下的在线学习问题。特别是，市场的一方，即代理商，必须在与其他代理商竞争成功匹配的同时，通过反复互动，了解他们对另一方，即公司的偏好。我们提出了一类分散的、无需通信和协调的算法，在结构化匹配市场中，代理可以使用这些算法来实现他们的稳定匹配。与以前的工作不同，所提出的算法完全基于代理人自己的游戏历史做出决策，而不需要预先知道公司的偏好。我们的算法是通过将从嘈杂的观察中学习个人偏好的统计问题与竞争公司的问题分开构建的。我们表明，在关于代理人和公司潜在偏好的现实结构假设下，所提出的算法招致后悔，并且在时间范围内至多以对数增长。我们的结果表明，在匹配市场的情况下，竞争不需要剧烈地影响去中心化、无通信和无协调的在线学习算法的性能。
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.
多代理多武装强盗中的社会学习
DOI：
10.1145/3393691.3394217
发表时间：
2019
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Sankararaman, Abishek;Ganesh, Ayalvadi;Shakkottai, Sanjay
通讯作者：
Shakkottai, Sanjay