2021/10/21 by Kavitha, Telikepalli, Király, Tamás, Matuschke, Jannik +2 · 2 citations
#Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2110.10984
We consider a matching problem in a bipartite graph G=(A∪ B,E) where nodes in A are agents having preferences in partial order over their neighbors, while nodes in B are objects without preferences. We propose a polynomial-time combinatorial algorithm based on LP duality that finds a maximum matching or assignment in G that is popular among all maximum matchings, if there exists one. Our algorithm can also be used to achieve a trade-off between popularity and cardinality by imposing a penalty on unmatched nodes in A. We also provide an O^*(|E|k) algorithm that finds an assignment whose unpopularity margin is at most k; this algorithm is essentially optimal, since the problem is NP-complete and Wl[1]-hard with parameter k. We also prove that finding a popular assignment of minimum cost when each edge has an associated binary cost is NP-hard, even if agents have strict preferences. By contrast, we propose a polynomial-time algorithm for the variant of the popular assignment problem with forced/forbidden edges. Finally, we present an application in the context of housing markets.