An Algorithm for Multi-Attribute Diverse Matching
An Algorithm for Multi-Attribute Diverse Matching
复制标题
DOI：
10.24963/ijcai.2020/1
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Saba Ahmadi-;Faez Ahmed;John P. Dickerson;M. Fuge;S. Khuller
中科院分区：
文献类型：
--
作者：
Saba Ahmadi-;Faez Ahmed;John P. Dickerson;M. Fuge;S. Khuller
二分b匹配是指市场一侧的代理与另一侧的一个或多个代理或物品相匹配，是一种经典的模型，用于医疗保健、广告、教育和一般资源分配等众多应用领域。传统上，这类模型的主要目标是在一定的约束条件下最大化成员匹配的线性函数(例如，线性社会福利最大化)。最近的工作研究了一个平衡整场比赛多样性和经济效率的新目标，其中目标是匹配上的单调子模函数。这个问题的基本形式在多项式时间内是可解的。在这项工作中，我们证明了沿着几个特征(例如，国籍、性别、技能)同时最大化多样性的问题是NP困难的。为了解决这个问题，我们开发了第一个组合算法，它在伪多项式时间内构造可证明最优的多样化b-匹配。我们还给出了同一问题的混合整数二次型公式，并证明了我们的方法保证了最优解，并且对于评审者分配应用程序所需的计算时间更少。源代码可在https://github.com/faezahmed/diverse_matching.上获得
Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e.g., country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application. The source code is made available at https://github.com/faezahmed/diverse_matching.