Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorErlebach, Thomas-
dc.contributor.authorRadoja, Matthew-
dc.contributor.editorHoefer, M.-
dc.identifier.citationProceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT 2015), Lecture Notes in Computer Science 9347, pp. 57–68, 2015en
dc.description.abstractIn 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.en
dc.rightsArchived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via
dc.titleFurther Results on Capacitated Network Design Gamesen
dc.typeConference Paperen
dc.description.presentedSAGT 2015, Saarbrückenen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERINGen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Scienceen
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.