A Consensus-Based Algorithm for Non-Convex Multiplayer Games: Conclusion

Table of Links

Abstract and 1 Introduction

2 Global convergence

2.1 Quantitative Laplace principle

2.2 Global convergence in mean-field law

3 Numerical experiments and 3.1 One-dimensional illustrative example

3.2 Nonlinear oligopoly games with several goods

4 Conclusion, Acknowledgments, Appendix, and References

4 Conclusion

Acknowledgments

The Department of Mathematics and Scientific Computing at the University of Graz, with which E.C. and H.H. are affiliated, is a member of NAWI Graz (https://nawigraz.at/en). E.C. has received funding from the European Union’s Framework Programme for Research and Innovation Horizon 2020 (2014–2020) under the Marie Sk lodowska–Curie Grant Agreement No. 861137. J.Q. is partially supported by the National Science and Engineering Research Council of Canada (NSERC) and by the 2023-2024 PIMS-Europe Fellowship.

Appendix

References

[1] Hyeong-Ohk Bae, Seung-Yeal Ha, Myeongju Kang, Hyuncheul Lim, Chanho Min, and Jane Yoo, A constrained consensus based optimization algorithm and its application to finance, Applied Mathematics and Computation 416 (2022), 126726.

[2] Christian Blum and Andrea Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Comput. Surv. 35 (September 2003), no. 3, 268–308.

[3] Fran¸cois Bolley, Jos´e A Canizo, and Jos´e A Carrillo, Stochastic mean-field limit: non-Lipschitz forces and swarming, Mathematical Models and Methods in Applied Sciences 21 (2011), no. 11, 2179–2210.

[4] Giacomo Borghi, Michael Herty, and Lorenzo Pareschi, An adaptive consensus based method for multi-objective optimization with uniform pareto front approximation, arXiv preprint arXiv:2208.01362 (2022).

[5] Giacomo Borghi, Michael Herty, and Lorenzo Pareschi, A consensus-based algorithm for multi-objective optimization and its mean-field description, 2022 ieee 61st conference on decision and control (cdc), 2022, pp. 4131– 4136.

[6] Giacomo Borghi, Michael Herty, and Lorenzo Pareschi, Constrained consensus-based optimization, SIAM Journal on Optimization 33 (2023), no. 1, 211–236.

[7] Leon Bungert, Philipp Wacker, and Tim Roith, Polarized consensus-based dynamics for optimization and sampling, arXiv preprint arXiv:2211.05238 (2022).

[8] Lucian Busoniu, Robert Babuska, and Bart De Schutter, A comprehensive survey of multiagent reinforcement learning, IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 38 (2008), no. 2, 156–172.

[9] Jos´e A Carrillo, Young-Pil Choi, and Samir Salem, Propagation of chaos for the Vlasov–Poisson–Fokker–Planck equation with a polynomial cut-off, Communications in Contemporary Mathematics 21 (2019), no. 04, 1850039.

[10] Jos´e A Carrillo, Young-Pil Choi, Claudia Totzeck, and Oliver Tse, An analytical framework for consensusbased global optimization method, Mathematical Models and Methods in Applied Sciences 28 (2018), no. 06, 1037–1066.

[11] Jos´e A Carrillo, Franca Hoffmann, Andrew M Stuart, and Urbain Vaes, Consensus-based sampling, Studies in Applied Mathematics 148 (2022), no. 3, 1069–1140.

[12] Jos´e A Carrillo, Shi Jin, Lei Li, and Yuhua Zhu, A consensus-based global optimization method for high dimensional machine learning problems, ESAIM: Control, Optimisation and Calculus of Variations 27 (2021), S5.

[13] Jose A Carrillo, Nicolas Garcia Trillos, Sixu Li, and Yuhua Zhu, Fedcbo: Reaching group consensus in clustered federated learning through consensus-based optimization, arXiv preprint arXiv:2305.02894 (2023).

[14] Jos´e Antonio Carrillo, Claudia Totzeck, and Urbain Vaes, Consensus-based optimization and ensemble kalman inversion for global optimization problems with constraints, Modeling and simulation for collective dynamics, 2023, pp. 195–230.

[15] Guanpu Chen, Yang Ming, Yiguang Hong, and Peng Yi, Distributed algorithm for ε-generalized nash equilibria with uncertain coupled constraints, Automatica 123 (2021), 109313.

[16] Jingrun Chen, Liyao Lyu, et al., A consensus-based global optimization method with adaptive momentum estimation, Communications in Computational Physics 31 (2022), no. 4, 1296–1316.

[17] Cristina Cipriani, Hui Huang, and Jinniao Qiu, Zero-inertia limit: from particle swarm optimization to consensus-based optimization, SIAM Journal on Mathematical Analysis 54 (2022), no. 3, 3091–3121.

[18] A.A. Cournot, T. Bacon, and I. Fisher, Researches into the mathematical principles of the theory of wealth, Economic classics, Macmillan, 1897.

[19] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song, Sbeed: Convergent reinforcement learning with nonlinear function approximation, International conference on machine learning, 2018, pp. 1125–1134.

[20] Amir Dembo and Ofer Zeitouni, Large deviations techniques and applications, Springer-Verlag Berlin Heidelberg, 2010.

[21] Yuyang Deng and Mehrdad Mahdavi, Local stochastic gradient descent ascent: Convergence analysis and communication efficiency, International conference on artificial intelligence and statistics, 2021, pp. 1387–1395.

[22] Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low, Fault-tolerant federated reinforcement learning with theoretical guarantee, Advances in Neural Information Processing Systems 34 (2021), 1007–1021.

[23] Tanner Fiez, Lillian Ratliff, Eric Mazumdar, Evan Faulkner, and Adhyyan Narang, Global convergence to local minmax equilibrium in classes of nonconvex zero-sum games, Advances in Neural Information Processing Systems 34 (2021), 29049–29063.

[24] Massimo Fornasier, Hui Huang, Lorenzo Pareschi, and Philippe S¨unnen, Consensus-based optimization on hypersurfaces: Well-posedness and mean-field limit, Mathematical Models and Methods in Applied Sciences 30 (2020), no. 14, 2725–2751.

[25] Massimo Fornasier, Hui Huang, Lorenzo Pareschi, and Philippe S¨unnen, Consensus-based optimization on the sphere: Convergence to global minimizers and machine learning, The Journal of Machine Learning Research 22 (2021), no. 1, 10722–10776.

[26] Massimo Fornasier, Hui Huang, Lorenzo Pareschi, and Philippe S¨unnen, Anisotropic diffusion in consensusbased optimization on the sphere, SIAM Journal on Optimization 32 (2022), no. 3, 1984–2012.

[27] Massimo Fornasier, Timo Klock, and Konstantin Riedl, Consensus-based optimization methods converge globally, arXiv e-prints (2021), arXiv–2103.

[28] Massimo Fornasier, Timo Klock, and Konstantin Riedl, Convergence of anisotropic consensus-based optimization in mean-field law, International conference on the applications of evolutionary computation (part of evostar), 2022, pp. 738–754.

[29] Michel Gendreau and Jean-Yves Potvin, Handbook of metaheuristics, 2nd ed., Springer Publishing Company, Incorporated, 2010.

[30] Chaitanya S Gokhale and Arne Traulsen, Evolutionary multiplayer games, Dynamic Games and Applications 4 (2014), 468–488.

[31] Seung-Yeal Ha, Shi Jin, and Doheon Kim, Convergence of a first-order consensus-based global optimization algorithm, Mathematical Models and Methods in Applied Sciences 30 (2020), no. 12, 2417–2444.

[32] Seung-Yeal Ha, Shi Jin, and Doheon Kim, Convergence and error estimates for time-discrete consensus-based optimization algorithms, Numerische Mathematik 147 (2021), 255–282.

[33] Seung-Yeal Ha, Myeongju Kang, Dohyun Kim, Jeongho Kim, and Insoon Yang, Stochastic consensus dynamics for nonconvex optimization on the stiefel manifold: Mean-field limit and convergence, Mathematical Models and Methods in Applied Sciences 32 (2022), no. 03, 533–617.

[34] Desmond J. Higham., An algorithmic introduction to numerical simulation of stochastic differential equations, SIAM Review 43 (2001), no. 3, 525–546.

[35] Hui Huang, Jian-Guo Liu, and Peter Pickl, On the mean-field limit for the Vlasov–Poisson–Fokker–Planck system, Journal of Statistical Physics 181 (2020), no. 5, 1915–1965.

[36] Hui Huang, Jinniao Qiu, and Konstantin Riedl, On the global convergence of particle swarm optimization methods, Applied Mathematics & Optimization 88 (2023), no. 2, 30.

[37] Hui Huang, Jinniao Qiu, and Konstantin Riedl, Consensus-based optimization for saddle point problems, SIAM Journal on Control and Optimization (to appear 2023).

[38] Pierre-Emmanuel Jabin and Zhenfu Wang, Mean field limit for stochastic particle systems, Active particles, volume 1, 2017, pp. 379–402.

[39] Dante Kalise, Akash Sharma, and Michael V Tretyakov, Consensus-based optimization via jump-diffusion stochastic differential equations, Mathematical Models and Methods in Applied Sciences 33 (2023), no. 02, 289–339.

[40] Mingxing Ke, Yuhua Xu, Alagan Anpalagan, Dianxiong Liu, and Yuli Zhang, Distributed toa-based positioning in wireless sensor networks: A potential game approach, IEEE Communications Letters 22 (2017), no. 2, 316– 319.

[41] Brooks King-Casas and Pearl H Chiu, Understanding interpersonal function in psychiatric illness through multiplayer economic games, Biological psychiatry 72 (2012), no. 2, 119–125.

[42] Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien P´erolat, David Silver, and Thore Graepel, A unified game-theoretic approach to multiagent reinforcement learning, Advances in neural information processing systems 30 (2017).

[43] Chongxuan Li, Taufik Xu, Jun Zhu, and Bo Zhang, Triple generative adversarial nets, Advances in neural information processing systems 30 (2017).

[44] Tianyi Lin, Chi Jin, and Michael Jordan, On gradient descent ascent for nonconvex-concave minimax problems, International conference on machine learning, 2020, pp. 6083–6093.

[45] Liu Liu, Ji Liu, and Dacheng Tao, Variance reduced methods for non-convex composition optimization, IEEE Transactions on Pattern Analysis and Machine Intelligence 44 (2021), no. 9, 5813–5825.

[46] Joao Maciel and Joao Paulo Costeira, A global solution to sparse correspondence problems, IEEE Transactions on Pattern Analysis and Machine Intelligence 25 (2003), no. 2, 187–199.

[47] Peter David Miller, Applied asymptotic analysis, Vol. 75, American Mathematical Soc., 2006.

[48] Yadati Narahari, Game theory and mechanism design, Vol. 4, World Scientific, 2014.

[49] John F Nash Jr, Equilibrium points in n-person games, Proceedings of the national academy of sciences 36 (1950), no. 1, 48–49.

[50] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn, Solving a class of non-convex min-max games using iterative first order methods, Advances in Neural Information Processing Systems 32 (2019).

[51] Ren´e Pinnau, Claudia Totzeck, Oliver Tse, and Stephan Martin, A consensus-based model for global optimization and its mean-field limit, Mathematical Models and Methods in Applied Sciences 27 (2017), no. 01, 183– 204.

[52] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang, Weakly-convex–concave min–max optimization: provable algorithms and applications in machine learning, Optimization Methods and Software 37 (2022), no. 3, 1087–1121.

[53] Konstantin Riedl, Leveraging memory effects and gradient information in consensus-based optimization: On global convergence in mean-field law, arXiv preprint arXiv:2211.12184 (2022).

[54] Konstantin Riedl, Timo Klock, Carina Geldhauser, and Massimo Fornasier, Gradient is all you need?, 2023.

[55] Rukhsana Ruby, Victor CM Leung, and David G Michelson, Centralized and game theoretical solutions of joint source and relay power allocation for af relay based network, IEEE Transactions on Communications 63 (2015), no. 8, 2848–2863.

[56] Jiaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon, Multi-agent generative adversarial imitation learning, Advances in neural information processing systems 31 (2018).

[57] Alain-Sol Sznitman, Topics in propagation of chaos, Ecole d’´et´e de probabilit´es de Saint-Flour XIX—1989, 1991, pp. 165–251.

[58] Claudia Totzeck and Marie-Therese Wolfram, Consensus-based global optimization with personal best, Mathematical Biosciences and Engineering 17 (2020), no. 5, 6026–6044.

[59] Helin Yang and Xianzhong Xie, Energy-efficient joint scheduling and resource management for uav-enabled multicell networks, IEEE Systems Journal 14 (2019), no. 1, 363–374.

[60] Sixing Yang, Yan Guo, Ning Li, and Dagang Fang, Df-cspg: A potential game approach for device-free localization exploiting joint sparsity, IEEE Wireless Communications Letters 8 (2018), no. 2, 608–611.

[61] Peng Yi and Lacra Pavel, An operator splitting approach for distributed generalized nash equilibria computation, Automatica 102 (2019), 111–121.

[62] Huan Zhao, Tingting Li, Yufeng Xiao, and Yu Wang, Improving multi-agent generative adversarial nets with variational latent representation, Entropy 22 (2020), no. 9, 1055.