Converging to Stability in Two-Sided Bandits: The Case of Unknown Preferences on Both Sides of a Matching Market

The classic literature on two-sided matching [Gale and Shapley, 1962, Roth and Xing, 1997, Haeringer and Wooders, 2011, e.g.], encompassing applications including long-and short-term labor markets, dating and marriage, school choice, and more, has typically focused on situations where agents are aware of their own preferences. The problem of learning preferences while participating in a repeated matching market first started receiving attention in the AI literature in the work of Das and Kamenica [2005], and the general idea of two-sided matching under unknown preferences has since been studied in economics and operations research as well Lee and Schwarz [2009], Johari et al. [2022]. This area of research has received renewed attention in the last few years, along with novel theoretical insights into convergence properties of upper-confidence-bound style algorithms Liu et al. [2021], Kong et al. [2022], Zhang et al. [2022]. The two-sided matching problem involves agents on two sides of a market who have preferences for each other but cannot communicate explicitly. The goal is to create a matching process that ensures stability, where no pairs of agents would rather be matched with each other over their current match. Gale and Shapley [1962] famously demonstrated, constructively, the existence of such matchings. The Gale-Shapley algorithm is structured around one side of the market proposing and the other side choosing whether to accept proposals. This theory has been applied to various markets, like matching medical students to residencies Roth and Peranson [1999] and students to schools Abdulkadiroğlu et al. [2005], with the assumption that agents know their own preferences. There has also been considerable interest in the AI community on two-sided matching in the presence of various constraints, e.g.