Course: Algorithmic Game Theory

Bachelor course 64331010, Caput Operations Research, HC Caput OR 3.5, 3 ects
Department of Econometrics and Operations Research
Faculty of Economics and Business Administration
VU University Amsterdam

News

• Inspection of the re-exam (written on June 29): Wednesday, July 14, 2010 at 14:30 in room 1E-61 (HG).

Course Description

Game theory provides a tool-set of various models and solution concepts to study the effect of strategic behavior, but mostly neglects computational and algorithmic issues. These issues are taken into account additionally in algorithmic game theory, a rather new and flourishing research field that lies at the intersection of economics, mathematics and computer science.

In this course, we will give an overview of fundamental results in this field. Both cooperative and non-cooperative games will be considered. Potential topics that will be covered in the course are:

• selfish routing (Nash flow, price of anarchy, Braess paradox, reducing the inefficiency)
• potential games (potential function, exact potential games, decomposition)
• congestion games (equivalence to potential games, price of anarchy, PLS-completeness)
• combinatorial auctions (Vickrey Auction, VCG mechanism, single-minded bidders) cost sharing (approximate core allocations, cost sharing mechanisms).

The goal of the course is to give the participants an overview of some fundamental results and at the same time lead them to state-of-the-art research topics in algorithmic game theory.

Prerequisites:

Some basic knowledge in the areas of operations research, algorithms or optimization is advantageous but not essential.

Time and Location

• Course starts on March 29, 2010 and ends on May 10, 2010.
• Monday, 15:30-17:15, HG-02A02, Vrije Universiteit Amsterdam
• Thursday, 11:00-12:45, HG-06A04, Vrije Universiteit Amsterdam

Lecturer

Prof. dr. Guido Schäfer
Email: g dot schaefer at cwi dot nl

Office at CWI:
Centrum Wiskunde & Informatica
Algorithms, Combinatorics and Optimization
Science Park 123, 1098 XG Amsterdam
Room: M235

Office at VU University Amsterdam:
Department of Econometrics and Operations Research
Faculty of Economics and Business Administration
Vrije Universiteit Amsterdam
De Boelelaan 1105, 1081 HV Amsterdam
Room: HG-01E61 (office hours by appointment)

References and Links

• Most topics that will be covered in class can be found in the following book:
  N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007. Errata.
  Note: The full-text of the book is available online here (username=agt1user, password=camb2agt).
• More details on selfish routing and the price of anarchy can be found in:
  T. Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press, 2005.
• Background on computational complexity:
  • M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
  • Online resources to complexity theory: A compendium of NP optimization problems.
• Article on the Braess paradox in New York Times (Dec. 25, 1990): What if They Closed 42d Street and Nobody Noticed?
• Collection of online resrouces on game theory: GameTheory.net

More references will be added as we go along with the course.

Course Material

• Lecture notes, March 29, 2010: lec01.pdf
• Lecture notes, April 1, 2010: lec02.pdf
• Lecture notes, April 8, 2010: lec03.pdf
• Lecture notes, April 12, 2010: lec04.pdf
• Lecture notes, April 15, 2010: lec05.pdf
• Lecture notes, April 19, 2010: lec06.pdf
• Lecture notes, April 22, 2010: lec07.pdf
• Lecture notes, April 29, 2010: lec08.pdf
• Lecture notes, May 3, 2010: lec09.pdf
• Lecture notes, May 6, 2010: lec10.pdf
• Lecture notes, May 10, 2010: lec11.pdf
• Complete lecture notes (as one pdf file): script-vu-agt10.pdf

Tutorials

Throughout the course, we will have a few tutorial sessions in which the assignments (see below) will be discussed. The main purpose of these sessions is to repeat and exercise the content that has been taught in class. Completing these assignments is not a prerequisite for participation in the final exam; nevertheless, please do try to solve them. Their contents will be relevant for the exam.

• Assignment 1 (April 15, 2010); Solutions.

Exam

• The exam is scheduled for Wednesday, May 26, 2010, 15:00-18:00, HG-04A05.
• The re-exam is scheduled for Tuesday, June 29, 2010, 8:30-11:30, HG-07A09.