随机纳什博弈中的近邻梯度响应与最佳响应方案研究
Research on Neighboring Gradient Response and Best-Response Schemes in Stochastic Nash Games
摘要: 本文研究了一个N人随机纳什博弈，其中第i个参与者最小化的目标函数为 f i ( x )+ r i ( x i ) ，其中 f i 是期望值，且 r i 具有高效的近邻评估。在此背景下，本文做出以下结果：1) 在串联梯度映射的强单调性假设条件下，为所提出的可变样本规模近邻随机梯度响应方案推导出最优收敛速率以及神谕复杂度界；2) 在与近邻最佳响应映射相关的合适压缩性质下，设计了一个可变样本规模近邻最佳响应方案，其中近邻最佳响应是通过求解一个样本平均问题来计算的。如果用于计算样本平均的批量大小以合适的速率增加，可以证明所得迭代以线性速率收敛，并推导出神谕复杂度。
Abstract: This paper studies an N-player stochastic Nash game, where the objective function minimized by the i-th player is f i ( x )+ r i ( x i ) , where f i is the expected value and r i has an efficient proximal evaluation. In this context, this paper obtains the following results: 1) Under the strong monotonic assumption of the concatenated gradient mapping, the optimal convergence rate and the oracle complexity bound are derived for the proposed variable sample size stochastic gradient response scheme; 2) Under the appropriate contraction property related to the proximal best-response mapping, a variable sample size proximal best-response scheme is designed, where the proximal best-response is computed by solving a sample average problem. If the batch size used for computing the sample average increases at an appropriate rate, it can be shown that the resulting iterations converge at a linear rate, and the oracle complexity is derived.
文章引用：黄文. 随机纳什博弈中的近邻梯度响应与最佳响应方案研究[J]. 应用数学进展, 2025, 14(6): 444-451. https://doi.org/10.12677/aam.2025.146333

参考文献

[1] Fudenberg, D. and Tirole, J. (1991) Game Theory. MIT Press.
[2] Başar, T. and Olsder, G.J. (1998). Dynamic Noncooperative Game Theory. 2nd Edition, Society for Industrial and Applied Mathematics.[CrossRef] 
[3] Nash, J.F. (1950) Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences, 36, 48-49. [Google Scholar] [CrossRef] [PubMed]
[4] Alpcan, T. and Basar, T. (2002) A Game-Theoretic Framework for Congestion Control in General Topology Networks. Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, 10-13 December 2002, 1218-1224. [Google Scholar] [CrossRef] 
[5] Yin, H.B., Shanbhag, U.V. and Mehta, P.G. (2011) Nash Equilibrium Problems with Scaled Congestion Costs and Shared Constraints. IEEE Transactions on Automatic Control, 56, 1702-1708. [Google Scholar] [CrossRef] 
[6] Lei, J., Shanbhag, U. and Chen, J. (2023) A Distributed Iterative Tikhonov Method for Networked Monotone Aggregative Hierarchical Stochastic Games.
[7] Facchinei, F. and Pang, J. (2009) Nash Equilibria: The Variational Approach. In: Convex Optimization in Signal Processing and Communications, Cambridge University Press, 443-493. [Google Scholar] [CrossRef] 
[8] Yousefian, F., Nedić, A. and Shanbhag, U.V. (2017) On Smoothing, Regularization, and Averaging in Stochastic Approximation Methods for Stochastic Variational Inequality Problems. Mathematical Programming, 165, 391-431. [Google Scholar] [CrossRef] 
[9] Jiang, H., Shanbhag, U.V. and Meyn, S.P. (2018) Distributed Computation of Equilibria in Misspecified Convex Stochastic Nash Games. IEEE Transactions on Automatic Control, 63, 360-371. [Google Scholar] [CrossRef] 
[10] Yousefian, F., Nedic, A. and Shanbhag, U.V. (2016) Self-Tuned Stochastic Approximation Schemes for Non-Lipschitzian Stochastic Multi-User Optimization and Nash Games. IEEE Transactions on Automatic Control, 61, 1753-1766. [Google Scholar] [CrossRef] 
[11] Lei, L., Shanbhag, U.V. and Sen, S. (2018) On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Computing Equilibria in Stochastic Nashgames. Mathematics of Operations Research.

为你推荐