A game theory-based approach to optimize the Hungarian assignment model
*Dipti ChauhanCorresponding authordiptichauhan82@gmail.comDepartment of Artificial Intelligence & Data SciencePrestige Institute of Engineering Management & ResearchIndore, Madhya Pradesh, 452010, India0000-0003-1665-7587View full profile → , Preeti Guptapgupta@piemr.edu.inDepartment of Computer Science & EngineeringPrestige Institute of Engineering Management & ResearchIndore, Madhya Pradesh, 452010, India0000-0002-7557-2666View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Oct 2025
- Published Online:
- 10 Sep 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JSMS-1627
- Pages:
- 1–21
Abstract
The Assignment Model is a basic optimization problem of Operations Research, which, by use of the Hungarian method, is always guaranteed to find an optimal solution but is of polynomial time complexity of O(n3). In this paper, we introduce another strategy which involves the use of game theory- namely, a min-min saddle point strategy- to effectively solve assignment problems. The suggested approach makes the computation simpler and more structured by hierarchically finding minimum row and column values, choosing the minimum global values as saddle-points, and repeatedly removing rows and columns in which they are set to considerable positions until an optimal allocation has been reached. The experimental test of 40 benchmark problems shows the approach to obtain solutions comparable to the Hungarian method with a high level of space and time efficiency. The study provides a new synthesis of game theory in assignment optimization, and its practical implementation in the field of management, engineering, and decision-making when the task is the allocation of resources. These results suggest the effectiveness of game-theoretic reasoning to classical optimization issues and that it can be used widely in modern resource allocation mechanisms.
Keywords
Subject Classifications
References
[1] T. Öncan, “A Survey of the Generalized Assignment Problem and Its Applications,” INFOR: Information Systems and Operational Research, vol. 45, no. 3, pp. 123–141 (Aug. 2007), doi: https://doi.org/10.3138/infor.45.3.123.
[2] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1–2, pp. 83–97 (Mar. 1955), doi: https://doi.org/10.1002/nav.3800020109.
[3] E. Munapo, “development of an accelerating hungarian method for assignment problems,” Восточно-Европейский журнал передовых технологий, vol. 4, no. 4–106 (2020), Available: https://cyberleninka.ru/article/n/development-of-an-accelerating-hungarian-method-for-assignment-problems
[4] K. Szabó, L. Szabó, and R. Kása, “Examination of Logistics Simulation Demand Related to Enterprises: Focusing on a Hungarian County,” Logistics, vol. 8, no. 1, p. 7 (Mar. 2024), doi: https://doi.org/10.3390/logistics8010007.
[5] F. Luna et al., “Optimization algorithms for large-scale real-world instances of the frequency assignment problem,” Soft Computing, vol. 15, no. 5, pp. 975–990 (Sep. 2010), doi: https://doi.org/10.1007/s00500-010-0653-4.
[6] M. T. Graciani, “Adding a \‘Non-\’ in cooperative game theory: a textbook history,” (Sep. 2023), doi: https://doi.org/10.11606/t.12.2023.tde-08112023-194820.
[7] J. Parikh, Jacek Dominik Śledziński, Śrma Zeynep Alparslan Gök, İsmail Özcan, and G. W. Weber, “Balancing Cooperation and Competition in Game Theory for Business,” CRC Press eBooks, pp. 130–156 (Mar. 2025), doi: https://doi.org/10.1201/9781003540434-8.
[8] K. E. Hajioui and R. Azennar, “Bridging economic insights through fixed point theory and game theory applications,” Journal of Interdisciplinary Mathematics, vol. 27, no. 7, pp. 1663–1677 (2024), doi: https://doi.org/10.47974/jim-2006.
[9] B. Gabrovšek, T. Novak, J. Povh, D. Rupnik Poklukar, and J. Žerovnik, “Multiple Hungarian Method for k-Assignment Problem,” Mathematics, vol. 8, no. 11, p. 2050 (Nov. 2020), doi: https://doi.org/10.3390/math8112050.
[10] D. P. Bertsekas, “The auction algorithm: A distributed relaxation method for the assignment problem,” Annals of Operations Research, vol. 14, no. 1, pp. 105–123 (Dec. 1988), doi: https://doi.org/10.1007/bf02186476.
[11] L. Beretta and A. Rubinstein, “Approximate Earth Mover’s Distance in Truly-Subquadratic Time,” Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 47–58 (Jun. 2024), doi: https://doi.org/10.1145/3618260.3649629.
[12] S. Zhang, Y. Xue, H. Zhang, X. Zhou, K. Li, and R. Liu, “Improved Hungarian algorithm–based task scheduling optimization strategy for remote sensing big data processing,” Geo-spatial Information Science, vol. 27, no. 4, pp. 1141–1154 (Apr. 2023), doi: https://doi.org/10.1080/10095020.2023.2178339.
[13] G. Jain, A. Kumar, and Shahid Ahmad Bhat, “Recent developments of game theory and reinforcement learning approaches: A systematic review,” IEEE access, pp. 1–1 (Jan. 2024), doi: https://doi.org/10.1109/access.2024.3352749.
[14] Z. Li, H. Zhu, Z. Yang, and Y. Luo, “Saddle Point of Orbital Pursuit-Evasion Game Under J2-Perturbed Dynamics,” Journal of Guidance, Control, and Dynamics, vol. 43, no. 9, pp. 1733–1739 (Sep. 2020), doi: https://doi.org/10.2514/1.g004459.
[15] J. Solomon, R. Rustamov, L. Guibas, and A. Butscher, “Earth mover’s distances on discrete surfaces,” ACM Transactions on Graphics, vol. 33, no. 4, pp. 1–12 (Jul. 2014), doi: https://doi.org/10.1145/2601097.2601175.
[16] M. E. Mkiramweni, C. Yang, J. Li, and W. Zhang, “A Survey of Game Theory in Unmanned Aerial Vehicles Communications,” IEEE Communications Surveys & Tutorials, vol. 21, no. 4, pp. 3386–3416 (May 2019), doi: https://doi.org/10.1109/comst.2019.2919613.
