Abstract
In a two-sided market with each agent ranking individuals on the other side according to their preferences, such as location or incentive, the stable marriage problem calls to find a perfect matching among the two sides such that no pair of agents prefers each other to their assigned matches. Recent studies show that the number of solutions can be large in practice. Yet the classic solution by the Gale-Shapley (GS) algorithm is optimal for agents on the one side and pessimal for those on the other side. Some algorithms find a stable marriage that optimizes a measure of the cumulative satisfaction of all agents, such as egalitarian cost. However, in many real-world circumstances, a decision-maker needs to examine a set of solutions that are stable and attentive to both sides and choose among them based on expert knowledge. With such a disposition, it is necessary to identify a set of high-quality stable marriages and provide transparent explanations for any reassigned matches to the decision-maker. In this paper, we provide efficient algorithms that find the k-best stable marriages by egalitarian cost. Our exhaustive experimental study using real-world data and realistic preferences demonstrates the efficacy and efficiency of our solution.
| Original language | English |
|---|---|
| Journal | Proceedings of the VLDB Endowment |
| Volume | 16 |
| Issue | 11 |
| Pages (from-to) | 3240-3252 |
| Number of pages | 13 |
| ISSN | 2150-8097 |
| DOIs | |
| Publication status | Published - 2023 |
| Event | 49th International Conference on Very Large Data Bases, VLDB 2023 - Vancouver, Canada Duration: 28 Aug 2023 → 1 Sept 2023 |
Conference
| Conference | 49th International Conference on Very Large Data Bases, VLDB 2023 |
|---|---|
| Country/Territory | Canada |
| City | Vancouver |
| Period | 28/08/2023 → 01/09/2023 |