Prof. Elias Koutsoupias - Seminar series on Algorithmic Game Theory and Mechanism Design
Professor Elias Koutsoupias will give a seminar series on Algorithmic Game Theory and Mechanism Design within the Course on Seminars of Computer Networks. All lectures will be held on Thursday, 10:15 - 13:30, Room A3, from April 19th to May 24th.
Course outline
April 19th
* Introduction to algorithmic game theory
- Games
- Equilibria
- Computation of equilibria
- Preview of network economics (price of anarchy, GSP)
April 26th
* Congestion and potential games
- Example games
- Definition of atomic and non-atomic congestion games
- Potential function
- Existence of pure Nash equilibria
- Potential games
- Relation between congestion and potential games
- Weighted congestion games
May 3rd
* Price of Anarchy and Stability
- Examples (scheduling / routing)
- Definition of PoA and PoS
- PoA of atomic congestion games
- PoA of non-atomic congestion games
- Smoothness and other types of equilibria
- PoS of congestion games
May 10th
* Mechanism design - Scheduling
- Example: single-item auction
- Mechanism design domains
- Scheduling
- Truthfulness
- Approximation bounds
May 17th
* Combinatorial auctions and GSP
- Definition
- Special cases (single-minded)
- GSP (truthfulness, analysis, PoA)
May 24th
* Bayesian and prior-free auctions
- Myerson's optimal auction
- Competitive auctions of digital goods