Tighter price of anarchy for selfish task allocation on selfish machines. (English) Zbl 1502.90071
Summary: Given a set \(L = \{J_1,J_2,\ldots, J_n\}\) of \(n\) tasks and a set \(M = \{M_1,M_2,\ldots,M_m\}\) of \(m\) identical machines, in which tasks and machines are possessed by different selfish clients. Each selfish client of machine \(M_i \in M\) gets a profit equal to its load and each selfish client of task allocated to \(M_i\) suffers from a cost equal to the load of \(M_i\). Our aim is to allocate the tasks on the \(m\) machines so as to minimize the maximum completion times of the tasks on each machine. A stable allocation is referred to as a dual equilibrium (DE). We firstly show that 4/3 is tight upper bound of the Price of Anarchy(PoA) with respect to dual equilibrium for \(m\in \{3,\ldots,9\}\). And secondly \((7m-6)/(5m-3)\) is an upper bound for \(m\geq 10\). The result is better than the existing bound of 7/5.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 91A10 | Noncooperative games |
| 91A80 | Applications of game theory |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Andelman, N.; Azar, Y.; Sorani, M., Truthful approximation mechanisms for scheduling selfish related machines, Theory Comput Syst, 40, 423-436 (2007) · Zbl 1121.68017 · doi:10.1007/s00224-006-1316-9 |
| [2] | Chen, B.; Gürel, S., Efficiency analysis of load balancing games with and without activation costs, J Sched, 15, 2, 157-164 (2012) · Zbl 1280.91095 · doi:10.1007/s10951-011-0247-8 |
| [3] | Chen, X.; Hu, X.; Ma, W.; Wang, C., Reducing price of anarchy of selfish task allocation with more selfishness, Theor Comput Sci, 507, 17-33 (2013) · Zbl 1302.91043 · doi:10.1016/j.tcs.2013.02.019 |
| [4] | Christodoulou, G.; Gourvès, L.; Pascual, F., Scheduling Selfish Tasks: About the Performance of Truthful Algorithms, Computing and Combinatorics: 13th Annual International Conference, COCOON 2007, LNCS 4598, 187-197 (2007), Berlin: Springer-Verlag, Berlin · Zbl 1206.90041 · doi:10.1007/978-3-540-73545-8_20 |
| [5] | Finn, G.; Horowitz, E., A linear time approximation algorithm for multiprocessor scheduling, BIT Numer Math, 19, 312-320 (1979) · Zbl 0413.68038 · doi:10.1007/BF01930985 |
| [6] | Garey, MR; Johnson, DS, Computers and intractabilities: a guide to the theory of NP-completeness (1979), New York: W. H. Freeman, New York · Zbl 0411.68039 |
| [7] | Graham, RL, Bounds on multiprocessing timing anomalies, SIAM J Appl Math, 17, 416-429 (1969) · Zbl 0188.23101 · doi:10.1137/0117039 |
| [8] | Hochbaum, DS; Shmoys, DB, Using dual approximation algorithms for scheduling problems: theoretical and practical results, J ACM, 34, 1, 144-162 (1987) · doi:10.1145/7531.7535 |
| [9] | Hung, HC; Lin, BMT; Posner, ME; Wei, J., Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs, J Sched, 22, 413-431 (2019) · Zbl 1434.90059 · doi:10.1007/s10951-018-0584-y |
| [10] | Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. In: STACS’99, LNCS vol 1563, pp 404-413 · Zbl 1099.91501 |
| [11] | Li, R.; Cheng, X.; Zhou, Y., Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines, Optim J Math Program Op Res, 63, 6, 867-882 (2014) · Zbl 1311.90050 |
| [12] | Lin, L.; Tan, Z., Inefficiency of Nash equilibrium for scheduling games with constrained jobs: aparametric analysis, Theor Comput Sci, 521, 2, 123-134 (2014) · Zbl 1307.91014 · doi:10.1016/j.tcs.2013.11.012 |
| [13] | Nisan, N.; Ronen, A., Algorithmic mechanism design, Games Econ Behav, 35, 166-196 (2001) · Zbl 0996.68251 · doi:10.1006/game.1999.0790 |
| [14] | Shulgina, ON; Shcherbakova, NK, About one algorithm for solving scheduling problem, Lobachevskii J Math, 36, 2, 211-214 (2015) · Zbl 1328.90059 · doi:10.1134/S1995080215020171 |
| [15] | Xie, F.; Zhang, Y.; Bai, Q., Inefficiency analysis of the scheduling game on limited identical machines with activation costs, Inf Process Lett, 116, 4, 316-320 (2016) · Zbl 1348.90327 · doi:10.1016/j.ipl.2015.10.006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
