| Sign up

PDF (1.1 MB)

Cite

Collect

Submit Manuscript

Open Access

Mixed Strategy Nash Equilibrium for Scheduling Games on Batching-Machines with Activation Cost

Long Zhang^¹(), Zhiwen Wang^², Jingwen Wang^², Donglei Du^³, Chuanwen Luo^⁴

1School of Management, and also with Institute of Operations Research, Qufu Normal University, Rizhao 276826, China

2Institute of Operations Research, Qufu Normal University, Rizhao 276826, China

3Faculty of Management, University of New Brunswick, Fredericton E3B9Y2, Canada

4School of Information Science and Technology, Beijing Forestry University, Beijing 100083, China, and also with the Engineering Research Center for Forestry-oriented Intelligent Information Processing of National Forestry and Grassland Administration, Beijing 100083, China

Show Author Information

Abstract

This paper studies two scheduling games on identical batching-machines with activation cost, where each game comprises $n$ jobs being processed on $m$ identical batching-machines. Each job, as an agent, chooses a machine (or, more accurately, a batch on a machine) for processing in order to minimize its disutility, which is comprised of its machine’s load and the activation cost it shares. Based on previous results, we present the Mixed strategy Nash Equilibria (MNE) for some special cases of the two games. For each game, we first analyze the conditions for the nonexistence of Nash equilibrium, then provide the MNE for the conditions, and offer the efficiency of MNE (mixed price of anarchy).

Keywords

scheduling game batching-machine Nash equilibrium mixed strategy mixed price of anarchy

References

[1]

O. Morgenstern and J. von Neumann, Theory of games and economic behavior. Princeton, NJ, USA: Princeton University Press, 1953.

[2]

J. Nash, Non-cooperative games, Ann. Math., vol. 54, no. 2, pp. 286–295, 1951.

Crossref Google Scholar

[3]

A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria, ACM T. Algorithms, vol. 3, no. 1, pp. 1–17, 2007.

Crossref Google Scholar

[4]

J. Ochs, Games with unique, mixed strategy equilibria: An experimental study, Game Econ. Behav., vol. 10, no. 1, pp. 202–217, 1995.

Crossref Google Scholar

[5]

I. Caragiannis, A. Fanelli, N. Gravin, and A. Skopalikl, Efficient computation of approximate pure Nash equilibria in congestion games, in Proc. IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), Palm Springs, CA, USA, pp. 532–541, 2011.

Crossref

[6]

A. Czumaj, M. Fasoulakis, and M. Jurdziński, Multi-player approximate Nash equilibria, in Proc. 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS), São Paulo, Brazil, pp. 1511–1513, 2017.

[7]

C. Papadimitriou, Algorithms games and the Internet, in Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), Hersonissos, Greece, 2001, pp. 749–753.

Crossref

[8]

J. R. Correa, A. S. Schulz, and N. E. Stier-Moses, Selfish routing in capacitated networks, Math. Oper. Res., vol. 29, no. 4, pp. 961–976, 2004.

Crossref Google Scholar

[9]

L. Zhang, J. G. Yu, and Y. Z. Zhang, Pareto-optimal algorithms for scheduling games on parallel-batching machines with activation cost, Asia. Pac. J. Oper. Res., vol. 38, no. 5, pp. 2140007:1–2140007:15, 2021.

Crossref Google Scholar

[10]

L. Zhang, J. G. Yu, Y. Z. Zhang, D. L. Du, and M. Guo, Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost, Theor. Comput. Sci., vol. 949, pp. 113730:1–113730:12, 2023.

Crossref Google Scholar

[11]

L. Zhang, J. G. Yu, Y. Z. Zhang, and D. L. Du, Approximate Nash equilibria for scheduling game on serial-batching-machines with activation cost, Int. J. Found. Comput. S, doi:10.1142/S0129054122460078.

Crossref Google Scholar

[12]

P. A. Chen, B. De Keijzer, D. Kempe, and G. Schäfer, The robust price of anarchy of altruistic games, in Proc. 7th International Workshop on Internet and Network Economics (WINE ), Berlin, Germany, pp. 383–390, 2011.

Crossref

[13]

G. Christodoulou and E. Koutsoupias, The price of anarchy of finite congestion games, in Proc. 37th Annual ACM Symposium on Theory of Computing (STOC), Baltimore, MD, USA, pp. 67–73, 2005.

Crossref

[14]

M. Feldman and T. Tamir, Conflicting congestion effects in resource allocation games, Oper. Res., vol. 60, no. 3, pp. 529–540, 2012.

Crossref Google Scholar

[15]

B. Chen and S. Gürel, Efficiency analysis of load balancing games with and without activation costs, J. Sched., vol. 15, no. 2, pp. 157–164, 2012.

Crossref Google Scholar

[16]

X. J. Chen, X. D. Hu, C. H. Wang, and X. Y. Wu, The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler, Theor. Comput. Sci., vol. 838, pp. 180–194, 2020.

Crossref Google Scholar

[17]

E. Georgoulaki, K. Kollias, and T. Tamir, Equilibrium inefficiency and computation in cost-sharing games in real-time scheduling systems, Algorithms, vol. 14, no. 4, pp. 103:1–103:16, 2021.

Crossref Google Scholar

[18]

L. Lin, X. C. Xian, Y. J. Yan, X. He, and Z. Y. Tan, Inefficiency of equilibria for scheduling game with machine activation costs, Theor. Comput. Sci., vol. 607, no. P2, pp. 193–207, 2015.

Crossref Google Scholar

[19]

K. Lee, Y. T. Leung, and M. L. Pinedo, Coordination mechanisms for parallel machine scheduling, Eur. J. Oper. Res., vol. 220, no. 2, pp. 305–313, 2012.

Crossref Google Scholar

Tsinghua Science and Technology

Volume 30 Issue 2,
April 2025

Pages 519-527

DOI: 10.26599/TST.2024.9010056

Cite this article:

Zhang L, Wang Z, Wang J, et al. Mixed Strategy Nash Equilibrium for Scheduling Games on Batching-Machines with Activation Cost. Tsinghua Science and Technology, 2025, 30(2): 519-527. https://doi.org/10.26599/TST.2024.9010056