Description
Introduction à la théorie des jeux (Olivier Serre)
Cet exposé sera une introduction à diverses classes de jeux étudiés en informatique, tout en soulignant les liens avec la théorie des jeux classique comme étudiée en mathématiques.
Une première partie sera basée sur des exemples (et des exercices): jeux sur des graphes, jeux matriciels et équilibre de Nash, jeux stochastiques, jeux à information imparfaite.
La seconde partie de l'exposée se penchera plus précisément sur des jeux à deux joueurs à durée infinie sur des graphes. On précisera les liens avec plusieurs autres problèmes d'informatique (théorie des automates / vérification) et on proposera des algorithmes de résolution
Efficacité des équilibres (Laurent Gourvès)
Il a été souvent observé que l'état atteint par des agents poursuivant un intérêt propre peut être collectivement sous optimal. Nous proposons de l'observer sur des jeux stratégiques et donnons des outils permettant de mesurer l'impact de la détérioration de la qualité de solutions du fait que l'on se restreint à des situations d'équilibre (prix d'anarchie, prix de la stabilité). Nous effectuons ces mesures sur des exemples simples. Dans une seconde partie nous nous intéressons à des moyens algorithmiques de réduire cet impact, toujours en l'illustrant avec des exemples.
Computational Aspects of Cooperative Game Theory (Michael Wooldridge)
Cooperative game theory studies the behavior of self-interested agents in strategic settings where binding agreements among agents are possible. We present a survey of work on the computational aspects of cooperative game theory. We begin by formally defining transferable utility games, and introducing key solution concepts for such games. We then discuss two major issues that arise when considering such games from a computational perspective: identifying compact representations for games, and the closely related problem of efficiently computing solution concepts for games. We survey several formalisms for cooperative games that have been proposed in the literature. We briefly discuss games with non-transferable utility and partition function games, and then overview algorithms for identifying welfare-maximizing coalition structures. The tutorial is closely based on a new textbook co-authored by Wooldridge with the same title: http://web.spms.ntu.edu.sg/~eelkind/coopbook/.
Slides for the course can be downloaded from:
http://web.spms.ntu.edu.sg/~eelkind/coopbook/slides.html
Network congestion games (Jose Rafaël Correa)
In this lectures we will study network congestion games in which a number of agents wish to travel from their origin to their destination. The salient feature of these games is that routes become congested due to larger traffic and therefore the agents decisions influence each other. We will discuss issues of existence, uniqueness, computation, and quality of equilibria in three different contexts: Nonatomic routing games, Atomic splittable games, and Dynamic routing games.
Mécanismes d'incitation (Christoph Dürr)
Ce cours va suivre essentiellement le chapitre ``Introduction to mechanism design for computer scientists" de Noam Nisan du livre Algorithmic Game Theory. Motivé par les résultats d'impossibilité d'Arrow et de Gibbard-Satterthwaite pour le choix social, nous allons étudier les mécanismes avec argent, comme l'enchère au second prix et le schéma de partage de coût de Shapley.
Cooperation in resource management of distributed systems (Krzysztof Rządca et Denis Trystram)
We investigate various approaches that improve the cooperation between stakeholders of distributed systems. In the discussed problems, the stakeholders do not behave strategically; however, the system must take into account stakeholders' individual (selfish) objectives. First, we consider the problem of scheduling jobs on a distributed supercomputer, composed of many multiprocessor machines. We show a centralized approximation algorithm that optimizes the global goal of the system (e.g. the global makespan) without worsening the local objectives. Then, we discuss a relaxed version of the algorithm that permits local slowdowns. Finally, we analyze various quantitative measures of 'fairness' in multi-agent systems. Here, we consider a problem of static resource allocation in a distributed storage system.