Fair allocation of indivisible items: modeling, computational complexity and algorithmics

PhD defended on November 16th, 2007, at ISAE Toulouse, with the following committee members:
Christian BESSIÈREPrésident du jury
Thibault GAJDOS
Jean-Michel LACHIVERDirecteur de thèse
Jérôme LANGDirecteur de thèse
Michel LEMAÎTREDirecteur de thèse
Patrice PERNYRapporteur
Boi FALTINGSRapporteur
Slides (in french)
Complete download (4.6 Mo)


Industrial projects are often faced with the problem of exploiting limited and expansive resources in common, especially space projects which are often cofunded by several entities, countries or organisations. The common exploitation of these resources must of course meet efficiency requirements, in order to avoid the resource to be underexploited, but also fairness requirements, as each agents expects a return on investments in proportion with her initial funding. We studied in this thesis the problem of fairly allocating indivisible goods (objects in other words) to a set of agents. We focused in particular on three different aspects: formal representation of the problem, computational complexity and algorithmics. The model of the resource allocation problem we introduce is primarly inspired by the theory of welfarism, and by the numerous studies in the fields of social choice and microeconomics, dealing with preference aggregation in collective decision-making and resource allocation problems. This model is also based on a compact representation language, inspired by the works about logical expression of preferences. The second issue we address deals with computational complexity of the previously defined resource allocation problem. We study two particular aspects : complexity of maximizing the collective utility, and complexity linked with the existence of an efficient and envy-free allocation. Finally, we study in the last part of the thesis the problem of computing a leximin egalitarian allocation, for which we propose and analyze several algorithms based on constraint programming. Our work is inspired by a real-world problem concerning the allocation of observation requests for a constellation of Earth observation satellites.

The thesis

PhD Thesis (in french)
Complete Download (2.8 Mo)
Download by chapter
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