Contributed Session Fri.2.MA 043

Friday, 13:15 - 14:45 h, Room: MA 043

Cluster 8: Game theory [...]

Equilibria in congestion games


Chair: Max Klimm



Friday, 13:15 - 13:40 h, Room: MA 043, Talk 1

Philipp von Falkenhausen
Optimal cost sharing protocols for matroid congestion games

Coauthor: Tobias Harks


We study the design of cost sharing protocols for weighted congestion games where the strategy spaces are either singletons or bases of a matroid. Our design goal is to devise protocols so as to minimize the resulting Price of Anarchy (PoA) and Price of Stability (PoS). We investigate three classes of protocols: basic protocols guarantee the existence of a pure Nash equilibrium, separable protocols additionally work with locally incomplete information on the players' choices, uniform protocols additionally even work with locally incomplete information on the available resources. For singleton games, we prove that among all basic and separable protocols, there is an optimal separable protocol minimizing the resulting PoS and PoA simultaneously at the value of Hn=∑i=1n 1/i for n-player games. For matroid games, we show again an optimal basic protocol yielding the nth harmonic number Hn for PoS and PoA. For separable protocols and matroids, however, we find a structural difference when minimizing the PoA: we devise an optimal separable protocol with PoA of n. For uniform protocols we show that the PoA is unbounded even for singleton games.



Friday, 13:45 - 14:10 h, Room: MA 043, Talk 2

Thomas Pradeau
Uniqueness of equilibrium on rings

Coauthor: Frédéric Meunier


We consider congestion games on networks with nonatomic users in the multiclass case, i.e., when the cost functions are not the same for all users. We are interested in the uniqueness property defined by Milchtaich [Milchtaich, I. 2005. Topological conditions for uniqueness of equilibrium in networks. Math. Oper. Res. {30}, 225-244] as the uniqueness of equilibrium flows for all assignments of strictly increasing cost functions. He settled the case of two-terminal networks.
In the present work, we characterize completely bidirectional rings for which the uniqueness property holds. The main result is that it holds precisely for five networks and those obtained from them by elementary operations. For other bidirectional rings, we exhibit affine cost functions yielding to two distinct equilibrium flows. We derive moreover nontrivial corollaries concerning the uniqueness property for general networks.



Friday, 14:15 - 14:40 h, Room: MA 043, Talk 3

Max Klimm
Existence and computation of equilibria in bottleneck congestion games

Coauthors: Tobias Harks, Martin Hoefer, Alexander Skopalik


Congestion games are an elegant and well studied model to investigate the effects of resource allocations by selfish agents. In a congestion game each player chooses a subset of resources and her private cost is the sum of the costs of the chosen resources. While the existence of equilibria as well as the complexity of their computation for this class of games is relatively well understood, much less is known for bottleneck congestion games. Here, the private cost of each player equals the maximum cost of all chosen resources. This class of games is motivated by data routing applications where the total delay of a user is closely related to the performance of the weakest link. We show that bottleneck congestion games always admit a pure strong equilibrium - a strengthening of the pure Nash equilibrium concept that is even resilient against coordinated deviations of coalitions of players. Further, we discuss cases, in which strong equilibria can be computed efficiently as well as related hardness results.


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.