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

doi:10.15960/j.cnki.issn.1007-6093.2023.03.010

运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 129-136.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.010

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

侯剑¹^,²^,*(), 李萌萌², 文竹²

1. 复旦大学经济学院, 上海 200433
2. 内蒙古工业大学经济管理学院, 内蒙古呼和浩特 010051

收稿日期:2021-06-09 出版日期:2023-09-15 发布日期:2023-09-14
通讯作者: 侯剑 E-mail:houjianimut@163.com
作者简介:侯剑, E-mail: houjianimut@163.com

The method for a class of Nash equilibrium game

Jian HOU¹^,²^,*(), Mengmeng LI², Zhu WEN²

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:2021-06-09 Online:2023-09-15 Published:2023-09-14
Contact: Jian HOU E-mail:houjianimut@163.com

摘要/Abstract

摘要：

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

关键词: 纳什均衡, Nikaido Isoda函数, 约束优化, 强凸函数

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.

Key words: Nash equilibrium game, Nikaido-Isoda function, constrained optimization problem, strongly convex function

中图分类号:

O225

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

Jian HOU, Mengmeng LI, Zhu WEN. The method for a class of Nash equilibrium game[J]. Operations Research Transactions, 2023, 27(3): 129-136.

图/表 3

参考文献 15

1	LuQ,LuS,LengY.A Nash-Stackelberg game approach in regional energy market considering users' integrated demand response[J].Energy,2019,175,456-470. doi: 10.1016/j.energy.2019.03.079
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. doi: 10.1007/s11276-019-01952-5
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. doi: 10.1007/s00170-014-5922-4
5	MamageishviliA,MihalákM,MüllerD.Tree Nash equilibria in the network creation game[J]. Internet Mathematics,2015,11,472-486. doi: 10.1080/15427951.2015.1016248
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.

$\varepsilon$	$x^{1}$	$x^{2}$
1$\times10^{-1}$	5.328 372 222 558 07	5.328 372 273 251 82
1$\times10^{-3}$	5.333 284 016 767 36	5.333 283 732 542 19
1$\times10^{-5}$	5.333 333 512 035 43	5.333 333 889 177 50
1$\times10^{-7}$	5.333 333 111 956 61	5.333 333 677 495 92

${\rm player}\ \nu$	${\rm 1}$	${\rm 2}$	${\rm 3}$	${\rm 4}$	${\rm 5}$	${\rm 6}$
$c_{i}$	${\rm 0.04 }$	${\rm 0.035 }$	${\rm 0.125 }$	${\rm 0.016 6 }$	${\rm 0.05 }$	${\rm 0.05 }$
$d_{i}$	${\rm 2 }$	${\rm 1.75 }$	${\rm 1 }$	${\rm 3.25 }$	${\rm 3 }$	${\rm 3 }$

$\varepsilon$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$	$x_{6}$
1$\times10^{-1}$	46.661 555	32.156 981	15.000 217	22.126 220	12.328 712	12.331 506
1$\times10^{-3}$	46.661 654	32.148 613	15.008 479	22.092 360	12.354 163	12.339 830
1$\times10^{-5}$	46.661 522	32.159 056	14.999 815	22.010 223	12.366 374	12.338 851

[1]	何新亚, 谷爱玲. VaR约束下两个相互竞争保险公司的最优再保险投资策略[J]. 运筹学学报, 2023, 27(3): 1-20.
[2]	刘鹏杰, 江羡珍, 宋丹. 一类具有充分下降性的谱共轭梯度法[J]. 运筹学学报, 2022, 26(4): 87-97.
[3]	成夏炎, 何滢, 赵聪聪, 李荣珩. 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022, 26(3): 109-119.
[4]	孙聪, 张亚. 梯度法简述[J]. 运筹学学报, 2021, 25(3): 119-132.
[5]	于海, 詹婉荣. 强收敛的球松弛CQ算法及其应用[J]. 运筹学学报, 2021, 25(1): 50-60.
[6]	林杨, 王应明. 不确定偏好序下的双边匹配博弈[J]. 运筹学学报, 2020, 24(1): 155-162.
[7]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[8]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[9]	张龙, 张玉忠, 柏庆国. 一类博弈排序问题的纳什均衡存在性证明 [J]. 运筹学学报, 2018, 22(1): 87-96.
[10]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[11]	陈宁, 孙文瑜, 袁锦昀. 解线性等式约束优化问题的模式搜索过滤集方法[J]. 运筹学学报, 2015, 19(3): 96-107.
[12]	刘水霞, 陈国庆. 求解互补约束优化问题的乘子松弛法[J]. 运筹学学报, 2014, 18(4): 119-130.
[13]	徐屹嵩, 王应明. 指派问题的多重最优解的择优方法[J]. 运筹学学报, 2014, 18(2): 96-102.
[14]	戴彧虹，刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18(1): 69-92.
[15]	刘媛媛, 欧宜贵. 基于非单调技术的ODE型混合方法[J]. 运筹学学报, 2013, 17(3): 11-22.

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

The method for a class of Nash equilibrium game

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 15

相关文章 15

编辑推荐

Metrics

本文评价