• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

New algorithms for solving zero-sum stochastic games

Thumbnail
View/Open
Solving_stochastic_games_efficiently_MOR.pdf (482.0Kb)
Date
2020
Notes
Published Online: 28 May 2020. https://doi.org/10.1287/moor.2020.1055
Link to item file
https://pubsonline.informs.org/doi/10.1287/moor.2020.1055
Dewey
Analyse
Sujet
zero-sum stochastic games; game theory
Journal issue
Mathematics of Operations Research
Publication date
2020
Publisher
INFORMS
Forthcoming
oui
URI
https://basepub.dauphine.fr/handle/123456789/20725
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Oliu Barton, Miquel
Type
Article accepté pour publication ou publié
Abstract (EN)
Zero-sum stochastic games, henceforth stochastic games, are a classical model in game theory in which two opponents interact and the environment changes in response to the players’ behavior. The central solution concepts for these games are the discounted values and the value, which represent what playing the game is worth to the players for different levels of impatience. In the present manuscript, we provide algorithms for computing exact expressions for the discounted values and for the value, which are polynomial in the number of pure stationary strategies of the players. This result considerably improves all the existing algorithms, including the most efficient one, due to Hansen, Koucký, Lauritzen, Miltersen and Tsigaridas (STOC 2011).

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.