Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
The complexity of Nash Equilibria in Reward Games
du groupe Modélisation et Verification

Date 2010-10-21  11:30-12:45
TitreThe complexity of Nash Equilibria in Reward Games 
RésuméWe study the complexity of Nash equilibria in games with limit-average objectives. While an arbitrary Nash equilibrium of such a game can be found in polynomial space, we show that deciding whether a game has an equilibrium whose payoff meets certain constraints is, in general, undecidable. A more refined analysis takes into account the complexity of the strategies that realise the equilibrium. While for stochastic games, the above problem is undecidable for both pure and randomised strategies, the problem becomes decidable when one looks for a pure-strategy equilibrium in a non-stochastic game. 
LieuSalle 076, LaBRI, Rez-de-chaussée 
OrateurMichael Ummels 
Emailummels@logic.rwth-aachen.de 
UrlRWTH Aachen 



Aucun document lié à cet événement.

Retour
Retour à l'index