The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 180-194 |
Journal / Publication | Theoretical Computer Science |
Volume | 838 |
Online published | 24 Jul 2020 |
Publication status | Published - 24 Oct 2020 |
Link(s)
Abstract
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.
Research Area(s)
- Decision-making principle, Load balancing game, Nash equilibrium, Price of anarchy, Price of stability
Citation Format(s)
The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler. / Chen, Xujin; Hu, Xiaodong; Wang, Chenhao et al.
In: Theoretical Computer Science, Vol. 838, 24.10.2020, p. 180-194.
In: Theoretical Computer Science, Vol. 838, 24.10.2020, p. 180-194.
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review