Short course description
Game theory provides a good model for the behavior and interaction of the selfish users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory, such as a general introduction to game theory, auctions, mechanisms, the costs of a central control optimum versus those of an equilibrium under selfish agents, and algorithms and complexity of computing equilibria.
You can also have a look at the course page in the ETHZ Vorlesungsverzeichnis.
Weekly schedule
Lectures take place weekly on Thursdays, 08.15-10.00, in
CAB
G11,
by
Problem classes take place weekly on Fridays, 10.15-12.00 in CAB G57 and 13.15-15.00 in LFW E15
Topics
- Introduction (algorithmic game theory basics)
- Basic Concepts of Game Theory (games in strategic form, games in extensive form,
pure strategies and mixed strategies in games, solution concepts of games, important games)
- Computational issues of game solutions
- Algorithmic Mechanism Design (basic ideas of mechanism design, social welfare and social
choice, voting systems, Vickrey's second price auction, VCG mechanisms, dominant
strategies and the revelation principle, computational issues, applications)
- Inefficiency of Equilibria (fundamental network examples, routing games, price of anarchy,
price of stability, network creation games)
Literature
- There are no lecture notes for the course. Taking your own notes is advisable.
-
[AGT]
Algorithmic Game Theory, edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani,
Cambridge University Press (to appear in November 2007)
-
Game Theory and Strategy, Philip D. Straffin,
The Mathematical Association of America, fifth printing, 2004
(this book was used in the last year course and is available in the computer science library;
its first few chapters cover some of the material of the first few weeks)
Advised Reading
- The papers that follow are particularly relevant for some topics of the lecture.
-
[1] Vincent Conitzer, Tuomas Sandholm. Complexity Results about Nash Equilibria. In
Proceedings of the 18th International Joint Conference on Artificial Intelligence
(IJCAI), 2003.
-
[2] Noam Nisan, Amir Ronen. Algorithmic Mechanism Design. In Proceedings of the 31st ACM Symposium on Theory of Computing, pages 129-140, 1999.
-
[3] Aaron Archer, Eva Tardos. Truthful Mechanisms for One-Parameter Agents. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 482-491, 2001.
-
[4] Daniel Lehmann, Liadan Ita O'Callaghan, Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. In Journal of the ACM. Volume 49, Issue 5, pages 577-602, 2002.
Schedule
|
Date
|
Topic
|
Exercise Sheets
|
Reference [AGT]. pp
|
|
Sep 27
|
Introduction to Algorithmic Game Theory
|
|
|
|
Oct 4
|
Strategic Games, domination, Nash equilibrium
|
Exercise Sheet 1
|
3-13, 30-31
|
|
Oct 11
|
Mixed Strategies, Mixed Nash Equilibrium
|
Exercise Sheet 2
|
8, 13
|
|
Oct 18
|
Zero-sum Games, Comput. Complexity of NE [1]
|
Exercise Sheet 3
|
16-18, 30-33
|
|
Oct 25
|
VCG Mechanisms [2], Archer-Tardos one-param. Agents [3]
|
Exercise Sheet 4
|
216-220
|
|
Nov 1
|
Combinatorial Auctions [4]
|
Exercise Sheet 5
Sol. to ex. 5.2 a)
|
267-275
|
|
Nov 8
|
Social choice, Elections, Arrow's theorem
|
Exercise Sheet 6
|
211-215
|
|
Nov 15
|
Gibbard-Satterthwaite Theorem, House Allocation Problem
|
Exercise Sheet 7
|
215, 253-255
|
|
Nov 22
|
Selfish Routing, the Price of Anarchy
|
Exercise Sheet 8
|
443-448, 461-467, 472-475
|
|
Nov 29
|
Network Formation Games
|
Exercise Sheet 9
|
487-494
|
|
Dec 6
|
Global Connection Games, Potential Games
|
Exercise Sheet 10
|
494-499
|
|
Dec 13
|
Keyword-Based Advertising Markets
|
|
699-702
|
|
Dec 20
|
Exam
|
|
|
Exercises
There will be weekly exercise assignments. They will appear on Friday morning in week
i, and you are asked to hand in the solutions to the problems on Thursday in week
i+1 during the lecture. The solutions to the problems will be discussed in the
problem class on Friday in week i+1. The exercises will be corrected and marked as
passed or failed.
Exam
There will be a written examination. You need to pass at least half of all (that is,
5 out of 10) exercise assignments to be admitted to the exam. All exercise assignments contribute
with a weight of 20 % to the final grade.
The exam will take place on Thursday, December 20, from 8.00 to 10.00. Written
notes of any kind will not be permitted.
|
inf.ethz.ch, CAB H15
