This course covers selected topics from
cooperative and noncooperative game theory, with applications in
telecommunication networks. After a broad introduction to the
fundamentals of game theory, we will see the use of different
theoretical concepts like "Nash and Stackelberg equilibria"
or the "price of anarchy" for some chosen application related
to traffic management in transportation networks. A non-exhaustive list
of the covered topics includes:
congestion games and Wardrop equilibrium;
cost allocation and auction games;
spanning tree games;
spot checking games over Networks.
Network algorithms, Linear and Mixed Integer Programming
50 % from the exercise points are required to be qualified to pass the exam
The final examination will be a written Klausur
The material for this course is mailny based on the following references:
P. Morris, Introduction to Game Theory. (cf. Apparat in the ZIB Library.)
V. Chvatal, Linear Programming. (cf. Apparat in the ZIB Library.)
T. Roughgarden, Selfish Routing and the Price of Anarchy. (cf. Apparat in the ZIB Library.)
N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, Algorithmic Game Theory.
(A free version of this book is available here.)
As well as on the following research articles (preprints are available on the Internet):
J.R. Correa, A.S. Schulz and N.E. Stier Moses, Selfish Routing in Capacited Networks,
Mathematics of Operations Research, 29(4): 961-976, 2004.
I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli,
Tight bounds for selfish and greedy load balancing ,
Automata, Languages and Programming, 4051:311-322, 2006.
G. Christodoulou and E. Koutsoupias, On the price of anarchy and stability
of correlated equilibria of linear congestion games , In Algorithms–ESA 2005 (pp. 59-70).
B. Awerbuch, Y. Azar and A. Epstein, The price of routing unsplittable flow,
In Proceedings of the 37th annual ACM symposium on Theory of computing (pp. 57-66). ACM, 2005.
V. Bonifaci, T. Harks and G. Schäfer, Stackelberg routing in arbitrary networks,
Mathematics of Operations Research, 35(2):330--346, 2010.
Y. Cai and C. Daskalakis, On Minimax Theorems for Multiplayer Games,
Proceedings of the 22d symposium on Discrete Algorithms SODA'11, (pp. 217-234), 2011.
P. Paruchuri, et al., Playing games for security: an efficient exact algorithm
for solving Bayesian Stackelberg games. In Proceedings of the 7th AAMAS, vol. 2, 2008.
R. Borndörfer, J. Buwaya, G. Sagnol and E. Swarat. Optimizing Toll Enforcement
in Transportation Networks: a Game-Theoretic Approach,
In Proceedings of the International Conference on Network Optimization (INOC), 2013.