Abstract
In this paper, we study the scheduling game with machine activation costs. A set of jobs is to be processed on identical parallel machines. The number of machines available is unlimited, and an activation cost is needed whenever a machine is activated in order to process jobs. Each job chooses a machine on which it wants to be processed. The cost of a job is the sum of the load of the machine it chooses and its shared activated cost. The social cost is the total cost of all jobs. Representing PoA as a function of the number of jobs, we get the tight bound of PoA. Representing PoA as a function of the smallest processing time of jobs, improved lower and upper bound are also given.
Supported by the National Natural Science Foundation of China (10971191, 11271324), Zhejiang Provincial Natural Science Foundation of China (LR12A01001) and Fundamental Research Funds for the Central Universities.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Berenbrink, P., Goldberg, L., Goldberg, P., Martin, R.: Utilitarian resource assignment. Journal of Discrete Algorithm 4, 567–587 (2006)
Chen, B., Gürel, S.: Resource allocation games of utilitarian social objectives. Journal of Scheduling 15, 157–164 (2012)
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Transactions on Algorithms 3(4) (2007)
Epstein, L.: Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy. Acta Informatica 47, 375–389 (2010)
Epstein, L., van Stee, R.: The price of anarchy on uniformly related machines revisited. Information and Computation 212, 37–54 (2012)
Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Nashification and the coordination ratio for a selfish routing game. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 514–526. Springer, Heidelberg (2003)
Feldman, M., Tamir, T.: Conflicting congestion effects in resource allocation games. Operations Research 60, 529–540 (2012)
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. Theoretical Computer Science 410, 3305–3326 (2009)
Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Computer Science Review 3, 65–69 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Lin, L., Yan, Y., He, X., Tan, Z. (2014). The PoA of Scheduling Game with Machine Activation Costs. In: Chen, J., Hopcroft, J.E., Wang, J. (eds) Frontiers in Algorithmics. FAW 2014. Lecture Notes in Computer Science, vol 8497. Springer, Cham. https://doi.org/10.1007/978-3-319-08016-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-08016-1_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08015-4
Online ISBN: 978-3-319-08016-1
eBook Packages: Computer ScienceComputer Science (R0)