The Dichotomous Affiliate Stable Matching Problem: Approval-Based Matching with Applicant-Employer Relations
The Dichotomous Affiliate Stable Matching Problem: Approval-Based Matching with Applicant-Employer Relations
复制标题
DOI：
10.24963/ijcai.2022/51
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Marina Knittel;Samuel Dooley;John P. Dickerson
中科院分区：
文献类型：
--
作者：
Marina Knittel;Samuel Dooley;John P. Dickerson
虽然稳定的婚姻问题及其变体模拟了大量的匹配市场，但它们未能捕捉到复杂的代理人关系，例如应聘者和雇主在面试市场中的从属关系。为了对这个问题进行建模，现有的关于匹配与外部性的文献允许代理商基于他们自己和他们附属公司的匹配提供完整的和总体的匹配排名。这种完全的排序限制是不现实的，而且模型可能有一个空的核心。为了解决这个问题，我们引入了二分联属稳定匹配(DASM)问题，其中代理人的偏好表明他们自己和他们的联属公司在市场上对另一个代理人的接受或拒绝。我们还假设代理人对整个匹配的偏好由他们(及其附属公司)匹配的一般加权估值函数确定。我们的结果有三个：(1)我们使用人类研究来证明现实世界的匹配排名遵循我们假设的估值函数；(2)我们通过提供一个高效的、易于实现的算法来证明总是存在稳定的解；以及(3)我们通过实验验证了我们的算法相对于基于线性规划的方法的效率。
While the stable marriage problem and its variants model a vast range of matching markets, they fail to capture complex agent relationships, such as the affiliation of applicants and employers in an interview marketplace. To model this problem, the existing literature on matching with externalities permits agents to provide complete and total rankings over matchings based off of both their own and their affiliates' matches. This complete ordering restriction is unrealistic, and further the model may have an empty core. To address this, we introduce the Dichotomous Affiliate Stable Matching (DASM) Problem, where agents' preferences indicate dichotomous acceptance or rejection of another agent in the marketplace, both for themselves and their affiliates. We also assume the agent's preferences over entire matchings are determined by a general weighted valuation function of their (and their affiliates') matches. Our results are threefold: (1) we use a human study to show that real-world matching rankings follow our assumed valuation function; (2) we prove that there always exists a stable solution by providing an efficient, easily-implementable algorithm that finds such a solution; and (3) we experimentally validate the efficiency of our algorithm versus a linear-programming-based approach.