Announcements:
- Assignment
4 is available. As opposed to what has been said in the last lecture: PLEASE FEEL
FREE TO WORK IN GROUPS OF AT MOST TWO AS BEFORE! Also the final assignment will value
the same as the previous ones (25%).
- Solutions for Assignments 1 and 2 are online.
- Assignment
3 has been issued.
- Assignment
2 has been issued.
- Because of several requests, the deadline for handing in the solutions to
Assignment 1 has been extended to Friday, March 7.
- Addition to Problem 2 of Assignment 1: you may assume that the cost
functions are non-decreasing.
- Assignment
1 has been issued.
- Lecture Notes and slides have been updated.
- Lecture Notes and slides are online (password
protected).
- The course starts on February 10, 2014, 13:00-14:45, Mathematical Building, room
611AB, Utrecht University.
Course Description:
Algorithmic game theory is a rather new and rapidly growing research area that lies
at the intersection of mathematics, theoretical computer science and economics. It uses
game-theoretical models and solution concepts to study situations of strategic decision
making, with a particular focus on computational and algorithmic issues. It combines
methodologies and techniques from areas like discrete optimization, algorithms,
computational complexity, game theory, mechanism design, etc.
Topics:
Potential topics that we will cover in the course are:
- computation of equilibria (potential function, PPAD-completeness)
- inefficiency of equilibria (price of stability, price of anarchy)
- selfish routing games (non-atomic, atomic, price of anarchy)
- congestion games (potential games, PLS-completeness)
- smoothness of games (robust price of anarchy, learning)
- reducing the inefficiency (network tolls, Stackelberg routing)
- combinatorial auctions (first-price, second-price, VCG mechanism)
- approximation and mechanism design (single-minded bidders)
- ad auctions and the generalized second-price auction
- revenue maximization and the Bayesian setting
Besides the material that we cover in class, we will also ask you to study some
material on your own and to solve take-home assignments.
This course is part of the Dutch Network on the Mathematics of Operations Research
(LNMB).
Aims and Prerequisites:
The aim of the course is to both learn about fundamental results of the field and to
get acquainted with recent state-of-the-art techniques.
We assume that the participants have some background knowledge in discrete
optimization (algorithms, complexity, linear programming, etc.); knowledge of game
theory is advantageous but not a prerequisite for the course.
Time and Location:
The course consists of 9 lectures.
Date/Time: |
Monday, 13:00-14:45 |
Location: |
Mathematical Building, room 611AB, Utrecht University |
The first lecture is on February 10, 2014. The last lecture is on April 7, 2014.
Lecturer:
Prof. Dr. Guido Schäfer
Email: g dot schaefer at cwi dot nl
Office hours by appointment
Office at CWI:
Centrum Wiskunde & Informatica
Networks and Optimization Group
Science Park 123, 1098 XG Amsterdam
Room: M235
Assessment:
Assignments will be issued on a bi-weekly basis.
PLEASE(!) WORK IN GROUPS OF AT MOST 2 STUDENTS TO SOLVE AND HAND IN THE
ASSIGNMENTS.
The assignments have to be handed in at the beginning of the next lecture or by
email (on due date, before 13:00). If you want to hand-in your solutions by email, then
please send them directly to me (g dot schaefer at cwi dot nl). Please ensure that
scans of hand-written solutions have a sufficiently high resolution for printing.
References and Links:
We will use selected chapters from the books listed below.
[NRTV07] |
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani
(Editors), Algorithmic Game Theory, Cambridge University Press, 2007.
Note: The full-text of the book is available online here (username=agt1user,
password=camb2agt). There is also an Errata. |
[Har14] |
J. Hartline, Mechanism Design and Approximation,
Manuscript.
Chapters 1-5 available here; see also this
website. |
If you want to learn more about convex programming (e.g., KKT conditions), the
following book (available online) might be a good start:
[BV09] |
S. Boyd and L. Vandenberghe, Convex Optimization,
Cambridge University Press, 2009.
Note: The full-text of the book is available online here. |
If you want to refresh your knowledge on complexity theory, you might want to check
Chapter 9 of the
Lecture Notes on Discrete Optimization that I gave as part of the Mastermath
program.
For more details on complexity classes (PLS, PPAD) and their relations, check out
the complexity zoo.
Course Material:
The online material of the course can be found here (password
protected).
Lecture 1 (Feb. 10)
- Topics: Examples of some phenomena (Prisoner's Dilemma, inefficiency of
equilibria, Braess paradox), Wardrop model & selfish routing
-
Homework (optional):
- Get familiar with the KKT conditions (if you want to learn more about convex
programming, the book [BV09] mentioned above might be a good start).
- Try to prove that the cost of a Nash flow is unique.
- Can you efficiently compute non-negative tolls that induce an optimal
flow?
Lecture 2 (Feb. 17)
- Topics: Selfish routing continued (Variational inequality, POA upper and
lower bound), Braess subgraph problem.
-
Homework (optional):
- Read and understand the inapproximability result discussed at the end of the
lecture (proof of Thm. 1.9 in the Lecture Notes).
- If you like start thinking already about Problem 1 of Assignment 1 (to be
issued Feb. 24); see slides.
Lecture 3 (Feb. 24)
- Topics: Braess subgraph problem, potential games, congestion games,
PLS
- Assignment
1 (due Mar. 3).
Lecture 4 (March 3)
- Topics: PLS-completeness, bounding the POS/POA in potential games
- Homework (optional): Try to prove/disprove that strong equilibria exist in
connection games.
Lecture 5 (March 10)
- Topics: strong price of anarchy, computation of mixed NE, Lemke-Howson
algorithm
- Assignment
2 (due Mar. 20).
Lecture 6 (March 17)
- Topics: PPAD-completeness (Sperner Lemma, Brouwer fixpoint, n-Nash),
hierarchy of equilibria, no regret learning algorithms, robust price of anarchy
-
Self-study:
- In a nutshell: Lecture Notes on No-Regret Dynamics by Tim
Roughgarden.
- For the interested reader: Chapter 4 (Learning, Regret Minimization, and
Equilibria) in [NRTV07].
Lecture 7 (March 24)
- Topics: Vickrey auction, combinatorial auctions
- Assignment
3 (due April 4).
Lecture 8 (March 31)
- Topics: Combinatorial auctions, single-minded bidders, approximate
mechanisms
Lecture 9 (April 7)
- Topics: Generalized second price auction, matching markets, smoothness for
auctions
- Assignment
4 (due April 23).