Stackelberg strategies for weighted load balancing games

• Autorzy: Stein Neta , Tamir Tami

Identyfikatory

DOI

10.15439/2022F52

• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

An instance of a weighted Stackelberg load balancing game is given by a set of identical machines, a set of variable-length jobs and a parameter 0 ≤ α ≤ 1. A centralized authority, denoted the leader, selects a subset of the jobs whose total length is at most an α-fraction of the total length and determines their assignment on the machines. After the controlled jobs are assigned, the remaining jobs join the schedule. They act selfishly, each determining its own assignment. Our work combines theoretical and experimental results for this setting. We suggest various heuristics for the leader and analyze their performance.

Słowa kluczowe

EN

computer science; schedule; cost; np-hard problem; game; load management; approximation algorithm

PL

informatyka; harmonogram; koszt; gra; zarządzanie obciążeniem

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 373--382
• Opis fizyczny: Bibliogr. 21 poz., wykr., wz.

Twórcy

autor

Stein Neta

• School of Computer Science Reichman University (IDC) Herzliya, Israel

autor

Tamir Tami

• School of Computer Science Reichman University (IDC) Herzliya, Israel

Bibliografia

• 1. E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602–1623, 2008.
• 2. V. Bonifaci, T. Harks, and G. Schäfer. Stackelberg Routing in Arbitrary Networks. Mathematics of Operations Research, 35(2), 330–346, 2010.
• 3. V. Bilò and C. Vinci. On stackelberg strategies in affine congestion games. Theory of Computing Systems, 63(6):1228–1249, 2019.
• 4. Y. Cho and S. Sahni. Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9(1):91–103, 1980.
• 5. A. Czumaj and B. Vöcking. Tight bounds for worst-case equilibria. ACM Trans. Algorithms, 3(1):4:1–4:17, 2007.
• 6. L. Epstein and J. Sgall. Approximation schemes for scheduling on uniformly related and identical parallel machines. In Proc. of the 7th European Symposium on Algorithms(ESA), 1999.
• 7. G. Finn and E. Horowitz. A linear time approximation algorithm for multiprocessor scheduling. BIT Numerical Mathematics, 19(3):312–320, 1979.
• 8. D. Fotakis. Stackelberg strategies for atomic congestion games. Theory of Computing Systems, 47(1):218–249, 2010.
• 9. M.R. Garey and R.L. Graham. Bounds for Multiprocessor Scheduling with Resource Constraints. SIAM J. J. Comput., 4(2): 187–200, 1975.
• 10. R.L. Graham. Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal, 45:1563–1581, 1966.
• 11. R.L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math., 17:263–269, 1969.
• 12. D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems: Practical and theoretical results. Journal of the ACM, 34(1):144–162, 1987.
• 13. S. G Karakostas, G. Kolliopoulos. Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica, 2009.
• 14. H. Kellerer and U. Pferschy. Cardinality constrained bin-packing problems. Annals of Operations Research, 92:335–349, 1999.
• 15. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. STACS, pages 404–413, 1999
• 16. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65–69, 2009.
• 17. VS A. Kumar and M. V Marathe. Improved results for stackelberg scheduling strategies. In International Colloquium on Automata, Languages, and Programming (ICALP), 2002.
• 18. T. Roughgarden. Stackelberg scheduling strategies. SIAM Journal on Computing, 33(2):332–350, 2004.
• 19. P. M. Swamidass (Eds.), Exponential service times. In Encyclopedia of Production and Manufacturing Management, 2000.
• 20. A. S. Schulz and N. E Stier Moses. On the performance of user equilibria in traffic networks. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’03, pages 86–87, 2003.
• 21. B. Vöcking. Algorithmic Game Theory, chapter 20: Selfish Load Balancing. Cambridge University Press, 2007.

Uwagi

1. Track 6: 15th International Workshop on Computational Optimization

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).