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
	exam