Two internships are proposed for Spring 2011 :

Jeux d'ordonnancement

Encadrants : Bruno Escoffier, Laurent Gourvès, Jérôme Monnot

Lieu : LAMSADE (Université Paris-Dauphine)

Pré-requis : Connaissances en algorithmique et théorie de la complexité Goût pour l'étude théorique de problèmes d'optimisation combinatoire

Description : http://mpri.master.univ-paris7.fr/stages-2011/20110131-094942/sujet-coca.pdf

Algorithmes à véracité garantie pour le problème d'affectation

Encadrants : Fanny Pascual, Olivier Spanjaard

Lieu : Laboratoire d'Informatique de Paris 6 (UPMC - Paris 6)

Pré-requis : Connaissances en algorithmique et théorie de la complexité Goût pour l'étude théorique de problèmes d'optimisation combinatoire

Description : Dans ce stage, nous nous intéressons au problème d'affectation dans le cadre de la théorie des jeux algorithmique. Le problème d'affection consiste à affecter des tâches à des agents : chaque agent définit des préférences sur les différentes tâches (i.e. il a une utilité associée à chaque tâche), et un algorithme doit ensuite affecter les tâches aux agents de façon à optimiser une fonction objectif globale. Cette fonction objectif globale représente le "bien être social", il peut par exemple s'agir de maximiser l'utilité moyenne des agents, ou bien l'utilité minimale. Nous nous intéressons à ce problème dans le cas où un agent est le seul à connaître les tâches qu'il est capable de faire : l'algorithme affecte les tâches selon les déclarations des agents. Le but d'un agent étant d'optimiser un objectif qui lui est propre, un agent peut mentir (en déclarant par exemple qu'il n'est pas capable de traiter certaines tâches) si cela lui permet d'optimiser son objectif. Notre but est donc de concevoir des algorithmes résistant aux manipulations. Un algorithme est dit à véracité garantie si chaque agent n'a pas d'intérêt (selon son propre objectif) à lui déclarer de fausses informations. Notre but est de concevoir des algorithmes à véracité garantie pour différentes variantes du problème d'affectation, ces algorithmes devant être le meilleur possible pour la fonction objectif globale considérée.

Travail à effectuer : Réaliser un état de l'art des travaux réalisés sur des problèmes connexes. Proposer des algorithmes à véracité garantie pour le problème étudié, analyser la performance de ces algorithmes au regard de la fonction de bien-être social considérée. Eventuellement proposer des résultats d'impossibilité (montrer par exemple qu'il n'existe pas d'algorithme à véracité garantie ayant un rapport d'approximation inférieur à une certaine valeur).

Référence : http://theory.stanford.edu/~shaddin/papers/nomoney.pdf