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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adler, I.: The equivalence of linear programs and zero-sum games. Int. J. Game Theory 42, 165–177 (2013)
Dantzig, G.B.: Programming of interdependent activities: II mathematical model. Econometrica 17, 200–211 (1949)
Dantzig, G.B.: A proof of the equivalence of the programming problem and the game problem. In: Koopmans, T.C. (eds) Activity analysis of production and allocation. Cowles Commission for Research in Economics, vol 13, pp. 330–338 (1951)
Dantzig, G.B.: Linear Programming and Extensions. RAND Corporation, Santa Monica (1963)
Dantzig, G.B.: Reminiscences about the origins of linear programming. Oper. Res. Lett. 1, 43–48 (1982)
Gale, D.: The Theory of Linear Economic Models. University of Chicago press, Chicago (1960)
von Neumann, J.: Zur theorie der gesellschaftsspiele. Math. Ann. 100, 295–320 (1928)
von Neumann, J.: Discussion of a maximum problem. In: Taub, A.H. (ed.) Collected Works of John von Neumann, vol. VI, pp. 89–95. Macmillan, New York (1947)
von Stengel, B.: Zero-Sum Games and Linear Programming Duality. Working paper, Department of Mathematics, London School of Economics (2022)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
We thank Songzi Du, Elliot Lipnowski, Roger Myerson, Bernhard von Stengel, and two anonymous referees for helpful comments. We are especially grateful to Ilan Adler and Rakesh Vohra for extensive discussions of the literature and our main result. Reny gratefully acknowledges financial support from the National Science Foundation (SES-1724747).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Brooks, B., Reny, P.J. A canonical game—75 years in the making—showing the equivalence of matrix games and linear programming. Econ Theory Bull 11, 171–180 (2023). https://doi.org/10.1007/s40505-023-00252-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40505-023-00252-8