Chen, Bo, Dr. and Gürel, Sinan. (2012) Efficiency analysis of load balancing games with and without activation costs. Journal of Scheduling, Vol.15 (No.2). pp. 157-164. ISSN 1094-6136

Preview

Text WRAP_Chen_9471193-wbs-111111-preprint_josh_paper.pdf - Accepted Version Download (331Kb)

Abstract

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.

[error in script] [error in script]

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH):	Resource allocation -- Mathematical models, Game theory
Journal or Publication Title:	Journal of Scheduling
Publisher:	Springer New York LLC
ISSN:	1094-6136
Date:	November 2012
Volume:	Vol.15
Number:	No.2
Page Range:	pp. 157-164
Identification Number:	10.1007/s10951-011-0247-8
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
References:	[1] S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppmann. Exact price of anarchy for polynomial congestion games. In B. Duran and W. Thomas, editors, Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, LNCS 3884, pages 218{229, Berlin, February 2006. Springer-Verlag. [2] E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T.Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602{1623, 2008. [3] B. Awerbuch, Y. Azar, and A. Epstein. The price of routing unsplittable ow. In 37th ACM Symposium on Theory of Computing, pages 57{66, Baltimore, MD, USA, 22{24 May 2005. [4] P. Berenbrink, L.A. Goldberg, P.W. Goldberg, and R. Martin. Utilitarian resource assignment. Journal of Discrete Algorithms, 4:567{587, 2006. [5] A. Czumaj. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Chap. 42, Selfish Routing on the Internet, pages 517{542. CRC Press, Boca Raton, FL, USA, 2004. [6] A. Czumaj and B. Vöcking. Tight bounds for the worst-case equilibria. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 413{420, Philadelphia, PA, USA, 2002. ACM-SIAM. [7] U. Endriss, N. Maudet, F. Sadri, and F. Toni. On optimal outcomes of negotiations over resources. In The 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 177{184, Melbourne, Australia, 2003. [8] A. Epstein, M. Feldman, and Y. Mansour. Strong equilibrium in cost sharing connection games. In EC '07: Proceedings of the 8th ACM conference on Electronic commerce, pages 84{92, New York, NY, USA, 2007. ACM. [9] J. Feigenbaum, C. H. Papadimitriou, and S. Shenker. Sharing the cost of multicast transmissions. Journal of Computer and System Sciences, 63(1):21{41, 2001. [10] M. Feldman and T. Tamir. Con icting congestion effects in resource allocation games. In G. Goos, J. Hartmanis, and J. van Leeuwen, editors, Proceedings of the 4th International Workshop on Internet and Network Economics, LNCS 5385, pages 109{117, Berlin, Heidelberg, December 2008. Springer-Verlag. [11] M. Gairing, T. Lucking, M. Mavronicolas, B. Monien, and M. Rode. Nash equilibria in discrete routing games with convex latency functions. Journal of Computer and System Sciences, 74:1199{1225, 2008. [12] M. Gairing, B. Monien, and K. Tiemann. Selfish routing with incomplete information. Theory of Computing Systems, 42:91{130, 2008. [13] M. Gairing and F. Scoppmann. Total latency in singleton congestion games. In X. Deng and F.C. Graham, editors, Proceedings of the 3rd Workshop on Internet and Network Economics (WINE 2007), LNCS 4858,, pages 381{387, Berlin, Heidelberg, December 2007. Springer-Verlag. [14] B. Heydenreich, R. Muller, and M. Uetz. Games and mechanism design in machine scheduling{an introduction. Production and Operations Management, 16(4):437{454, 2007. [15] M. Hoefer and A. Souza. Tradeoffs and average-case equilibria in selfish routing. ACM Transactions on Computation Theory. To appear. [16] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In G. Goos, J. Hartmanis, and J. van Leeuwen, editors, Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science, LNCS 1563, pages 404{413, Berlin, May 1999. Springer-Verlag. [17] T. Lucking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish routing. Theor. Comput. Sci., 406(3):187{206, 2008. [18] P. McBurney, S. Parsons, and M. Wooldridge. Desiderata for argumentation protocols. In The 1st International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 402{409, Bologna, Italy, 2002. [19] C. Papadimitriou. Algorithms, games, and the internet. In Proc. 33rd ACM Symposium on Theory of Computing, pages 749{753. ACM Press, 2001. [20] T. Roughgarden. Intrinsic robustness of the price of anarchy. In STOC '09: Proceedings of the 41st annual ACM symposium on Theory of computing, pages 513{522, New York, NY, USA, 2009. ACM. [21] T. Roughgarden and E. Tardos. How bad is selfish routing? J. ACM, 49(2):236{ 259, 2002. [22] T.W. Sandholm. Contract types for satisficing task allocation: I theoretical results. In The AAAI Spring Symposium: Satisficing Models, Palo Alto, California, USA, 1998. [23] B. Vöcking. Algorithmic Game Theory, chapter Selfish Load Balancing, pages 517{542. Cambridge University Press, 2007.
URI:	http://wrap.warwick.ac.uk/id/eprint/39042

Request changes to a record

Actions (login required)

View Item