Bandit Learning in Decentralized Matching Markets

Abstract

We study two-sided matching markets in which one side of the market (the players) does not have a priori knowledge about its preferences for the other side (the arms) and is required to learn its preferences from experience. Also, we assume the players have no direct means of communication. This model extends the standard stochastic multi-armed bandit framework to a decentralized multiple player setting with competition. We introduce a new algorithm for this setting that, over a time horizon $T$, attains $\mathcal{O}(\log (T))$ stable regret when preferences of the arms over players are shared, and $\mathcal{O}(\log (T{)}^2)$ regret when there are no assumptions on the preferences on either side. Moreover, in the setting where a single player may deviate, we show that the algorithm is incentive compatible whenever the arms' preferences are shared, but not necessarily so when preferences are fully general.

arXiv comment34 pages

References in corpus (6)

• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Delay and Cooperation in Nonstochastic Bandits
• An Experimental Study of Decentralized Matching
• Selfish Robustness and Equilibria in Multi-Player Bandits
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences
• Competing Bandits: The Perils of Exploration Under Competition

Cited by in corpus (8)

• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences
• Decentralized Learning in Online Queuing Systems
• Beyond ${\log }^2(T)$ Regret for Decentralized Bandits in Matching Markets
• Learning in Multi-Stage Decentralized Matching Markets
• A survey on multi-player bandits
• An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit
• PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators
• Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship