k-Best Egalitarian Stable Marriages for Task Assignment

TY - GEN

T1 - k-Best Egalitarian Stable Marriages for Task Assignment

AU - Wu, Siyuan

AU - Hou U, Leong

AU - Karras, Panagiotis

N1 - Publisher Copyright: © 2023 VLDB Endowment.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

U2 - 10.14778/3611479.3611522

DO - 10.14778/3611479.3611522

M3 - Conference article

AN - SCOPUS:85171854316

SN - 2150-8097

VL - 16

SP - 3240

EP - 3252

JO - Proceedings of the VLDB Endowment

JF - Proceedings of the VLDB Endowment

IS - 11

T2 - 49th International Conference on Very Large Data Bases, VLDB 2023

Y2 - 28 August 2023 through 1 September 2023

ER -