Envy-Free Matchings with Lower Quotas
Envy-Free Matchings with Lower Quotas
复制标题
低配额、无嫉妒的匹配
DOI：
10.1007/s00453-018-0493-7
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Yokoi Yu
中科院分区：
文献类型：
--
作者：
Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda;Yokoi Yu
虽然医院/居民问题的每个实例都允许稳定匹配，但具有较低配额的问题（HR-LQ）具有不具有稳定匹配的实例。对于这样的例子，我们期望存在一个无嫉妒匹配，这是一个放松的稳定匹配保持一种公平性。在本文中，我们调查了存在的嫉妒免费匹配在几个设置，医院有较低的配额，并不是所有的医生-医院对是可以接受的。我们首先提供一个算法，决定是否一个给定的HR-LQ实例有一个无嫉妒匹配或没有。然后，我们考虑由于Huang的分类稳定匹配模型中的无嫉妒性（在：Procurat 1 n of 21st annual ACM-SIAM symposium on discrete algorithms（SODA 2010），SIAM，Philadelphia，pp 1235-1253，2010中），即，每个医院都有医生子集的上限和下限配额。我们表明，对于这个模型，决定存在的嫉妒自由匹配一般是NP-困难的，但在多项式时间内可解的，如果配额是paramodular。
While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor–hospital pairs are acceptable. We first provide an algorithm that decides whether a given HR-LQ instance has an envy-free matching or not. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (in: Procedings of 21st annual ACM-SIAM symposium on discrete algorithms (SODA2010), SIAM, Philadelphia, pp 1235–1253, 2010), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.
登录
查看更多内容
分类稳定匹配
DOI：
--
发表时间：
2009
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Chien
通讯作者：
Chien
具有设定约束的最小成本流
影响因子：
2.1
作者：
Refael Hassin
通讯作者：
Refael Hassin
较低配额的匹配：算法和复杂性
影响因子：
1.1
作者：
Arulselvan A
通讯作者：
Arulselvan A
DOI：
10.1007/978-3-642-23719-5_16
发表时间：
2011-09
期刊：
--
影响因子：
--
作者：
Koki Hamada;K. Iwama;S. Miyazaki
通讯作者：
Koki Hamada;K. Iwama;S. Miyazaki
影响因子：
6.1
作者：
T. Fleiner
通讯作者：
T. Fleiner