求解廣義納什均衡問題的增量罰算法

羅美菊, 吳歐

(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