Fair solutions for some multiagent optimization problems
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2013), Fair solutions for some multiagent optimization problems, Autonomous Agents and Multi-Agent Systems, 26, 2, p. 184-201. 10.1007/s10458-011-9188-z
Type
Article accepté pour publication ou publiéDate
2013Nom de la revue
Autonomous Agents and Multi-Agent SystemsVolume
26Numéro
2Éditeur
Springer
Pages
184-201
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Escoffier, BrunoLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
We 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.Mots-clés
Multiagent optimization; Combinatorial optimization; FairnessPublications associées
Affichage des éléments liés par titre et auteur.
-
Bazgan, Cristina; Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2012) Communication / Conférence
-
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
-
Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010) Article accepté pour publication ou publié