Pareto optimal matchings of students to courses in the presence of prerequisites

Katarina Cechlarova, Bettina Klaus () and David F.Manlove

Cahiers de Recherches Economiques du Département d'économie from Université de Lausanne, Faculté des HEC, Département d’économie

Abstract: We consider the problem of allocating applicants to courses, where each applicant has a subset of acceptable courses that she ranks in strict order of preference. Each applicant and course has a capacity, indicating the maximum number of courses and applicants they can be assigned to, respectively. We thus essentially have a many-tomany bipartite matching problem with one-sided preferences, which has applications to the assignment of students to optional courses at a university. We consider additive preferences and lexicographic preferences as two means of extending preferences over individual courses to preferences over bundles of courses. We additionally focus on the case that courses have prerequisite constraints: we will mainly treat these constraints as compulsory, but we also allow alternative prerequisites. We further study the case where courses may be corequisites. For these extensions to the basic problem, we present the following algorithmic results, which are mainly concerned with the computation of Pareto optimal matchings (POMs). Firstly, we consider compulsory prerequisites. For additive preferences, we show that the problem of finding a POM is NP-hard. On the other hand, in the case of lexicographic preferences we give a polynomial-time algorithm for finding a POM, based on the well-known sequential mechanism. However we show that the problem of deciding whether a given matching is Pareto optimal is co-NP-complete. We further prove that finding a maximum cardinality (Pareto optimal) matching is NP-hard. Under alternative prerequisites, we show that finding a POM is NP-hardfor either additive or lexicographic preferences. Finally we consider corequisites. We prove that, as in the case of compulsory prerequisites, finding a POM is NP-hard for additive preferences, though solvable in polynomial time for lexicographic preferences. In the latter case, the problem of finding a maximum cardinality POM is NP-hard and very difficult to approximate.

Keywords: many-to-many matching problem; course allocation; additive / lexicographic preferences; polynomial-time algorithm; NP-hardness (search for similar items in EconPapers)
JEL-codes: C63 C78 (search for similar items in EconPapers)
Pages: 25 pp.
Date: 2018-04
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.unil.ch/de/files/live/sites/de/files/working-papers/16.04.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:lau:crdeep:16.04

Access Statistics for this paper

More papers in Cahiers de Recherches Economiques du Département d'économie from Université de Lausanne, Faculté des HEC, Département d’économie Université de Lausanne, Faculté des HEC, Département d’économie, Internef, CH-1015 Lausanne. Contact information at EDIRC.
Bibliographic data for series maintained by Christina Seld ().