CSpace  > 应用数学研究所
The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler
Chen, Xujin1,2; Hu, Xiaodong1,2; Wang, Chenhao1,2,3; Wu, Xiaoying1,2
2020-10-24
Source PublicationTHEORETICAL COMPUTER SCIENCE
ISSN0304-3975
Volume838Pages:180-194
AbstractWe study the efficiency of Nash equilibria for the load balancing game with a randomizing scheduler. In the game, we are given a set of facilities and a set of players along with a scheduler, where each facility is associated with a linear cost function, and the players are randomly ordered by the scheduler. Each player chooses exactly one of these facilities to fulfill his task, which incurs to him a cost depending on not only the cost function of the facility he chooses and the players who choose the same facility (as in a usual load balancing game), but also his uncertain position in the uniform random ordering. From an individual perspective, each player tries to choose a facility for optimizing his own objective that is determined by a certain decision-making principle. From a system perspective, it is desirable to minimize the maximum cost among all players, which is a commonly used criterion for load balancing. We estimate the price of anarchy and price of stability for this class of load balancing games under uncertainty, provided all players follow one of the four decision-making principles, namely the bottom-out, win-or-go-home, minimum-expected-cost, and minimax-regret principles. Our results show that the efficiency loss of Nash equilibria in these decentralized environments heavily rely on player's attitude toward the uncertainty. (C) 2020 Elsevier B.V. All rights reserved.
KeywordLoad balancing game Price of anarchy Price of stability Decision-making principle Nash equilibrium
DOI10.1016/j.tcs.2020.07.024
Indexed BySCI
Language英语
Funding ProjectMOST of China[2018AAA0101002] ; NNSF of China[11531014] ; CAS[ZDBS-LY7008]
WOS Research AreaComputer Science
WOS SubjectComputer Science, Theory & Methods
WOS IDWOS:000566368800014
PublisherELSEVIER
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/52082
Collection应用数学研究所
Corresponding AuthorWu, Xiaoying
Affiliation1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
2.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
3.City Univ Hong Kong, Hong Kong, Peoples R China
Recommended Citation
GB/T 7714
Chen, Xujin,Hu, Xiaodong,Wang, Chenhao,et al. The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler[J]. THEORETICAL COMPUTER SCIENCE,2020,838:180-194.
APA Chen, Xujin,Hu, Xiaodong,Wang, Chenhao,&Wu, Xiaoying.(2020).The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler.THEORETICAL COMPUTER SCIENCE,838,180-194.
MLA Chen, Xujin,et al."The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler".THEORETICAL COMPUTER SCIENCE 838(2020):180-194.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Chen, Xujin]'s Articles
[Hu, Xiaodong]'s Articles
[Wang, Chenhao]'s Articles
Baidu academic
Similar articles in Baidu academic
[Chen, Xujin]'s Articles
[Hu, Xiaodong]'s Articles
[Wang, Chenhao]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Chen, Xujin]'s Articles
[Hu, Xiaodong]'s Articles
[Wang, Chenhao]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

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