求解广义纳什均衡问题的增量罚算法

罗美菊, 吴欧

(1.辽宁大学数学院,辽宁 沈阳 110036;2.中国人民解放军理工大学理学院,江苏 南京 210007)

求解广义纳什均衡问题的增量罚算法

罗美菊1, 吴欧2

(1.辽宁大学数学院,辽宁 沈阳 110036;2.中国人民解放军理工大学理学院,江苏 南京 210007)

研究每个局中人的决策集都有可能与竞争者的决策集有关的广义纳什均衡问题.给出了该广义纳什均衡问题罚函数形式的再定式.通过分析其KKT点的特点,进一步给出了求解广义纳什均衡问题的增量罚算法.

广义纳什均衡问题;罚函数;KKT条件;算法

1 引言

广义纳什均衡问题(generalized Nash equilibrium problem简记为GNEP)是标准的纳什均衡问题的一种推广.它考虑每个局中人的决策集都有可能与竞争者的决策集有关的情形.最早的关于GNEP的研究在1952年由文献[1]给出.此后,在1965年文献[2]中考虑了所有局中人的决策都满足相同的约束条件的GNEP.此外,1991年文献[3]运用变分不等式或拟变分不等式再定式的方法考虑了GNEP.广义纳什均衡问题在实际中有着广泛的应用.特别地,近期关于GNEP的研究大部分都集中在工程应用上[45],主要目的是从博弈论的观点得到更好的平衡系统.

关于GNEP,对于不同的目标函数和问题集目前已有很多方法对其求解.其中比较著名的是将GNEP表示成拟变分不等式问题[3,6],再进一步求解.此外,通过引入拟变分不等式问题的价值函数,也可将GNEP再定式为最小值为零的最优化问题[7],进而应用全局优化方法求解.亦可通过罚函数方法把GNEP转化成一系列纳什均衡问题,然后给出该纳什均衡问题变分不等式形式的再定式,进而对其求解[6,8].

本文提出了一种新的求解GNEP的方法–增量罚函数方法.利用该方法在一定条件下能得到合理的GNEP的解.

2 广义纳什均衡问题

本文考虑有N个局中人的非合作博弈问题.以后把第v个局中人简单的记作v.用nv维向量xv表示局中人v的策略,其中nv为正整数.将所有局中人的策略用向量

3 广义纳什均衡问题的再定式

4 求解广义纳什均衡问题的增量罚算法

[1]Debreu G.A social equilibrium existence theorem[J].Proceedings of the National Academy of Sciences, 1952,38:886-893.

[2]Rosen J B.Existence and uniqueness of equilibrium points for concave N-person games[J].Econometrica, 1965,33:520-534.

[3]Harker P T.Generalized Nash games and quasi-variational inequalities[J].European Journal of Operational Research,1991,54:81-94.

[4]Kesselman A,Leonardi S,Bonifaci V.Game-theoretic analysis of internet switching with sel fi sh users[J]. Proceedings of the First International Workshop on Internet and Network Economics,WINE,Lecture Notes in Computer Science,2005,3828:236-245.

[5]Pang J S,Scutari G,Facchinei F,et al.Distributed power allocation with rate constraints in Gaussian parallel interference channels[J].IEEE Transactions on Information Theory,2008,54:3471-3489.

[6]Pang J S,Fukushima M.Quasi-variational inequalities,generalized Nash equilibria,multi-leader-follower games[J].Computational Management Science,2005,2:21-56.

[7]Fukushima M.A class of gap functions for quasi-variational inequality problems[J].Journal of Industrial and Management Optimization,2007,3:165-171.

[8]Facchinei F,Pang J S.Large-Scale Nonlinear Optimization[M].Heidelberg:Springer-Verlag,2006.

Incremental penalty method for solving generalized NASH equilibrium problem

Luo Meiju1,Wu Ou2
(1.School of Mathematics,Liaoning University,Shenyang 110036,China;
2.College of Science,PLA University of Science and Technology,Nanjing 210007,China)

This paper is concerned with the generalized Nash equilibrium problem(GNEP),in which each player′s strategy set may depend on the rival players′strategies.We then propose a penalized reformulation for GNEP.Furthermore,we present an incremental penalty method for solving GNEP by analysis characteristic of the KKT points.

generalized Nash equilibrium problem,penalty function,KKT condition,algorithm

O225

A

1008-5513(2012)05-0599-05

2011-12-10.

辽宁大学青年基金(2011LDQN09).

罗美菊(1982-),博士,讲师,研究方向：随机均衡问题及其应用.

2010 MSC:90C33