Optimization Online


On the Equivalencey of Linear Programming Problems and Zero-Sum Games

Ilan Adler (adler***at***ieor.berkeley.edu)

Abstract: In 1951, Dantzig showed the equivalence of linear programming and two-person zero-sum games. However, in the description of his reduction from linear programming to zero-sum games, he noted that there was one case in which his reduction does not work. This also led to incomplete proofs of the relationship between the Minmax Theorem of game theory and the Strong Duality Theorem of linear programming. In this note, we fill these gaps.

Keywords: Zero-sum Games, Minmax Theorem, Linear Programming, Strong Duality, Farkas' Lemma, Ville's Theorem

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Other Topics (Game Theory )

Citation: Manuscript, Depatrment of IEOR, University of California, Berkeley, CA 94720, June/2010

Download: [PDF]

Entry Submitted: 06/18/2010
Entry Accepted: 06/18/2010
Entry Last Modified: 01/15/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society