Show simple item record

dc.contributor.authorAyesta, U.
dc.contributor.authorBrun, O.
dc.contributor.authorPrabhu, B.J.
dc.date.accessioned2017-02-21T08:11:14Z
dc.date.available2017-02-21T08:11:14Z
dc.date.issued2011-12-31
dc.identifier.issn0166-5316
dc.identifier.urihttp://hdl.handle.net/20.500.11824/374
dc.description.abstractWe investigate the price of anarchy of a load balancing game with K dispatchers. The service rates and holding costs are assumed to depend on the server, and the service discipline is assumed to be processor-sharing at each server. The performance criterion is taken to be the weighted mean number of jobs in the system, or equivalently, the weighted mean sojourn time in the system. Independent of the state of the servers, each dispatcher seeks to determine the routing strategy that optimizes the performance for its own traffic. The interaction of the various dispatchers thus gives rise to a non-cooperative game. For this game, we first show that, for a fixed amount of total incoming traffic, the worst-case Nash equilibrium occurs when each player routes exactly the same amount of traffic, i.e., when the game is symmetric. For this symmetric game, we provide the expression for the loads on the servers at the Nash equilibrium. Using this result, we then show that, for a system with two or more servers, the price of anarchy, which is the worst-case ratio of the global cost of the Nash equilibrium to the global cost of the centralized setting, is lower bounded by K(2√K-1) and upper bounded by √K, independent of the number of servers.
dc.formatapplication/pdf
dc.language.isoengen_US
dc.rightsReconocimiento-NoComercial-CompartirIgual 3.0 Españaen_US
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/3.0/es/en_US
dc.subjectAtomic games
dc.subjectLoad balancing
dc.subjectPrice of anarchy
dc.subjectProcessor sharing
dc.titlePrice of anarchy in non-cooperative load balancing games
dc.typeinfo:eu-repo/semantics/articleen_US
dc.identifier.doi10.1016/j.peva.2011.08.002
dc.relation.publisherversionhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-80054866027&doi=10.1016%2fj.peva.2011.08.002&partnerID=40&md5=694fba5b58046ce37d85857d05c87232
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessen_US
dc.type.hasVersioninfo:eu-repo/semantics/publishedVersionen_US
dc.journal.titlePerformance Evaluationen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Reconocimiento-NoComercial-CompartirIgual 3.0 España
Except where otherwise noted, this item's license is described as Reconocimiento-NoComercial-CompartirIgual 3.0 España