New Algorithms for Solving Zero-Sum Stochastic Games

DOI10.1287/moor.2020.1055zbMath1466.91022arXiv1810.13019OpenAlexW3029167794MaRDI QIDQ4991675

Miquel Oliu-Barton

Publication date: 3 June 2021

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.13019

zbMATH Keywords

complexityminimaxalgorithmslinear programmingstochastic gameslimit valuediscounted values

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Algorithmic game theory and complexity (91A68)

Related Items (2)

Shapley–Snow Kernels, Multiparameter Eigenvalue Problems, and Stochastic Games ⋮ Constant payoff in zero-sum stochastic games

Cites Work

• A new polynomial-time algorithm for linear programming
• Computing uniformly optimal strategies in two-player stochastic games
• Stochastic limit-average games are in EXPTIME
• The complexity of stochastic games
• Repeated games with absorbing states
• The complexity of solving reachability games using value and strategy iteration
• An inequality for the discriminant of a polynomial
• Algorithms for discounted stochastic games
• A contribution to von Neumann's theory of games
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• An Inequality About Factors of Polynomials
• The Asymptotic Theory of Stochastic Games
• On Stochastic Games with Stationary Optimal Strategies
• The Asymptotic Value in Finite Stochastic Games
• Exact algorithms for solving stochastic games
• The Big Match
• Stochastic Games
• A formula for the value of a stochastic game
• Recursive Concurrent Stochastic Games
• Stochastic games
• A first course on zero-sum repeated games

This page was built for publication: New Algorithms for Solving Zero-Sum Stochastic Games