2010/12/29 by Paluch, Katarzyna
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1101.0021
Suppose that each member of a set of agents has a preference list of a subset of houses, possibly involving ties and each agent and house has their capacity denoting the maximum number of correspondingly agents/houses that can be matched to him/her/it. We want to find a matching M, for which there is no other matching M' such that more agents prefer M' to M than M to M'. (What it means that an agent prefers one matching to the other is explained in the paper.) Popular matchings have been studied quite extensively, especially in the one-to-one setting. We provide a characterization of popular b-matchings for two defintions of popularity, show some NP-hardness results and for certain versions describe polynomial algorithms.