N&O Seminar Bernhard von Stengel

Bernhard von Stengel from London School of Economics gives a seminar talk titled "Zero-Sum Games and Linear Programming Duality".

7 Jun 2024 from 11 a.m. to 7 Jun 2024 noon CEST (GMT+0200)
Room L120 and online


Bernhard von Stengel

London School of Economics


Zero-Sum Games and Linear Programming Duality

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). Separately, we state a new strongly polynomial reduction of LP duality (and possible infeasibility) to a zero-sum game. 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.