Nash Equilibrium Problems With Scaled Congestion Costs and Shared Constraints

被引:103
作者
Yin, Huibing [1 ]
Shanbhag, Uday V. [1 ]
Mehta, Prashant G. [1 ]
机构
[1] Univ Illinois, Urbana, IL 61801 USA
基金
美国国家科学基金会;
关键词
Game theory; optimization; variational methods; OPTICAL NETWORKS; GAMES;
D O I
10.1109/TAC.2011.2137590
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider a class of convex Nash games where strategy sets are coupled across agents through a common constraint and payoff functions are linked via a scaled congestion cost metric. A solution to a related variational inequality problem provides a set of Nash equilibria characterized by common Lagrange multipliers for shared constraints. While this variational problem may be characterized by a non-monotone map, it is shown to admit solutions, even in the absence of restrictive compactness assumptions on strategy sets. Additionally, we show that the equilibrium is locally unique both in the primal space as well as in the larger primal-dual space. The existence statements can be generalized to accommodate a piece-wise-smooth congestion metric while affine restrictions, surprisingly, lead to both existence and global uniqueness guarantees. In the second part of the technical note, we discuss distributed computation of such equilibria in monotone regimes via a distributed iterative Tikhonov regularization (ITR) scheme. Application to a class of networked rate allocation games suggests that the ITR schemes perform better than their two-timescale counterparts.
引用
收藏
页码:1702 / 1708
页数:7
相关论文
共 20 条
[1]   Distributed algorithms for Nash equilibria of flow control games [J].
Alpcan, T ;
Basar, T .
ADVANCES IN DYNAMIC GAMES: APPLICATIONS TO ECONOMICS, FINANCE, OPTIMIZATION, AND STOCHASTIC CONTROL, 2005, 7 :473-498
[2]   Hybrid noncooperative game model for wireless communications [J].
Alpcan, Tansu ;
Basar, Tamer .
ADVANCES IN DYNAMIC GAME THEORY: NUMERICAL METHODS, ALGORITHMS, AND APPLICATIONS TO ECOLOGY AND ECONOMICS, 2007, 9 :411-+
[3]  
[Anonymous], 1990, CLASSICS APPL MATH
[4]  
[Anonymous], 1999, NUMERICAL OPTIMIZATI, DOI DOI 10.1007/B98874
[5]  
[Anonymous], 2003, SPRINGER SERIES OPER, DOI DOI 10.1007/978-0-387-21815-16
[6]  
ANTIPIN AS, 2003, ZH VYCH MAT MAT FIZ, V43, P1451
[7]  
Aubin J.-P., 1979, Studies in Mathematics and Its Applications, V7
[8]  
Basar T., 1999, SOC IND APPL MATH, V2nd
[9]  
Facchinei F., 2009, Convex Optimization in Signal Processing and Communications
[10]   On generalized Nash games and variational inequalities [J].
Facchinei, Francisco ;
Fischer, Andreas ;
Piccialli, Veronica .
OPERATIONS RESEARCH LETTERS, 2007, 35 (02) :159-164