Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization

References

• Ahmadi H, Shanbhag UV (2020) On the resolution of misspecified convex optimization and monotone variational inequality problems. Comput. Optim. Appl, ePub ahead of print June 22, https://doi.org/10.1007/s10589-020-00193-z.Google Scholar
• Ahmadi H, Aybat N, Shanbhag U (2020) On the analysis of inexact augmented Lagrangian schemes for misspecified conic convex programs. IEEE Trans Automatic Control. Forthcoming.Google Scholar
• Alpcan T, Basar T (2002) A game-theoretic framework for congestion control in general topology networks. Lawrence D, Zhu J, chairs. Proc. 41st IEEE Conf. Decision Control, vol. 2 (IEEE, Piscataway, NJ), 1218–1224.Google Scholar
• Altman E, Hayel Y, Kameda H (2007) Evolutionary dynamics and potential games in non-cooperative routing. Chlamtac I, Altman E, Basar T, Crowcroft J, Ephremides A, Miorandi D (steering committee). Proc. Fifth Internat. Sympos. Model. Optim. Mobile, Ad Hoc, Wireless Networks (IEEE, Piscataway, NJ), 1–5.Google Scholar
• Aysal TC, Yildiz ME, Sarwate AD, Scaglione A (2009) Broadcast gossip algorithms for consensus. IEEE Trans. Signal Processing 57(7):2748–2761.Crossref, Google Scholar
• Basar T, Olsder GJ (1999) Dynamic Noncooperative Game Theory, vol. 23 (SIAM, Philadelphia).Google Scholar
• Bernheim BD (1984) Rationalizable strategic behavior. Econometrica 52(4):1007–1028.Crossref, Google Scholar
• Bischi GI, Naimzada AK, Sbragia L (2007) Oligopoly games with local monopolistic approximation. J. Econom. Behav. Organ. 62(3):371–388.Crossref, Google Scholar
• Bischi GI, Sbragia L, Szidarovszky F (2008) Learning the demand function in a repeated cournot oligopoly game. Internat. J. Systems Sci. 39(4):403–419.Crossref, Google Scholar
• Boyd S, Ghosh A, Prabhakar B, Shah D (2006) Randomized gossip algorithms. IEEE/ACM Trans. Networking (TON) 14(SI):2508–2530.Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Google Scholar
• Byrd RH, Chin GM, Nocedal J, Wu Y (2012) Sample size selection in optimization methods for machine learning. Math. Programming 134(1):127–155.Crossref, Google Scholar
• Candogan O, Ozdaglar A, Parrilo PA (2013) Dynamics in near-potential games. Games Econom. Behav. 82:66–90.Crossref, Google Scholar
• Chow YS, Teicher H (2012) Probability Theory: Independence, Interchangeability, Martingales (Springer Science & Business Media, New York).Google Scholar
• Dafermos S (1988) Sensitivity analysis in variational inequalities. Math. Oper. Res. 13(3):421–434.Link, Google Scholar
• Davis D (2016) The asynchronous PALM algorithm for nonsmooth nonconvex problems. Preprint, submitted April 2, https://arxiv.org/abs/1604.00526.Google Scholar
• d’Esopo D (1959) A convex programming procedure. Naval Res. Logist. Quart. 6(1):33–42.Crossref, Google Scholar
• Facchinei F, Pang JS (2009) Nash equilibria: The variational approach. Palomar DP, Eldar YC, eds. Convex Optimization in Signal Processing and Communications (Cambridge University Press, Cambridge, UK), 443–493.Google Scholar
• Facchinei F, Piccialli V, Sciandrone M (2011) Decomposition algorithms for generalized potential games. Comput. Optim. Appl. 50(2):237–262.Crossref, Google Scholar
• Fudenberg D, Levine DK (1998) The Theory of Learning in Games, MIT Press Series on Economic Learning and Social Evolution, vol. 2 (MIT Press, Cambridge, MA).Google Scholar
• Fudenberg D, Ishii Y, Kominers SD (2014) Delayed-response strategies in repeated games with observation lags. J. Econom. Theory 150:487–514.Crossref, Google Scholar
• Ghadimi S, Lan G (2016) Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Programming 156(1–2):59–99.Crossref, Google Scholar
• Ghadimi S, Lan G, Zhang H (2016) Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Math. Programming 155(1–2):267–305.Crossref, Google Scholar
• González-Sánchez D, Hernández-Lerma O (2016) A survey of static and dynamic potential games. Sci. China Math. 59(11):2075–2102.Crossref, Google Scholar
• Grammatico S, Parise F, Colombino M, Lygeros J (2015) Decentralized convergence to Nash equilibria in constrained deterministic mean field control. IEEE Trans. Automatic Control 61(11):3315–3329.Crossref, Google Scholar
• Grinblatt M, Titman S, Wermers R (1995) Momentum investment strategies, portfolio performance, and herding: A study of mutual fund behavior. Amer. Econom. Rev. 85(5):1088–1105.Google Scholar
• Ho-Nguyen N, Kilinç-Karzan F (2019) Exploiting problem structure in optimization under uncertainty via online convex optimization. Math. Programming 177(1–2):113–147.Crossref, Google Scholar
• Jalilzadeh A, Shanbhag UV, Blanchet JH, Glynn PW (2018) Optimal smoothed variable sample-size accelerated proximal methods for structured nonsmooth stochastic convex programs. Preprint, submitted March 2, https://arxiv.org/abs/1803.00718.Google Scholar
• Jiang H, Shanbhag UV (2016) On the solution of stochastic optimization and variational problems in imperfect information regimes. SIAM J. Optim. 26(4):2394–2429.Crossref, Google Scholar
• Jiang H, Shanbhag UV, Meyn SP (2018) Distributed computation of equilibria in misspecified convex stochastic Nash games. IEEE Trans. Automatic Control 63(2):360–371.Crossref, Google Scholar
• Jofré A, Thompson P (2019) On variance reduction for stochastic smooth convex optimization with multiplicative noise. Math. Programming 174(1–2):253–292.Crossref, Google Scholar
• Kannan A, Shanbhag UV (2012) Distributed computation of equilibria in monotone Nash games via iterative regularization techniques. SIAM J. Optim. 22(4):1177–1205.Crossref, Google Scholar
• Kelly FP, Maulloo AK, Tan DK (1998) Rate control for communication networks: Shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49(3):237–252.Crossref, Google Scholar
• Kirman AP (1975) Learning by firms about demand conditions. Day RH, Groves T, eds. Adaptive Economic Models (Elsevier, New York), 137–156.Crossref, Google Scholar
• Koshal J, Nedić A, Shanbhag UV (2013) Regularized iterative stochastic approximation methods for stochastic variational inequality problems. IEEE Trans. Automatic Control 58(3):594–609.Crossref, Google Scholar
• Koshal J, Nedić A, Shanbhag UV (2016) Distributed algorithms for aggregative games on graphs. Oper. Res. 64(3):680–704.Link, Google Scholar
• Larsson T, Patriksson M (1994) A class of gap functions for variational inequalities. Math. Programming 64(1–3):53–79.Crossref, Google Scholar
• Lei J, Shanbhag UV (2017) A randomized inexact proximal best-response scheme for potential stochastic Nash games. Middleton R, Nesic D, co-chairs. 2017 IEEE 56th Annual Conf. Decision Control (CDC) (IEEE, Piscataway, NJ), 1646–1651.Google Scholar
• Lei J, Shanbhag UV (2018) Linearly convergent variable sample-size schemes for stochastic Nash games: Best-response schemes and distributed gradient-response schemes. 2018 IEEE Conf. Decision Control (CDC) (IEEE, Piscataway, NJ), 3547–3552.Google Scholar
• Lei J, Shanbhag UV, Pang JS, Sen S (2020) On synchronous, asynchronous, and randomized best-response schemes for computing equilibria in stochastic Nash games. Math. Oper. Res. 45(1):157–190.Google Scholar
• Leonard D, Nishimura K (1999) Nonlinear dynamics in the Cournot model without full information. Ann. Oper. Res. 89:165–173.Crossref, Google Scholar
• Marden JR (2007) Learning in large–scale games and cooperative control. Unpublished doctoral dissertation, University of California, Los Angeles, Los Angeles.Google Scholar
• Marden JR, Arslan G, Shamma JS (2009) Cooperative control and potential games. IEEE Trans. Systems Man Cybernetics B: Cybernetics 39(6):1393–1407.Crossref, Google Scholar
• Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Crossref, Google Scholar
• Nash JF Jr (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1):48–49.Crossref, Google Scholar
• Nesterov Y (2012) Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2):341–362.Crossref, Google Scholar
• Nisan N, Schapira M, Valiant G, Zohar A (2011) Best response mechanisms. Proc. Conf. Innovations Comput. Sci. 2011, 155–165.Google Scholar
• Pang JS, Sen S, Shanbhag UV (2017) Two-stage non-cooperative games with risk-averse players. Math. Programming 165(1):235–290.Crossref, Google Scholar
• Parise F, Grammatico S, Gentile B, Lygeros J (2015) Network aggregative games and distributed mean field control via consensus theory. Preprint, submitted June 25, https://arxiv.org/abs/1506.07719.Google Scholar
• Pearce DG (1984) Rationalizable strategic behavior and the problem of perfection. Econometrica 52(4):1029–1050.Crossref, Google Scholar
• Ravat U, Shanbhag UV (2011) On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games. SIAM J. Optim. 21(3):1168–1199.Crossref, Google Scholar
• Richtárik P, Takáč M (2014) Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Programming 144(1–2):1–38.Crossref, Google Scholar
• Robbins H, Siegmund D (1985) A convergence theorem for non negative almost supermartingales and some applications. Herbert Robbins Selected Papers (Springer, New York), 111–135.Crossref, Google Scholar
• Salehisadaghiani F, Pavel L (2016) Distributed Nash equilibrium seeking: A gossip-based algorithm. Automatica J. IFAC 72:209–216.Crossref, Google Scholar
• Schmidt M, Roux NL, Bach FR (2011) Convergence rates of inexact proximal-gradient methods for convex optimization. Adv. Neural Inform. Processing Systems 24:1458–1466.Google Scholar
• Scutari G, Barbarossa S, Palomar DP (2006) Potential games: A framework for vector power control problems with coupled constraints. Castanie F, general chair. Proc. IEEE Internat. Conf. Acoustics Speech Signal Processing, vol. 4 (IEEE, Piscataway, NJ), 241–244.Google Scholar
• Scutari G, Palomar DP (2010) Mimo cognitive radio: A game theoretical approach. IEEE Trans. Signal Processing 58(2):761–780.Crossref, Google Scholar
• Scutari G, Palomar DP, Facchinei F, Pang JS (2010) Convex optimization, game theory, and variational inequality theory. IEEE Signal Processing Magazine 27(3):35–49.Crossref, Google Scholar
• Shanbhag UV, Blanchet JH (2015) Budget-constrained stochastic approximation. Proc. 2015 Winter Simulation Conf. (IEEE, Piscataway, NJ), 368–379.Google Scholar
• Shanbhag UV, Pang JS, Sen S (2016) Inexact best-response schemes for stochastic Nash games: Linear convergence and iteration complexity analysis. Giua A, general chair. Decision Control (CDC), 2016 IEEE 55th Conf. (IEEE, Piscataway, NJ) 3591–3596.Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on Stochastic Programming, MPS/SIAM Series on Optimization, vol. 9 (SIAM, Philadelphia).Crossref, Google Scholar
• Shi W, Pavel L (2017) Lana: An ADMM-like Nash equilibrium seeking algorithm in decentralized environment. Sun J, general chair. 2017 Amer. Control Conf. (ACC) (IEEE, Piscataway, NJ), 285–290.Google Scholar
• Szidarovszky F (2004) Global stability analysis of a special learning process in dynamic oligopolies. J. Econom. Res. 9(2):175–190.Google Scholar
• Tatarenko T, Shi W, Nedich A (2018) Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking. Preprint, submitted September 18, https://arxiv.org/abs/1809.07383.Google Scholar
• Tseng P (2001) Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109(3):475–494.Crossref, Google Scholar
• Xu Y, Yin W (2015) Block stochastic gradient iteration for convex and nonconvex optimization. SIAM J. Optim. 25(3):1686–1716.Crossref, Google Scholar
• Ye M, Hu G (2017) Distributed Nash equilibrium seeking by a consensus based approach. IEEE Trans. Automatic Control 62(9):4811–4818.Crossref, Google Scholar
• Yi P, Pavel L (2019) An operator splitting approach for distributed generalized Nash equilibria computation. Automatica J. IFAC 102:111–121.Crossref, Google Scholar
• Yousefian F, Nedic A, Shanbhag UV (2013) A regularized smoothing stochastic approximation (RSSA) algorithm for stochastic variational inequality problems. Hill RR, general chair. 2013 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 933–944.Google Scholar
• Yousefian F, Nedić A, Shanbhag UV (2016) Self-tuned stochastic approximation schemes for non-Lipschitzian stochastic multi-user optimization and Nash games. IEEE Trans. Automatic Control 61(7):1753–1766.Crossref, Google Scholar
• Yu CK, van der Schaar M, Sayed A (2017) Distributed learning for stochastic generalized Nash equilibrium problems. IEEE Trans. Signal Processing 65(15):3893–3908.Crossref, Google Scholar
• Zhu M, Frazzoli E (2016) Distributed robust adaptive equilibrium computation for generalized convex games. Automatica J. IFAC 63:82–91.Crossref, Google Scholar