Nash Equilibrium Problems of Polynomials

References

• [1] Adam L, Horčík R, Kasl T, Kroupa T (2021) Double oracle algorithm for computing equilibria in continuous games. Proc. Conf. AAAI Artificial Intelligence 35(6):5070–5077.Crossref, Google Scholar
• [2] Ahmadi AA, Zhang J (2021) Semidefinite programming and Nash equilibria in bimatrix games. INFORMS J. Comput. 33(2):607–628.Abstract, Google Scholar
• [3] Aubin JP (2002) Optima and Equilibria: An Introduction to Nonlinear Analysis, Graduate Texts in Mathematics, volume 140 (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• [4] Breton M, Zaccour G, Zahaf M (2006) A game-theoretic formulation of joint implementation of environmental projects. Eur. J. Oper. Res. 168(1):221–239.Crossref, Google Scholar
• [5] Chen Y, Lan G, Ouyang Y (2014) Optimal primal-dual methods for a class of saddle point problems. SIAM J. Optim. 24(4):1779–1814.Crossref, Google Scholar
• [6] Contreras J, Klusch M, Krawczyk JB (2004) Numerical solutions to Nash-Cournot equilibria in coupled constraint electricity markets. IEEE Trans. Power Systems 19(1):195–206.Crossref, Google Scholar
• [7] Couzoudis E, Renner P (2013) Computing generalized Nash equilibria by polynomial programming. Math. Methods Oper. Res. 77(3):459–472.Crossref, Google Scholar
• [8] Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• [9] Datta RS (2010) Finding all Nash equilibria of a finite game using polynomial algebra. Econom. Theory 42(1):55–96.Crossref, Google Scholar
• [10] Dresher M, Karlin S, Shapley L (2016) Polynomial games. Kuhn HW, Tucker AW, eds. Contributions to the Theory of Games, volume 1 (Princeton University Press, Princeton, NJ), 161–180.Google Scholar
• [11] Facchinei F, Kanzow C (2010) Generalized Nash equilibrium problems. Ann. Oper. Res. 175(1):177–211.Crossref, Google Scholar
• [12] Farnia F, Ozdaglar A (2020) Do GANs always have Nash equilibria? Daumé III H, Singh A, eds. Proc. 37th Internat. Conf. Machine Learning (PMLR, New York), 3029–3039.Google Scholar
• [13] Glicksberg IL (1952) A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proc. Amer. Math. Soc. 3(1):170–174.Google Scholar
• [14] Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y (2020) Generative adversarial networks. Commun. ACM 63(11):139–144.Crossref, Google Scholar
• [15] Gürkan G, Pang JS (2009) Approximations of Nash equilibria. Math. Program. 117(1):223–253.Crossref, Google Scholar
• [16] Harris J (2013) Algebraic Geometry: A First Course, Graduate Texts in Mathematics, vol. 133 (Springer Science & Business Media, New York).Google Scholar
• [17] Henrion D, Lasserre JB (2005) Detecting global optimality and extracting solutions in Gloptipoly. Henrion D, Garulli A, eds. Positive Polynomials in Control, Lecture Notes in Control and Information Science, vol. 312 (Springer, Berlin, Heidelberg), 293–310.Crossref, Google Scholar
• [18] Henrion D, Korda M, Lasserre JB (2020) The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs, Optimization and its Applications, vol. 4 (World Scientific, Singapore).Crossref, Google Scholar
• [19] Henrion D, Lasserre JB, Löfberg J (2009) Gloptipoly 3: Moments, optimization and semidefinite programming. Optim. Methods Software 24(4–5):761–779.Crossref, Google Scholar
• [20] Hillar C, Nie J (2008) An elementary and constructive solution to Hilbert’s 17th problem for matrices. Proc. Amer. Math. Soc. 136(1):73–76.Crossref, Google Scholar
• [21] Kontogiannis SC, Panagopoulou PN, Spirakis PG (2006) Polynomial algorithms for approximating Nash equilibria of bimatrix games. Spirakis PG, Mavronicolas M, Kontogiannis SC, eds. WINE 2006 Internat. Workshop Internet Network Econom. (Springer, Berlin, Heidelberg), 286–296.Google Scholar
• [22] Krawczyk JB, Uryasev S (2000) Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assessment 5(1):63–73.Crossref, Google Scholar
• [23] Kroupa T, Votroubek T (2023) Multiple oracle algorithm to solve continuous games. Proc. Decision Game Theory Security 13th Internat. Conf. GameSec 2022 (Springer, Berlin, Heidelberg), 149–167.Google Scholar
• [24] Kulkarni AA, Shanbhag UV (2012) On the variational equilibrium as a refinement of the generalized Nash equilibrium. Automatica 48(1):45–55.Crossref, Google Scholar
• [25] Laraki R, Lasserre JB (2012) Semidefinite programming for min–max problems and games. Math. Program. 131(1):305–332.Crossref, Google Scholar
• [26] Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• [27] Lasserre JB (2006) Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3):822–843.Crossref, Google Scholar
• [28] Lasserre JB (2015) An Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge Texts in Applied Mathematics, vol. 52 (Cambridge University Press, Cambridge, UK).Google Scholar
• [29] Lasserre JB, Laurent M, Rostalski P (2008) Semidefinite characterization and computation of zero-dimensional real radical ideals. Foundations Comput. Math. 8(5):607–647.Crossref, Google Scholar
• [30] Laurent M (2009) Sums of squares, moment matrices and optimization over polynomials. Putinar M, Sullivant S, eds. Emerging Applications of Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, vol. 149 (Springer, New York), 157–270.Crossref, Google Scholar
• [31] Magron V, Wang J (2021) TSSOS: A Julia library to exploit sparsity for large-scale polynomial optimization. Preprint, submitted March 1, https://arxiv.org/abs/2103.00915.Google Scholar
• [32] Maskin E (1999) Nash equilibrium and welfare optimality. Rev. Econom. Stud. 66(1):23–38.Crossref, Google Scholar
• [33] Nash J (1951) Non-cooperative games. Ann. Math. 54(2):286–295.Crossref, Google Scholar
• [34] Nedić A, Ozdaglar A (2009) Subgradient methods for saddle-point problems. J. Optim. Theory Appl. 142(1):205–228.Crossref, Google Scholar
• [35] Nie J (2011) Polynomial matrix inequality and semidefinite representation. Math. Oper. Res. 36(3):398–415.Link, Google Scholar
• [36] Nie J (2012) Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces. Front. Math. China 7(2):321–346.Crossref, Google Scholar
• [37] Nie J (2013a) Certifying convergence of Lasserre’s hierarchy via flat truncation. Math. Program. 142(1):485–510.Crossref, Google Scholar
• [38] Nie J (2013b) Polynomial optimization with real varieties. SIAM J. Optim. 23(3):1634–1646.Crossref, Google Scholar
• [39] Nie J (2014a) The A-truncated K-moment problem. Foundations Comput. Math. 14(6):1243–1276.Crossref, Google Scholar
• [40] Nie J (2014b) Optimality conditions and finite convergence of Lasserre’s hierarchy. Math. Program. 146(1):97–121.Crossref, Google Scholar
• [41] Nie J (2017) Symmetric tensor nuclear norms. SIAM J. Appl. Algebra Geom. 1(1):599–625.Crossref, Google Scholar
• [42] Nie J (2019) Tight relaxations for polynomial optimization and Lagrange multiplier expressions. Math. Program. 178(1):1–37.Crossref, Google Scholar
• [43] Nie J, Demmel J (2009) Sparse SOS relaxations for minimizing functions that are summations of small polynomials. SIAM J. Optim. 19(4):1534–1558.Crossref, Google Scholar
• [44] Nie J, Ranestad K (2009) Algebraic degree of polynomial optimization. SIAM J. Optim. 20(1):485–502.Crossref, Google Scholar
• [45] Nie J, Tang X (2023) Convex generalized Nash equilibrium problems and polynomial optimization. Math. Program. 198:1485–1518.Crossref, Google Scholar
• [46] Nie J, Zhang X (2018) Real eigenvalues of nonsymmetric tensors. Comput. Optim. Appl. 70(1):1–32.Crossref, Google Scholar
• [47] Nie J, Tang X, Xu L (2021) The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials. Comput. Optim. Appl. 78(2):529–557.Crossref, Google Scholar
• [48] Nie J, Yang Z, Zhou G (2022) The saddle point problem of polynomials. Foundations Comput. Math. 22(4):1133–1169.Crossref, Google Scholar
• [49] Parrilo PA (2006) Polynomial games and sum of squares optimization. Proc. 45th IEEE Conf. Decision Control (IEEE, Piscataway, NJ), 2855–2860.Google Scholar
• [50] Putinar M (1993) Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3):969–984.Crossref, Google Scholar
• [51] Qu Z, Tang X (2022) A correlative sparse Lagrange multiplier expression relaxation for polynomial optimization. Preprint, submitted August 8, https://arxiv.org/abs/2208.03979.Google Scholar
• [52] Ratliff LJ, Burden SA, Sastry SS (2013) Characterization and computation of local Nash equilibria in continuous games. 2013 51st Annu. Allerton Conf. Commun. Control Comput. (IEEE, Piscataway, NJ), 917–924.Google Scholar
• [53] Schofield N, Sened I (2002) Local Nash equilibrium in multiparty politics. Ann. Oper. Res. 109(1):193–211.Crossref, Google Scholar
• [54] Schweighofer M (2005) Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15(3):805–825.Crossref, Google Scholar
• [55] Shafarevich IR (2013) Basic Algebraic Geometry 1: Varieties in Projective Space (Springer Science & Business Media, Berlin, Heidelberg).Crossref, Google Scholar
• [56] Stein ND, Ozdaglar A, Parrilo PA (2008) Separable and low-rank continuous games. Internat. J. Game Theory 37(4):475–504.Crossref, Google Scholar
• [57] Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11(1–4):625–653.Crossref, Google Scholar
• [58] Uryas’ev S, Rubinstein RY (1994) On relaxation algorithms in computation of noncooperative equilibria. IEEE Trans. Automatic Control 39(6):1263–1267.Crossref, Google Scholar
• [59] Waki H, Kim S, Kojima M, Muramatsu M (2006) Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1):218–242.Crossref, Google Scholar
• [60] Wang J, Magron V, Lasserre JB (2021a) Chordal-TSSOS: A moment-SOS hierarchy that exploits term sparsity with chordal extension. SIAM J. Optim. 31(1):114–141.Crossref, Google Scholar
• [61] Wang J, Magron V, Lasserre JB (2021b) TSSOS: A moment-SOS hierarchy that exploits term sparsity. SIAM J. Optim. 31(1):30–58.Crossref, Google Scholar
• [62] Wang J, Magron V, Lasserre JB, Mai NHA (2022) CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization. ACM Trans. Math. Software 48(4):1–26.Crossref, Google Scholar
• [63] Young P, Zamir S (2014) Handbook of Game Theory (Elsevier, Amsterdam).Google Scholar