Efficiency analysis of load balancing games with and without activation costs

被引:26
作者
Chen, Bo [1 ,2 ]
Gurel, Sinan [1 ,3 ]
机构
[1] Univ Warwick, Warwick Business Sch, Ctr Discrete Math & Its Applicat DIMAP, Coventry CV4 7AL, W Midlands, England
[2] Qufu Normal Univ, Qingdao 273165, Shandong, Peoples R China
[3] Middle E Tech Univ, Dept Ind Engn, TR-06800 Ankara, Turkey
关键词
Resource allocation game; Congestion cost; Load balancing; Cost sharing; Price of anarchy; Price of stability; LATENCY; DESIGN; PRICE;
D O I
10.1007/s10951-011-0247-8
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
In this paper, we study two models of resource allocation games: the classical load-balancing game and its new variant involving resource activation costs. The resources we consider are identical and the social costs of the games are utilitarian, which are the average of all individual players' costs. Using the social costs we assess the quality of pure Nash equilibria in terms of the price of anarchy (PoA) and the price of stability (PoS). For each game problem, we identify suitable problem parameters and provide a parametric bound on the PoA and the PoS. In the case of the load-balancing game, the parametric bounds we provide are sharp and asymptotically tight.
引用
收藏
页码:157 / 164
页数:8
相关论文
共 22 条
  • [1] Aland S, 2006, LECT NOTES COMPUT SC, V3884, P218
  • [2] [Anonymous], 1 INT JOINT C AUT AG
  • [3] [Anonymous], 13 ANN ACM SIAM S DI
  • [4] [Anonymous], HDB SCHEDULING ALGOR
  • [5] [Anonymous], ACM T COMPU IN PRESS
  • [6] [Anonymous], 2 INT JOINT C AUT AG
  • [7] [Anonymous], 37 ACM S THEOR COMP
  • [8] THE PRICE OF STABILITY FOR NETWORK DESIGN WITH FAIR COST ALLOCATION
    Anshelevich, Elliot
    Dasgupta, Anirban
    Kleinberg, Jon
    Tardos, Eva
    Wexler, Tom
    Roughgarden, Tim
    [J]. SIAM JOURNAL ON COMPUTING, 2008, 38 (04) : 1602 - 1623
  • [9] Utilitarian resource assignment
    Berenbrink, Petra
    Goldberg, Leslie Ann
    Goldberg, Paul W.
    Martin, Russell
    [J]. JOURNAL OF DISCRETE ALGORITHMS, 2006, 4 (04) : 567 - 587
  • [10] Epstein A, 2007, EC'07: PROCEEDINGS OF THE EIGHTH ANNUAL CONFERENCE ON ELECTRONIC COMMERCE, P84