Value-Positivity for Matrix Games

• 成果类型: Article; Early Access
• 署名作者: Chatterjee, Krishnendu; Oliu-Barton, Miquel; Saona, Raimundo
• 署名单位: Institute of Science & Technology - Austria; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0332
• 发表日期: 2024
• 关键词: Stochastic games; additive reward

摘要

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.