Evènement pour le 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