Show simple item record

Fair solutions for some multiagent optimization problems

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553		*
dc.date.accessioned2012-01-23T14:58:03Z
dc.date.available2012-01-23T14:58:03Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/7927
dc.language.isoenen
dc.subjectMultiagent optimizationen
dc.subjectCombinatorial optimizationen
dc.subjectFairnessen
dc.subject.ddc003en
dc.titleFair solutions for some multiagent optimization problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider optimization problems in a multiagent setting where a solution is evaluated with a vector. Each coordinate of this vector represents an agent’s utility for the solution. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for all agents. Then, a natural aim is to find solutions that maximize the satisfaction of the least satisfied agent, where the satisfaction of an agent is defined as his relative utility, i.e., the ratio between his utility for the given solution and his maximum possible utility. This criterion captures a classical notion of fairness since it focuses on the agent with lowest relative utility. We study worst-case bounds on this ratio: for which ratio a feasible solution is guaranteed to exist, i.e., to what extend can we find a solution that satisfies all agents? How can we build these solutions in polynomial time? For several optimization problems, we give polynomial-time deterministic algorithms which (almost always) achieve the best possible ratio.en
dc.relation.isversionofjnlnameAutonomous Agents and Multi-Agent Systems
dc.relation.isversionofjnlvol26
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages184-201
dc.relation.isversionofdoi10.1007/s10458-011-9188-zen
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01508747*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record