Chen, Bo, Dr. and Gürel, Sinan (2009) Resource allocation games of various social objectives. Journal of Scheduling . ISSN 1094-6136

PDF WRAP_Chen_9471193-wbs-291209-resource_allocation.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (220Kb)

Abstract

In this paper, we study resource allocation games of two different cost components for individual game players and various social costs. The total cost of each individual player consists of the congestion cost, which is the same for all players sharing the same resource, and resource activation cost, which is proportional to the individual usage of the resource. The social costs we consider are, respectively, the total of costs of all players and the maximum congestion cost plus total resource activation cost. Using the social costs we assess the quality of Nash equilibria in terms of the price of anarchy (PoA) and the price of stability (PoS). For each problem, we identify one or two problem parameters and provide parametric bounds on the PoA and PoS. We show that they are unbounded in general if the parameter involved are not restricted.

Item Type:	Submitted Journal Article
Subjects:	Q Science > QA Mathematics H Social Sciences > HM Sociology
Divisions:	Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH):	Resource allocation -- Mathematical models, Nash manifolds, Equilibrium (Economics), Game theory
Journal or Publication Title:	Journal of Scheduling
Publisher:	Springer New York LLC
ISSN:	1094-6136
Date:	10 July 2009
Status:	Peer Reviewed
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 Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, LNCS 3884, pages 218{229. Springer-Verlag, February 2006. [2] E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T.Wexler, and T. Rough-garden. 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 flow. In Proceedings of the 37th ACM Symposium on Theory of Computing, pages 57{66. ACM, May 2005. [4] G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 67{73. ACM, May 2005. [5] A. Czumaj. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Selfish Routing on the Internet, pages 517{542. CRC Press, Boca Raton, FL, USA, 2004. [6] A. Epstein, M. Feldman, and Y. Mansour. Strong equilibrium in cost sharing connection games. In Proceedings of the 8th ACM Conference on Electronic Commerce, pages 84{92. ACM, 2007. [7] 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. [8] M. Feldman and T. Tamir. Conflicting congestion effects in resource allocation games. In Proceedings of the 4th International Workshop on Internet and Network Economics, LNCS 5385, pages 109{117. Springer-Verlag, December 2008. [9] M. Gairing, T. Lücking, M. Mavronicolas, B. Monien, and M. Rodea. Nash equilibria in discrete routing games with convex latency functions. Journal of Computer and System Sciences, 74:1199{1225, 2008. [10] B. Heydenreich, R. Müller, and M. Uetz. Games and mechanism design in machine scheduling{an introduction. Production and Operations Management, 16(4):437{454, 2007. [11] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science, LNCS 1563, pages 404{413. Springer-Verlag, May 1999. [12] T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish routing. Theoretical Computer Science, 406(3):187{206, 2008. [13] C. Papadimitriou. Algorithms, games, and the Internet. In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 749{753. ACM Press, 2001. [14] S. Suri, C.D. T¶oth, and Y. Zhou. Selfish load balancing and atomic congestion games. Algorithmica, 47:79{96, 2007. [15] 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/2524

Request changes to a record

Actions (login required)

View Item