Distributed GNE Seeking Under Partial-Decision Information Over Networks via a Doubly-Augmented Operator Splitting Approach
Open accessThe DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Abstract
We consider distributed computation of generalized Nash equilibrium (GNE) over networks, in games with shared coupling constraints. Existing methods require that each player has full access to opponents' decisions. In this paper, we assume that players have only partial-decision information, and can communicate with their neighbors over an arbitrary undirected graph. We recast the problem as that of finding a zero of a sum of monotone operators through primal-dual analysis. To distribute the problem, we doubly augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We introduce a single-layer algorithm, fully distributed with respect to both primal and dual variables. We show its convergence to a variational GNE with fixed step sizes, by reformulating it as a forward-backward iteration for a pair of doubly-augmented monotone operators.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Convex Analysis and Monotone Operator Theory in Hilbert Spaces
Bauschke, H. H., & Combettes, P. L. (2011) · CMS Books in Mathematics · doi:10.1007/978-1-4419-9467-7 · Cited by 2,962
Graph Theoretic Methods in Multiagent Networks
Mesbahi, M., & Egerstedt, M. (2010) · Princeton University Press eBooks · doi:10.1515/9781400835355 · Cited by 2,897 · cited 1×
“If agent i can get information from agent j , then ( j, i ) ∈ E and agent j belongs to agent i ’s neighbor set and connected if any two agents are connected [33].”
BackgroundExistence and Uniqueness of Equilibrium Points for Concave N-Person Games
Rosen, J. B. (1965) · Econometrica · doi:10.2307/1911749 · Cited by 2,686
A Social Equilibrium Existence Theorem*
Debreu, G. (1952) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.38.10.886 · Cited by 1,504 · cited 1×
“Literature review: The study of GNE dates back to the work presented in [9] and [10]; see [11] and [12] for a historical review.”
BackgroundGeneralized Nash Equilibrium Problems
Facchinei, F., & Kanzow, C. (2009) · Annals of Operations Research · doi:10.1007/s10479-009-0653-x · Cited by 914
Saad, W., Han, Z., Poor, H., & Basar, T. (2012) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2186410 · Cited by 891 · cited 1×
“…(GNE) problems in games with shared coupling constraints arise in various network scenarios, where a set of players (agents) compete for limited network resources, e.g., power grids and smart grids [2], optical networks [3], wireless communication networks [4], [5], electric vehicle charging [7].”
Distributed Nash Equilibrium Seeking by a Consensus Based Approach
Ye, M., & Hu, G. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2688452 · Cited by 520 · cited 3×
“Remark 6: Note that Assumption 4 on F is weaker than those in the work presented in [1] and [27].”
BackgroundMethodDistributed Algorithms for Aggregative Games on Graphs
Koshal, J., Nedić, A., & Shanbhag, U. V. (2016) · Operations Research · doi:10.1287/opre.2016.1501 · Cited by 341 · cited 6×
“This extra correction term compared to a consensus or a gossip-based algorithm [25], [26], is instrumental in proving convergence with fixed step sizes, on a single-time scale, in the partial-information case.”
BackgroundMethodInfluentialA Passivity-Based Approach to Nash Equilibrium Seeking Over Networks
Gadjov, D., & Pavel, L. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2833140 · Cited by 339 · cited 4×
“To account for partial-decision information, we endow each agent with an auxiliary variable that estimates the other agents’ decisions (primal variables), as in NE seeking over networks [28], [29].”
BackgroundMethodInfluentialSelf-citationProx-regular functions in variational analysis
Poliquin, R. A., & Rockafellar, R. T. (1996) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-96-01544-9 · Cited by 333
Distributed Nash equilibrium seeking for aggregative games with coupled constraints
Liang, S., Yi, P., & Hong, Y. (2017) · Automatica · doi:10.1016/j.automatica.2017.07.064 · Cited by 328 · cited 2×
“This is relaxed in [13], via a continuous-time consensus and projected gradient dynamics, and in [40] via a two-layer consensus-based projected-gradient algorithm, both only for aggregative games.”
BackgroundOpinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate
Ghaderi, J., & Srikant, R. (2014) · Automatica · doi:10.1016/j.automatica.2014.10.034 · Cited by 325 · cited 1×
“…radio networks, where users adaptively adjust their operating parameters based on interactions with the environment and other users in the network [20], congestion games in ad hoc networks [21], to networked Nash–Cournot competition [22], and opinion dynamics in social networks [23], [24].”
BackgroundDistributed Nash equilibrium seeking: A gossip-based algorithm
Salehisadaghiani, F., & Pavel, L. (2016) · Automatica · doi:10.1016/j.automatica.2016.06.004 · Cited by 309
Self-citationAn operator splitting approach for distributed generalized Nash equilibria computation
Yi, P., & Pavel, L. (2019) · Automatica · doi:10.1016/j.automatica.2019.01.008 · Cited by 271 · cited 3×
“For games with generally coupled costs and affine coupling constraints, distributed and center-free GNE seeking is investigated via an operator approach in [17], [18], [36]: a forward-backward”
InfluentialSelf-citationDynamic Control of Agents Playing Aggregative Games With Coupling Constraints
Grammatico, S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2672902 · Cited by 212 · cited 1×
“We show its convergence to a variational GNE with fixed step sizes, by re-formulating it as a forward–backward iteration for a pair of doubly-augmented monotone operators.”
MethodConvergence Rate Analysis of Several Splitting Schemes
Davis, D., & Yin, W. (2016) · Scientific Computation · doi:10.1007/978-3-319-41589-5_4 · Cited by 206 · cited 1×
“For nonexpan-sive operators it is known that such iteration has a convergence rate of O (1 /k ) [39], therefore under assumption of cocoercivity on the extended pseudogradient, the algorithm will enjoy it.”
BackgroundCompetitive Targeted Advertising Over Networks
Bimpikis, K., Ozdaglar, A., & Yildiz, E. (2016) · Operations Research · doi:10.1287/opre.2015.1430 · Cited by 143 · cited 1×
“competition [22], and opinion dynamics in social networks [23], [24].”
BackgroundOpportunistic Spectrum Access for CR-VANETs: A Game-Theoretic Approach
Cheng, N., Zhang, N., Lu, N., Shen, X., Mark, J. W., & Liu, F. (2013) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2013.2274201 · Cited by 137 · cited 1×
“n scenarios range from spectrum access in cognitive radio networks, where users adaptively adjust their operating parameters based on interactions with the environment and other users in the network, [20], congestion games in ad-hoc networks, [21], to networked Nash-Cournot competition, [22], and opinion dynamics in s…”
BackgroundNetwork Games: Theory, Models, and Dynamics
Menache, I., & Ozdaglar, A. (2011) · Synthesis lectures on communication networks · doi:10.2200/s00330ed1v01y201101cnt009 · Cited by 137
Salehisadaghiani, F., Shi, W., & Pavel, L. (2019) · Automatica · doi:10.1016/j.automatica.2019.01.012 · Cited by 128 · cited 4×
“To account for partial-decision information, we endow each agent with an auxiliary variable that estimates the other agents’ decisions (primal variables), as in NE seeking over networks [28], [29].”
BackgroundMethodInfluentialSelf-citationDistributed robust adaptive equilibrium computation for generalized convex games
Zhu, M., & Frazzoli, E. (2015) · Automatica · doi:10.1016/j.automatica.2015.10.012 · Cited by 127
Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
Yu, C.-K., van der Schaar, M., & Sayed, A. H. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2695451 · Cited by 119 · cited 1×
“work Cournot game appeared also in the numerical studies of [37] (penalty-based algorithm, reaching a region near the pure penalized NE), and [17] (dual-distributed algorithm), but both assumed perfect opponents’ decision information.”
BackgroundAtomic Congestion Games on Graphs and Their Applications in Networking
Tekin, C., Liu, M., Southwell, R., Huang, J., & Ahmad, S. H. A. (2012) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2012.2182779 · Cited by 100 · cited 1×
“…radio networks, where users adaptively adjust their operating parameters based on interactions with the environment and other users in the network [20], congestion games in ad hoc networks [21], to networked Nash–Cournot competition [22], and opinion dynamics in social networks [23], [24].”
BackgroundGames with coupled propagated constraints in optical networks with multi-link topologies
Pan, Y., & Pavel, L. (2009) · Automatica · doi:10.1016/j.automatica.2008.11.007 · Cited by 71 · cited 1×
“…(GNE) problems in games with shared coupling constraints arise in various network scenarios, where a set of players (agents) compete for limited network resources, e.g., power grids and smart grids [2], optical networks [3], wireless communication networks [4], [5], electric vehicle charging [7].”
BackgroundSelf-citationCournot competition in networked markets
Bimpikis, K., Ehsani, S., & İlkılıç, R. (2014) · ACM Conference on Economics and Computation (EC) · doi:10.1145/2600057.2602882 · Cited by 69 · cited 3×
“…radio networks, where users adaptively adjust their operating parameters based on interactions with the environment and other users in the network [20], congestion games in ad hoc networks [21], to networked Nash–Cournot competition [22], and opinion dynamics in social networks [23], [24].”
BackgroundMethodA doubly-augmented operator splitting approach for distributed GNE seeking over networks
Pavel, L. (2018) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2018.8619821 · Cited by 13 · cited 5×
“Compared to the work presented in [1], here we relax the assumption of cocoercivity of the extended pseudo-gradient.”
BackgroundMethodInfluentialSelf-citation
Metadata
- Authors
- Pavel, L.
- Venue
- IEEE Transactions on Automatic Control
- Published
- 2020-04
- Volume
- 65
- Issue
- 4
- Pages
- 1584-1597
- ISSN
- 0018-9286 (ISSN-L)
- 1558-2523
- 2334-3303
- OpenAlex
- W2951873227
- Cited by
- 159
- References
- 26
- FWCI
- 8.40
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.