Thumbnail

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

Lesca, Julien; Minoux, Michel; Perny, Patrice (2019), The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases, Algorithmica, 81, 1, p. 98–123. 10.1007/s00453-018-0434-5

View/Open
Type
Article accepté pour publication ou publié
Date
2019
Journal name
Algorithmica
Volume
81
Number
1
Publisher
Springer
Pages
98–123
Publication identifier
Metadata
Show full item record
Author(s)
Lesca, Julien
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Minoux, Michel
Laboratoire d'Informatique de Paris 6 [LIP6]
Perny, Patrice
Laboratoire d'Informatique de Paris 6 [LIP6]
Abstract (EN)
We consider a one-to-one assignment problem consisting of matching nobjects with n agents. Any matching leads to a utility vector whose n componentsmeasure the satisfaction of the various agents. We want to find an assignmentmaximizing a global utility defined as an ordered weighted average (OWA) of then individual utilities. OWA weights are assumed to be non-increasing with ranks ofsatisfaction so as to include an idea of fairness in the definition of social utility. Wefirst prove that the problem is NP-hard; then we propose a polynomial algorithmunder some restrictions on the set of admissible weight vectors, proving that theproblem belongs to XP.
Subjects / Keywords
Assignment problem; Fairness; Ordered Weighted Average; Complexity