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, June 4, 2012

Technische Universität Berlin
Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Patrice Marcotte - Université de Montréal

Network Design and Equilibrium

More than 50 years after its introduction, the notion of equilibrium is still a topic of active research (and even controversy!) in the field of transportation. In this presentation, I will illustrate the importance of this concept through three applications. The first is concerned with a design problem involving equilibrium constraints (MPEC) for which "price-of-anarchy" results will be discussed. The second is a multiclass extension of traffic assignment, where proper formulations help to capture the very nature of the problem. The third model shows how the introduction of simple constraints calls for new paradigms. Throughout the exposition, I will make the connection with congestion games and mention unresolved issues.

Colloquium - 16:00

Philipp von Falkenhausen - Technische Universität Berlin

Design of Mechanisms for Good Equilibria

The rich framework of congestion games can not only be applied to traffic applications where the cost of the system is latency and thus equally experienced by the users but also to applications where the cost is money and can be thus be shared among the users in arbitrary ways. In the latter setting, the existence and quality of the game's equilibria strongly depend on the mechanism by which the cost is shared.

While in some applications the mechanism can optimize globally, in other settings the mechanism needs to work in a distributed way. This motivates a classification of mechanisms which I will introduce in the first part of the talk. In the second part, I will present mechanisms from three such classes that are optimal with respect to the price of anarchy for singleton and matroid congestion games.

This is joint work with Tobias Harks.

Letzte Aktualisierung: 22.05.2012