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.

Lien vers l'article: www.lamsade.dauphine.fr/~tlilane/wine13.pdf