Pareto optimality in many-to-many matching problems

Cechlarova, K. and Eirinakis, P. and Fleiner, Tamás and Magos, D. and Mourtos, I. (2014) Pareto optimality in many-to-many matching problems. Discrete Optimization, 14. pp. 160-169. ISSN 1572-5286

Preview

Text ParetoOptimality.pdf Download (897kB) | Preview

Abstract

Consider a many-to-many matching market that involves two finite disjoint sets, a set A of applicants and a set C of courses. Each applicant has preferences on the different sets of courses she can attend, while each course has a quota of applicants that it can admit. In this paper, we examine Pareto optimal matchings (briefly POM) in the context of such markets, that can also incorporate additional constraints, e.g., each course bearing some cost and each applicant having a limited budget available. We provide necessary and sufficient conditions for a many-to-many matching to be Pareto optimal and show that checking whether a given matching is Pareto optimal can be accomplished in 0(1 A 12 I C 12) time. Moreover, we provide a generalized version of serial dictatorship, which can be used to obtain any many-to-many POM. We also study some structural questions related to POM. We show that, unlike in the one-to-one case, finding a maximum cardinality POM is NP-hard for many-to-many markets. (C) 2014 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item