Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLesca, Julien
hal.structure.identifierLaboratoire d'Informatique de Paris 6 [LIP6]
dc.contributor.authorMinoux, Michel
hal.structure.identifierLaboratoire d'Informatique de Paris 6 [LIP6]
dc.contributor.authorPerny, Patrice
HAL ID: 9264
dc.date.accessioned2019-04-11T10:21:03Z
dc.date.available2019-04-11T10:21:03Z
dc.date.issued2019
dc.identifier.issn0178-4617
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18625
dc.language.isoenen
dc.subjectAssignment problemen
dc.subjectFairnessen
dc.subjectOrdered Weighted Averageen
dc.subjectComplexityen
dc.subject.ddc005en
dc.titleThe Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Casesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameAlgorithmica
dc.relation.isversionofjnlvol81en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2019-01
dc.relation.isversionofjnlpages98–123en
dc.relation.isversionofdoi10.1007/s00453-018-0434-5en
dc.contributor.countryeditoruniversityotherFRANCE
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-26T13:20:15Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record