The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases

摘要

We consider a one-to-one assignment problem consisting of matching n objects with n agents. Any matching leads to a utility vector whose n components measure the satisfaction of the various agents. We want to find an assignment maximizing a global utility defined as an ordered weighted average (OWA) of the n individual utilities. OWA weights are assumed to be non-increasing with ranks of satisfaction so as to include an idea of fairness in the definition of social utility. We first prove that the problem is NP-hard; then we propose a polynomial algorithm under some restrictions on the set of admissible weight vectors, proving that the problem belongs to XP.