{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T16:07:44Z","timestamp":1774022864077,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,8]],"date-time":"2024-04-08T00:00:00Z","timestamp":1712534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CAREER","award":["ECCS-1944500"],"award-info":[{"award-number":["ECCS-1944500"]}]},{"name":"NSF","award":["ECCS-2231863"],"award-info":[{"award-number":["ECCS-2231863"]}]},{"name":"ONR","award":["N00014-22-1-2757"],"award-info":[{"award-number":["N00014-22-1-2757"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            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 \u03f5\n            <jats:sup>-4<\/jats:sup>\n            that appears to be best known result for this class of constrained stochastic optimization problems, where \u03f5 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.\n          <\/jats:p>","DOI":"10.1145\/3632525","type":"journal-article","created":{"date-parts":[[2023,11,11]],"date-time":"2023-11-11T09:36:26Z","timestamp":1699695386000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games"],"prefix":"10.1145","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3734-1082","authenticated-orcid":false,"given":"Afrooz","family":"Jalilzadeh","sequence":"first","affiliation":[{"name":"University of Arizona, Tucson, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2628-741X","authenticated-orcid":false,"given":"Farzad","family":"Yousefian","sequence":"additional","affiliation":[{"name":"Rutgers University New Brunswick, New Brunswick, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1042-8118","authenticated-orcid":false,"given":"Mohammadjavad","family":"Ebrahimi","sequence":"additional","affiliation":[{"name":"Rutgers University New Brunswick, New Brunswick, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,8]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600425"},{"key":"e_1_3_1_4_2","volume-title":"Convex Analysis and Optimization","author":"Bertsekas D. P.","year":"2003","unstructured":"D. P. Bertsekas, A. Nedi\u0107, and A. Ozdaglar. 2003. Convex Analysis and Optimization. Vol. 1. Athena Scientific."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2553085"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-010-9757-3"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1080\/02331934.2010.539689"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1161-4"},{"key":"e_1_3_1_9_2","first-page":"4510","volume-title":"IEEE 55th Conference on Decision and Control (CDC\u201916)","author":"Cui S.","year":"2016","unstructured":"S. Cui and U. V. Shanbhag. 2016. On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems. In IEEE 55th Conference on Decision and Control (CDC\u201916). IEEE, 4510\u20134515."},{"issue":"2","key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/s11228-021-00572-6","article-title":"On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems","volume":"29","author":"Cui S.","year":"2021","unstructured":"S. Cui and U. V. Shanbhag. 2021. On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems. Set-val. Variat. Anal. 29, 2 (2021), 453\u2013499.","journal-title":"Set-val. Variat. Anal."},{"key":"e_1_3_1_11_2","first-page":"15111","volume-title":"Advances in Neural Information Processing Systems","author":"Deng Y.","year":"2020","unstructured":"Y. Deng, M. M. Kamani, and M. Mahdavi. 2020. Distributionally robust federated averaging. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 15111\u201315122. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/ac450d10e166657ec8f93a1b65ca1b14-Paper.pdf"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/2839357.2839358"},{"key":"e_1_3_1_13_2","volume-title":"Finite-dimensional Variational Inequalities and Complementarity Problems. Vols. I, II","author":"Facchinei F.","year":"2003","unstructured":"F. Facchinei and J.-S. Pang. 2003. Finite-dimensional Variational Inequalities and Complementarity Problems. Vols. I, II. Springer-Verlag, New York."},{"key":"e_1_3_1_14_2","volume-title":"Advances in Neural Information Processing Systems","author":"Goodfellow I.","year":"2014","unstructured":"I. Goodfellow, J. Pouget-Abadie, Me. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. 2014. Generative adversarial nets. In Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (Eds.), Vol. 27. Curran Associates, Inc. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2014\/file\/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf"},{"key":"e_1_3_1_15_2","article-title":"On the convergence of single-call stochastic extra-gradient methods","volume":"32","author":"Hsieh Y.-G.","year":"2019","unstructured":"Y.-G. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos. 2019. On the convergence of single-call stochastic extra-gradient methods. Adv. Neural Inf. Process. Syst. 32 (2019).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1031953"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-010-9613-x"},{"key":"e_1_3_1_18_2","first-page":"3551","volume-title":"Winter Simulation Conference (WSC\u201919)","author":"Jalilzadeh A.","year":"2019","unstructured":"A. Jalilzadeh and U. V. Shanbhag. 2019. A proximal-point algorithm with variable sample-sizes (PPAWSS) for monotone stochastic variational inequality problems. In Winter Simulation Conference (WSC\u201919). IEEE, 3551\u20133562."},{"issue":"4","key":"e_1_3_1_19_2","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1287\/stsy.2022.0095","article-title":"Smoothed variable sample-size accelerated proximal methods for nonsmooth stochastic convex programs","volume":"12","author":"Jalilzadeh A.","year":"2022","unstructured":"A. Jalilzadeh, U. V. Shanbhag, J. H. Blanchet, and P. W. Glynn. 2022. Smoothed variable sample-size accelerated proximal methods for nonsmooth stochastic convex programs. Stoch. Syst. 12, 4 (2022), 373\u2013410.","journal-title":"Stoch. Syst."},{"key":"e_1_3_1_20_2","doi-asserted-by":"crossref","unstructured":"A. Jalilzadeh F. Yousefian and M. Ebrahimi. 2023. Stochastic approximation for estimating the price of stability in stochastic Nash games. arXiv preprint: https:\/\/arxiv.org\/abs\/2203.01271","DOI":"10.1145\/3632525"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.925853"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/1048637"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1287\/10-SSY011"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/110825352"},{"key":"e_1_3_1_25_2","first-page":"2930","volume-title":"American Control Conference","author":"Kannan A.","year":"2014","unstructured":"A. Kannan and U. V. Shanbhag. 2014. The pseudomonotone stochastic variational inequality problem: Analytical statements and stochastic extragradient schemes. In American Control Conference. IEEE, 2930\u20132935."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-019-00120-x"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1357378"},{"key":"e_1_3_1_28_2","first-page":"747","article-title":"The extragradient method for finding saddle points and other problems","volume":"12","author":"Korpelevich G. M.","year":"1976","unstructured":"G. M. Korpelevich. 1976. The extragradient method for finding saddle points and other problems. Matecon 12 (1976), 747\u2013756.","journal-title":"Matecon"},{"key":"e_1_3_1_29_2","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1109\/TAC.2012.2215413","article-title":"Regularized iterative stochastic approximation methods for variational inequality problems","volume":"58","author":"Koshal J.","year":"2013","unstructured":"J. Koshal, A. Nedi\u0107, and U. V. Shanbhag. 2013. Regularized iterative stochastic approximation methods for variational inequality problems. IEEE Trans. Automat. Control 58(3) (2013), 594\u2013609.","journal-title":"IEEE Trans. Automat. Control"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496309867"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-009-9522-7"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0330046"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1785414.1785439"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575559"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622525"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2011.09.043"},{"key":"e_1_3_1_41_2","first-page":"933","volume-title":"Winter Simulations Conference (WSC\u201913)","author":"Yousefian F.","year":"2013","unstructured":"F. Yousefian, A. Nedi\u0107, and U. V. Shanbhag. 2013. A regularized smoothing stochastic approximation (RSSA) algorithm for stochastic variational inequality problems. In Winter Simulations Conference (WSC\u201913). IEEE, 933\u2013944."},{"key":"e_1_3_1_42_2","doi-asserted-by":"crossref","first-page":"5831","DOI":"10.1109\/CDC.2014.7040302","volume-title":"53rd IEEE Conference on Decision and Control","author":"Yousefian F.","year":"2014","unstructured":"F. Yousefian, A. Nedi\u0107, and U. V. Shanbhag. 2014. Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems. In 53rd IEEE Conference on Decision and Control. IEEE, 5831\u20135836."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1175-y"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11228-018-0472-9"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632525","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:01Z","timestamp":1750178161000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,8]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3632525"],"URL":"https:\/\/doi.org\/10.1145\/3632525","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,8]]},"assertion":[{"value":"2022-03-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}