论文标题
解决具有矩阵约束的最大流行匹配问题
Solving the Maximum Popular Matching Problem with Matroid Constraints
论文作者
论文摘要
我们考虑的问题是，在具有双面偏好和矩阵约束的多对多匹配设置中找到最大的流行匹配。这个问题是由Kamiyama（2020）提出的，并在基本有序的特殊情况下解决了。利用新显示的矩阵交换属性，我们表明该问题对于任意矩阵可以解决。我们进一步调查了不同的受欢迎程度，代理商在词典偏好方面投票，并表明即使在$ b $匹配的案例中，存在和验证问题都变得困惑。
We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Kamiyama (2020) and solved in the special case where matroids are base orderable. Utilizing a newly shown matroid exchange property, we show that the problem is tractable for arbitrary matroids. We further investigate a different notion of popularity, where the agents vote with respect to lexicographic preferences, and show that both existence and verification problems become coNP-hard, even in the $b$-matching case.
