Home » Node » 6050

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


© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma