Thursday, March 10, 2011
Speaker: Laurent Doyen
Venue: IST Austria
We consider game models for the design of reactive systems working in resource-constrained environments. In mean-payoff games, the resource usage is computed as the long-run average resource level. In energy games, the resource usage is the initial amount of resource necessary to maintain the resource 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, energy 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 forthe simple decision problem of existence of a winning strategy.This observation provides new complexity results for solvingmean-payoff games, and new insights for mean-payoff games combinedwith other conditions such as fairness, imperfect information, or multi-resource systems, though the strong equivalence with energy games usually breaks in such cases.