Répartition budgétaire sous le prisme de l'équité et de l'efficacité.
26/11/2024 à 10h00
M. Pierre CARDI présente ses travaux en soutenance le 26/11/2024 à 10h00
À l'adresse suivante : niversité Paris Dauphine - PSL Place du Maréchal de Lattre de Tassigny 75016 PARIS- Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Répartition budgétaire sous le prisme de l'équité et de l'efficacité.
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. Laurent GOURVES
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Laurent GOURVES | Directeur de recherche | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| M. Julien LESCA | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Co-encadrant de thèse |
| M. Umberto GRANDI | Professeur des universités | Université de Toulouse | Rapporteur |
| M. Nicolas MAUDET | Professeur des universités | Université paris 6 | Examinateur |
| Mme Meltem OZTURK | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Examinatrice |
| Mme Fanny PASCUAL | Professeur | Université Paris 6 | Rapporteure |
Résumé
Nous étudions un problème de répartition dans lequel n agents partagent un budget commun. Chaque agent soumet des demandes indivisibles (qui peuvent, par exemple, représenter le coût d’un projet de recherche), et une autorité centrale doit décider lesquelles accepter. L’utilité d’un agent est définie par la somme des montants alloués à ses demandes acceptées. L’objectif est de garantir une répartition équitable entre les agents tout en maximisant l’utilisation du budget, ce qui soulève des tensions entre équité et efficacité, particulièrement en raison de l’indivisibilité des demandes. Dans un premier temps, nous nous intéressons à des garanties dans le pire des cas. Idéalement, on souhaiterait que chaque agent reçoive une fraction 1/n du budget. En pratique, cela est rarement possible puisque les demandes sont indivisibles : chaque demande sera soit rejetée, soit entièrement acceptée. Pour surmonter cette contrainte, nous proposons de borner dans le pire cas la plus grande proportion du budget allouée à l’agent le moins favorisé, en étudiant des classes d’instances définies par deux paramètres essentiels : le nombre d’agents et la valeur de la demande la plus importante rapportée au budget. Des algorithmes efficaces garantissant des solutions proches de ces bornes sont également introduits, offrant des garanties robustes sur la répartition budgétaire, même lorsque l’équité parfaite est inatteignable. Puis, nous explorons des notions spécifiques d'équité et d'efficacité. Les critères d'équité étudiés incluent la maximisation de l'utilité minimale (max-min), la proportionnalité, et une version adaptée de l’absence de jalousie, ainsi que leurs relaxations jusqu’à une ou toute demande près. Concernant l'efficacité, nous examinons la maximisation du bien-être social utilitariste et l’optimalité de Pareto. Une analyse approfondie des relations entre ces concepts est menée, accompagnée de propositions d’algorithmes polynomiaux pour construire des solutions respectant ces critères. Enfin, nous généralisons le problème à des contextes où les agents sont regroupés en districts. Ce cadre reflète des situations réelles où il est nécessaire de garantir une équité non seulement entre individus, mais aussi entre groupes, comme des régions, des genres ou des communautés. Une fonction objectif générique est introduite pour modéliser les priorités locales et globales, équilibrant l’équité intra- et inter-districts. Un algorithme d’approximation totalement polynomial est proposé pour optimiser cette fonction, offrant une flexibilité adaptée à divers contextes décisionnels. En combinant résultats théoriques, algorithmes constructifs et applications pratiques, cette thèse fournit des outils pour résoudre des problématiques complexes d'allocation de ressources, allant de la gestion de quotas carbone à l’allocation de ressources en cloud computing ou au financement de projets collaboratifs.