The Fair OWA One-to-one Assignment Problem: NP-hardness and Polynomial Time Special Cases
| Autor: | Michel Minoux, Julien Lesca, Patrice Perny |
|---|---|
| Přispěvatelé: | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), DECISION, LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
General Computer Science Matching (graph theory) Applied Mathematics ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY 0102 computer and information sciences 02 engineering and technology 01 natural sciences Polynomial algorithm Measure (mathematics) Computer Science Applications Combinatorics Set (abstract data type) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering One-to-one 020201 artificial intelligence & image processing [INFO]Computer Science [cs] Assignment problem Time complexity Social utility ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Algorithmica Algorithmica, Springer Verlag, In press, ⟨10.1007/s00453-018-0434-5⟩ |
| ISSN: | 0178-4617 1432-0541 |
| DOI: | 10.1007/s00453-018-0434-5⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink