Please use this identifier to cite or link to this item:
Title: Further Results on Capacitated Network Design Games
Authors: Erlebach, Thomas
Radoja, Matthew
First Published: 28-Sep-2015
Presented at: SAGT 2015, Saarbrücken
Start Date: 28-Sep-2015
End Date: 30-Sep-2015
Publisher: Springer
Citation: Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT 2015), Lecture Notes in Computer Science 9347, pp. 57–68, 2015
Abstract: 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.
DOI Link: 10.1007/978-3-662-48433-3_5
ISSN: 0302-9743
ISBN: 978-3-662-48432-6
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Archived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper_37.pdfPost-review (final submitted)287.84 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.