Abstract: The problem of two-sided matching markets has a wide range of real-world applications and has been extensively studied in the literature. A line of recent works has focused on the problem setting where the preferences of one-side market participants are unknown a priori and are learned by iteratively interacting with the other side of participants. All these works are based on explore-then-commit (ETC) and upper confidence bound (UCB) algorithms, two common strategies in multi-armed bandits (MAB). Thompson sampling (TS) is another popular approach, which attracts significant attention due to its easier implementation and better empirical performance. In many problems, even when UCB and ETC-type algorithms have already been analyzed, researchers continue to study TS for its benefits. However, the convergence analysis of TS is much more challenging and remains open in many problem settings. In this paper, we provide the first regret analysis for TS in the new setting of iterative matching markets. Extensive experiments demonstrate the practical advantages of the TS-type algorithm over the ETC and UCB-type baselines.
Introduction
Matching markets are a cornerstone of economic theory, governing how resources and participants are paired in systems ranging from college admissions to labor platforms like Upwork. Traditionally, these markets are analyzed using the Gale-Shapley framework, which assumes that all participants have a complete and known preference ranking of the other side.
In modern digital marketplaces, however, this assumption rarely holds. An employer may not know the true quality of a freelancer until they have collaborated, and a student may not know their fit for a university until they attend an interview. This necessitates a learning-based approach where participants must explore their options to estimate preferences while simultaneously attempting to secure the best possible match. This paper, authored by researchers from Shanghai Jiao Tong University and Carnegie Mellon University, introduces the first theoretical and empirical framework for applying Thompson Sampling (TS) to these decentralized, iterative matching markets.
The Challenge: Competition and Blocking
Learning in matching markets is typically modeled as a Multi-Armed Bandit (MAB) problem. In a standard MAB setting, a player pulls an arm and receives a reward. In a matching market, however, the environment is competitive. If two players (e.g., employers) attempt to match with the same arm (e.g., a high-quality freelancer), only one succeeds based on the arm's own preferences. The "losing" player is blocked; they receive no reward and, crucially, no information about the arm's value for that round.
This blocking mechanism breaks standard bandit algorithms. While previous research has adapted Upper Confidence Bound (UCB) and Explore-Then-Commit (ETC) strategies to handle this, Thompson Sampling—despite its reputation for superior empirical performance—has lacked a rigorous theoretical guarantee in this specific decentralized context. The randomness inherent in TS makes it difficult to bound the "cascading regret" that occurs when one player's sub-optimal choice blocks another player's optimal match.
Conflict-Avoiding Thompson Sampling (CA-TS)
To address these challenges, the authors propose Conflict-Avoiding Thompson Sampling (CA-TS). The algorithm is designed for a decentralized environment where players do not communicate or coordinate their choices. Instead, they learn purely from their own successes and rejections.
Key Algorithmic Components
- Posterior Sampling: Players maintain a probability distribution (such as Beta or Gaussian) representing their belief about each arm's mean reward. In each round, they sample from these distributions to determine their preferred arm.
- The Plausible Set: To mitigate the risk of repeated rejections, each player maintains a "plausible set" of arms. This set filters out arms that are highly likely to reject the player based on the outcomes of previous rounds.
- Random Delay Mechanism: To prevent players from becoming trapped in cycles of constant collisions, CA-TS employs a Bernoulli trial. A player either attempts to match with a new optimal arm from their plausible set or repeats their choice from the previous round, introducing a stabilizing delay.
Theoretical and Empirical Results
The primary contribution of this work is the first stable regret analysis for Thompson Sampling in matching markets. The authors prove a stable regret bound of:
$$\mathcal{O}\left(\frac{\log^2 T}{\Delta^2}\right)$$
Where $T$ is the time horizon and $\Delta$ represents the reward gap between arms. While the constant factors in this bound currently show an exponential dependence on the number of players ($N$), this represents a landmark theoretical step for Bayesian methods in matching markets.
Empirical Performance
The authors evaluated CA-TS against CA-UCB, P-ETC, and D-ETC across several synthetic market configurations, including global preference markets, random preference markets, and heterogeneous markets with varying utility models.
- Robustness: Unlike ETC algorithms, which require prior knowledge of the reward gap to set exploration budgets, CA-TS adapts to the gap naturally.
- Efficiency: CA-TS consistently achieved lower cumulative regret and reached a stable matching significantly faster than UCB-based methods. UCB algorithms often suffer from over-exploration of sub-optimal arms, whereas the posterior sampling in CA-TS more aggressively exploits high-value arms as confidence grows.
Conclusion and Future Work
CA-TS demonstrates that Thompson Sampling is not only practically superior for decentralized matching markets but also theoretically sound. However, challenges remain. The current theoretical bound's exponential dependence on the number of players suggests room for tightening the analysis. Furthermore, this work focuses on "player-pessimal" stable regret; achieving sub-linear regret for "player-optimal" matches in a strictly decentralized setting remains one of the most difficult open problems in the field. Future research may also explore how minimal, privacy-preserving communication between players could further reduce market instability and regret.
Summary updated