The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler
文献类型：期刊论文
| 作者 | Chen, Xujin2,3 ; Hu, Xiaodong2,3; Wang, Chenhao1,2,3; Wu, Xiaoying2,3
|
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2020-10-24 |
| 卷号 | 838页码:180-194 |
| 关键词 | Load balancing game Price of anarchy Price of stability Decision-making principle Nash equilibrium |
| ISSN号 | 0304-3975 |
| DOI | 10.1016/j.tcs.2020.07.024 |
| 英文摘要 | We 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. |
| 资助项目 | MOST of China[2018AAA0101002] ; NNSF of China[11531014] ; CAS[ZDBS-LY7008] |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000566368800014 |
| 出版者 | ELSEVIER |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/52081]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Wu, Xiaoying |
| 作者单位 | 1.City Univ Hong Kong, Hong Kong, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。