|
Evènement pour le groupe Modélisation et Verification
Date | 2010-10-21 11:30-12:45 |
Titre | The 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. |
Lieu | Salle 076, LaBRI, Rez-de-chaussée |
Orateur | Michael Ummels |
Email | ummels@logic.rwth-aachen.de |
Url | RWTH Aachen |
Aucun document lié à cet événement. RetourRetour à l'index
| |