• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

New algorithms for solving zero-sum stochastic games

Oliu Barton, Miquel (2020), New algorithms for solving zero-sum stochastic games, Mathematics of Operations Research

View/Open
Solving_stochastic_games_efficiently_MOR.pdf (482.0Kb)
Type
Article accepté pour publication ou publié
External document link
https://pubsonline.informs.org/doi/10.1287/moor.2020.1055
Date
2020
Journal name
Mathematics of Operations Research
Publisher
INFORMS
Metadata
Show full item record
Author(s)
Oliu Barton, Miquel
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).
Subjects / Keywords
zero-sum stochastic games; game theory

Related items

Showing items related by title and author.

  • Thumbnail
    Shapley-Snow kernels, multiparameter eigenvalue problems and zero-sum stochastic games 
    Oliu-Barton, Miquel; Attia, Luc (2019) Document de travail / Working paper
  • Thumbnail
    Constant payoff in zero-sum stochastic games 
    Catoni, Olivier; Oliu-Barton, Miquel; Ziliotto, Bruno (2021) Article accepté pour publication ou publié
  • Thumbnail
    Optimal Strategies in Zero-Sum Repeated Games with Incomplete Information: The Dependent Case 
    Oliu-Barton, Miquel; Gensbittel, Fabien (2020) Article accepté pour publication ou publié
  • Thumbnail
    Existence of the uniform value in zero-sum repeated games with a more informed controller 
    Gensbittel, Fabien; Oliu-Barton, Miquel; Venel, Xavier (2014) Article accepté pour publication ou publié
  • Thumbnail
    A formula for the value of a stochastic game 
    Attia, Luc; Oliu Barton, Miquel (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo