Ecole de recherche d'hiver: Algorithmic Game Theory

December 9-13, 2013, ENS Lyon

Speakers: Claire Mathieu and Christoph Dürr.


Algorithmic Game Theory is a research area at the interface of computer science, game theory, and economics. It is largely motivated by new decentralized nature of various applications in the Internet. This course aims to give an introduction into the important results of this area. As textbook we suggest "Networks, Crowds, and Markets: Reasoning About a Highly Connected World" by Easley et Kleinberg.



congestion games,

network routing game

the Braess paradox

the inefficiency of equilibria, price of anarchy, price of stability (Hoteling)

exact potential games

equivalence of congestion games and exact potential games

the class PLS

the stable marriage problem

the Pott's model


Nash equilibria

pure and mixed Nash equilibria

Nash's theorem

several fix point theorems (incl. Sperner's lemma)

the complexity of finding Nash equilibria

the Lemke-Howson Algorithm

the class PPAD

two player zero sum games



google adwords

Adwords and generalized online matching

Online primal-dual algorithms for maximizing ad-auctions revenue


mechanism design

Condorcet's paradox

Arrow's impossibility theorem

Vickrey-Clarke-Groves mechanisms

Archer,Tardos' theorem


network creation games