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
Dr. Syamantak Das (Email)
Time & Room:


Literature: The course is based on parts of the literature below and recent research articles that will be added later.