A canonical game—75 years in the making—showing the equivalence of matrix games and linear programming

Benjamin Brooks () and Philip J. Reny ()
Additional contact information
Benjamin Brooks: University of Chicago
Philip J. Reny: University of Chicago

Economic Theory Bulletin, 2023, vol. 11, issue 2, No 1, 180 pages

Abstract: Abstract According to Dantzig (Econometrica, 17, p.200, 1949), von Neumann was the first to observe that for any finite two-person zero-sum game, there is a feasible linear programming (LP) problem whose saddle points yield equilibria of the game, thus providing an immediate proof of the minimax theorem from the strong duality theorem. We provide an analogous construction going in the other direction. For any LP problem, we define a game and, with a brief and elementary proof, show that every equilibrium either yields a saddle point of the LP problem or certifies that one of the primal or dual programs is infeasible and the other is infeasible or unbounded. We thus obtain an immediate proof of the strong duality theorem from the minimax theorem. Taken together, von Neumann’s and our results provide a succinct and elementary demonstration that matrix games and linear programming are “equivalent” in a classical sense.

Keywords: Matrix games; Linear programming; Equivalence (search for similar items in EconPapers)
JEL-codes: C61 C72 D00 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s40505-023-00252-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:etbull:v:11:y:2023:i:2:d:10.1007_s40505-023-00252-8

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/40505

DOI: 10.1007/s40505-023-00252-8

Access Statistics for this article

Economic Theory Bulletin is currently edited by Nicholas C. Yannelis

More articles in Economic Theory Bulletin from Springer, Society for the Advancement of Economic Theory (SAET) Contact information at EDIRC.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().