Congestion Games: Equilibria, Networks, and Complexity

We study the existence, computation, and quality of (approximate) pure Nash equilibria in atomic (network) congestion games with increasing and decreasing resource cost functions. For weighted congestion games with polynomial and general increasing resource cost functions, we give super-constant lower bounds on the non-existence of approximate equilibria. For network games with decreasing cost functions, we bound the Price of Stability of broadcast games. Finally, we give an algorithm solving the two disjoint shortest path problem in undirected graphs with non-negative edge lengths.
Wir untersuchen die Existenz, die Berechnung und die Qualität von (approximativen) reinen Nash Gleichgewichten in diskreten (Netzwerk-)Auslastungsspielen mit steigenden und fallenden Kostenfunktionen. Für gewichtete Spiele mit steigenden Kostenfunktionen zeigen wir untere Schranken an die Nicht-Existenz von approximativen Gleichgewichten. In Broadcast-Netzwerk-Spielen mit fallenden Kostenfunktionen beschränken wir den Price of Stability. Schließlich entwickeln wir einen Algorithmus zur Berechnung zweier disjunkter kürzester Pfade in ungerichteten Graphen mit nicht-negativen Kantenlängen.