On the Equivalence of Zero-Sum Games and Conic Programs

• 成果类型: Article; Early Access
• 署名作者: Dimou, Nikos
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2025.0926
• 发表日期: 2026-03-30
• 关键词: minimax theorem; Strong Duality; conic linear programming; two-player zero-sum games; Nash equilibrium; almost equivalence; Duality

摘要

We prove the almost equivalence of the minimax theorem and the strong duality theorem for a large class of games and conic programs. The previous fundamental results on the equivalence of linear programming and two-player zero-sum games with simplex strategy sets are extended to Banach spaces, and a comprehensive framework unifying two-player zero-sum games and conic linear programs is established. Specifically, we show that, for every zero-sum game with a bilinear payoff function and strategy sets that represent bases of convex cones, the minimax equality holds, and its game value and Nash equilibria can be found by solving a primal-dual pair of conic programs. Conversely, the minimax theorem for the same class of games almost always implies strong duality of conic linear programming. In fact, we give a game-dependent characterization of strict feasibility and show that minimax is equivalent to a generalized version of Ville's theorem of the alternative. Several well-established game classes are embedded in the introduced model, including (i) semi-infinite, (ii) semidefinite, (iii) quantum, (iv) time-dependent, and (v) polynomial games as well as (vi) the mixed extension of any continuous game with compact strategy sets.