Show simple item record

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

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
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorTlilane, Lydia
dc.date.accessioned2017-09-01T09:52:38Z
dc.date.available2017-09-01T09:52:38Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16665
dc.description.abstractfrNous é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.en
dc.language.isofren
dc.subjectMatroïdesen
dc.subjectutilités additivesen
dc.subjectalgorithme décentraliséen
dc.subjectguarantie dans le pire casen
dc.subject.ddc003en
dc.titleUn algorithme décentralisé pour construire une base d'un matroïde commune à un ensemble d'agentsen
dc.typeCommunication / Conférence
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00946405/en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.conftitle15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF 2014)en
dc.relation.confdate2014-02
dc.relation.confcityBordeauxen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceNationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-08-29T12:56:38Z
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