AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.1 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

Long Zhang1( ), Zhiwen Wang2, Jingwen Wang2, Donglei Du3, Chuanwen Luo4
School of Management, and also with Institute of Operations Research, Qufu Normal University, Rizhao 276826, China
Institute of Operations Research, Qufu Normal University, Rizhao 276826, China
Faculty of Management, University of New Brunswick, Fredericton E3B9Y2, Canada
School 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 gamebatching-machineNash equilibriummixed strategymixed 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

77

Views

11

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 21 July 2023
Revised: 22 January 2024
Accepted: 15 March 2024
Published: 20 August 2024
© The Author(s) 2025.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return