一类纳什均衡问题的求解算法

展开
  • 1. 复旦大学经济学院, 上海 200433
    2. 内蒙古工业大学经济管理学院, 内蒙古呼和浩特 010051
侯剑, E-mail: houjianimut@163.com

收稿日期: 2021-06-09

  网络出版日期: 2023-09-14

The method for a class of Nash equilibrium game

Expand
  • 1. College of Economics, Fudan University, Shanghai 200433, China
    2. School of Economics and Management, Inner Mongolia University of Technology, Hohhot 010051, Neimenggu, China

Received date: 2021-06-09

  Online published: 2023-09-14

摘要

随着纳什均衡问题被应用到多个领域,其求解算法也得到了越来越多的关注。但鉴于纳什均衡是由一系列优化问题组成的复杂系统,经典的约束优化算法不能被直接应用于求解该问题中,导致求解该问题的困难。对于一类效用函数是强凸的纳什均衡问题,利用Nikaido-Isoda函数将其转化为一类与之完全等价的光滑约束优化问题进行求解是一种有效途径。本文在纳什均衡问题效用函数的梯度具有强单调性这一假设条件下给出求解此类问题的Nikaido-Isoda算法并证明该算法具有全局收敛性。最后,通过求解两类经典纳什均衡问题,验证了该算法的可行性和有效性。

本文引用格式

侯剑, 李萌萌, 文竹 . 一类纳什均衡问题的求解算法[J]. 运筹学学报, 2023 , 27(3) : 129 -136 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.03.010

Abstract

The Nash equilibrium game has been applied to many fields, the algorithm for the problem has attracted much attention in recent years. But since the Nash equilibrium game is a complex system composed by a series of optimization problems, the standard optimization method cannot be directly used for the problem, this leads to the difficulty of solving it. For a class of Nash equilibrium games with strongly convex payoff functions, using the Nikaido-Isoda function to transform the Nash equilibrium game into a smooth constraint optimization problem is an effective method to solve the Nash equilibrium game. Based on the gradient strongly monotonity of the Nash equilibrium payoff function, we present a Nikaido-Isoda algorithm for the game and the global convergence of the algorithm is proved. Finally, by solving two kinds of standard Nash equilibrium problems, the feasibility and effectiveness of the Nikaido-Isoda algorithm are verified.

参考文献

1 LuQ,LuS,LengY.A Nash-Stackelberg game approach in regional energy market considering users' integrated demand response[J].Energy,2019,175,456-470.
2 StephensE R,SmithD B,MahantiA.Game theoretic model predictive control for distributed energy demand-side management[J].IEEE Transactions on Smart Grid,2017,6,1394-1402.
3 HaghighatdoostV,KhorsandiS.Game theoretic spectrum allocation for competing wireless access technologies to maximize the social welfare[J].Wireless Networks,2019,25,3557-3577.
4 AlaeiS,AlaeiR,SalimiP.A game theoretical study of cooperative advertising in a single-manufacturer-two-retailers supply chain[J].The International Journal of Advanced Manufacturing Technology,2014,74,101-111.
5 MamageishviliA,MihalákM,MüllerD.Tree Nash equilibria in the network creation game[J]. Internet Mathematics,2015,11,472-486.
6 查旭,左斌,胡云安.利用退火回归神经网络极值搜索算法求纳什均衡解[J].控制与决策,2006,21,1167-1171.
7 余谦,王先甲.利基于粒子群优化求解纳什均衡的演化算法[J].武汉大学学报(理学版),2006,(1):25-29.
8 李焕哲,吴志健,郭肇禄,等.两阶段多峰优化算法求解纳什均衡[J].武汉大学学报(理学版),2016,65,444-450.
9 李小焕,何洪津,韩德仁.一种改进的自适应投影法解广义纳什均衡问题[J].南京师大学报(自然科学版),2011,34,10-14.
10 KanzowC,SteckD.Augmented Lagrangian methods for the solution of generalized Nash equilibrium problems[J]. SIAM Journal on Optimization,2018,26,2034-2058.
11 GalliL,KanzowC,SciandroneM.A nonmonotone trust-region method for generalized Nash equilibrium and related problems with strong convergence properties[J]. Computational Optimization and Applications,2017,12,156-173.
12 MigotT,MonicaG C.A parametrized variational inequality approach to track the solution set of a generalized Nash equilibrium problem[J].European Journal of Operational Research,2020,283,1136-1147.
13 MigotT,CojocaruM G.A decomposition method for a class of convex generalized Nash equilibrium problems[J].Optimization and Engineering,2020,3,1-27.
14 FanX,JiangL,LiM.Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints[J].Journal of Industrial and Management Optimization,2019,4,1795-1807.
15 Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems[M]. Springer Science and Business Media, 2007.
文章导航

/