EUVIMEDEUVIMED entdecken
Crossref

Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games

Afrooz Jalilzadeh, Farzad Yousefian, Mohammadjavad Ebrahimi

ACM Transactions on Modeling and Computer Simulation · 30.04.2024 · 34 (2) · 1-24

DOI: 10.1145/3632525 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Modeling and Computer Simulation, online erschienen am 08.04.2024. Verfasst von Afrooz Jalilzadeh und 2 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: NSF CAREER, NSF, ONR.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The goal in this article is to approximate the Price of Stability (PoS) in stochastic Nash games using stochastic approximation (SA) schemes. PoS is among the most popular metrics in game theory and provides an avenue for estimating the efficiency of Nash games. In particular, evaluating the PoS can help with designing efficient networked systems, including communication networks and power market mechanisms. Motivated by the absence of efficient methods for computing the PoS, first we consider stochastic optimization problems with a nonsmooth and merely convex objective function and a merely monotone stochastic variational inequality (SVI) constraint. This problem appears in the numerator of the PoS ratio. We develop a randomized block-coordinate stochastic extra-(sub)gradient method where we employ a novel iterative penalization scheme to account for the mapping of the SVI in each of the two gradient updates of the algorithm. We obtain an iteration complexity of the order ϵ -4 that appears to be best known result for this class of constrained stochastic optimization problems, where ϵ denotes an arbitrary bound on suitably defined infeasibility and suboptimality metrics. Second, we develop an SA-based scheme for approximating the PoS and derive lower and upper bounds on the approximation error. To validate the theoretical findings, we provide preliminary simulation results on a networked stochastic Nash Cournot competition.

Förderung

  • NSF CAREER
  • NSF
  • ONR

Zitieren

APA

Jalilzadeh, A., Yousefian, F., & Ebrahimi, M. (2024). Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games. ACM Transactions on Modeling and Computer Simulation, 34(2), 1-24. https://doi.org/10.1145/3632525

Vancouver

Jalilzadeh A, Yousefian F, Ebrahimi M. Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games. ACM Transactions on Modeling and Computer Simulation. 2024;34(2):1-24. doi:10.1145/3632525

BibTeX
@article{Jalilzadeh2024,
  author = {Jalilzadeh, Afrooz and Yousefian, Farzad and Ebrahimi, Mohammadjavad},
  title = {Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games},
  journal = {ACM Transactions on Modeling and Computer Simulation},
  year = {2024},
  volume = {34},
  number = {2},
  pages = {1--24},
  doi = {10.1145/3632525}
}
Kostenlos starten →