Publication

Stochastic limit-average games are in EXPTIME

2008
Journal Articles

Résumé

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.

Source officielle

https://infoscience.epfl.ch/entities/publication/a1757dd4-2a1a-4198-952b-dcc87018451d

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

2008
Journal Articles

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/a1757dd4-2a1a-4198-952b-dcc87018451d

À propos de ce résultat

Concepts associés (10)

Jeu coopératif (théorie des jeux)

En théorie des jeux, un jeu coopératif est un jeu tel que les joueurs ont la possibilité de se concerter et de s'engager à coopérer avant de définir la stratégie à adopter. À deux joueurs et deux stratégies avec une matrice des gains de la forme : où , , et . Des joueurs rationnels vont coopérer sur l'une ou l'autre des stratégies et recevoir les gains élevés. Pour ce faire, ils doivent pouvoir se coordonner sur l'une ou l'autre des stratégies, sous peine de se retrouver dans une situation défavorable.

Chaîne de Markov

vignette|Exemple élémentaire de chaîne de Markov, à deux états A et E. Les flèches indiquent les probabilités de transition d'un état à un autre. En mathématiques, une chaîne de Markov est un processus de Markov à temps discret, ou à temps continu et à espace d'états discret. Un processus de Markov est un processus stochastique possédant la propriété de Markov : l'information utile pour la prédiction du futur est entièrement contenue dans l'état présent du processus et n'est pas dépendante des états antérieurs (le système n'a pas de « mémoire »).

Processus stochastique

Un processus ou processus aléatoire (voir Calcul stochastique) ou fonction aléatoire (voir Probabilité) représente une évolution, discrète ou à temps continu, d'une variable aléatoire. Celle-ci intervient dans le calcul classique des probabilités, où elle mesure chaque résultat possible (ou réalisation) d'une épreuve. Cette notion se généralise à plusieurs dimensions. Un cas particulier important, le champ aléatoire de Markov, est utilisé en analyse spatiale.

Afficher plus

Publications associées (10)

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

John Lygeros, Kenan Zhang

This paper studies the routing and charging behaviors of electric vehicles in a competitive ride-hailing market. When the vehicles are idle, they can choose whether to continue cruising to search for passengers, or move a charging station to recharge. The ...

IEEE2023

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

Efstratios Panteleimon Skoulakis

In this paper we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU), for convergence to \textit{Coarse Correlated Equilibria} (CCE) in general games. CMWU effectively corresponds to the standard MWU algorithm but where ...

2022

Quantifying Commitment in Nash Equilibria

Thomas Alois Weber

To quantify a player's commitment in a given Nash equilibrium of a finite dynamic game, we map the corresponding normal-form game to a "canonical extension," which allows each player to adjust his or her move with a certain probability. The commitment meas ...

2019

Afficher plus