|
Evènement pour le groupe Modélisation et Verification
Date | 2010-12-16 11:30-12:30 |
Titre | Energy and Mean-Payoff Games |
Résumé | We consider game models for the design of reactive systems
working in ressource-constrained environments.
In mean-payoff games, the ressource usage is computed as
the long-run average ressource level.
In energy games, the ressource usage is the intial amount
of ressource necessary to maintain the ressource level positive.
The resource can be memory, battery, or network usage for example.
While mean-payoff games are a well-established model in game theory
and computer science, energyy games have received attention only recently.
The talk reviews recent results about these games and their relationship.
Although they differ very basically in their definition,
it is known that energy and mean-payoff games are equivalent for
the simple decision problem of existence of a winning strategy.
This observation provides new complexity results for solving
mean-payoff games, and new insights for mean-payoff games combined
with other conditions such as fairness, imperfect information,
or multi-ressource systems, though the strong equivalence with
energy games usually breaks in such cases.
|
Lieu | Salle 076, LaBRI, Rez-de-chaussée |
Orateur | Laurent Doyen |
Email | doyen@lsv.ens-cachan.fr |
Url | LSV, Cachan |
Aucun document lié à cet événement. RetourRetour à l'index
| |