Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility
This work addresses the challenge of designing online algorithms for matching markets that are both efficient and robust to strategic deviations, which is crucial for applications like school admissions or job markets, though it builds incrementally on prior work in one-to-one settings.
The paper tackles the problem of learning preferences in many-to-one matching markets with uncertainty, proposing algorithms that achieve near-optimal regret bounds while ensuring incentive compatibility. It introduces the AETDA algorithm for responsiveness settings with polynomial player-optimal guarantees and the ODA algorithm for broader substitutable preferences, establishing upper bounds for stable regret.
Two-sided matching markets have been widely studied in the literature due to their rich applications. Since participants are usually uncertain about their preferences, online algorithms have recently been adopted to learn them through iterative interactions. An existing work initiates the study of this problem in a many-to-one setting with responsiveness. However, their results are far from optimal and lack guarantees of incentive compatibility. We first extend an existing algorithm for the one-to-one setting to this more general setting and show it achieves a near-optimal bound for player-optimal regret. Nevertheless, due to the substantial requirement for collaboration, a single player's deviation could lead to a huge increase in its own cumulative rewards and a linear regret for others. In this paper, we aim to enhance the regret bound in many-to-one markets while ensuring incentive compatibility. We first propose the adaptively explore-then-deferred-acceptance (AETDA) algorithm for responsiveness setting and derive an upper bound for player-optimal stable regret while demonstrating its guarantee of incentive compatibility. To the best of our knowledge, it constitutes the first polynomial player-optimal guarantee in matching markets that offers such robust assurances without known $Δ$, where $Δ$ is some preference gap among players and arms. We also consider broader substitutable preferences, one of the most general conditions to ensure the existence of a stable matching and cover responsiveness. We devise an online DA (ODA) algorithm and establish an upper bound for the player-pessimal stable regret for this setting.