Popular matchings with variable item copies

AbstractWe consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M∗ is popular if there is no matching M such that the number of people who prefer M to M∗ exceeds the number who prefer M∗ to M. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: •Given a graph G=(A∪B,E) where A is the set of people and B is the set of items, and a list 〈c1,…,c|B|〉 denoting upper bounds on the number of copies of each item, does there exist 〈x1,…,x|B|〉 such that for each i, having xi copies of the i-th item, where 1≤xi≤ci, enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each ci is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k