Classroom: MPI 3rd Floor Rotunda.
Class Hours: Tuesday 4:15-5:45.
First Class: October 13th.
Office Hours: Chien-Chung, Monday 4-5PM, Kurt, Tuesday 3-4PM.
Description: this seminar course focuses on algorithmic game theory. You can find the syllabus here. Our course will be based on certain selected papers and a recent book written by Nisan, Roughgarden, Tardos and Vazirani.
Policy: students will be divided into two or three groups (depending on the number of enrolled students). All students are expected to read all materials. In every week, one group of students will be responsible for presenting. In particular, three students are chosen at random in the group to present (he/she will be informed two days in advance).
First Week: Chien-Chung gave an introduction to algorithmic game theory. Simple examples such as the prisoner's dilemma and battle of the sexes are discussed. A proof of von Neumann's minimax theorem is also presented.
Second week: Chien-Chung discussed several topics about the ineffiency of equilibria and mechanism design, such as the price of anarchy/stability, Braess' paradox, and the second-price auction. The existence of pure Nash equilibria in load balancing game in the context of related machines is proved. The tight bound of the price of anarchy for identical machines in pure Nash equilibria is also shown.
Third Week: Christopher Haccius, Hendrik Molter, and Paarijaat Aditya presented the price of anarchy and an algorithm for finding Nash equilibria for load balancing games in the context of uniformely related machines.
Fourth Week: Karl Bringmann, Xiaoqi Cao and Goran Doychev presented the paper: Selfish Load Balancing and Atomic Congestion Games by Subhash Suri, Csaba D. Toth, and Yunhong Zhou (SPAA 2004, Journal version in Algorithmica 2007).
Fifth Week: Martin Schmidt, Stephan Max and Helge Rhodin discussed potential games (Sections 19.3, 19.4).
Sixth Week: Krzysztof Drys, Qinqing Zheng, and Paarijaat Aditya discussed routing games (Sections 18.3, 18.4, 18.5).
Seventh Week: Marc Eisenbarth and Yongtao Shuai presented a paper by Nisan and Ronen: Algorithmic Mechanism Design (STOC 1999). Angelina Vidali is very kind to be our guest teacher.
Eighth Week: Touseef Liaqat, Sebastian Wendland, Stephan Max, Helge Rhodin, Aliaksandr Talaika, Christopher Haccius presented a paper by Correa, Schulz and Stier-Moses: A Geometric Approach to the Price of Anarchy in Nonatomic Congestion Games (Games and Economic Behavior 2008).
Ninth Week: Andreas Rau, Karsten Knuth, Heiko Jenal, Qinqing Zheng, Hendrik Molter and Frederic Raber presented combinatorial auctions (Sections 11.1, 11.2, 11.3).
Tenth Week: Yongtao Shuai, Marvin Kuennemann, and Faraz Manshad presented the design of scalable resource allocation mechanisms (Sections 21.1 21.2).
Eleventh Week: Maksim Lapin, Weijia Shao, Martin Schmidt, Touseef Liaqat, Stephan Max, and Aliaksandr Talaika presented a paper by George Christodoulou, Elias Koutsoupias, Akash Nanavati: Coordination Mechanism (ICALP 2004).
Twelfth Week: Yongtao Shuai, Xiaoqi Cao, Kaushik Mukherjee, Marvin Kunnemann, Marc Eisenbarth, and Faraz Manshadi presented a paper by Correa, Schulz and Steir Moses: Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem (IPCO 2004).
Thirteenth Week: Andreas Rau, Christian Mathieu, and Praveen Chundi presented a paper by Buchfuhrer et al.: Inapproximability for VCG-Based Combinatorial Auctions (SODA 2010).
Fourteenth Week : Helge Rhodin, Christopher Haccius, Kaushik Mukherjee, Fidaa Abed, Marvin Kunnemann, and Touseef Liaqat presented a paper by George Christodoulou, Elias Koutsoupias: On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. (ESA 2005).