Algorithms for stochastic games ? A survey

DOI10.1007/BF01415989zbMath0736.90082MaRDI QIDQ3984137

Thirukkannamangai E. S. Raghavan, Jerzy A. Filar

Publication date: 27 June 1992

Published in: [https://portal.mardi4nfdi.de/entity/Q3031760 ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research] (Search for Journal in Brave)

zbMATH Keywords

Nash equilibriastochastic gamesinfinite time horizonfinite statefinite actioncomputation of minimax optimal stationary strategiessurvey algorithms

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A finite step algorithm via a bimatrix game to a single controller non- zero sum stochastic game, Quantitative solution of omega-regular games, A potential reduction algorithm for two-person zero-sum mean payoff stochastic games, Automatic verification of concurrent stochastic systems, Inventory control under substitutable demand: A stochastic game application, A Dijkstra-type algorithm for dynamic games, Non zero-sum stochastic games in admission, service and routing control in queueing systems, Zero-sum stochastic games with unbounded costs: Discounted and average cost cases, A characterization of stationary Nash equilibria of constrained stochastic games with independent state processes, Survey of linear programming for standard and nonstandard Markovian control problems. Part I: Theory, Zero-sum Markov games and worst-case optimal control of queueing systems, Cops and invisible robbers: the cost of drunkenness, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, Solving subclasses of multi-player stochastic games via linear complementarity problem formulations -- a survey and some new results, A convex programming-based algorithm for mean payoff stochastic games with perfect information, Automated Verification of Concurrent Stochastic Games, The complexity of stochastic Müller games, Completely mixed strategies for generalized bimatrix and switching controller stochastic game, Formal modelling and verification of probabilistic resource bounded agents, Orderfield property of mixtures of stochastic games, Stochastic limit-average games are in EXPTIME, Max Plus Algebra, Optimization and Game Theory, On Finding Large Sets of Rewards in Two-Player ETP–ESP Games, A Policy Improvement Algorithm for Solving a Mixture Class of Perfect Information and AR-AT Semi-Markov Games, Value set iteration for two-person zero-sum Markov games, Saddle-point calculation for constrained finite Markov chains, A survey of computational complexity results in systems and control, Unifying temporal and organizational scales in multiscale decision-making, Adaptive policy for two finite Markov chains zero-sum stochastic game with unknown transition matrices and average payoffs, Linear Programming and Zero-Sum Two-Person Undiscounted Semi-Markov Games, Nonzero-sum stochastic games with unbounded costs: Discounted and average cost cases, Zero-sum stochastic games over the field of real algebraic numbers, Generalized cops and robbers: a multi-player pursuit game on graphs, A Characterization of Stationary Nash Equilibria of Single Controller Constrained Stochastic Games, Stochastic scheduling games with Markov decision arrival processes, A leader-follower partially observed, multiobjective Markov game

Uses Software

• NPSOL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for discounted switching control stochastic games
• On stochastic games with additive reward and transition structure
• Bilinear programming and structured stochastic games
• Quadratic programming and the single-controller stochastic game
• On equilibria in repeated games with absorbing states
• An orderfield property for stochastic games when one player controls transition probabilities
• Linear programming and undiscounted stochastic games in which one player controls transitions
• Fictitious play applied to sequences of games and discounted stochastic games
• A modified form of the iterative method of dynamic programming
• Discounted Markov games; successive approximation and stopping times
• A finite algorithm for the switching control stochastic game
• Finite state Markovian decision processes
• An iterative method of solving a game
• A Matrix Game Solution of the Single-Controller Stochastic Game
• Player aggregation in the traveling inspector model
• Nonlinear programming and stationary strategies in stochastic games
• Successive Approximation Methods in Undiscounted Stochastic Games
• Myopic Solutions of Markov Decision Processes and Stochastic Games
• A Stochastic Game Model of a Weapons Development Competition
• The Asymptotic Theory of Stochastic Games
• On Stochastic Games with Stationary Optimal Strategies
• Equilibrium Points of Bimatrix Games
• On Nonterminating Stochastic Games
• Bimatrix Equilibrium Points and Mathematical Programming
• On some stocxastic tactical antisubmarine games
• The Big Match
• Algorithms for Stochastic Games with Geometrical Interpretation
• Stochastic Games with Perfect Information and Time Average Payoff
• Perturbation theory and finite Markov chains
• Noncooperative Stochastic Games
• Stochastic Games
• Stochastic games