• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2013
Journal name
Autonomous Agents and Multi-Agent Systems
Volume
26
Number
2
Publisher
Springer
Pages
184-201
Publication identifier
10.1007/s10458-011-9188-z
Metadata
Show full item record
Author(s)
Escoffier, Bruno
Laboratoire 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 cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (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.
Subjects / Keywords
Multiagent optimization; Combinatorial optimization; Fairness

Related items

Showing items related by title and author.

  • Thumbnail
    Solutions équitables approchées pour divers problèmes d’optimisation combinatoire 
    Bazgan, Cristina; Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2012) Communication / Conférence
  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation 
    Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo