Decentralized Bandits without Global Clock for Dynamic Matching Market

Two-sided matching markets are pervasive in numerous real-world applications, ranging from labor markets to online advertising. A rich line of research has studied the matching bandit problem, where participants learn their preferences through iterative interactions. However, existing works assume a static environment with fixed participants and require synchronized learning, in which all participants start simultaneously and have access to a global clock. In reality, matching markets are inherently dynamic: participants may enter and leave at arbitrary time steps without any global signal, creating coordination challenges. To study the dynamic setting, we first investigate one-sided learning under uncoordinated player arrivals, where only the players need to learn their preferences. We propose the Way-SE algorithm, which achieves a regret of $O(\frac{K^2 \log T}{\Delta_{\min}^2})$, where $K$ is the number of arms, $T$ is the time horizon, and $\Delta_{min}$ is the minimum utility gap. This is done through a distributed exploration mechanism that coordinates exploration implicitly via just local clocks. More importantly, we extend our work to fully decentralized dynamic two-sided learning, where both sides need to learn their preferences, and players arrive or depart arbitrarily. We introduce Way-SE-2S, the first algorithm to achieve sublinear regret $O\left(\frac{K T^{1-1/K}(\log T)^{2/K}}{\Delta_{\min}^2}\right)$ in this challenging environment, without requiring global signals, restrictive preference structures, or observability of the results of competing agents. Our work provides the first theoretical guarantee for stable matching in fully decentralized and uncoordinated bandit markets.

Many real-world systems need to match people or organizations with opportunities, such as job applicants with companies, students with schools, or users with recommendations. Participants of the systems often change from time to time: some join late, while others leave without informing anyone else. A match that was good before may become outdated after such changes. The problem becomes harder when no central coordinator tells everyone when to update their choices. This paper studies how participants can still find good matches in these changing environments. We first design a method for a simpler case where participants only arrive and do not leave, and where only one side needs to learn about their preferences on the other side. We then design another method for the hard case where participants come and go, and where both sides need to learn about their preferences. We prove that these methods keep mismatches limited over time, even when each participant only sees its own experience and doesn’t observe what happen to others. This is the first study on this difficult problem. It suggests that effective matching for dynamic participants can be achieved without a central coordinator, and without a shared time schedule among the participants.