Student-Project-Resource Allocation: Complexity of the Symmetric Case

摘要

In this paper, we consider a student-project-resource allocation problem, in which students and indivisible resources are allocated to every project. The allocated resources determine endoge-nously the student capacity of a project. Traditionally, this problem is divided in two: (I) resources are allocated to projects based on expected demands (resource allocation problem), and (II) students are matched with projects based on the capacity determined in the previous problem (many-to-one matching problem). Although both problems are well-understood, unless the expectations used in the first problem are correct, we obtain a suboptimal outcome. Thus, it is desirable to solve this problem as a whole, without dividing it. We start by introducing a compact representation that takes advantage of the symmetry of preferences. Then, we show that computing a nonwasteful matching is FP~(NP)-complete. Besides, a fair matching can be found in polynomial-time. Finally, deciding whether a stable (i.e. nonwasteful and fair) matching exists is NP~(NP)-complete.