The Price of Anarchy for Selfish Ring Routing is Two
journal contribution
posted on 2015-06-01, 14:53 authored by Xujin Chen, Benjamin Doerr, Carola Doerr, Xiaodong Hu, Weidong Ma, Rob van SteeWe 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.
History
Citation
ACM Trans. Economics and Comput., 2014, 2, pp. 8-8Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer ScienceVersion
- AM (Accepted Manuscript)
Published in
ACM Trans. Economics and Comput.Publisher
Association for Computing Machinery (ACM)issn
2167-8375eissn
2167-8383Copyright date
2014Available date
2015-06-01Publisher DOI
Publisher version
http://dl.acm.org/citation.cfm?doid=2632259.2548545Notes
© 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 http://doi.acm.org/10.1145/2548545Language
enAdministrator link
Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC