IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v42y2013i1p165-177.html
   My bibliography  Save this article

The equivalence of linear programs and zero-sum games

Author

Listed:
  • Ilan Adler

Abstract

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 note, we fill these gaps. Copyright Springer-Verlag 2013

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jogath:v:42:y:2013:i:1:p:165-177
    DOI: 10.1007/s00182-012-0328-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00182-012-0328-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00182-012-0328-8?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. R.J. Aumann & S. Hart (ed.), 2002. "Handbook of Game Theory with Economic Applications," Handbook of Game Theory with Economic Applications, Elsevier, edition 1, volume 3, number 3.
    2. Raghavan, T.E.S., 1994. "Zero-sum two-person games," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 2, chapter 20, pages 735-768, Elsevier.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    2. 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.
    3. 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.
    4. 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).
    5. 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.
    6. 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.
    7. 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).
    8. Makoto Shimoji, 2022. "Bayesian persuasion in unlinked games," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(3), pages 451-481, November.
    9. Valizadeh, Mehrdad & Gohari, Amin, 2019. "Playing games with bounded entropy," Games and Economic Behavior, Elsevier, vol. 115(C), pages 363-380.
    10. 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.

    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. Brandl, Florian, 2017. "The distribution of optimal strategies in symmetric zero-sum games," Games and Economic Behavior, Elsevier, vol. 104(C), pages 674-680.
    2. Marco Faravelli & Randall Walsh, 2011. "Smooth Politicians And Paternalistic Voters: A Theory Of Large Elections," Levine's Working Paper Archive 786969000000000250, David K. Levine.
    3. Ding, Zhanwen & Shi, Guiping, 2009. "Cooperation in a dynamical adjustment of duopoly game with incomplete information," Chaos, Solitons & Fractals, Elsevier, vol. 42(2), pages 989-993.
    4. Jhinyoung Shin & Rajdeep Singh, 2010. "Corporate Disclosures: Strategic Donation of Information," International Review of Finance, International Review of Finance Ltd., vol. 10(3), pages 313-337, September.
    5. Mario Guajardo & Kurt Jörnsten & Mikael Rönnqvist, 2016. "Constructive and blocking power in collaborative transportation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 25-50, January.
    6. Sylvie Thoron, 2016. "Morality Beyond Social Preferences: Smithian Sympathy, Social Neuroscience and the Nature of Social Consciousness [La moralité au delà des préférences sociales. La sympathie Smithienne, les neurosc," Post-Print hal-01645043, HAL.
    7. Nan Xia & S. Rajagopalan, 2009. "Standard vs. Custom Products: Variety, Lead Time, and Price Competition," Marketing Science, INFORMS, vol. 28(5), pages 887-900, 09-10.
    8. Gerard Llobet & Javier Suarez, 2010. "Entrepreneurial Innovation, Patent Protection and Industry Dynamics," Working Papers wp2010_1001, CEMFI.
    9. Platz, Trine Tornøe & Østerdal, Lars Peter, 2017. "The curse of the first-in–first-out queue discipline," Games and Economic Behavior, Elsevier, vol. 104(C), pages 165-176.
    10. Jihui Chen & Qiang Fu, 2017. "Do exclusivity arrangements harm consumers?," Journal of Regulatory Economics, Springer, vol. 51(3), pages 311-339, June.
    11. Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2009. "Protocols with No Acknowledgment," Operations Research, INFORMS, vol. 57(4), pages 905-915, August.
    12. Yusuke Kamishiro & Roberto Serrano & Myrna Wooders, 2021. "Monopolists of scarce information and small group effectiveness in large quasilinear economies," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(4), pages 801-827, December.
    13. Tristan Tomala, 2011. "Fault Reporting in Partially Known Networks and Folk Theorems," Operations Research, INFORMS, vol. 59(3), pages 754-763, June.
    14. Sen, Debapriya & Tauman, Yair, 2007. "General licensing schemes for a cost-reducing innovation," Games and Economic Behavior, Elsevier, vol. 59(1), pages 163-186, April.
    15. Sent, Esther-Mirjam, 2004. "The legacy of Herbert Simon in game theory," Journal of Economic Behavior & Organization, Elsevier, vol. 53(3), pages 303-317, March.
    16. José-Manuel Giménez-Gómez & António Osório & Josep E. Peris, 2015. "From Bargaining Solutions to Claims Rules: A Proportional Approach," Games, MDPI, vol. 6(1), pages 1-7, March.
    17. Valentiny, Pál, 2019. "Közgazdaságtan a jogalkalmazásban [Forensic economics]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(2), pages 134-162.
    18. Ünsal Özdilek, 2020. "Land and building separation based on Shapley values," Palgrave Communications, Palgrave Macmillan, vol. 6(1), pages 1-13, December.
    19. Ichiro Nishizaki & Tomohiro Hayashida & Yuki Shintomi, 2016. "A core-allocation for a network restricted linear production game," Annals of Operations Research, Springer, vol. 238(1), pages 389-410, March.
    20. Hiroki Saitoh & Shigehiro Serizawa, 2008. "Vickrey allocation rule with income effect," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 35(2), pages 391-401, May.

    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:spr:jogath:v:42:y:2013:i:1:p:165-177. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.