Optimizing with Uncertainty: An Introduction to Online Algorithms and Algorithmic Game Theory

Course in Winter 2017/18

Traditional optimization theory assumes complete knowledge of information. However, in reality, input might be uncertain - they might be incomplete, revealed over time or might involve choices made by selfish players. In this course, we shall deal with solving optimization problems under such uncertainties.

In the first part of the course, we shall develop the notion of online computation - an area which deals with developing algorithms that make decisions on the basis of input that is built over time. We shall introduce formal models of measuring the efficiency of such algorithms and develop algorithms for various flavors of online optimization problems. These problems find applications in areas such as planning, logistics, communication or machine learning.

In the second part, we learn to handle situations where we are not all-powerful, but instead have to deal with other decision makers as well. We learn to design mechanisms that take into account the actions of these strategic players and how to analyze the performance of these mechanisms. We encounter this type of problems in transportation and data networks, (online) auctions, and assigning students to schools.

Dr. Ruben Hoeksma (Email)
Dr. Syamantak Das (Email)
Time & Room:

Tue : 14:00-16:00 ; MZH 1450
Thu : 16:00-18:00 ; MZH 1100
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
Date Topic Notes Exercises
17.10.2017 Introduction, Ski-Rental Lecture 1 Exercise 1
19.10.2017 Deterministic paging algorithms Lecture 2 -
24.10.2017 List Update Problem Sections 2.1-2.3 from [4] -
26.10.2017 Exercise session - -
31.10.2017 No lecture (Day of German Unity) - -
02.11.2017 Makespan minimization on identical parallel machines - -
07.11.2017 Makespan minimization under restricted assignments Lecture 4,5 Exercise 2
09.11.2017 Exercises - -
14.11.2017 Randomized Paging Algorithm Basic probability Notes by Luca Trevisan Exercise 3
16.11.2017 Randomized Paging Algorithm, Yao's principle Section 2.2 from [5] -
21.11.2017 Exercises - -
23.11.2017 Weighted Completion Time Scheduling Section 4.3 from [4] -
28.11.2017 Min Cost Matching - Exercise 4
30.11.2017 Min Cost Matching - -
5.12.2017 k-server on a line Section 6.3 from [4] -
7.12.2017 Lower bound for k-server, Summary of Course Section 6.2 from [4] -
12.12.2017 Introduction AGT: games and equilibria Section 1 and first part of Section 2 in lecture notes on AGT (Examples to come) -
14.12.2017 Existence of equilibria and best responses Sections 2.1 and 2.2 in lecture notes on AGT -
19.12.2017 Efficiency: atomic and non-atomic routing games Sections 3 and 3.1 in lecture notes on AGT -
21.12.2017 Exercise Session Tutorial exercises -
09.01.2018 Upper bounds for POA in non-atomic routing Section 3.2 in lecture notes on AGT -
11.01.2018 Upper bound on POA in atomic routing and smoothness Sections 3.3 lecture notes on AGT Exercise 5
23.01.2018 Single item auctions Sections 4, 4.1, and 4.2 in lecture notes on AGT -
25.01.2018 Sponsored search auctions Section 4.3 and 4.4 in lecture notes on AGT -
30.01.2018 Exercises Tutorial exercises -
01.02.2018 Revenue maximizing auctions Section 4.5 in lecture notes on AGT Exercise 6