• 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 - No thumbnail

Un algorithme décentralisé pour construire une base d'un matroïde commune à un ensemble d'agents

Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2014), Un algorithme décentralisé pour construire une base d'un matroïde commune à un ensemble d'agents, 15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF 2014), 2014-02, Bordeaux, France

Type
Communication / Conférence
External document link
https://hal.archives-ouvertes.fr/hal-00946405/
Date
2014
Conference title
15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF 2014)
Conference date
2014-02
Conference city
Bordeaux
Conference country
France
Metadata
Show full item record
Author(s)
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]
Tlilane, Lydia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (FR)
Nous étudions un problème qui généralise l'allocation d'objets indivisibles à un groupe d'agents. Ce problème est défini sur un matroïde M=(X,F) où X est un ensemble d'éléments et F une famille d'ensembles indépendants. Les matroïdes modélisent plusieurs problèmes en optimisation combinatoire (forêts, affectation, ordonnancement, ...). Ils sont d'autant plus riches qu'ils utilisent des algorithmes polynomiaux (le glouton et les algorithmes d'intersection de deux matroïdes).Soient n agents tels que chaque agent i a une utilité u_i(x)>=0 pour chaque élément x du matroïde. Ces utilités sont additives et privées (les agents n'ont pas accès aux utilités de leurs pairs). L'objectif est de trouver une base (ensemble indépendant maximal pour l'inclusion) avec une garantie dans le pire des cas sur l'utilité des agents. Nous supposons que l'optimum pour chaque agent vaut 1. Ainsi, les n agents interagissent dans le but de construire une base B partitionnée en B_1,...,B_n où B_i est la contribution de l'agent i et de façon à garantir u_i(B_i)>=e_i pour tout i et pour un e_i dans ]0,1].Il existe un algorithme pour l'allocation d'objets indivisibles où l'utilité de chaque agent i pour sa part vaut au moins V_n(a_i) [1]. V_n est une fonction décroissante et a_i représente l'utilité maximale de l'agent i pour un objet. Cet algorithme est centralisé et nécessite en entrée les utilités des agents.Nous proposons un algorithme polynomial décentralisé qui prend en entrée un matroïde et n<=8 agents et qui retourne une base partitionnée en n parts. L'utilité de chaque agent pour sa part est au moins V_n(a_i) où a_i est l'utilité maximale de l'agent i pour un élément du matroïde. Cet algorithme est valable pour tous les problèmes qui ont une structure de matroïde. De plus, l'utilité de chaque agent reste méconnue des autres, tout en préservant la garantie donnée dans [1]. [1] E. Markakis and C.A. Psomas. On worst-case allocations in the presence of indivisible goods. WINE, 278-289, 2011.
Subjects / Keywords
Matroïdes; utilités additives; algorithme décentralisé; guarantie dans le pire cas

Related items

Showing items related by title and author.

  • Thumbnail
    Approximation du point idéal dans des matroïdes: bornes et algorithmes 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    A matroid approach to the worst case allocation of indivisible goods 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    Approximate Tradeoffs on Matroids 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2012) Communication / Conférence
  • Thumbnail
    Approximate tradeoffs on weighted labeled matroids 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié
  • Thumbnail
    A Protocol for Cutting Matroids Like Cakes 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
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