The Complexity of Student-Project-Resource Matching-Allocation Problems

Abstract

I settle the computational complexity of student-project-resource matching-allocation problems, in which students and resources are assigned to projects \citep{pc2017}. A project's capacity for students is endogenously determined by the resources allocated to it. I show that finding a nonwasteful matching is ${\text{FP}}^{\text{NP}}[\text{log}]$-hard, and deciding a stable matching is ${\text{NP}}^{\text{NP}}$-complete. To obtain these results, I introduce two new problems: (i) \textsc{ParetoPartition}, shown ${\text{FP}}^{\text{NP}}[\text{poly}]$-hard and also strongly ${\text{FP}}^{\text{NP}}[\text{log}]$-hard, and (ii) \textsc{$\forall \exists$-4-Partition}, shown strongly ${\text{NP}}^{\text{NP}}$-complete.

technical report