Abstract
In this paper, we propose a new algorithm for addressing the problem ofmatching markets with complementary preferences, where agents' preferences areunknown a priori and must be learned from data. The presence of complementarypreferences can lead to instability in the matching process, making thisproblem challenging to solve. To overcome this challenge, we formulate theproblem as a bandit learning framework and propose the Multi-agent Multi-typeThompson Sampling (MMTS) algorithm. The algorithm combines the strengths ofThompson Sampling for exploration with a double matching technique to achieve astable matching outcome. Our theoretical analysis demonstrates theeffectiveness of MMTS as it is able to achieve stability at every matchingstep, satisfies the incentive-compatibility property, and has a sublinearBayesian regret over time. Our approach provides a useful method for addressingcomplementary preferences in real-world scenarios.