Competing Bandits in Matching Markets

Abstract

Stable matching, a classical model for two-sided markets, has long been studied with little consideration for how each side's preferences are learned. With the advent of massive online markets powered by data-driven matching platforms, it has become necessary to better understand the interplay between learning and market objectives. We propose a statistical learning model in which one side of the market does not have a priori knowledge about its preferences for the other side and is required to learn these from stochastic rewards. Our model extends the standard multi-armed bandits framework to multiple players, with the added feature that arms have preferences over players. We study both centralized and decentralized approaches to this problem and show surprising exploration-exploitation trade-offs compared to the single player multi-armed bandits setting.

arXiv comment15 pages, 3 figures. A version appears in the Proceedings of The 23nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2020

References in corpus (4)

• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Delay and Cooperation in Nonstochastic Bandits
• Competing Bandits: The Perils of Exploration Under Competition
• Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without

Cited by in corpus (6)

• Assortment planning for two-sided sequential matching markets
• Selfish Robustness and Equilibria in Multi-Player Bandits
• My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits
• The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
• Decentralized Matching in a Probabilistic Environment
• PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators