–
March 10, 2016
Résumé : Le problème d'avoir à partager de manière efficace et
équitable un ensemble d'objets indivisibles entre des agents est un
problème complexe et ayant de nombreuses applications concrètes, allant
de l'allocation de cours à des étudiants à l'allocation de tâches sur
des machines. Dans cet exposé, après une introduction générale sur le
problème de partage équitable de ressources, nous nous pencherons sur
un protocole très simple d'allocation d'objets indivisibles : les
séquences de choix. Ce protocole est remarquable car il est très simple
à instancier sur des problèmes concrets, et possède néanmoins des
propriétés très intéressantes. Nous nous intéresserons plus
particulièrement au problème de calcul d'une séquence optimale, et à
des considération liées au comportement stratégique des agents.
Note : Cet exposé ne nécessite aucun prérequis technique (sauf
peut-être une connaissance basique de la complexité des problèmes).
