Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2304.03651 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929400795103232 |
|---|---|
| author | Lei, Jinlong Shanbhag, Uday V. Chen, Jie |
| author_facet | Lei, Jinlong Shanbhag, Uday V. Chen, Jie |
| contents | We consider a class of nonsmooth aggregative games over networks in stochastic regimes, where each player is characterized by a composite cost function $f_i+r_i$, $f_i$ is a smooth expectation-valued function dependent on its own strategy and an aggregate function of rival strategies, and $r_i$ is a nonsmooth convex function of its strategy with an efficient prox-evaluation. We design a fully distributed iterative proximal stochastic gradient method overlaid by a Tikhonov regularization, where each player may independently choose its steplengths and regularization parameters while meeting some coordination requirements. Under a monotonicity assumption on the pseudo-gradient mapping, we prove the almost sure convergence to the least-norm Nash equilibrium. In addition, when each $r_i$ is an indicator function of a compact convex set, we establish the convergence rate associated with the expected gap function at the time-averaged sequence. We further establish high probability bounds for the gap function via both Markov's inequality as well as a more refined argument that leverages Azuma's inequality. Furthermore, we consider the extension to the private hierarchical regime where each player is a leader with respect to a collection of private followers competing in a strongly monotone game, parametrized by leader decisions. By leveraging a convolution-smoothing framework, we present amongst the first fully distributed schemes for computing a Nash equilibrium of a game complicated by such a hierarchical structure. Based on this framework, we extend the rate statements to accommodate the computation of a hierarchical stochastic Nash equilibrium by using a Fitzpatrick gap function. Finally, we validate the proposed methods on a networked Nash-Cournot equilibrium problem and a hierarchical generalization, observing that regularization has a beneficial impact on empirical behavior. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_03651 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Distributed Iterative Tikhonov Method for Networked Monotone Aggregative Hierarchical Stochastic Games Lei, Jinlong Shanbhag, Uday V. Chen, Jie Optimization and Control We consider a class of nonsmooth aggregative games over networks in stochastic regimes, where each player is characterized by a composite cost function $f_i+r_i$, $f_i$ is a smooth expectation-valued function dependent on its own strategy and an aggregate function of rival strategies, and $r_i$ is a nonsmooth convex function of its strategy with an efficient prox-evaluation. We design a fully distributed iterative proximal stochastic gradient method overlaid by a Tikhonov regularization, where each player may independently choose its steplengths and regularization parameters while meeting some coordination requirements. Under a monotonicity assumption on the pseudo-gradient mapping, we prove the almost sure convergence to the least-norm Nash equilibrium. In addition, when each $r_i$ is an indicator function of a compact convex set, we establish the convergence rate associated with the expected gap function at the time-averaged sequence. We further establish high probability bounds for the gap function via both Markov's inequality as well as a more refined argument that leverages Azuma's inequality. Furthermore, we consider the extension to the private hierarchical regime where each player is a leader with respect to a collection of private followers competing in a strongly monotone game, parametrized by leader decisions. By leveraging a convolution-smoothing framework, we present amongst the first fully distributed schemes for computing a Nash equilibrium of a game complicated by such a hierarchical structure. Based on this framework, we extend the rate statements to accommodate the computation of a hierarchical stochastic Nash equilibrium by using a Fitzpatrick gap function. Finally, we validate the proposed methods on a networked Nash-Cournot equilibrium problem and a hierarchical generalization, observing that regularization has a beneficial impact on empirical behavior. |
| title | A Distributed Iterative Tikhonov Method for Networked Monotone Aggregative Hierarchical Stochastic Games |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2304.03651 |