×

Scheduling games with machine-dependent priority lists. (English) Zbl 1435.90072

Caragiannis, Ioannis (ed.) et al., Web and Internet economics. 15th international conference, WINE 2019, New York, NY, USA, December 10–12, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11920, 286-300 (2019).
Summary: We consider a scheduling game in which jobs try to minimize their completion time by choosing a machine to be processed on. Each machine uses an individual priority list to decide on the order according to which the jobs on the machine are processed. We characterize four classes of instances in which a pure Nash equilibrium (NE) is guaranteed to exist, and show by means of an example, that none of these characterizations can be relaxed. We then bound the performance of Nash equilibria for each of these classes with respect to the makespan of the schedule and the sum of completion times. We also analyze the computational complexity of several problems arising in this model. For instance, we prove that it is NP-hard to decide whether a NE exists, and that even for instances with identical machines, for which a NE is guaranteed to exist, it is NP-hard to approximate the best NE within a factor of \(2-\frac{1}{m}-\epsilon\) for every \(\epsilon>0\).
In addition, we study a generalized model in which players’ strategies are subsets of resources, where each resource has its own priority list over the players. We show that in this general model, even unweighted symmetric games may not have a pure NE, and we bound the Price of Anarchy with respect to the total players’ costs.
For the entire collection see [Zbl 1429.91006].

MSC:

90B35 Deterministic scheduling theory in operations research
91A14 Potential and congestion games
91A80 Applications of game theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ackermann, H., Goldberg, P., Mirrokni, V.S., Röglin, H., Vöcking, B.: A unified approach to congestion games and two-sided markets. Internet Math. 5(4), 439-457 (2008) · Zbl 1194.91030 · doi:10.1080/15427951.2008.10129171
[2] Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602-1623 (2008) · Zbl 1173.91321 · doi:10.1137/070680096
[3] Awerbuch, B., Azar, Y., Richter, Y., Tsur, D.: Tradeoffs in worst-case equilibria. Theor. Comput. Sci. 361(2-3), 200-209 (2006) · Zbl 1097.68012 · doi:10.1016/j.tcs.2006.05.010
[4] Caragiannis, I., Gkatzelis, V., Vinci, C.: Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling. In: Devanur, N.R., Lu, P. (eds.) WINE 2017. LNCS, vol. 10660, pp. 74-87. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71924-5_6 · Zbl 1405.91015 · doi:10.1007/978-3-319-71924-5_6
[5] Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM J. Comput. 9(1), 91-103 (1980). https://doi.org/10.1137/0209007 · Zbl 0446.68025 · doi:103&publication_year=1980&doi=10.1137/0209007
[6] Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 345-357. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_31 · Zbl 1098.91079 · doi:10.1007/978-3-540-27836-8_31
[7] Cole, R., Correa, J., Gkatzelis, V., Mirrokni, V., Olver, N.: Decentralized utilitarian mechanisms for scheduling games. Games Econ. Behav. 92, 306-326 (2015) · Zbl 1356.91006 · doi:10.1016/j.geb.2013.03.011
[8] Marquis de Condorcet, M.J.A.: Essai sur l’application de l’analyse a la probabilite des decisions: rendues a la pluralite de voix. De l’Imprimerie royale (1785)
[9] Correa, J., Queyranne, M.: Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost. Naval Res. Logistics 59(5), 384-395 (2012) · Zbl 1407.90149 · doi:10.1002/nav.21497
[10] Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1), 4 (2007) · Zbl 1322.91017 · doi:10.1145/1186810.1186814
[11] Farzad, B., Olver, N., Vetta, A.: A priority-based model of routing. Chicago J. Theor. Comput. Sci. 1 (2008) · Zbl 1286.68227
[12] Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: Computing nash equilibria for scheduling on restricted parallel links. Theory Comput. Syst. 47(2), 405-432 (2010) · Zbl 1203.90064 · doi:10.1007/s00224-009-9191-9
[13] Gourvès, L., Monnot, J., Moretti, S., Thang, N.K.: Congestion games with capacitated resources. Theory Comput. Syst. 57(3), 598-616 (2015) · Zbl 1327.91041 · doi:10.1007/s00224-014-9541-0
[14] Graham, R.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563-1581 (1966) · Zbl 0168.40703 · doi:10.1002/j.1538-7305.1966.tb01709.x
[15] Hoeksma, R., Uetz, M.: The price of anarchy for utilitarian scheduling games on related machines. Discrete Optim. 31, 29-39 (2019) · Zbl 1506.90103 · doi:10.1016/j.disopt.2018.08.001
[16] Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM (JACM) 24(2), 280-289 (1977) · Zbl 0382.90048 · doi:10.1145/322003.322011
[17] Immorlica, N., Li, L.E., Mirrokni, V., Schulz, A.: Coordination mechanisms for selfish scheduling. Theor. Comput. Sci. 410(17), 1589-1598 (2009) · Zbl 1172.90004 · doi:10.1016/j.tcs.2008.12.032
[18] Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37(1), 27-35 (1991) · Zbl 0711.68045 · doi:10.1016/0020-0190(91)90246-E
[19] Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404-413. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_38 · Zbl 1099.91501 · doi:10.1007/3-540-49116-3_38
[20] Piliouras, G., Nikolova, E., Shamma, J.S.: Risk sensitivity of price of anarchy under uncertainty. ACM Trans. Econo. Comput. 5, 5-27 (2016)
[21] Rosenthal, R.: A class of games possessing pure-strategy nash equilibria. Int. J. Game Theory 2(1), 65-67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[22] Roughgarden, T.: Intrinsic robustness of the price of anarchy. J. ACM 62(5), 32 (2015) · Zbl 1427.91015 · doi:10.1145/2806883
[23] Smith, W.E.: Various optimizers for single-stage production. Naval Res. Logistics Q. 3(1-2), 59-66 (1956) · doi:10.1002/nav.3800030106
[24] Vöcking, B.
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.