论文标题
新型公平稳定匹配类型的算法
Algorithms for new types of fair stable matchings
论文作者
论文摘要
我们研究了在稳定的婚姻问题中找到“公平”稳定匹配的问题，但列表不完整（SMI）。对于$ i $ $ $的SMI，可能会有许多稳定的比赛，为男女组提供了明显不同的结果。我们在SMI中介绍了两个新的公平概念。首先，在所有稳定的比赛中，遗憾的稳定匹配匹配可以最大程度地减少一个最糟糕的男人和最糟糕的女人的排名。其次，最小值的总和稳定匹配匹配可以最大程度地减少所有稳定的比赛中最坏的男人和最坏的女人的排名。我们提出了两种新的有效算法，以找到这些类型的稳定匹配。首先，遗憾的等级迭代算法在$ O（d_0 nm）$时间中发现了遗憾的稳定匹配时间，其中$ d_0 $是最坏的男人与最糟糕的男人中最糟糕的女人之间的排名绝对差异，男性稳定的匹配，$ n $是男性或$ m $ $ $ $ $ $ $ $ $ $ $ $ M $的数量。其次，最小值总和算法在$ o（d_s m）$ time中找到了最小的regret和稳定的匹配，其中$ d_s $是每个女性最佳和男人最佳的人和男人最佳稳定的稳定匹配中最糟糕的男人之间的差异。进行了比较几种类型的公平最佳稳定匹配的实验，并表明遗憾的程度迭代算法会产生与其他公平目标相对于其他公平目标竞争的匹配。另一方面，现有类型的“公平”稳定匹配并不能与遗憾与稳定的匹配近似。
We study the problem of finding "fair" stable matchings in the Stable Marriage problem with Incomplete lists (SMI). For an instance $I$ of SMI there may be many stable matchings, providing significantly different outcomes for the sets of men and women. We introduce two new notions of fairness in SMI. Firstly, a regret-equal stable matching minimises the difference in ranks of a worst-off man and a worst-off woman, among all stable matchings. Secondly, a min-regret sum stable matching minimises the sum of ranks of a worst-off man and a worst-off woman, among all stable matchings. We present two new efficient algorithms to find stable matchings of these types. Firstly, the Regret-Equal Degree Iteration Algorithm finds a regret-equal stable matching in $O(d_0 nm)$ time, where $d_0$ is the absolute difference in ranks between a worst-off man and a worst-off woman in the man-optimal stable matching, $n$ is the number of men or women, and $m$ is the total length of all preference lists. Secondly, the Min-Regret Sum Algorithm finds a min-regret sum stable matching in $O(d_s m)$ time, where $d_s$ is the difference in the ranks between a worst-off man in each of the woman-optimal and man-optimal stable matchings. Experiments to compare several types of fair optimal stable matchings were conducted and show that the Regret-Equal Degree Iteration Algorithm produces matchings that are competitive with respect to other fairness objectives. On the other hand, existing types of "fair" stable matchings did not provide as close an approximation to regret-equal stable matchings.
