Stability and Pareto Optimality in Refugee Allocation Matchings

We focus on the refugee matching problem-a general "two-sided matching under preferences" model with multi-dimensional feasibility constraints. We propose a taxonomy of stability concepts for the problem; identify relations between them; and show that even for two natural weakenings of the standard stability concept, non-existence and NP-hardness results persist. We then identify several natural weaker stability concepts for which we present a polynomial-time and strategy-proof algorithm that returns a stable matching. We also examine the complexity of computing and testing Pareto optimal matchings.