On the Equivalence of Zero-Sum Games and Conic Programs

References

• [1] Adler I (2013) The equivalence of linear programs and zero-sum games. Internat. J. Game Theory 42(1):165–177.Crossref, Google Scholar
• [2] Alizadeh F, Goldfarb D (2003) Second-order cone programming. Math. Programming 95(1):3–51.Crossref, Google Scholar
• [3] Anderson EJ (1983) A review of duality theory for linear programming over topological vector spaces. J. Math. Anal. Appl. 97(2):380–392.Crossref, Google Scholar
• [4] Anderson EJ, Lewis A, Wu SY (1989) The capacity problem. Optimization 20(6):725–742.Crossref, Google Scholar
• [5] Bellman R (1966) Dynamic programming. Science 153(3731):34–37.Crossref, Google Scholar
• [6] Bonnans JF, Shapiro A (2013) Perturbation Analysis of Optimization Problems (Springer Science & Business Media, New York).Google Scholar
• [7] Cachon GP, Netessine S (2006) Game theory in supply chain analysis. Johnson MD, ed. Models, Methods, and Applications for Innovative Decision Making (INFORMS, Catonsville, MD), 200–233.Link, Google Scholar
• [8] Cai Y, Daskalakis C (2011) On minmax theorems for multiplayer games. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 217–234.Google Scholar
• [9] Cai Y, Candogan O, Daskalakis C, Papadimitriou C (2016) Zero-sum polymatrix games: A generalization of minmax. Math. Oper. Res. 41(2):648–655.Link, Google Scholar
• [10] Casini E, Miglierina E (2010) Cones with bounded and unbounded bases and reflexivity. Nonlinear Anal. Theory Methods Appl. 72(5):2356–2366.Crossref, Google Scholar
• [11] Craven BD, Koliha JJ (1977) Generalizations of Farkas’ theorem. SIAM J. Math. Anal. 8(6):983–997.Crossref, Google Scholar
• [12] Dantzig GB (1951) A proof of the equivalence of the programming problem and the game problem. Koopmans TC, ed. Activity Analysis of Production and Allocation (John Wiley & Sons, New York), 330–335.Google Scholar
• [13] Dantzig GB (1956) Constructive proof of the min-max theorem. Pacific J. Math. 6(4):25–33.Crossref, Google Scholar
• [14] Dantzig GB (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [15] Dresher M, Karlin S, Shapley LS (1950) Polynomial games. Kuhn HW, Tucker AW, eds. Contributions to the Theory of Games I, vol. 24 (Princeton University Press, Princeton, NJ), 161–180.Google Scholar
• [16] Duffin RJ (1956) Infinite programs. Kuhn HW, Tucker AW, eds. Linear Inequalities and Related Systems, vol. 38 (Princeton University Press, Princeton, NJ), 157–170.Google Scholar
• [17] Fan K (1952) Fixed-point and minimax theorems in locally convex topological linear spaces. Proc. Natl. Acad. Sci. USA 38(2):121–126.Crossref, Google Scholar
• [18] Ferrero O (1989) Theorems of the alternative for set-valued functions in infinite-dimensional spaces. Optimization 20(2):167–175.Crossref, Google Scholar
• [19] Glicksberg IL (1952) A further generalization of the Kakutani fixed theorem, with application to Nash equilibrium points. Proc. Amer. Math. Soc. 3(1):170–174.Google Scholar
• [20] Ickstadt C, Theobald T, Tsigaridas E (2024) Semidefinite games. Internat. J. Game Theory 53(3):827–857.Crossref, Google Scholar
• [21] Ickstadt C, Theobald T, Tsigaridas E, Varvitsiotis A (2023) Semidefinite network games: Multiplayer minimax and complementarity problems. Preprint, submitted October 31, https://arxiv.org/abs/2310.20333.Google Scholar
• [22] Jain R, Watrous J (2009) Parallel approximation of non-interactive zero-sum quantum games. 24th Annual IEEE Conf. Comput. Complexity (IEEE, Washington, DC), 243–253.Google Scholar
• [23] Karlin S (1953) The theory of infinite games. Ann. Math. 58(2):371–401.Crossref, Google Scholar
• [24] Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Proc. 16th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 302–311.Google Scholar
• [25] Khanh PD, Mo TH, Tran TT (2019) Necessary and sufficient conditions for qualitative properties of infinite dimensional linear programming problems. Numerical Functional Anal. Optim. 40(8):924–943.Crossref, Google Scholar
• [26] Kretschmer KS (1961) Programmes in paired spaces. Canadian J. Math. 13(2):221–238.Crossref, Google Scholar
• [27] Kuhn HW, Tucker AW (1953) Contributions to the Theory of Games, vol. 28 (Princeton University Press, Princeton, NJ).Google Scholar
• [28] Kuhn HW, Tucker AW, eds. (1956) Linear Inequalities and Related Systems, vol. 38 (Princeton University Press, Princeton, NJ).Google Scholar
• [29] Lai H, Wu SY (1992) Extremal points and optimal solutions for general capacity problems. Math. Programming 54(1):87–113.Crossref, Google Scholar
• [30] Levinson N (1966) A class of continuous linear programming problems. J. Math. Anal. Appl. 16(1):73–83.Crossref, Google Scholar
• [31] Nash P, Anderson EJ (1987) Linear Programming in Infinite-Dimensional Spaces: Theory and Applications (John Wiley & Sons, New York).Google Scholar
• [32] Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [33] Nocedal J, Wright SJ (1999) Numerical Optimization (Springer, New York).Crossref, Google Scholar
• [34] Parrilo PA (2006) Polynomial games and sum of squares optimization. Proc. 45th IEEE Conf. Decision Control (IEEE, Washington, DC), 2855–2860.Google Scholar
• [35] Pataki G, Touzov A (2024) How do exponential size solutions arise in semidefinite programming? SIAM J. Optim. 34(1):977–1005.Crossref, Google Scholar
• [36] Shapiro A (2001) On duality theory of conic linear problems. Nonconvex Optimization and Its Applications, vol. 57 (Springer), 135–155.Google Scholar
• [37] Shapiro A (2009) Semi-infinite programming, duality, discretization and optimality conditions. Optimization 58(2):133–161.Crossref, Google Scholar
• [38] Soyster A (1975) A semi-infinite game. Management Sci. 21(7):806–812.Link, Google Scholar
• [39] Tijs S (1979) Semi-infinite linear programs and semi-infinite matrix games. Nieuw Archief Voor Wiskunde (Serie III) 27:197–214.Google Scholar
• [40] Ville J (1938) Sur la théorie générale des jeux ou intervient l’habileté des joueurs. Borel E, et al., eds. Traité du Calcul des Probabilités et des ses Applications’, Tome IV (Paris, Gauthiers-Villars), 105–113.Google Scholar
• [41] von Neumann J (1928) Zur theorie der gesellschaftsspiele. Math. Ann. 100(1):295–320.Crossref, Google Scholar
• [42] von Neumann J, Morgenstern O (1944) Theory of Games and Economic Behavior (Princeton University Press, Princeton, NJ).Google Scholar
• [43] von Stengel B (2002) Computing equilibria for two-person games. Aumann RJ, Hart S, eds. Handbook of Game Theory with Economic Applications, vol. 3 (Elsevier, Amsterdam), 1723–1759.Crossref, Google Scholar
• [44] von Stengel B (2024) Zero-sum games and linear programming duality. Math. Oper. Res. 49(2):1091–1108.Link, Google Scholar
• [45] Weiss G (2008) A simplex based algorithm to solve separated continuous linear programs. Math. Programming 115(1):151–198.Crossref, Google Scholar
• [46] Wolkowicz H, Saigal R, Vandenberghe L (2012) Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, vol. 27 (Springer Science & Business Media, New York).Google Scholar
• [47] Yang X, Yang X, Chen G (2000) Theorems of the alternative and optimization with set-valued maps. J. Optim. Theory Appl. 107(3):627–640.Crossref, Google Scholar