Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Gerhard Woeginger - Eindhoven University of Technology

Optimization at the second level

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

Max Klimm - TU Berlin

The equilibrium existence problem in congestion games

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.

Letzte Aktualisierung: 06.12.2012