LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Languages: French
Types: Article
Subjects: Partage équitable, Allocation, Choix social, Décision collective, Welfarisme, Représentation compacte de préférences, Agrégation de préférences, Complexité, Algorithmique, Programmation par contraintes, Satellites, 000, Fair allocation, Social choice, Collective decision-making, Welfarism, Compact preference representation, Preference aggregation, Complexity, Algorithmics, Constraint programming
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. 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 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.
  • No references.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article