Kybernetika 59 no. 4, 575-591, 2023

Bayesian Nash equilibrium seeking for multi-agent incomplete-information aggregative games

Hanzheng Zhang, Huashu Qin and Guanpu ChenDOI: 10.14736/kyb-2023-4-0575

Abstract:

In this paper, we consider a distributed Bayesian Nash equilibrium (BNE) seeking problem in incomplete-information aggregative games, which is a generalization of either Bayesian games or deterministic aggregative games. We handle the aggregation function to adapt to incomplete-information situations. Since the feasible strategies are infinite-dimensional functions and lie in a non-compact set, the continuity of types brings barriers to seeking equilibria. To this end, we discretize the continuous types and then prove that the equilibrium of the derived discretized model is an $\epsilon$-BNE. On this basis, we propose a distributed algorithm for an $\epsilon$-BNE and further prove its convergence.

Keywords:

aggregative games, Bayesian games, equilibrium approximation, distributed algorithms

Classification:

91A27, 91A43, 68W15

paper.pdf

References:

  1. K. Akkarajitsakul, E. Hossain and D. Niyato: Distributed resource allocation in wireless networks under uncertainty and application of Bayesian game. IEEE Commun. Magazine 49 (2011), 8, 120-127.   DOI:10.1109/MCOM.2011.5978425
  2. U. Bhaskar, Y. Cheng, Y. K. Ko and C. Swamy: Hardness results for signaling in Bayesian zero-sum and network routing games. In: Proc. 2016 ACM Conference on Economics and Computation, pp. 479-496.   CrossRef
  3. G. Chen, K. Cao and Y. Hong: Learning implicit information in Bayesian games with knowledge transfer. Control Theory Technol. 18 (2020), 3, 315-323.   DOI:10.1007/s11768-020-0086-2
  4. G. Chen, Y. Ming, Y. Hong and P. Yi: Distributed algorithm for $\epsilon$-generalized Nash equilibria with uncertain coupled constraints. Automatica 123, (2021), 109313.   DOI:10.1016/j.automatica.2020.109313
  5. M. Gro{\ss}hans, C. Sawade, M. Bruckner and T. Scheffer: Bayesian games for adversarial regression problems. In: International Conference on Machine Learning 2013, pp. 55-63.   CrossRef
  6. S. Guo, H. Xu and L. Zhang: Existence and approximation of continuous Bayesian Nash equilibria in games with continuous type and action spaces. SIAM J. Optim. 31 (2021), 4, 2481-2507.   DOI:10.1137/19M1298032
  7. W. Guo, M. I. Jordan and T. Lin: A variational inequality approach to Bayesian regression games In: 2021 60th IEEE Conference on Decision and Control (CDC), pp. 795-802.   CrossRef
  8. J. C. Harsanyi: Games with incomplete information played by "Bayesian'' players, I-III; Part I. The basic model. Management Sci. 14 (1967), 3, 159-182.   DOI:10.1287/mnsc.14.3.159
  9. L. Huang and Q. Zhu: Convergence of Bayesian Nash equilibrium in infinite Bayesian games under discretization. arXiv:2102.12059 (2021).   CrossRef
  10. S. Huang, J. Lei and Y. Hong: A linearly convergent distributed Nash equilibrium seeking algorithm for aggregative games. IEEE Trans. Automat. Control 68 (2023), 3, 1753-1759.   DOI:10.1109/TAC.2022.3154356
  11. J. Koshal, A. Nedić and U. V. Shanbhag: Distributed algorithms for aggregative games on graphs. Oper. Res. 64 (2016), 3, 680-704.   DOI:10.1287/opre.2016.1501
  12. V. Krishna: Auction Theory. Academic Press, London 2009.   CrossRef
  13. V. Krishnamurthy and H. V. Poor: Social learning and Bayesian games in multiagent signal processing: How do local and global decision makers interact? IEEE Signal Process. Magazine, 30 (2013) 3, 43-57.   DOI:10.1109/MSP.2012.2232356
  14. S. Liang, P. Yi and Y. Hong: Distributed Nash equilibrium seeking for aggregative games with coupled constraints. Automatica {\mi85} (2017), 179-185.   DOI:10.1016/j.automatica.2017.07.064
  15. A. Meirowitz: On the existence of equilibria to Bayesian games with non-finite type and action spaces. Econom. Lett. 78 (2003), 2, 213-218.   DOI:10.1016/S0165-1765(02)00216-1
  16. P. R. Milgrom and R. Journal Weber: Distributional strategies for games with incomplete information. Math. Oper. Res. 10 (1985), 4, 619-632.   DOI:10.1287/moor.10.4.619
  17. A. Nedic, A. Ozdaglar and P. A. Parrilo: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 4, 922-938.   DOI:10.1109/TAC.2010.2041686
  18. Z. Rabinovich, V. Naroditskiy, E. H. Gerding and R. J. Nicholas: Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types. Artif. Intell. 195 (2013), 106-139.   CrossRef
  19. B. Rynne and M. A. Youngson: Linear Functional Analysis. Springer Science and Business Media, 2007.   CrossRef
  20. T. Ui: Bayesian Nash equilibrium and variational inequalities. J. Math. Econom. 63 (2016), 139-146.   DOI:10.1016/j.jmateco.2016.02.004
  21. G. Xu, G. Chen, H. Qi and Y. Hong: Efficient algorithm for approximating Nash equilibrium of distributed aggregative games. IEEE Trans. Cybernet. 53 (2023), 7, 4375-4387.   DOI:10.1109/TCYB.2022.3175831
  22. H. Zhang, G. Chen and Y. Hong: Distributed algorithm for continuous-type Bayesian Nash equilibrium in subnetwork zero-sum games. arXiv:2209.06391 (2022).   CrossRef