GROSS-HUMBERT Nathanaël

doctorant à Sorbonne Université
Équipe : SMA
https://sites.google.com/view/gross--humbertnathanael/accueil

Direction de recherche : Aurélie BEYNIER

Co-encadrement : BENABBOU Nawal, MAUDET Nicolas

Étude des notions de diversité et d'envie dans le cadre de problèmes d'affectation avec groupes d'agents

L'objectif de cette thèse est d'étudier les notions de diversité et d'équité dans le cadre de problèmes d'allocation de ressources où l'ensemble des agents est partitionné en un certain nombre de types. Ces problématiques ont de nombreuses applications, en premier lieu dans le problème qui a inspiré le modèle, l'immobilier de Singapour, mais également dans des problèmes plus divers tels que la répartition des élèves en écoles ou l'allocation des ressources médicales.
Les travaux effectués se divisent en deux grands axes, le premier étudie les mécanismes d'allocations dans un contexte où les agents souhaitent se regrouper par types, mais sont limités par des quotas de diversité, le deuxième étudie l'équité entre les types eux-mêmes. Dans le cadre du premier axe, nous considérons un modèle qui dispose, en plus d'une partition de l'ensemble des agents en un certain nombre de types, d'une partition de l'ensemble des ressources (ou objets) en un certain nombre de blocs, et de quotas de diversité entre ces types et ces blocs. Nous introduisons dans ce modèle une dynamique d'amélioration en autorisant les agents à effectuer des échanges de ressources bilatéraux. Cette dynamique introduit une notion de stabilité, où une allocation est stable si elle est invariante par cette dynamique. Nous étudions les propriétés de cette notion de stabilité, puis nous considérons deux mécanismes d'allocations. Le premier est le mécanisme de loterie, utilisé en situation réelle, qui consiste à ordonner les agents, puis les laisser sélectionner leur objet favori chacun leur tour dans l'ordre. Le second, basé sur notre dynamique, consiste à partir d'une allocation quelconque et à appliquer des échanges améliorants jusqu'à atteindre une allocation stable. Nous présentons ensuite plusieurs séries d'expériences effectuées avec ces mécanismes et discutons de leurs résultats.
Dans le cadre du deuxième axe, nous discutons de la notion d'équité, au travers de la notion d'envie. Nous posons 4 axiomes qui représentent des propriétés que l'on souhaite retrouver dans une notion d'envie, puis nous listons un certain nombre de définitions utilisées dans la littérature, et nous vérifions lesquelles vérifient quels axiomes. Cela fait, nous définissons nos propres notions d'envies, basées sur des comparaisons utilisant des sous-groupes, et nous les situons par rapport aux axiomes, puis nous discutons de leurs aspects computationnels. Nous explorons ensuite les différentes interprétations possibles du concept de monotonie. Nous introduisons une relaxation de nos notions d'envie, le degré d'envie, que nous montrons difficile à calculer. Nous présentons alors deux méthodes d'approximation. La première, plus efficace, repose sur une réduction à une variante du problème du sac à dos, la deuxième, théoriquement beaucoup plus longue, repose sur une succession d'échantillonnage par une chaine de Markov. Si les résultats théoriques indiquent que cette deuxième méthode a une complexité beaucoup trop importante pour être utilisable en pratique, une série d'expériences suggère qu'elle serait en réalité bien plus rapide.

Soutenance : 04/09/2024

Membres du jury :

Umberto GRANDI, Professeur, Université Toulouse Capitole [Rapporteur]
Ramón PINO PÉREZ, Professeur, Universidad de Los Andes [Rapporteur]
Jérôme LANG, Directeur de recherche, Université Paris Dauphine - PSL
Anaëlle WILCZYNSKI, Maîtresse de conférences, CentraleSupélec
Nawal BENABBOU, Maîtresse de conférences, Sorbonne Université
Nicolas MAUDET, Professeur, Sorbonne Université
Aurélie BEYNIER, Maîtresse de conférences, Sorbonne Université

Date de départ : 30/09/2024

Publications 2021-2024