Name
Title | ||
|---|---|---|
The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00453-018-0434-5 | Algorithmica |
Keywords | Field | DocType |
Assignment problem,Fairness,Ordered weighted average,Complexity | Discrete mathematics,Combinatorics,One-to-one,Assignment problem,Polynomial algorithm,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
81 | 1 | 1432-0541 |
Citations | PageRank | References |
1 | 0.36 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien Lesca | 1 | 46 | 8.51 |
| Michel Minoux | 2 | 741 | 100.18 |
| Patrice Perny | 3 | 514 | 42.23 |