Ecole de recherche d'hiver: Algorithmic Game Theory

December 9-13, 2013, ENS Lyon

Speakers: Claire Mathieu and Christoph Dürr.

Outline

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.

Schedule

Monday

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

Tuesday

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

Wednesday

auctions,

google adwords

Adwords and generalized online matching

Online primal-dual algorithms for maximizing ad-auctions revenue

Thursday

mechanism design

Condorcet's paradox

Arrow's impossibility theorem

Vickrey-Clarke-Groves mechanisms

Archer,Tardos' theorem

Friday

network creation games

exa