Approximate Nash Equilibria in Large Nonconvex Aggregative Games

References

• [1] Aubin J, Ekeland I (1976) Estimates of the duality gap in nonconvex optimization. Math. Oper. Res. 1(3):225–245.Link, Google Scholar
• [2] Basile A, Graziano M, Pesce M (2016) Oligopoly and cost sharing in economics with public goods. Internat. Econom. Rev. 57(2):487–505.Crossref, Google Scholar
• [3] Bertsekas D (1979) Convexification procedures and decomposition methods for nonconvex optimization problems. J. Optim. Theory Appl. 29(2):169–197.Crossref, Google Scholar
• [4] Bertsekas D (1996) Constrained-Optimization and Lagrangian Multiplier Methods (Athena Scientific, Belmont, MA).Google Scholar
• [5] Bertsekas D (2009) Convex Optimization Theory (Athena Scientific, Belmont, MA).Google Scholar
• [6] Bertsekas D, Sandell N (1982) Estimates of the duality gap for large-scale separable nonconvex optimization problems. 21st IEEE Conf. Decision Control (IEEE, Orlando, FL), 782–785.Google Scholar
• [7] Bertsekas D, Lauer G, Sandell N, Posbergh T (1983) Optimal short-term scheduling of large-scale power systems. IEEE Trans. Automatic Control 28(1):1–11.Crossref, Google Scholar
• [8] Bi Y, Tang A (2020) Duality gap estimation via a refined Shapley–Folkman lemma. SIAM J. Optim. 30(2):1094–1118.Crossref, Google Scholar
• [9] Corchón L (1994) Comparative statics for aggregative games: The strong concavity case. Math. Soc. Sci. 28(3):151–165.Crossref, Google Scholar
• [10] Dafermos S (1980) Traffic equilibrium and variational inequalities. Transportation Sci. 14(1):42–54.Link, Google Scholar
• [11] David J, Castrillo P, Verdier T (1992) A general analysis of rent-seeking games. Public Choice 73(3):335–350.Crossref, Google Scholar
• [12] Ekeland I, Témam R (1999) Convex Analysis and Variational Problems (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [13] Facchinei F, Pang J (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems (Springer-Verlag, New York).Google Scholar
• [14] Fang E, Liu H, Wang M (2019) Blessing of massive scale: Spatial graphical model estimation with a total cardinality constraint approach. Math. Programming 176(1–2):175–205.Crossref, Google Scholar
• [15] Foucart R, Wan C (2018) Strategic decentralization and the provision of global public goods. J. Environ. Econom. Management 92:537–558.Crossref, Google Scholar
• [16] Hiriart-Urruty J, Lemarechal C (1993) Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods (Springer-Verlag, Berlin/Heidelberg).Crossref, Google Scholar
• [17] Hofbauer J, Sigmund K (1998) Evolutionary Games and Population Dynamics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [18] Horta J, Altman E, Caujolle M, Kofman D, Menga D (2018) Real-time enforcement of local energy market transactions respecting distribution grid constraints. Popovski P, ed. 2018 IEEE Internat. Conf. Comm. Control Comput. Tech. Smart Grids (IEEE, Aalborg, Denmark), 1–7.Google Scholar
• [19] Hreinsson K, Scaglione A, Alizadeh M, Chen Y (2021) New insights from the Shapley-Folkman lemma on dispatchable demand in energy markets. IEEE Trans. Power Systems 36(5):4028–4041.Crossref, Google Scholar
• [20] Jacquot P, Beaude O, Gaubert S, Oudjane N (2017) Demand response in the smart grid: The impact of consumers temporal preferences. Lehnert R, Speh R, eds. 2017 IEEE Internat. Conf. Smart Grid Comm. (IEEE, Dresden, Germany), 540–545.Google Scholar
• [21] Jacquot P, Wan C, Beaude O, Oudjane N (2021) Efficient estimation of equilibria in large aggregative games with coupling constraints. IEEE Trans. Automatic Control 66(6):2762–2769.Crossref, Google Scholar
• [22] Jensen M (2010) Aggregative games and best-reply potentials. Econom. Theory 43(1):45–66.Crossref, Google Scholar
• [23] Kakutani S (1941) A generalization of Brouwer’s fixed point theorem. Duke Math. J. 8(3):457–459.Crossref, Google Scholar
• [24] Kerdreux T, Colin I, d’Aspremont A (2019) An approximate Shapley-Folkman theorem. Preprint, https://arxiv.org/abs/1712.08559.Google Scholar
• [25] Lauer G, Sandell N, Bertsekas D, Posbergh T (1982) Solution of large-scale optimal unit commitment problems. IEEE Trans. Power Apparatus Systems PAS-101(1):79–86.Crossref, Google Scholar
• [26] Libman L, Orda A (1997) Atomic resource sharing in noncooperative networks. Proc. INFOCOM ’97, vol. 3 (IEEE, Kobe, Japan), 1006–1013.Google Scholar
• [27] Marcotte P, Patriksson M (2007) Traffic equilibrium. Laporte G, Barnhart C, eds. Transportation, vol. 14 (Elsevier), 623–713.Google Scholar
• [28] Meyers C (2006) Network flow problems and congestion games: Complexity and approximation results. Unpublished PhD dissertation, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• [29] Murphy F, Sherali H, Soyster A (1982) A mathematical programming approach for determining oligopolistic market equilibrium. Math. Programming 24(1):92–106.Crossref, Google Scholar
• [30] Myerson R, Weber R (1993) A theory of voting equilibria. Amer. Political Sci. Rev. 87(1):102–114.Crossref, Google Scholar
• [31] Orda A, Rom R, Shimkin N (1993) Competitive routing in multiuser communication networks. IEEE/ACM Trans. Networks 1(5):510–521.Crossref, Google Scholar
• [32] Paccagnan D, Kamgarpour M, Lygeros J (2016) On aggregative and mean field games with applications to electricity markets. 2016 Eur. Control Conf. (IEEE, Aalborg, Denmark), 196–201.Google Scholar
• [33] Paccagnan D, Gentile B, Parise F, Kamgarpour M, Lygeros J (2019) Nash and Wardrop equilibria in aggregative games with coupling constraints. IEEE Trans. Automatic Control 64(4):1373–1388.Crossref, Google Scholar
• [34] Palfrey T, Rosenthal H (1983) A strategic calculus of voting. Public Choice 41(1):7–53.Crossref, Google Scholar
• [35] Pappalardo M (1986) On the duality gap in nonconvex optimization. Math. Oper. Res. 11(1):30–35.Link, Google Scholar
• [36] Rosen J (1965) Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33(3):520–534.Crossref, Google Scholar
• [37] Rosenthal R (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.Crossref, Google Scholar
• [38] Sagratella S (2016) Computing all solutions of Nash equilibrium problems with discrete strategy sets. SIAM J. Optim. 26(4):2190–2218.Crossref, Google Scholar
• [39] Scutari G, Facchinei F, Pang J, Palomar D (2014) Real and complex monotone communication games. IEEE Trans. Inform. Theory 60(7):4197–4231.Crossref, Google Scholar
• [40] Selten R (1970) Preispolitik der Mehrproduktenunternehmung in der Statischen Theorie (Springer Verlag, Berlin).Crossref, Google Scholar
• [41] Starr R (1969) Quasi-equilibria in markets with non-convex preferences. Econometrica 37(1):25–38.Crossref, Google Scholar
• [42] Tran-Thanh L, Polukarov M, Chapman A, Rogers A, Jennings N (2011) On the existence of pure strategy Nash equilibria in integer–splittable weighted congestion games. Algorithmic Game Theory (Springer, Berlin/Heidelberg), 236–253.Crossref, Google Scholar
• [43] Udell M, Boyd S (2016) Bounding duality gap for separable problems with linear constraints. Comput. Optim. Appl. 64(2):355–378.Crossref, Google Scholar
• [44] Vujanic R, Peyman M, Goulart P, Morari M (2014) Large scale mixed-integer optimization: A solution method with supply chain applications. 22nd Mediterranean Conf. Control Automation (IEEE, Paleromo, Italy), 804–809.Google Scholar
• [45] Vujanic R, Peyman M, Goulart P, Sebastien M, Manfred M (2016) A decomposition method for large scale MILPs, with performance guarantees and a power system application. Automatica 67:144–156.Crossref, Google Scholar
• [46] Wang M (2017) Vanishing price of decentralization in large coordinative nonconvex optimization. SIAM J. Optim. 27(3):1977–2009.Crossref, Google Scholar
• [47] Xu Y, Yin W (2013) A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3):1758–1789.Crossref, Google Scholar
• [48] Yu W, Lui R (2006) Dual methods for nonconvex spectrum optimization of multicarrier systems. IEEE Trans. Comm. 54(7):1310–1322.Crossref, Google Scholar