Department of Computer, Control and Management Engineering

Abstract:

LP duality (the strong duality theorem of linear programming) and the minimax theorem for zero-sum games are considered "equivalent" in the sense that one can easily be proved from the other. However, the classic proof by Dantzig (1951) of LP duality from the minimax theorem is flawed. It needs an additional assumption of strict complementarity. We show that this assumption amounts to assuming the Lemma of Farkas, which proves LP duality directly. We fix this with a new, different proof via the Theorems of Gordan (1873) and Tucker (1956), distilled from Adler (2013). We also describe some lesser known beautiful existing direct proofs of the minimax theorem and the Lemma of Farkas. This is a mostly expository talk on a rather general but fundamental topic and is not too technical.