Abstract. We consider the problem of finding a popular matching in the Capacitated House Allocation problem (CHA). An instance of CHA involves a set of agents and a set of houses. Each agent has a preference list in which a subset of houses are ranked in strict order, and each house may be matched to a number of agents that must not exceed its capacity. A matching M is popular if there is no other matching M such that the number of agents who prefer their allocation in M to that in M exceeds the number of agents who prefer their allocation in M to that in M . Here, we give an O( √ Cn1 + m) algorithm to determine if an instance of CHA admits a popular matching, and if so, to find a largest such matching, where C is the total capacity of the houses, n1 is the number of agents and m is the total length of the agents' preference lists. For the case where preference lists may contain ties, we give an O(( √ C + n1)m) algorithm for the analogous problem.
Manlove and Sng REF investigated the capacitated house allocation problem, in which the houses have diverse capacities.
Popular matchings in the capacitated house allocation problem
In Proceedings of ESA 2006, the 14th Annual European Symposium on Algorithms, (LNCS 4168
Computer Science