Distributed Finite-Time Nash Equilibrium Seeking for Non-Cooperative Games

Abstract

The paper aims to design a distributed algorithm for players in games such that the players can learn Nash equilibriums of non-cooperative games in finite time. We first consider the quadratic non-cooperative games and design estimate protocols for the players such that they can estimate all the other players' actions in distributed manners. In order to make the players track all the other players' real actions in finite time, a bounded gradient dynamics is designed for players to update their actions by using the estimate information. Then the algorithm is extended to more general noncooperative games and it is proved that players' estimates can converge to all the other players' real actions in finite time and all players can learn the unique Nash equilibrium in finite time under mild assumptions. Finally, simulation examples are provided to verify the validity of the proposed finite-time distributed Nash equilibrium seeking algorithms.

Keywords

Nash equilibrium / non-cooperative game / distributed algorithm / finite-time convergence

References

[1] T. Basar and G. Olsder, Dynamic Noncooperative Game Theory:Second Edition (Classics in Applied Mathematics). Philadelphia, PA, USA: SIAM, 1999.

[2] F. Salehisadaghiani and L. Pavel, Distributed Nash equilibrium seeking: A gossip-based algorithm, Automatica, vol. 72, pp. 209-216, 2016.

[3] D. Gadjov and L. Pavel, A passivity-based approach to Nash equilibrium seeking over networks, IEEE Trans. Autom. Control, vol. 64, no. 3, pp. 1077-1092, 2019.

[4] M. Ye and G. Hu, Distributed Nash equilibrium seeking by a consensus based approach, IEEE Trans. Autom. Control, vol. 62, no. 9, pp. 4811-4818, 2017.

[5] J. Wang and N. Elia, Control approach to distributed optimization. In Proceedings of the 48 th annual Allerton conference on communication control, and computing (Allerton), pp.557-561, 2010.

[6] S.S. Kia, J. Cortés, and S. Martínez, Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication, Automatica, vol. 55, pp. 254-264, 2015.

[7] P. Lin, W. Ren, and J.A. Farrell, Distributed continuous-time optimization: nonuniform gradient gains, finite-time convergence, and convex constraint set, IEEE Trans. Autom. Control, vol. 62, no. 5, pp. 2239-2253, 2017.

[8] Z. Feng and G. Hu, Finite-time distributed optimization with quadratic objective functions under uncertain information, 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 208-213, 2017.

[9] Y. Song and W. Chen, Finite-time convergent distributed consensus optimisation over networks, IET Control Theory Appl., vol.10, no. 11, pp. 1314-1318, 2016.

[10] T. Tatarenko, W. Shi, and A. Nedić, Accelerated gradient play algorithm for distributed Nash equilibrium seeking, 2018 IEEE Conference on Decision and Control (CDC), pp. 3561-3566, 2018,

[11] F. Salehisadaghiani, W. Shi, and L. Pavel, Distributed Nash equilibrium seeking under partial-decision information via the alternating direction method of multipliers, Automatica, vol. 103, pp. 27-35, 2019.

[12] M. Ye, Distributed strategy design for solving games in systems with bounded control inputs, 2019 IEEE 15th International Conference on Control and Automation (ICCA), pp. 266-271, 2019.

[13] J. Rosen, Existence and uniqueness of equilibrium points for concave N-person games, Econometrica, vol. 33, no. 3, pp. 520-534, 1965.

[14] M.S. Stanković, K.H. Johansson, and D.M. Stipanović, Distributed seeking of Nash equilibria with applications to mobile sensor networks, IEEE Trans. Autom. Control, vol. 57, no. 4, pp. 904-919, 2012.

[15] S. Wen, X. He, and T. Huang, Distributed neuro-dynamic algorithm for price-based game in energy consumption system, Neural Process Lett., vol. 51, no. 1, pp. 559-575, 2019.

[16] B. Gao and L. Pavel, Continuous-time convergence rates in potential and monotone games[Online]. Available: https://arxiv.org/abs/2011.10682.