Game-theoretical approach for task allocation problems with constraints. (English) Zbl 07736294
Summary: The distributed task allocation problem, as one of the most interesting distributed optimization challenges, has received considerable research attention recently. Previous works mainly focused on the task allocation problem in a population of individuals, where there are no constraints for affording task amounts. The latter condition, however, cannot always be hold. In this paper, we study the task allocation problem with constraints of task allocation in a game-theoretical framework. We assume that each individual can afford different amounts of task and the cost function is convex. To investigate the problem in the framework of population games, we construct a potential game and calculate the fitness function for each individual. We prove that when the Nash equilibrium point in the potential game is in the feasible solutions for the limited task allocation problem, the Nash equilibrium point is the unique globally optimal solution. Otherwise, we also derive analytically the unique globally optimal solution. In addition, in order to confirm our theoretical results, we consider the exponential and quadratic forms of cost function for each agent. Two algorithms with the mentioned representative cost functions are proposed to numerically seek the optimal solution to the limited task problems. We further perform Monte Carlo simulations which provide agreeing results with our analytical calculations.
MSC:
| 91A22 | Evolutionary games |
Keywords:
replicator dynamics; population game; evolutionary game theory; Nash equilibrium; distributed optimizationReferences:
| [1] | Balaji, P. G.; German, X.; Srinivasan, D., Urban traffic signal control using reinforcement learning agents, IET Intell. Transp. Syst., 4, 177-188 (2010) |
| [2] | Pantoja, A.; Quijano, N., Distributed optimization using population dynamics with a local replicator equation, (Proc. 51st IEEE Conf. Decis. Control (2012)), 3790-3795 |
| [3] | Pantoja, A.; Obando, G.; Quijano, N., Distributed optimization with information-constrained population dynamics, J. Franklin Inst., 356, 209-236 (2019) · Zbl 1405.93021 |
| [4] | Mojica-Nava, E.; Rivera, S.; Quijano, N., Game-theoretic dispatch control in microgrids considering network losses and renewable distributed energy resources integration, IET Gener. Transm. Distrib., 11, 1583-1590 (2017) |
| [5] | Pantoja, A.; Quijano, N., A population dynamics approach for the dispatch of distributed generators, IEEE Trans. Ind. Electron., 58, 4559-4567 (2011) |
| [6] | Obando, G.; Pantoja, A.; Quijano, N., Building temperature control based on population dynamics, IEEE Trans. Control Syst. Technol., 22, 404-412 (2013) |
| [7] | Wang, D.; Wang, Z.; Chen, M.; Wang, W., Distributed optimization for multi-agent systems with constraints set and communication time-delay over a directed graph, Inf. Sci., 438, 1-14 (2018) · Zbl 1440.68308 |
| [8] | Turner, J.; Meng, Q.; Schaefer, G.; Whitbrook, A.; Soltoggio, A., Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system, IEEE Trans. Cybern., 48, 2583-2597 (2018) |
| [9] | Liu, Q.; Wang, J., A second-order multi-agent network for bound-constrained distributed optimization, IEEE Trans. Autom. Control, 60, 3310-3315 (2015) · Zbl 1360.90202 |
| [10] | Nedic, A.; Olshevsky, A.; Shi, W., Achieving geometric convergence for distributed optimization over time-varying graphs, SIAM J. Optim., 27, 2597-2633 (2017) · Zbl 1387.90189 |
| [11] | Shi, X.; Cao, J.; Wen, G.; Perc, M., Finite-time consensus of opinion dynamics and its applications to distributed optimization over digraph, IEEE Trans. Cybern., 49, 3767-3779 (2019) |
| [12] | Tian, F.; Yu, W.; Fu, J.; Gu, W.; Gu, J., Distributed optimization of multiagent systems subject to inequality constraints, IEEE Trans. Cybern., 51, 2232-2241 (2021) |
| [13] | Liu, P.; Xiao, F.; Wei, B.; Wang, A., Distributed constrained optimization problem of heterogeneous linear multi-agent systems with communication delays, Syst. Control Lett., 155, Article 105002 pp. (2021) · Zbl 1478.93031 |
| [14] | Wang, X.-F.; Hong, Y.; Sun, X.-M.; Liu, K.-Z., Distributed optimization for resource allocation problems under large delays, IEEE Trans. Ind. Electron., 66, 9448-9457 (2019) |
| [15] | Khattab, M. M.; Søyland, K., Limited-resource allocation in construction projects, Comput. Ind. Eng., 31, 229-232 (1996) |
| [16] | Federgruen, A.; Zipkin, P., Solution techniques for some allocation problems, Math. Program., 25, 13-24 (1983) · Zbl 0492.90053 |
| [17] | Yin, P. Y.; Wang, J. Y., A particle swarm optimization approach to the nonlinear resource allocation problem, Appl. Math. Comput., 184, 232-242 (2006) · Zbl 1127.90417 |
| [18] | Nedic, A., Distributed gradient methods for convex machine learning problems in networks: distributed optimization, IEEE Signal Process. Mag., 37, 92-101 (2020) |
| [19] | Cassandras, C. G.; Li, W., Sensor networks and cooperative control, Eur. J. Control, 11, 436-463 (2005) · Zbl 1293.93069 |
| [20] | Chen, F.; Chen, X.; Xiang, L.; Ren, W., Distributed economic dispatch via a predictive scheme: heterogeneous delays and privacy preservation, Automatica, 123, Article 109356 pp. (2021) · Zbl 1461.93018 |
| [21] | Olfati-Saber, R.; Fax, J. A.; Murray, R. M., Consensus and cooperation in networked multi-agent systems, Proc. IEEE, 95, 215-233 (2007) · Zbl 1376.68138 |
| [22] | Yi, P.; Hong, Y.; Liu, F., Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems, Automatica, 74, 259-269 (2016) · Zbl 1348.93024 |
| [23] | Xu, J.; Zhu, S.; Soh, Y. C.; Xie, L., A dual splitting approach for distributed resource allocation with regularization, IEEE Trans. Control Netw. Syst., 6, 403-414 (2018) · Zbl 1515.93132 |
| [24] | Cao, M.; Spielman, D. A.; Morse, A. S., A lower bound on convergence of a distributed network consensus algorithm, (Proc. IEEE Conf. Decision Control (2005)), 2356-2361 |
| [25] | Fang, L.; Antsaklis, P. J.; Tzimas, A., Asynchronous consensus protocols: preliminary results, simulations and open questions, (Proc. IEEE Conf. Decision Control (2005)), 2194-2199 |
| [26] | Tsianos, K. I.; Lawlor, S.; Rabbat, M. G., Consensus-based distributed optimization: practical issues and applications in large-scale machine learning, (Proc. 50th Allerton Conf. Commun. Control Comput (2012)), 1543-1550 |
| [27] | Menache, I.; Ozdaglar, A., Network Games: Theory, Models, and Dynamics, Synthesis Lectures Commun. Netw., vol. 4, 1-159 (2011) · Zbl 1304.91008 |
| [28] | Chen, G.; Li, Z., Distributed optimal resource allocation over strongly connected digraphs: a surplus-based approach, Automatica, 125, Article 109459 pp. (2021) · Zbl 1461.93181 |
| [29] | Jie, Y.; Liu, C. Z.; Li, M., Game theoretic resource allocation model for designing effective traffic safety solution against drunk driving, Appl. Math. Comput., 376, Article 125142 pp. (2020) · Zbl 1475.91046 |
| [30] | Wang, Q.; He, N.; Chen, X., Replicator dynamics for public goods game with resource allocation in large populations, Appl. Math. Comput., 328, 162-170 (2018) · Zbl 1427.91046 |
| [31] | Huang, Y.; Ren, T.; Zheng, J., Evolution of cooperation in public goods games with dynamic resource allocation: a fairness preference perspective, Appl. Math. Comput., 445, Article 127844 pp. (2023) · Zbl 1511.91060 |
| [32] | Barreiro-Gomez, J.; Obando, G.; Quijano, N., Distributed population dynamics: optimization and control applications, IEEE Trans. Syst. Man Cybern. Syst., 47, 304-314 (2016) |
| [33] | Sun, C.; Sun, W.; Wang, X.; Zhou, Q., Potential game theoretic learning for the minimal weighted vertex cover in distributed networking systems, IEEE Trans. Cybern., 49, 1968-1978 (2019) |
| [34] | Jaleel, H.; Shamma, J. S., Distributed optimization for robot networks: from real-time convex optimization to game-theoretic self-organization, Proc. IEEE, 108, 1953-1967 (2020) |
| [35] | Sun, C.; Wang, X.; Qiu, H.; Chen, Q.; Zhou, Q., Distributed optimization for weighted vertex cover via heuristic game theoretic learning, (Proc. 59th IEEE Conf. Decis. Control (2020)), 325-330 |
| [36] | Tan, S.; Wang, Y.; Vasilakos, A. V., Distributed population dynamics for searching generalized Nash equilibria of population games with graphical strategy interactions, IEEE Trans. Syst. Man Cybern. Syst., 52, 1-10 (2021) |
| [37] | Zhu, Y.; Li, W.; Zhao, M.; Hao, J.; Zhao, D., Empirical policy optimization for n-player Markov games, IEEE Trans. Cybern. (2023) |
| [38] | Zhu, Y.; Xia, C.; Wang, Z.; Chen, Z., Networked decision-making dynamics based on fair, extortionate and generous strategies in iterated public goods games, IEEE Trans. Netw. Sci. Eng., 9, 2450-2462 (2022) |
| [39] | Zhu, Y.; Zhang, Z.; Xia, C.; Chen, Z., Equilibrium analysis and incentive-based control of the anticoordinating networked game dynamics, Automatica, 147, Article 110707 pp. (2023) · Zbl 1505.91089 |
| [40] | Ocampo-Martinez, C.; Quijano, N., Game-theoretical methods in control of engineering systems, IEEE Control Syst. Mag., 37, 30-32 (2017) · Zbl 1477.93113 |
| [41] | Riehl, J.; Ramazi, P.; Cao, M., A survey on the analysis and control of evolutionary matrix games, Annu. Rev. Control, 45, 87-106 (2018) |
| [42] | Marden, J. R.; Shamma, J. S., Game theory and control, Annu. Rev. Control, Robot. Auton. Syst., 1, 105-134 (2018) |
| [43] | Rizk, Y.; Awad, M.; Tunstel, E. W., Decision making in multiagent systems: a survey, IEEE Trans. Cogn. Dev. Syst., 10, 514-529 (2018) |
| [44] | Chen, X.; Wang, L., Effects of cost threshold and noise in spatial snowdrift games with fixed multi-person interactions, Europhys. Lett., 90, Article 38003 pp. (2010) |
| [45] | Martinez-Piazuelo, J.; Quijano, N.; Ocampo-Martinez, C., A payoff dynamics model for generalized Nash equilibrium seeking in population games, Automatica, 140, Article 110227 pp. (2022) · Zbl 1486.91008 |
| [46] | Bertsekas, D.; Nedic, A.; Ozdaglar, A., Convex Analysis and Optimization (2003), Athena Scientific Press: Athena Scientific Press Cambridge, MA · Zbl 1140.90001 |
| [47] | Quijano, N.; Ocampo-Martinez, C.; Barreiro-Gomez, J.; Obando, G.; Pantoja, A.; Mojica-Nava, E., The role of population games and evolutionary dynamics in distributed control systems: the advantages of evolutionary game theory, IEEE Control Syst. Mag., 37, 70-97 (2017) · Zbl 1477.91007 |
| [48] | Sandholm, W. H., Population Games and Evolutionary Dynamics (2010), Cambridge University Press · Zbl 1208.91003 |
| [49] | Nocedal, J.; Wright, S., Numerical Optimization (2006), Press: Press New York, NY: Springer New York · Zbl 1104.65059 |
| [50] | Bauso, D.; Giarrë, L.; Pesenti, R., Non-linear protocols for optimal distributed consensus in networks of dynamic agents, Syst. Control Lett., 55, 918-928 (2006) · Zbl 1111.68009 |
| [51] | Chen, X.; Brännström, Å.; Dieckmann, U., Parent-preferred dispersal promotes cooperation in structured populations, Proc. R. Soc. B, Biol. Sci., 286, Article 20181949 pp. (2019) |
| [52] | Sun, C.; Wang, X.; Liu, J., Evolutionary game theoretic approach for optimal resource allocation in multi-agent systems, Proc. Chin. Autom. Congr., 5588-5592 (2017) |
| [53] | Martinez-Piazuelo, J.; Diaz-Garcia, G.; Quijano, N.; Giraldo, L. F., Discrete-time distributed population dynamics for optimization and control, IEEE Trans. Syst. Man Cybern. Syst., 52, 7112-7122 (2022) |
| [54] | Sydulu, M., A very fast and effective noniterative “λ-logic based” algorithm for economic dispatch of thermal units, Proc. IEEE, 2, 1434-1437 (1999) |
| [55] | Hartmann, A. K.; Rieger, H., Optimization Algorithms in Physics (2002), Wiley-Vch Press: Wiley-Vch Press Berlin · Zbl 1003.82002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
