An Almost Ideal Coordination Mechanism for Unrelated Machine Scheduling

Theory of Computing Systems - Tập 63 - Trang 114-127 - 2018
Ioannis Caragiannis1, Angelo Fanelli2
1Department of Computer Engineering and Informatics, University of Patras, Rion-Patras, Greece
2CNRS (UMR-6211), Université de Caen Basse-Normandie, Caen, France

Tóm tắt

Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable properties of a coordination mechanism includes simplicity in its definition and efficiency of the outcomes of the induced game. We present a broad class of coordination mechanisms for unrelated machine scheduling that are simple to define and we identify one of its members (mechanism DCOORD) that is superior to all known mechanisms. In particular, DCOORD induces potential games with logarithmic price of anarchy and only constant price of stability. Both bounds are almost optimal.

Tài liệu tham khảo

Abed, F., Correa, J.R., Huang, C.-C.: Optimal coordination mechanisms for multi-job scheduling games. In: Proceedings of the 22nd European Symposium on Algorithms (ESA), LNCS 8737, Springer, pages 13–24 (2014)

Abed, F., Huang, C.: Preemptive coordination mechanisms for unrelated machines. In: Proceedings of the 20th Annual European Symposium on Algorithms (ESA), LNCS 7501, Springer, pages 12–23 (2012)

Awerbuch, B., Azar, Y., Grove, E.F., Kao, M.-Y., Krishnan, P., Vitter, J.S.: Load balancing in the L p norm. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 383-391 (1995)

Azar, Y., Fleischer, L., Jain, K., Mirrokni, V.S., Svitkina, Z.: Optimal coordination mechanisms for unrelated machine scheduling. Oper. Res. 63 (3), 489–500 (2015)

Bhattacharya, S., Im, S., Kulkarni, J., Munagala, K.: Coordination mechanisms from (almost) all scheduling policies. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS), pages 121–134 (2014)

Caragiannis, I.: Better bounds for online load balancing on unrelated machines. In: Proceedings of the 19th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 972-981 (2008)

Caragiannis, I.: Efficient coordination mechanisms for unrelated machine scheduling. Algorithmica 66, 512–540 (2013)

Caragiannis, I., Gkatzelis, V., Vinci, C.: Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling. In: Proceedings of the 13th International Conference on Web and Internet Economics (WINE), LNCS 10660, Springer, pages 74–87 (2017)

Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. Theor. Comput. Sci. 410(36), 3327–3336 (2009)

Cohen, J., Dürr, C., Thang, N.K.: Smooth inequalities and equilibrium inefficiency in scheduling games. In: Proceedings of the 8th International Workshop on Internet and Network Economics (WINE), LNCS 7695, Springer, pages 350–363 (2012)

Cole, R., Correa, J.R., Gkatzelis, V., Mirrokni, V.S., Olver, N.: Decentralized utilitarian mechanisms for scheduling games. Games and Econ. Behav. 92, 306–326 (2015)

Immorlica, N., Li, L., Mirrokni, V.S., Schulz, A.S.: Coordination mechanisms for selfish scheduling. Theor. Comput. Sci. 410(17), 1589–1598 (2009)

Thông tin
Thông tin xuất bản

Theory of Computing Systems

Tập 63

114-127

Thông tin tác giả