Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

Stackelberg Strategies for Weighted Load Balancing Games

,

DOI: http://dx.doi.org/10.15439/2022F52

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 373–382 ()

Full text

Abstract. An instance of a weighted Stackelberg load balancing games is given by a set of identical machines, a set of variable-length jobs, and a parameter $0\leq\alpha\leq 1$. A centralized authority, denoted {\em the leader}, selects a subset of the jobs whose total length is at most an $\alpha$-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.

References

  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.