Publication

Stochastic limit-average games are in EXPTIME

Thomas Henzinger
2008
Journal Articles

Abstract

The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within e in time exponential in a polynomial in the size of the game times polynomial in logarithmic in 1/epsilon, for all epsilon > 0.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Stochastic limit-average games are in EXPTIME

Chat with Graph Search

Routing and charging game in ride-hailing service with electric vehicles

Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update

Quantifying Commitment in Nash Equilibria