Top

Journal of Combinatorial Optimization

Published in:

01-11-2019

On the price of anarchy of two-stage machine scheduling games

Authors: Deshi Ye, Lin Chen, Guochuan Zhang

Published in: Journal of Combinatorial Optimization | Issue 3/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider a scheduling game, in which both the machines and the jobs are players. Machines are controlled by different selfish agents and attempt to maximize their workloads by choosing a scheduling policy among the given set of policies, while each job is controlled by a selfish agent that attempts to minimize its completion time by selecting a machine. Namely, this game was done in two-stage. In the first stage, every machine simultaneously chooses a policy from some given set of policies, and in the second stage, every job simultaneously chooses a machine. In this work, we use the price of anarchy to measure the efficiency of such equilibria where each machine is allowed to use one of the at most two policies. We provide nearly tight bounds for every combination of two deterministic scheduling policies with respect to two social objectives: minimizing the maximum job completion, and maximizing the minimum machine completion time.

previous article Big data driven urban railway planning: Shenzhen metro case study

next article An improved mechanism for selfish bin packing

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Ashlagi I, Tennenholtz M, Zohar A (2010) Competing schedulers. In: Proceedings of the 24th AAAI conference on artificial intelligence (AAAI), pp. 691–696

Azar Y, Jain K, Mirrokni V (2008) (Almost) optimal coordination mechanisms for unrelated machine scheduling. In: Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms (SODA), pp 323–332

Caragiannis I (2009) Efficient coordination mechanisms for unrelated machine scheduling. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 815–824

Chen X, Epstein L, Kleiman E, van Stee R (2013) Maximizing the minimum load: the cost of selfishness. Theoret Comput Sci 482:9–19MathSciNetCrossRef

Chen X, Hu X, Ma W, Wang C (2012) Efficiency of dual equilibria in selfish task allocation to selfish machines. In: Proceedings of the 6th international conference on combinatorial optimization and applications (COCOA), pp. 312–323

Christodoulou G, Koutsoupias E, Nanavati A (2004) Coordination mechanisms. In: Proceedings of the 31st international colloquium on automata, languages, and programming (ICALP), pp 45–56

Cohen J, Dürr C, Nguyen Kim T (2011) Non-clairvoyant scheduling games. Theory Comput Syst 1–21

Cole R, Correa JR, Gkatzelis V, Mirrokni V, Olver N (2011) Inner product spaces for minsum coordination mechanisms. In: Proceedings of the 43rd annual ACM symposium on theory of computing (STOC), pp 539–548

Deuermeyer BL, Friesen DK, Langston MA (1982) Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J Algebraic Discrete Methods 3(2):190–196MathSciNetCrossRef

Dobson G (1984) Scheduling independent tasks on uniform processors. SIAM J Comput 13:705–716MathSciNetCrossRef

Dubey P (1986) Inefficiency of Nash equilibria. Math Oper Res 11(1):1–8MathSciNetCrossRef

Epstein L, Kleiman E, Stee R (2009) Maximizing the minimum load: the cost of selfishness. In: Proceedings of the 5th international workshop on internet and network economics (WINE), pp 232–243

Epstein L, Kleiman E, Stee R (2014) The cost of selfishness for maximizing the minimum load on uniformly related machines. J Comb Optim 27(4):767–777MathSciNetCrossRef

Epstein L, Stee R (2012) The price of anarchy on uniformly related machines revisited. Inf Comput 212:37–54MathSciNetCrossRef

Fabrikant A, Luthra A, Maneva E, Papadimitriou C, Shenker S (2003) On a network creation game. In: ACM Symposium on principles of distributed computing (PODC), pp 347–351

Feldman M, Immorlica N, Lucier B, Roughgarden T, Syrgkanis V (2016) The price of anarchy in large games. In: Proceedings of the 48th annual ACM symposium on theory of computing (STOC), pp 963–976

Finn G, Horowitz E (1979) A linear time approximation algorithm for multiprocessor scheduling. BIT Numer Math 19(3):312–320MathSciNetCrossRef

Friesen DK (1987) Tighter bounds for LPT scheduling on uniform processors. SIAM J Comput 16:554–560MathSciNetCrossRef

Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell System Tech J 45:1563–1581CrossRef

Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17:263–269MathSciNetMATH

Heydenreich B, Müller R, Uetz M (2007) Games and mechanism design in machine scheduling—an introduction. Prod Oper Manag 16(4):437–454CrossRef

Hoeksma R, Uetz M (2011) The price of anarchy for minsum related machine scheduling. In: Proceedings of the 9th international conference on approximation and online algorithms (WAOA), pp 261–273

Immorlica N, Li LE, Mirrokni VS, Schulz AS (2009) Coordination mechanisms for selfish scheduling. Theor Comput Sci 410:1589–1598MathSciNetCrossRef

Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. In: Proceedings of the 16th symposium on theoretical aspects of computer science (STACS), pp 404–413

Lin L, Tan Z (2014) Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis. Theor Comput Sci 521:123–134MathSciNetCrossRef

Lucier B, Borodin A (2010) Price of anarchy for greedy auctions. In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms (SODA), pp 537–553

Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory. Cambridge University Press, Cambridge CrossRef

Roughgarden T, Tardos E (2004) Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ Behav 47(2):389–403MathSciNetCrossRef

Roughgarden T, Tardos E (2002) How bad is selfish routing? J ACM 49(2):236–259MathSciNetCrossRef

Tan Z, Wan L, Zhang Q, Ren W (2012) Inefficiency of equilibria for the machine covering game on uniform machines. Acta Inform 49(6):361–379MathSciNetCrossRef

Vetta AR (2002) Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions. In: Symposium on the foundations of computer science (FOCS), pp 416–425

Title: On the price of anarchy of two-stage machine scheduling games
Authors: Deshi Ye
Lin Chen
Guochuan Zhang
Publication date: 01-11-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2021
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00474-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2021

An improved algorithm for the -MaxSAT problem: asking branchings to satisfy the clauses

On the complexity and approximability of repair position selection problem

Improved algorithms for single vehicle scheduling on tree/cycle networks

Tropical paths in vertex-colored graphs

A spectral partitioning algorithm for maximum directed cut problem

Modified Greedy Heuristic for the one-dimensional cutting stock problem

Premium Partner