LNMB PhD Course: Algorithmic Game Theory 2014

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.

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.

• Assignment 1 (issued Feb. 24), due Mar. 3 due March 7.
• Assignment 2 (issued Mar. 10), due Mar. 20.
• Assignment 3 (issued Mar. 24), due Apr. 4.
• Assignment 4 (issued Apr. 9), due Apr. 23.

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.

If you want to learn more about convex programming (e.g., KKT conditions), the following book (available online) might be a good start:

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).