About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
1st International ICST Workshop on Game Theory for Networks

Research Article

On the price of anarchy in unbounded delay networks

Cite
BibTeX Plain Text
  • @INPROCEEDINGS{10.1145/1190195.1190210,
        author={Tao  Wu and David  Starobinski},
        title={On the price of anarchy in unbounded delay networks},
        proceedings={1st International ICST Workshop on Game Theory for Networks},
        publisher={ACM},
        proceedings_a={GAMENETS},
        year={2012},
        month={4},
        keywords={},
        doi={10.1145/1190195.1190210}
    }
    
  • Tao Wu
    David Starobinski
    Year: 2012
    On the price of anarchy in unbounded delay networks
    GAMENETS
    ACM
    DOI: 10.1145/1190195.1190210
Tao Wu1,*, David Starobinski2,*
  • 1: Nokia Research Center, Cambridge, Massachusetts, USA
  • 2: Boston University, Boston, Massachusetts, USA
*Contact email: tao.a.wu@nokia.com, staro@bu.edu

Abstract

We investigate the worst case delay ratio between the Nash equilibrium and the social optimum in networks of N parallel links (routes) with unbounded delay functions. We compute this ratio, known as the "price of anarchy", for the case when the link delay functions correspond to M/M/ 1-FCFS or M/G/ 1-PS. For this problem, we find that the price of anarchy depends on the network topology in the sense that it is precisely equal to N. We then extend our results to M/G/ 1-FCFS and G/G/ 1-FCFS delay functions and compute the price of anarchy in a heavy load regime. Our results indicate that, even in very simple topological settings, the price of selfish behavior can potentially be very high.

Published
2012-04-04
Publisher
ACM
http://dx.doi.org/10.1145/1190195.1190210
Copyright © 2006–2025 ACM
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL