UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 9317

Popular Matchings in the Weighted Capacitated House Allocation Problem
Sng,C.T.S. Manlove,D.F.

Publication Type: Journal
Appeared in: Journal of Discrete Algorithms, volume 8
Page Numbers : 102-116
Publisher: Elsevier Science
Year: 2010
ISBN/ISSN:

URL: This publication is available at this URL.

Abstract:

We consider the problem of finding a popular matching in the Weighted Capacitated House Allocation problem (WCHA). An instance of WCHA involves a set of agents and a set of houses. Each agent has a positive weight indicating his priority, and a preference list in which a subset of houses are ranked in strict order. Each house has a capacity that indicates the maximum number of agents who could be matched to it. A matching M of agents to houses is popular if there is no other matching M' such that the total weight of the agents who prefer their allocation in M' to that in M exceeds the total weight of the agents who prefer their allocation in M to that in M'. Here, we give an O(\sqrt{C}n1+m) algorithm to determine if an instance of WCHA 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.

Keywords: Popular matching problem; Priorities; Strict preference lists; Maximum popular matching; Polynomial-time algorithm


PDF Bibtex entry Endnote XML