Microtheory Seminar Series. "Zero-Sum Games and Linear Programming Duality"
Published: 13 March 2024
19 March 2024. Professor Bernhard von Stengel, London School of Economics
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