Pareto Optimal Matching with Multilayer Preferences: How Hard Can It Be?
摘要
We study Pareto optimal matching under multilayer preferences, where each agent has more than one preference list with each list representing a criterion based on which the agents of the opposite side are evaluated. We introduce four intuitive concepts of Pareto optimality with multilayer preferences and study parameterized complexity of them. We obtain W[1]-hardness, W[2]-hardness and para-NP-hardness results for most parameters except n, the number of men/women. Although n is FPT, we show that \(O^*(n!)\) time algorithm is essentially optimal for most of the concepts. In addition, almost no concept admits polynomial kernels with respect to n. These results even hold for combined parameters. We then consider cases where preferences satisfy certain desirable properties, that is, uniformity, single-layer and master list. We show that if preferences are uniform or single-layered, all of them are simply trivial and can be determined in polynomial time. However, the problem soon becomes NP-hard even when the maximum Hamming distance of preferences is a constant. For the case of master list, we find that even when there are only three layers and the preference lists on each side are all derived from the same single master list, the four problems remain NP-hard.