IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v49y2024i2p1091-1108.html

Zero-Sum Games and Linear Programming Duality

Author

Listed:
  • Bernhard von Stengel

    (Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom)

Abstract

The minimax theorem for zero-sum games is easily proved from the strong duality theorem of linear programming. For the converse direction, the standard proof by Dantzig is known to be incomplete. We explain and combine classical theorems about solving linear equations with nonnegative variables to give a correct alternative proof more directly than Adler. We also extend Dantzig’s game so that any max-min strategy gives either an optimal LP solution or shows that none exists.

Suggested Citation

  • Bernhard von Stengel, 2024. "Zero-Sum Games and Linear Programming Duality," Mathematics of Operations Research, INFORMS, vol. 49(2), pages 1091-1108, May.
    • Handle: RePEc:inm:ormoor:v:49:y:2024:i:2:p:1091-1108
    DOI: 10.1287/moor.2022.0149
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.0149
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.0149?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Michele Conforti & Marco Di Summa & Giacomo Zambelli, 2007. "Minimally Infeasible Set-Partitioning Problems with Balanced Constraints," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 497-507, August.
    2. Ilan Adler, 2013. "The equivalence of linear programs and zero-sum games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 165-177, February.
    3. Guillermo Owen, 1967. "Communications to the Editor--An Elementary Proof of the Minimax Theorem," Management Science, INFORMS, vol. 13(9), pages 765-765, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chen, Shun & Zhao, Xudong & Chen, Zhilong & Hou, Benwei & Wu, Yipeng, 2022. "A game-theoretic method to optimize allocation of defensive resource to protect urban water treatment plants against physical attacks," International Journal of Critical Infrastructure Protection, Elsevier, vol. 36(C).
    2. Han, Lin & Zhao, Xudong & Chen, Zhilong & Gong, Huadong & Hou, Benwei, 2021. "Assessing resilience of urban lifeline networks to intentional attacks," Reliability Engineering and System Safety, Elsevier, vol. 207(C).
    3. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    4. Ilan Adler & Martin Bullinger & Vijay V. Vazirani, 2024. "A Generalization of von Neumann's Reduction from the Assignment Problem to Zero-Sum Games," Papers 2410.10767, arXiv.org, revised Jan 2026.
    5. Valizadeh, Mehrdad & Gohari, Amin, 2019. "Playing games with bounded entropy," Games and Economic Behavior, Elsevier, vol. 115(C), pages 363-380.
    6. Galichon, A. & Jacquet, A., 2025. "The matching problem with linear transfers is equivalent to a hide-and-seek game," Games and Economic Behavior, Elsevier, vol. 152(C), pages 333-344.
    7. Daskalakis, Constantinos & Deckelbaum, Alan & Kim, Anthony, 2015. "Near-optimal no-regret algorithms for zero-sum games," Games and Economic Behavior, Elsevier, vol. 92(C), pages 327-348.
    8. Takao Fujimoto & B.B.Upeksha P. Perera & Giorgio Giorgi, 2016. "Two Proofs of the Farkas-Minkowski Theorem by Tandem Method and by Use of an Orthogonal Complement," DEM Working Papers Series 129, University of Pavia, Department of Economics and Management.
    9. Hou, Benwei & Chen, Pengxu & Zhao, Xudong & Chen, Zhilong, 2025. "Optimal allocation of defensive resources in regional railway networks under intentional attacks," Reliability Engineering and System Safety, Elsevier, vol. 257(PB).
    10. Constantin Ickstadt & Thorsten Theobald & Elias Tsigaridas, 2024. "Semidefinite games," International Journal of Game Theory, Springer;Game Theory Society, vol. 53(3), pages 827-857, September.
    11. Benjamin Brooks & Philip J. Reny, 2023. "A canonical game—75 years in the making—showing the equivalence of matrix games and linear programming," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 11(2), pages 171-180, October.
    12. Vikas Vikram Singh & Abdel Lisser, 2018. "Variational inequality formulation for the games with random payoffs," Journal of Global Optimization, Springer, vol. 72(4), pages 743-760, December.
    13. Krishnendu Chatterjee & Miquel Oliu-Barton & Raimundo Saona, 2025. "Value-Positivity for Matrix Games," Mathematics of Operations Research, INFORMS, vol. 50(4), pages 2502-2525, November.
    14. Makoto Shimoji, 2022. "Bayesian persuasion in unlinked games," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(3), pages 451-481, November.
    15. Ueda, Masahiko & Fujita, Ayaka, 2025. "Zero-determinant strategies in repeated continuously-relaxed games," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 670(C).
    16. Amir Ali Ahmadi & Jeffrey Zhang, 2021. "Semidefinite Programming and Nash Equilibria in Bimatrix Games," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 607-628, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:49:y:2024:i:2:p:1091-1108. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.