Please use this identifier to cite or link to this item:
Title: The Price of Anarchy for Selfish Ring Routing is Two
Authors: Chen, Xujin
Doerr, Benjamin
Doerr, Carola
Hu, Xiaodong
Ma, Weidong
van Stee, Rob
First Published: Jun-2014
Publisher: Association for Computing Machinery (ACM)
Citation: ACM Trans. Economics and Comput., 2014, 2, pp. 8-8
Abstract: We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. This important social cost function is much less understood than the average latency. We show that the price of anarchy is at most two, when the network is a ring and the link latencies are linear. Our bound is tight. This is the first sharp bound for the maximum latency objective.
DOI Link: 10.1145/2548545
ISSN: 2167-8375
eISSN: 2167-8383
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2014, Association for Computing Machinery (ACM). Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Description: © ACM, 2014. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Economics and Computation archive Volume 2 Issue 2, June 2014
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
RingRouting.pdfPost-review (final submitted)249.76 kBUnknownView/Open

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