paper_37.pdf (287.84 kB)
Further Results on Capacitated Network Design Games
conference contributionposted on 2015-07-22, 16:29 authored by Thomas Erlebach, Matthew Radoja
In a capacitated network design game, each of n players selects a path from her source to her sink. The cost of each edge is shared equally among the players using the edge. Every edge has a finite capacity that limits the number of players using the edge. We study the price of stability for such games with respect to the max-cost objective, i.e., the maximum cost paid by any player. We show that the price of stability is O(n) for symmetric games, and this bound is tight. Furthermore, we show that the price of stability for asymmetric games can be Ω(n log n), matching the previously known upper bound. We also prove that the convergence time of best response dynamics cannot be bounded by any function of n.
CitationProceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT 2015), Lecture Notes in Computer Science 9347, pp. 57–68, 2015
Author affiliation/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science
SourceSAGT 2015, Saarbrücken
- AM (Accepted Manuscript)