论文标题
零和线性编程双重性
Zero-Sum Games and Linear Programming Duality
论文作者
论文摘要
从线性编程的强双重定理可以轻松证明用于零和游戏的最小值定理。对于相反的方向，已知Dantzig（1951）的标准证明是不完整的。我们解释并结合了与非负变量求解线性方程的经典定理，以提供正确的替代证明，比Adler（2013）更直接地提供了替代证明。我们还扩展了Dantzig的游戏，以便任何Max-Min策略都提供最佳的LP解决方案，或者表明不存在。
The minimax theorem for zero-sum games is easily proved from the strong duality theorem of linear programming. For the converse direction, the standard proof by Dantzig (1951) is known to be incomplete. We explain and combine classical theorems about solving linear equations with nonnegative variables to give a correct alternative proof, more directly than Adler (2013). We also extend Dantzig's game so that any max-min strategy gives either an optimal LP solution or shows that none exists.
