Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties
Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties
复制标题
DOI：
10.4230/lipics.stacs.2022.31
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Hiromichi Goko;K. Makino;S. Miyazaki;Yu Yokoi
中科院分区：
文献类型：
--
作者：
Hiromichi Goko;K. Makino;S. Miyazaki;Yu Yokoi
由于农村地区医院存在严重的住院者短缺问题，我们研究了医院/住院者模型，该模型将医院与较低的指标相关联，目标是尽可能地满足他们。在偏好列表严格的情况下，由于众所周知的农村医院定理，在任何稳定匹配中，分配到每家医院的居民人数都是相同的；因此，没有算法干预的余地。然而，当将关系引入偏好列表时，这将不再适用，因为居民数量可能会因稳定匹配而变化。本文构造了一个寻找低配额下总满意度最大的稳定匹配的优化问题。我们首先研究了在四种自然情况下，总满意度随稳定匹配选择的变化情况，并提供了这些最大差距的确切值。随后，我们提出了一种策略证明逼近算法；在一种情况下，它最优地解决了问题，而在其他三种np困难的情况下，它产生了比朴素的平局打破方法更好的近似因子。最后，我们展示了上述三种NP-hard情景的不近似结果。
Motivated by the serious problem that hospitals in rural areas suffer from a shortage of residents, we study the Hospitals/Residents model in which hospitals are associated with lower quotas and the objective is to satisfy them as much as possible. When preference lists are strict, the number of residents assigned to each hospital is the same in any stable matching because of the well-known rural hospitals theorem; thus there is no room for algorithmic interventions. However, when ties are introduced to preference lists, this will no longer apply because the number of residents may vary over stable matchings. In this paper, we formulate an optimization problem to find a stable matching with the maximum total satisfaction ratio for lower quotas. We first investigate how the total satisfaction ratio varies over choices of stable matchings in four natural scenarios and provide the exact values of these maximum gaps. Subsequently, we propose a strategy-proof approximation algorithm for our problem; in one scenario it solves the problem optimally, and in the other three scenarios, which are NP-hard, it yields a better approximation factor than that of a naive tie-breaking method. Finally, we show inapproximability results for the above-mentioned three NP-hard scenarios.