Value-positivity for matrix games
Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. 2024. Value-positivity for matrix games. Mathematics of Operations Research.
Download
No fulltext has been uploaded. References only!
Journal Article
| Epub ahead of print
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
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.
Publishing Year
Date Published
2024-10-01
Journal Title
Mathematics of Operations Research
Publisher
Institute for Operations Research and the Management Sciences
Acknowledgement
This research was supported by Fondation CFM pour la Recherche, the H2020 European Research Council [Grant ERC-CoG-863818 (ForM-SMArt)], the Austrian Science Fund [Grant 10.55776/COE12], ANID Chile [Grant ACT210005], and Agence Nationale de la Recherche [Grant ANR-21-CE40-0020].
ISSN
eISSN
IST-REx-ID
Cite this
Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. Value-positivity for matrix games. Mathematics of Operations Research. 2024. doi:10.1287/moor.2022.0332
Chatterjee, K., Oliu-Barton, M., & Saona Urmeneta, R. J. (2024). Value-positivity for matrix games. Mathematics of Operations Research. Institute for Operations Research and the Management Sciences. https://doi.org/10.1287/moor.2022.0332
Chatterjee, Krishnendu, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta. “Value-Positivity for Matrix Games.” Mathematics of Operations Research. Institute for Operations Research and the Management Sciences, 2024. https://doi.org/10.1287/moor.2022.0332.
K. Chatterjee, M. Oliu-Barton, and R. J. Saona Urmeneta, “Value-positivity for matrix games,” Mathematics of Operations Research. Institute for Operations Research and the Management Sciences, 2024.
Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. 2024. Value-positivity for matrix games. Mathematics of Operations Research.
Chatterjee, Krishnendu, et al. “Value-Positivity for Matrix Games.” Mathematics of Operations Research, Institute for Operations Research and the Management Sciences, 2024, doi:10.1287/moor.2022.0332.