Description
Date depot: 1 janvier 1900
Titre: Optimisation équitable multi-agents sur des domaines combinatoire
Directeur de thèse:
Patrice PERNY (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
L’optimisation combinatoire multi-agents est un domaine en plein essor qui se situe au carrefour de la théorie de la décision et l’optimisation combinatoire. Il s’agit de résoudre des problèmes d’optimisation dans lesquels plusieurs agents ont des points de vues différents, potentiellement conflictuels, sur l’utilité des solutions réalisables. Dès lors, on se trouve face à une double difficulté :
- la prise en compte de préférences complexes ; on doit d’une part manipuler des modèles de décision multicritères capables de rendre compte des préférences de chaque agent dans la recherche d’une solution optimale, et d’autre part modéliser et de contrôler l’équité globale des solutions en utilisant des procédures d’agrégation non-linéaires (e.g. OWA, intégrales de Choquet, fonction d’utilités) capables d’évaluer dans quelle mesure une solution répartit équitablement la satisfaction sur l’ensemble des agents.
- la nature combinatoire de l’espace de recherche. Outre la difficulté habituelle de devoir explorer un ensemble de solutions de grande taille défini en compréhension, la représentation implicite de préférences sur des domaines combinatoires nécessite de manipuler des langages de représentation compacte des préférences. De plus, la recherche des solutions optimales équitables sur un domaine combinatoire nécessite des algorithmes spécifiques du fait du caractère non-linéaire des critères de décision utilisés.
Face à ces deux difficultés, on dispose aujourd’hui de très peu d’outils opérationnels pour déterminer, dans un problème d’optimisation combinatoire, des solutions capables de satisfaire le plus équitablement possible les agents impliqués. L’objet de cette thèse est alors de s’intéresser à des problèmes d’optimisation combinatoire multi-agents avec le double objectif de formuler de nouveaux problèmes mieux aptes à rendre compte des besoins du domaine (en particulier pour les problèmes d’affectation multi-agents et de planification multi-agents qui connaissent de très nombreuses applications) et des algorithmes de résolution efficaces pour ces problèmes. Au-delà de ces quelques exemples, les applications potentielles concernent tous les problèmes d’optimisation multi-agents dans les graphes, mais aussi les problèmes de mariages stables et d’affectation équitable, les enchères combinatoires et le partage équitable de ressources.
Doctorant.e: Lesca Julien