Popular and clan-popular b-matchings

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 houses/agents (respectively) that can be matched to him/her/it. We want to find a matching M  , called popular, for which there is no other matching M′M′ such that more agents prefer M′M′ to M than M   to M′M′, subject to a suitable definition of “prefers”. In the above problem each agent uses exactly one vote to compare two matchings. In the other problem we consider in the paper each agent has a number of votes equal to their capacity. Given two matchings M   and M′M′, an agent compares their best house in matching M∖M′M∖M′ to their best house in matching M′∖MM′∖M and gives one vote accordingly, then their second best houses and so on. A matching M   for which there is no matching M′M′ such that M′M′ gets a bigger number of votes than M, when M   and M′M′ are compared in the way described above, is then called clan-popular. Popular matchings have been studied quite extensively, especially in the one-to-one setting. In the many-to-many setting we provide a characterisation of popular and clan-popular matchings, show NP-hardness results for very restricted cases of the above problems and for certain versions describe novel polynomial algorithms. The given characterisation is also valid for popular matchings in the one-to-one setting.