We show that strong duality for conic linear programming directly implies the minimax theorem for a wide class of infinite two-player zero-sum games. In fact, for every two-player zero-sum game with "cone-leveled" strategy sets, or more generally with strategy sets that can be written as unions of "cone-leveled" subsets, its game value and (approximate) optimal strategies can be calculated by solving a primal-dual pair of conic linear problems. The original result proven by von Neumann is therefore naturally generalized to the infinite-dimensional case, and a strong, rigorous connection between infinite two-player zero-sum games and mathematical programming is established.
翻译:本文展示了锥形线性规划的强对偶定理如何直接导出了一类无限维度的双人零和博弈的极小极大定理。事实上,对于任意的双人零和博弈,只要其策略集合是“锥体分层”的,或更普遍地说,其策略集合能够被写成“锥体分层”子集之并的形式,其博弈价值和(近似的)最优策略可以通过求解一对原对偶锥形线性问题来计算。从而将 von Neumann 原本证明的结论自然地推广到了无限维度的情形,并建立了无限维双人零和博弈和数学规划之间的强有力而严格的联系。