Monday, December 17, 2012
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
The talk surveys and discusses a number of algorithmic problems
located at the second level of the polynomial hierarchy. Most
of these problems are taken from geometry, graph theory, social
choice, and robust optimization; some of them are genuinely
intractable, and some of them only pretend to be intractable.
Colloquium - 16:00
Abstract:
Weighted congestion games are an important class of noncooperative games that constitute an elegant model for the resource usage by selfish users. Unfortunately, they need not possess a pure Nash equilibrium, in general. We give a complete characterization of the maximal set of cost functions that one allow on the resources in order to guarantee the existence of a pure Nash equilibrium. I will also review further results on the existence and computation of equilibria in congestion games obtained in my PhD thesis.
Joint work with Tobias Harks, Martin Hoefer, Rolf H. Möhring and Alexander Skopalik.