Randomness and Fairness in Two-Sided Matching with Limited Interviews
Randomness and Fairness in Two-Sided Matching with Limited Interviews
复制标题
有限访谈双面匹配的随机性和公平性
DOI：
10.4230/lipics.itcs.2021.74
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
É. Tardos
中科院分区：
文献类型：
--
作者：
Hedyeh Beyhaghi;É. Tardos
我们研究的结果在一个匹配的市场，双方都有有限的能力考虑选项。例如，在国家住院医师匹配计划中，医生只能申请一小部分医院，医院也受到面试候选人所需时间的限制。我们的主要发现如下：（1）在市场上，工作只能考虑有限数量的候选人进行面试，它增加了最终匹配的大小，如果系统有一个候选人可以发送的申请数量的限制。(2)允许所有申请人申请完全相同数量的职位的公平制度最大限度地提高了预期的匹配规模。更具体地，从作为申请数量的整数k开始，匹配大小随着少数申请者被允许申请一个附加位置而减小（然后随着他们都被允许申请k +1而再次增加）。虽然这似乎是自然的期望，匹配的大小将是一个单调增加和凹函数的应用程序的数量，我们的研究结果表明，两者都不是真的。即使在一个所有职位和所有候选人都有可能是好的，并且不同雇主和候选人的判断是独立的市场中，这些结果也是成立的。我们的主要技术贡献是计算通过延迟接受算法找到的匹配的预期大小，作为偏好统一且独立的市场中面试和申请数量的函数。通过模拟，我们证实，这些发现延伸到市场的排名成为相关的采访后。2012年ACM学科分类计算理论→机械设计
We study the outcome in a matching market where both sides have limited ability to consider options. For example, in the national residency matching program, doctors are limited to apply to a small set of hospitals, and hospitals are limited by the time required to interview candidates. Our main findings are the following: (1) In markets where jobs can only consider a limited number of candidates for interview, it increases the size of the resulting matching if the system has a limit on the number of applications a candidate can send. (2) The fair system of all applicants being allowed to apply to the exact same number of positions maximizes the expected size of the matching. More particularly, starting from an integer k as the number of applications, the matching size decreases as a few applicants are allowed to apply to one additional position (and then increases again as they are all allowed to apply to k + 1). Although it seems natural to expect that the size of the matching would be a monotone increasing and concave function in the number of applications, our results show that neither is true. These results hold even in a market where a-priori all jobs and all candidates are equally likely to be good, and the judgments of different employers and candidates are independent. Our main technical contribution is computing the expected size of the matching found via the deferred acceptance algorithm as a function of the number of interviews and applications in a market where preferences are uniform and independent. Through simulations we confirm that these findings extend to markets where rankings become correlated after the interviews. 2012 ACM Subject Classification Theory of computation → Algorithmic mechanism design