A Tie-breaking based Local Search Algorithm for Stable Matching Problems
The stable marriage problem with incomplete lists and ties (SMTI) and the hospitals/residents problem with ties (HRT) are important in matching theory with broad practical applications. In this paper, we introduce a tie-breaking based local search algorithm (TBLS) designed to achieve a weakly stable matching of maximum size for both the SMTI and HRT problems. TBLS begins by arbitrarily resolving all ties and iteratively refines the tie-breaking strategy by adjusting the relative order within ties based on preference ranks and the current stable matching. Additionally, we introduce TBLS-E, an equity-focused variant of TBLS, specifically designed for the SMTI problem. This variant maintains the objective of maximizing matching size, while enhancing equity through two simple modifications. In comparison with ten other approximation and local search algorithms, TBLS achieves the highest matching size, while TBLS-E exhibits the lowest sex equality cost. Significantly, TBLS-E preserves a matching size comparable to that of TBLS. Both our algorithms demonstrate faster computational speed than other local search algorithms in solving large-sized instances.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Beyond $\log^2(T)$ Regret for Decentralized Bandits in Matching Markets
We design decentralized algorithms for regret minimization in the two-sided matching market with one-sided bandit feedback that significantly improves upon the prior works (Liu et al. 2020a, 2020b, Sankararaman et al. 20…
Finding Robust Solutions to Stable Marriage
We study the notion of robustness in stable matching problems. We first define robustness by introducing (a,b)-supermatches. An $(a,b)$-supermatch is a stable matching in which if $a$ pairs break up it is possible to fin…
Equitable Stable Matchings in Quadratic Time
Can a stable matching that achieves high equity among the two sides of a market be reached in quadratic time? The Deferred Acceptance (DA) algorithm finds a stable matching that is biased in favor of one side; optimizing…
Core and stability notions in many-to-one matching markets with indifferences
In a many-to-one matchingmodel with responsive preferences in which indifferences are allowed, we study three notions of core, three notions of stability, and their relationships. We show that (i) the core contains the s…
Benefits of marriage as a search strategy
We propose and investigate a model for mate searching and marriage in large societies based on a stochastic matching process and simple decision rules. Agents have preferences among themselves given by some probability d…