Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique

Thèse soutenue le 16 novembre 2007 à la salle des thèses de l'ISAE (Toulouse), devant le jury composé de :
Christian BESSIÈREPrésident du jury
Ulle ENDRISS
Thibault GAJDOS
Jean-Michel LACHIVERDirecteur de thèse
Jérôme LANGDirecteur de thèse
Michel LEMAÎTREDirecteur de thèse
Patrice PERNYRapporteur
Thomas SCHIEX
Boi FALTINGSRapporteur
Soutenance de thèse
Téléchargement complet (4.6 Mo)

Résumé

Le problème de l'exploitation commune de ressources limitées et coûteuses se pose très souvent dans le milieu industriel, et plus particulièrement dans le domaine spatial pour lequel les projets sont très souvent financés par plusieurs entités, pays ou organismes. L'exploitation de ces ressources doit bien entendu répondre à des critères d'efficacité, afin d'empêcher sa sous-exploitation, mais aussi à des critères d'équité, chaque agent espérant un retour sur investissement en rapport avec sa contribution financière. Nous nous sommes intéressés, au cours de ce travail de thèse, au problème de partage équitable de biens indivisibles (autrement dit d'objets) entre des agents, dont nous abordons trois aspects principaux : modélisation du problème, complexité et algorithmique. La modélisation du problème de partage que nous proposons s'inspire tout d'abord de la théorie du bien-être social et des nombreux travaux sur l'agrégation de préférences dans les problèmes de décision collective et de partage que l'on peut trouver dans le domaine du choix social et de la microéconomie. Elle s'appuie de plus sur un langage de représentation compacte inspiré des travaux sur l'expression logique de préférences. Nous nous intéressons dans un deuxième temps à la complexité du problème de partage tel qu'il a été défini, dont nous étudions deux aspects particuliers : complexité du problème de maximisation de l'utilité collective, et complexité du problème d'existence d'un partage efficace et sans envie. Enfin, dans la dernière partie du travail de thèse, nous nous penchons sur le problème de calcul d'un partage égalitariste au sens du leximin, problème pour lequel nous proposons et analysons plusieurs algorithmes fondés sur la programmation par contraintes. Ce travail de thèse s'appuie sur un problème réel d'allocation de prises de vue pour une constellation de satellites d'observation de la Terre.

Le manuscrit

Manuscrit de thèse
Téléchargement complet (2.8 Mo)
Téléchargement par chapitres
Prélude : Page de garde, résumé, table des matières, notations. prelude.pdf
Introduction introduction.pdf

Partie 1 : Modélisation
Chapitre 1 : Partage et décision collective. chapitre1.pdf
Chapitre 2 : Droits exogènes. chapitre2.pdf

Partie 2 : Représentation compacte et complexité
Chapitre 3 : Représentation compacte. chapitre3.pdf
Chapitre 4 : Complexité du problème de partage. chapitre4.pdf

Partie 3 : Algorithmique
Chapitre 5 : Préordre leximin et programmation par contraintes chapitre5.pdf
Chapitre 6 : Expérimentations chapitre6.pdf

Conclusion conclusion.pdf
Bibliographie bibliographie.pdf
Annexes : Tables des figures et des tableaux, liste des symboles, annexes, index. annexes.pdf