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

PhD defended on November 16^th, 2007, at ISAE Toulouse, with the following committee members:

Christian BESSIÈRE	Président du jury
Ulle ENDRISS
Thibault GAJDOS
Jean-Michel LACHIVER	Directeur de thèse
Jérôme LANG	Directeur de thèse
Michel LEMAÎTRE	Directeur de thèse
Patrice PERNY	Rapporteur
Thomas SCHIEX

Boi FALTINGS	Rapporteur

Slides (in french)

Complete download (4.6 Mo)

Abstract

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.