– COCA

Le projet traite de problèmes à l'interface entre optimisation combinatoire et théorie des jeux. L'optimisation combinatoire est un domaine très actif en informatique. C'est certainement dû aux nombreuses applications pratiques (ex. en télécommunications, transport, ingénierie). Cependant le contexte stratégique dans lequel ces problèmes émergent est souvent mis de côté. C'est à dire un contexte dans lequel les retombées du choix d'un individu dépendent du choix d'autres individus. C'est typiquement le cas lorsque plusieurs agents, guidés par leur seul intérêt, partagent (et sont en compétition sur) une ressource commune (ex. un réseau, un marché). Avec le développement d'Internet et du commerce électronique, ce type de problèmes mettant en jeu à la fois une base combinatoire et une dimension stratégique sont d'une importance grandissante en informatique. Si aucune entité centrale ne régit les décisions des agents alors il est très peu probable qu'ils tendent spontanément vers une configuration socialement bonne. En effet, les intérêts divergeants des agents et les possibles interférences de leurs décisions mènent souvent à une sous exploitation du potentiel des ressources disponibles. Le but de ce projet est d'apporter des solutions opérationnelles qui peuvent minimiser, voire éviter, cette perte d'efficacité (dans un contexte combinatoire), en étudiant l'impact que peut avoir une entité extérieure qui essaie d'influencer le jeu vers un équilibre socialement bon. L'accent est mis sur les aspects algorithmiques. L'utilisation d'outils de la théorie des jeux pour ces problèmes est particulièrement pertinente car l'objet même de cette discipline est de décrire les comportements rationnels pour des problèmes décisionnels où l'intéraction joue un rôle crucial.