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

Value-Positivity for Matrix Games

Author

Listed:
  • Krishnendu Chatterjee

    (Institute of Science and Technology Austria, 3400 Klosterneuburg, Austria)

  • Miquel Oliu-Barton

    (CEREMADE, CNRS, Université Paris Dauphine-PSL University, 75016 Paris, France)

  • Raimundo Saona

    (Institute of Science and Technology Austria, 3400 Klosterneuburg, Austria)

Abstract

Matrix games are the most basic model in game theory, and yet robustness with respect to small perturbations of the matrix entries is not fully understood. In this paper, we introduce value positivity and uniform value positivity, two properties that refine the notion of optimality in the context of polynomially perturbed matrix games. The first concept captures how the value depends on the perturbation parameter, and the second consists of the existence of a fixed strategy that guarantees the value of the unperturbed matrix game for every sufficiently small positive parameter. We provide polynomial-time algorithms to check whether a polynomially perturbed matrix game satisfies these properties. We further provide the functional form for a parameterized optimal strategy and the value function. Finally, we translate our results to linear programming and stochastic games, where value positivity is related to the existence of robust solutions.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ormoor:v:50:y:2025:i:4:p:2502-2525
    DOI: 10.1287/moor.2022.0332
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.0332
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.0332?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. 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.
    2. Tijs, S.H. & Vrieze, O.J., 1980. "Perturbation theory for games in normal form and stochastic games," Other publications TiSEM 55093d43-90d7-4ec8-ba9e-e, Tilburg University, School of Economics and Management.
    3. 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.
    4. Miquel Oliu-Barton, 2021. "New Algorithms for Solving Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 255-267, February.
    5. T. E. S. Raghavan & Zamir Syed, 2002. "Computing Stationary Nash Equilibria of Undiscounted Single-Controller Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 27(2), pages 384-400, May.
    6. Truman Bewley & Elon Kohlberg, 1976. "The Asymptotic Theory of Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 1(3), pages 197-208, August.
    7. Raghavan, T.E.S. & Tijs, S.H. & Vrieze, O.J., 1985. "On stochastic games with additive reward and transition structure," Other publications TiSEM 28f85a14-9a6e-4ed8-9a4b-a, Tilburg University, School of Economics and Management.
    8. Luc Attia & Miquel Oliu-Barton, 2021. "Shapley–Snow Kernels, Multiparameter Eigenvalue Problems, and Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(3), pages 1181-1202, August.
    9. Nimrod Megiddo, 1991. "On Finding Primal- and Dual-Optimal Bases," INFORMS Journal on Computing, INFORMS, vol. 3(1), pages 63-65, February.
    10. Luc Attia & Miquel Oliu-Barton, 2019. "A formula for the value of a stochastic game," Proceedings of the National Academy of Sciences, Proceedings of the National Academy of Sciences, vol. 116(52), pages 26435-26443, December.
    11. Robert G. Jeroslow, 1973. "Asymptotic Linear Programming," Operations Research, INFORMS, vol. 21(5), pages 1128-1141, October.
    12. Arnab Nilim & Laurent El Ghaoui, 2005. "Robust Control of Markov Decision Processes with Uncertain Transition Matrices," Operations Research, INFORMS, vol. 53(5), pages 780-798, October.
    13. A. J. Hoffman & R. M. Karp, 1966. "On Nonterminating Stochastic Games," Management Science, INFORMS, vol. 12(5), pages 359-370, January.
    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. Luc Attia & Miquel Oliu-Barton & Raimundo Saona, 2025. "Marginal Values of a Stochastic Game," Mathematics of Operations Research, INFORMS, vol. 50(1), pages 482-505, February.
    2. Guillaume Garnier & Bruno Ziliotto, 2023. "Percolation Games," Mathematics of Operations Research, INFORMS, vol. 48(4), pages 2156-2166, November.
    3. Dongdong Ge & Chengwenjian Wang & Zikai Xiong & Yinyu Ye, 2025. "From an Interior Point to a Corner Point: Smart Crossover," INFORMS Journal on Computing, INFORMS, vol. 37(6), pages 1670-1688, November.
    4. Samuel Bismuth & Ivan Bliznets & Erel Segal-Halevi, 2019. "Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations," Papers 1912.00459, arXiv.org, revised Jul 2025.
    5. Levy, Yehuda John, 2022. "Uniformly supported approximate equilibria in families of games," Journal of Mathematical Economics, Elsevier, vol. 98(C).
    6. Miquel Oliu-Barton, 2021. "New Algorithms for Solving Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 255-267, February.
    7. Krishnendu Chatterjee & Rupak Majumdar & Thomas Henzinger, 2008. "Stochastic limit-average games are in EXPTIME," International Journal of Game Theory, Springer;Game Theory Society, vol. 37(2), pages 219-234, June.
    8. 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.
    9. Luc Attia & Miquel Oliu-Barton, 2021. "Shapley–Snow Kernels, Multiparameter Eigenvalue Problems, and Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(3), pages 1181-1202, August.
    10. Johannes Horner & Takuo Sugaya & Satoru Takahashi & Nicolas Vieille, 2009. "Recursive Methods in Discounted Stochastic Games: An Algorithm for delta Approaching 1 and a Folk Theorem," Cowles Foundation Discussion Papers 1742, Cowles Foundation for Research in Economics, Yale University, revised Aug 2010.
    11. Endre Boros & Khaled Elbassioni & Vladimir Gurvich & Kazuhisa Makino, 2013. "On Canonical Forms for Zero-Sum Stochastic Mean Payoff Games," Dynamic Games and Applications, Springer, vol. 3(2), pages 128-161, June.
    12. K. Avrachenkov & V. Ejov & J. A. Filar & A. Moghaddam, 2019. "Zero-Sum Stochastic Games over the Field of Real Algebraic Numbers," Dynamic Games and Applications, Springer, vol. 9(4), pages 1026-1041, December.
    13. Alper Atamtürk & Andrés Gómez, 2017. "Maximizing a Class of Utility Functions Over the Vertices of a Polytope," Operations Research, INFORMS, vol. 65(2), pages 433-445, March-Apr.
    14. Erling D. Andersen, 1999. "On Exploiting Problem Structure in a Basis Identification Procedure for Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 95-103, February.
    15. Yann Briheche & Frederic Barbaresco & Fouad Bennis & Damien Chablat, 2018. "Theoretical Complexity of Grid Cover Problems Used in Radar Applications," Journal of Optimization Theory and Applications, Springer, vol. 179(3), pages 1086-1106, December.
    16. Ayush Verma & Vikas Vikram Singh & Abdel Lisser, 2025. "Single-Controller Chance-Constrained Stochastic Games," Journal of Optimization Theory and Applications, Springer, vol. 207(1), pages 1-21, October.
    17. Atlanta Chakraborty & Vijay Chandru & M. R. Rao, 2020. "A linear programming primer: from Fourier to Karmarkar," Annals of Operations Research, Springer, vol. 287(2), pages 593-616, April.
    18. Luc Attia & Miquel Oliu-Barton, 2024. "Stationary Equilibria in Discounted Stochastic Games," Dynamic Games and Applications, Springer, vol. 14(2), pages 271-284, May.
    19. Miquel Oliu-Barton, 2022. "Weighted-average stochastic games with constant payoff," Operational Research, Springer, vol. 22(3), pages 1675-1696, July.
    20. 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).

    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:50:y:2025:i:4:p:2502-2525. 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.