Return to Colloquia & Seminar listing
The equivalence of linear programs and zero-sum games
Algebra & Discrete Mathematics| Speaker: | Ilan Adler, University of California, Berkeley |
| Location: | 1147 MSB |
| Start time: | Thu, Mar 1 2012, 3:10PM |
In 1951, Dantzig showed the equivalence of linear programming problems and two-person zero-sum games. However, in the description of his reduction from linear programs to zero-sum games, he noted that there was one case in which the reduction does not work. This also led to incomplete proofs of the relationship between the Minimax Theorem of game theory and the Strong Duality Theorem of linear programming. In this Talk, I fill these gaps. In particular, I’ll present two complete strongly polynomial reductions of LP’s to zero-sum games, a Karp-type reduction which is applicable to LP’s with rational data, and a Cook type reduction which is applicable to LP’s with real data. I’ll also discuss the relationship between the Minimax Theorem and the Strong Duality Theorem .