Abstract
Two-sided matching markets are ubiquitous in real-world applications, from labor platforms to school admissions. Recent research has explored settings where one side's preferences are unknown and must be learned through iterative interactions. While Explore-Then-Commit (ETC) and Upper Confidence Bound (UCB) strategies have been adapted for these markets, Thompson Sampling (TS) has remained largely unstudied due to the complexities of its theoretical analysis in high-conflict environments. This paper introduces Conflict-Avoiding Thompson Sampling (CA-TS), providing the first regret analysis for a TS-based algorithm in decentralized matching markets. Our results show that CA-TS achieves a stable regret bound of $O(\log^2 T / \Delta^2)$ and significantly outperforms existing baselines in empirical tests.
The Challenge of Competitive Learning
In a standard Multi-Armed Bandit (MAB) problem, an agent learns the value of different options (arms) by trying them. In a matching market, multiple players compete for the same set of arms. If two players select the same arm, the arm accepts only its most preferred player. The rejected player receives zero reward and, crucially, no information about the arm's quality.
This "blocking" mechanism creates a significant hurdle for learning. Without coordination, players can enter cycles of mutual interference, preventing them from converging to a stable matching—a state where no player and arm would both prefer to be matched with each other over their current partners. While UCB-based methods provide theoretical guarantees, Thompson Sampling is often preferred in practice for its superior empirical performance and ease of implementation. However, proving its convergence in this competitive setting is challenging because a player's failure to learn can be caused by either poor sampling or external competition.
Conflict-Avoiding Thompson Sampling (CA-TS)
To address these challenges, we propose the Conflict-Avoiding Thompson Sampling (CA-TS) algorithm. CA-TS is a decentralized approach that allows players to learn their preferences while minimizing collisions. The algorithm relies on three key mechanisms:
- Bayesian Posterior Updates: Each player maintains a Beta distribution for each arm. A player only updates their beliefs when they are successfully matched with an arm and receive a reward signal.
- The Plausible Set: Players use market feedback to prune their search space. By observing which players were matched to which arms in previous rounds, a player can identify arms that are "plausible" to accept them. Specifically, they avoid arms that recently accepted a player whom the arm prefers more than themselves.
- Random Delay Mechanism: To break "oscillating" conflicts where players repeatedly clash over the same arms, CA-TS introduces a Bernoulli-distributed delay. With a certain probability, a player will repeat their previous choice instead of sampling a new one, effectively "staggering" their exploration.
Theoretical Results
The primary theoretical contribution of this work is the first regret analysis for Thompson Sampling in matching markets. We prove that CA-TS achieves a cumulative stable regret of $O(\frac{\log^2 T}{\Delta^2})$, where $T$ is the number of rounds and $\Delta$ is the reward gap between arms. This bound matches the best-known results for UCB-based algorithms in this setting, establishing TS as a theoretically sound alternative for decentralized matching.
Empirical Performance
We evaluated CA-TS against several baselines, including CA-UCB, Explore-Then-Commit (ETC) variants, and UCB-D4, using synthetic simulations with varying preference structures and reward gaps.
As shown in the experimental results, CA-TS consistently achieves lower cumulative regret and reaches a stable matching faster than competing methods. In particular, CA-TS demonstrates high robustness in "hard" learning scenarios where the reward gap between arms is small. While ETC-based methods often fail to converge if their fixed exploration phase is too short, CA-TS adaptively manages exploration through its Bayesian framework. Furthermore, the "Cumulative Market Unstability" metric confirms that CA-TS leads the market to a stable state more efficiently, minimizing the time spent in sub-optimal configurations.
Conclusion and Future Directions
CA-TS provides a powerful, decentralized solution for learning in matching markets, bridging the gap between the practical success of Thompson Sampling and the rigorous requirements of market stability. While our current analysis assumes that arm preferences for players are known, future work could extend this framework to fully two-sided uncertainty. Additionally, investigating the scaling behavior of these algorithms in much larger markets remains an important area for further research.
Summary updated