max planck institut
mpii logo Minerva of the Max Planck Society


Learning, Game Theory and Optimization (Summer 2013)

Time: Wednesday, 8:30 a.m. to 10 a.m. The two Friday lectures (marked red in the schedule) will take place 10:15 a.m. to 11:45 a.m.
First meeting: 24.04. (second week of the semester)
Lecturer: Martin Hoefer
Tutorials: Monday, 9:00 a.m. to 10 a.m. The last tutorial (29.07.) will start from 8:30 a.m. (to avoid possible collision with the Artificial Intelligence endterm exam).
Tutor: Bojana Kodric
Room: 024 on the ground floor of the MPI building (E1.4).
Prerequisites: Basics in algorithm design, probability theory and calculus. No background in game theory is required.
Description: This course covers some recent progress on design and analysis of algorithms with connections to game theory and learning. The problems we are solving arise in large network systems like traffic systems, wireless networks, or online markets, and the techniques used for their solution extend classic results in machine learning or optimal stopping theory.

Topics of the lecture are:
  • Basic Concepts from Game Theory
  • Potential Games and Routing
  • Stable Allocation
  • Online Learning
  • Secretary Problems and Online Auctions
  • Prophet Inequalities and Bayesian Mechanism Design
Credits: This is a 6-credit-points class. There will be one lecture and one tutorial session per week.
Exercises: We will hand out exercises every week and each student should score at least 50% in the first half and 50% in the second half in order to be allowed to take the exam.
There will be no exercise sheet handed out on Jun 12.
Exam: Send an e-mail to the tutor in order to reserve a time slot for the oral exam. Your grade will only be dependent on the exam.
Exam schedule:
Time 01.08. 02.08. 01.10.
9:00 reserved reserved
9:40 reserved reserved reserved
10:20 reserved reserved reserved
11:00 reserved reserved reserved
11:40 reserved
14:00 reserved reserved
14:40 reserved
15:20 reserved
Date Topic Reference Homework
Apr 24 Nash equilibrium Introduction [pdf], (25.04.2013.--11:30h)
Nash equilibrium [pdf], (08.05.2013.--22:00h)
May 1 Public Holiday (Tag der Arbeit/Workers' Day) 2
May 8 Nash equilibrium 3
May 15 Congestion Games Congestion Games [pdf], (22.05.2013.--18:00h) 4
May 22 Congestion Games 5
May 29 Stable Matching Stable Matching [pdf], (29.05.2013.--15:05h) 6
Jun 5 Online Learning Online Learning [pdf], (27.06.2013.--11:22h) 7
Jun 7 Online Learning
Jun 12 Online Learning
Jun 19 No class 8
Jun 26 Online Learning 9
Jul 3 Secretary Problems Secretary Problems [pdf], (22.07.2013.--14:00h) 10
Jul 10 Secretary Problems 11
Jul 17 Prophet Inequalities 12
Jul 19 Prophet Inequalities
Jul 24 No class

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)