Adam Smith Business School

Professor Bernhard von Stengel, London School of Economics

"Zero-Sum Games and Linear Programming Duality"
Tuesday, 19 March 2024. 16:00-17:30
Room 355 Gilbert Scott Building

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). 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.

Bio

Bernhard von Stengel, educated in Germany and the US with degrees in mathematics and computer science, is a mathematical game theorist at the London School of Economics and Political Science. He is an expert on computational and geometric methods for solving games. He chaired the 2016 World Congress of the Game Theory Society, and is co-editor of the International Journal of Game Theory.

---

For further information, please contact business-school-research@glasgow.ac.uk

We foster a positive and productive environment for seminars through our Code of conduct.

First published: 13 March 2024