Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
Two-sided matching markets describe a large class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. In many real-world applications (e.g. content matching or online labor markets), the knowledge about preferences may not be readily available and must be learned, i.e., one side of the market (aka agents) may not know their preferences over the other side (aka arms). Recent research on online settings has focused primarily on welfare optimization aspects (i.e. minimizing the overall regret) while paying little attention to the game-theoretic properties such as the stability of the final matching. In this paper, we exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions. We initiate the study of the sample complexity of finding a stable matching, and provide theoretical bounds on the number of samples needed to reach a stable matching with high probability. Finally, our empirical results demonstrate intriguing tradeoffs between stability and optimality of the proposed algorithms, further complementing our theoretical findings.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Stable Marriage Matching for Traffic-Aware Space-Air-Ground Integrated Networks: A Gale-Shapley Algorithmic Approach
In keeping with the rapid development of communication technology, a new communication structure is required in a next-generation communication system. In particular, research using High Altitude Platform (HAP) or Unmann…
Sophisticated Students in Boston Mechanism and Gale-Shapley Algorithm for School Choice Problem
We present our experimental results of simulating the school choice problem which deals with the assignment of students to schools based on each group's complete preference list for the other group using two algorithms: …
Distributed Learning in Markovian Restless Bandits over Interference Graphs for Stable Spectrum Sharing
We study distributed learning for spectrum access and sharing among multiple cognitive communication entities, such as cells, subnetworks, or cognitive radio users (collectively referred to as cells), in communication-co…
On the existence of stable contract systems
In 1962, Gale and Shapley \cite{GS} introduced the concept of stable marriages and proved their existence. Since then, the statement of the stability problem has been highly generalized. And a lot of proofs has emerged f…
Competing Bandits in Matching Markets via Super Stability
We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of `super-stability' from Irving (1994), we d…