Strategyproof matching with regional minimum and maximum quotas
Strategyproof matching with regional minimum and maximum quotas
复制标题
具有区域最小和最大配额的策略证明匹配
DOI：
10.1016/j.artint.2016.02.002
复制
发表时间：
2016
影响因子：
14.4
通讯作者：
Makoto Yokoo
中科院分区：
文献类型：
--
作者：
Masahiro Goto;Atsushi Iwasaki;Yujiro Kawasaki;Ryoji Kurata;Yosuke Yasuda;Makoto Yokoo
本文考虑了个人/区域最小/最大配额的匹配问题。虽然这种配额在许多现实世界中是相关的，但缺乏考虑到这种配额的防战略机制。我们首先表明，没有任何限制的区域结构，检查存在一个可行的匹配，满足所有配额是NP完全的。然后，假设区域具有分层结构（即，一棵树），我们表明，检查一个可行的匹配的存在，可以在时间上线性的区域的数量。在延迟接受机制的基础上，提出了两种防策略匹配机制，分别称为基于优先级列表的区域最小最大延迟接受机制（PLDA-RQ）和基于区域最小最大延迟接受机制的循环选择延迟接受机制（RSDA-RQ）。当实行区域配额时，稳定的匹配可能不再存在，因为构成稳定性的公平和不浪费是不相容的。我们证明了这两种机制都是公平的。因此，它们不可避免地是浪费的。我们表明，这两种机制满足不同版本的nonwastefulness分别，每一个都比原来的nonwastefulness弱。此外，我们比较我们的机制与人工上限机制，通过模拟实验，这表明他们有一个明显的优势，在非浪费和学生福利。
This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare.
登录
查看更多内容
分类稳定匹配
DOI：
--
发表时间：
2009
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Chien
通讯作者：
Chien
与美国军事学院的（选择的部门）合同相匹配
影响因子：
6.1
作者：
Tayfun Sönmez;T. Switzer
通讯作者：
T. Switzer
陆军职业专业申办：完善后备军官训练队分支机制
影响因子：
8.2
作者：
Tayfun Sönmez
通讯作者：
Tayfun Sönmez
与法定人数匹配
影响因子：
2
作者：
Daniel Monte;Norovsambuu Tumennasan
通讯作者：
Norovsambuu Tumennasan
影响因子：
1.7
作者：
Hafalir, Isa E.;Yenmez, M. Bumin;Yildirim, Muhammed A.
通讯作者：
Yildirim, Muhammed A.