Home » Node » 27378

Seminario Bernhard von Stengel (London School of Economics) - Zero-sum Games and LP Duality

Bernhard von Stengel (London School of Economics)
Data dell'evento: 
Thursday, 23 November, 2023 - 16:00
DIAG - Aula Magna
Stefano Leonardi: leonardi@diag.uniroma1.it


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.

gruppo di ricerca: 
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma