Competing Bandits in Matching Markets via Super Stability
We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of `super-stability' from Irving (1994), we demonstrate the advantage of the Extended Gale-Shapley (GS) algorithm over the standard GS algorithm in achieving true stable matchings under incomplete information. By employing the Extended GS algorithm, our centralized algorithm attains a logarithmic pessimal stable regret dependent on an instance-dependent admissible gap parameter. This algorithm is further adapted to a decentralized setting with a constant regret increase. Finally, we establish a novel centralized instance-dependent lower bound for binary stable regret, elucidating the roles of the admissible gap and super-stable matching in characterizing the complexity of stable matching with bandit feedback.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Competing Bandits in Matching Markets
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 matc…
Multi-Armed BanditsDecentralized Competing Bandits in Non-Stationary Matching Markets
Understanding complex dynamics of two-sided online matching markets, where the demand-side agents compete to match with the supply-side (arms), has recently received substantial interest. To that end, in this paper, we i…
Competing Bandits in Decentralized Large Contextual Matching Markets
Sequential learning in a multi-agent resource constrained matching market has received significant interest in the past few years. We study decentralized learning in two-sided matching markets where the demand side (aka …
Core and stability notions in many-to-one matching markets with indifferences
In a many-to-one matchingmodel with responsive preferences in which indifferences are allowed, we study three notions of core, three notions of stability, and their relationships. We show that (i) the core contains the s…
Competing Bandits in Time Varying Matching Markets
We study the problem of online learning in two-sided non-stationary matching markets, where the objective is to converge to a stable match. In particular, we consider the setting where one side of the market, the arms, h…