On the Equivalence of Zero-Sum Games and Conic Programs

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.