partages inegaux - Professeur Phifix[PDF] les partages inégaux exercices 6ème primaire
[PDF] partage inégaux cm1
[PDF] partages inégaux structure multiplicative
[PDF] perspective cavalière exercices corrigés seconde
[PDF] photosynthèse cours pdf
[PDF] mécanisme de la photosynthèse pdf
[PDF] les deux phases de la photosynthèse
[PDF] phase sombre de la photosynthèse
[PDF] phase photochimique de la photosynthèse
[PDF] la photosynthèse cours
[PDF] photosynthèse phase claire
[PDF] photosynthèse cours terminale s pdf
[PDF] evaluation cm2 proposition principale et subordonn
[PDF] evaluation plus que parfait
Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique 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. Nousnous 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 logiquede 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. Mots-clefs : 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. Fair allocation of indivisible items : modeling, computational complexity and algorithmics 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. Keywords : Fair allocation, social choice, collective decision-making, welfarism, compact preference representation, preference aggregation, complexity, algorithmics, constraint programming, satellites.Sylvain Bouveret - Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique
THÈSEEn vue de l"obtention du
DDOOCCTTOORRAATT DDEE LL""UUNNIIVVEERRSSIITTÉÉ DDEE TTOOUULLOOUUSSEEDélivré par
l"Institut Supérieur de l"Aéronautique et de l"EspaceSpécialité : intelligence artificielle
Présentée et soutenue par
Sylvain BOUVERET
le 16 novembre 2007 Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique JURYM. Christian Bessière, président du jury
M. Ulle Endriss
M. Thibault Gajdos
M. Jean-Michel Lachiver
M. Jérôme Lang, directeur de thèse
M. Michel Lemaître
M. Patrice Perny, rapporteur
M. Thomas Schiex
École doctorale : mathématiques, informatique et télécommunications de Toulouse Unités de recherche : équipe d"accueil SUPAERO-ONERA MOIS (ONERA-DCSD, centre de Toulouse) - IRIT - CNESRapporteur : M. Boi Faltings
Directeur de thèse : M. Jérôme Lang
Jetiens à remercier toutes les personnes qui ont contribué, de près ou de loin, à la réalisation de ce travail de
thèse. Ils ont le droit à ma reconnaissance et à un exemplaire gratuit de ce manuscrit s"ils le souhaitent.
Je tiens toutefois à adresser quelques remerciements particuliers aux personnes qui seront citées dans les
deux pages suivantes, et qui m"ont très certainement apporté autant sur le plan te?nique que sur le plan humain.
En premier lieu, je tire un coup de ?apeau à Jean-Mi?el La?iver, Jérôme Lang et Mi?el Lemaître, qui
m"ont encadré pendant ces trois années. Ils ont su m"apporter, par leur relative disponibilité, leurs différences, et leurs
qualités te?niques et humaines, tous les ingrédients nécessaires à la réalisation d"un travail de thèse dans des conditions
excellentes. J"espère avoir encore moult occasions de les côtoyer, que ce soit pour une discussion te?nique, à l"autre
bout du monde, ou encore au détour d"un ?emin ou d"une falaise.Simon de Givry, Thomas S?iex et Gérard Verfaillie ont eu l"occasion de suivre mon travail de près à l"occasion
en particulier de leur participation à mon comité de thèse, même si leur influence sur ce travail dépasse largement ce
cadre restreint. Je les en remercie vivement! Merci particulièrement à Thomas S?iex d"avoir accepté de faire partie
de mon jury.Merci infiniment aux Professeurs Boi Faltings et Patrice Perny, qui ont eu la lourde tâ?e probablement quelque
peu fastidieuse d"être les rapporteurs du présent manuscrit. J"ai eu plaisir à discuter avec eux, à l"occasion de multiples
rencontres, et leurs conseils m"ont été très utiles pour améliorer ce manuscrit ainsi que pour la suite de mon travail.
J"aimerais remercier en outre Patrice Perny pour m"avoir accueilli dans son équipe au Laboratoire d"Informatique de
Paris 6 pendant deux semaines.
Je remercie ?ristian Bessière, Ulle Endriss et Thibault Gajdos, membres de mon éclectique jury de thèse, pour
la qualité de leur analyse, la précision de leurs questions et la pertinence de leurs conseils lors de la soutenance. Merci
à ?ristian Bessière d"avoir accepté de présider le jury. Merci à Thibault Gajdos d"avoir accepté de s"aventurer sur les
terres inconnues de l"informatique en participant à mon jury de thèse. Je remercie enfin ?aleureusement Ulle Endriss,
pour avoir lu le manuscrit avec autant d"attention, pour toutes les discussions que nous avons pu avoir au cours de ma
thèse, pour l"énergie qu"il déploie à organiser des événements fédérateurs dans la communauté, et pour m"avoir donné
l"occasion de participer à de nombreuses reprises à des groupes de travail.J"ai effectué ma thèse au sein de l"équipe Conduite et Décision du Département Commande des Systèmes et
Dynamique du vol de l"Onera, où j"ai bénéficié de conditions de travail particulièrement agréables. J"aimerais donc
remercier Patrick Fabiani et Jean-François Gabard de m"avoir accueilli dans cette équipe, ainsi que tous les membres de
l"unité dont j"ai apprécié la compagnie. Merci à ?ristophe "Tof" Garion, de Supaéro, de m"avoir fait confiance et de
m"avoir fait découvrir le monde merveilleux de Java et de l"enseignement. Merci aussi à tous les personnels (te?niques,
administratifs, gardes, etc.) qui nous facilitent la tâ?e au quotidien et contribuent à nous rendre le travail plus agréable.
D"un point de vue plus pragmatique, je remercie le Cnes et l"Onera d"avoir financé cette thèse. Je remercie aussi
l"ANR pour le financement des missions dont j"ai pu bénéficier à plusieurs reprises au cours de ma thèse, dans le
cadre de ma participation au projet Phac.???Outre les personnes que j"ai déjà citées dans les paragraphes précédents, j"ai eu la ?ance de faire de multiples
connaissances durant ma thèse, au détour de groupes de travail, de conférences ou de séminaires. Je pense tout d"abord
à toutes les personnes qui gravitent autour du groupeMultiAgent Resource Allocationet du projet ANR Phac, et
en particulier les gens du Lamsade dont Yann ?evaleyre, Sylvia Estivie et Nicolas Maudet, du Cril, de l"ILLC,
et du Lip6. Je remercie à cette occasion particulièrement l"équipe Décision du Lip6, qui m"a accueilli ?aleureusement
pendant deux semaines, et notamment (outre Patrice Perny que j"ai déjà cité), Olivier Spanjaard, Paul Weng, et la
joyeuse équipe des thésards, Lucie, Nicolas, et les autres. Merci aussi à Bruno Zanuttini pour toutes nos discussions
communes, pour ses qualités humaines, et pour son invitation à l"Université de Caen.Merci à la meute des thésards toulousains, parmi lesquels :?les thésards du DCSD et assimilés : Clément et ses sandales, Cédric et son professeur émérite K. Hungus,
l"autre Cédric, Nico, Greg le millionnaire, Greg le prolétaire, Manu tentionnaire, ?arles, Olivier, Flo, Stéphane,
Julien, Patrice, Sophie, Florent et les autres;?les piliers du DMAE : Claire et sa polaire frottée, Bruno, inventeur du cadeau concept et de la loi de
Frackowiak, Nico;?la horde de l"Irit : Élise, Kévin, Nico; ?les joyeux drilles de l"Inra : Matthias, dont l"activité principale consiste à compiler le C;?les autres : rajoutez votre nom ici si je vous ai oublié : ..........................................
Merci à Barth de m"avoir hébergé tant de fois lorsque j"étais en mission. Merci aux membres de la confrérie
Saint-Luc, issus d"une longue lignée de maîtres brasseurs depuis 2007. Merci aux amis pro?es et moins pro?es, aux
grimpeurs, aux nageurs, aux cinéphiles, aux cynophiles, aux amateurs de bovins, aux skieurs, aux randonneurs, aux
?er?eurs, aux étudiants, aux coureurs, aux piliers de comptoir, aux adeptes du jeu de mots, auxgeeks, aux mélomanes,
aux ours des montagnes,...Merci à tous les professeurs qui m"ont donné l"envie d"apprendre, la curiosité intellectuelle, et le goût de la re?er?e.
Merci à ma mère de m"avoir soutenu et donné l"opportunité de faire des études. Merci enfin à Marianne, pour tout le reste, tout ce qui compte réellement. ????? ?????? ??q??????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???? ?????q?= 0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???? ?????q= 0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???? R R ??Q???N?R\ {0}?Q\ {0}??N\ {0} R +???Q+?R+\ {0}??Q+\ {0} X nX× ··· ×X???? x x?y?(x,y)? max v?? v?Mod(?)