Back to Search
Start Over
Average Reward Timed Games
- Source :
- Lecture Notes in Computer Science ISBN: 9783540309468, FORMATS
- Publication Year :
- 2005
- Publisher :
- Springer, 2005.
-
Abstract
- We consider real-time games where the goal consists, for each player, in maximizing the average reward he or she receives per time unit. We consider zero-sum rewards, so that a reward of +r to one player corresponds to a reward of –r to the other player. The games are played on discrete-time game structures which can be specified using a two-player version of timed automata whose locations are labeled by reward rates. Even though the rewards themselves are zero-sum, the games are not, due to the requirement that time must progress along a play of the game. Since we focus on control applications, we define the value of the game to a player to be the maximal average reward per time unit that the player can ensure. We show that, in general, the values to players 1 and 2 do not sum to zero. We provide algorithms for computing the value of the game for either player; the algorithms are based on the relationship between the original, infinite-round game, and a derived game that is played for only finitely many rounds. As memoryless optimal strategies exist for both players in both games, we show that the problem of computing the value of the game is in NP∩coNP.
- Subjects :
- Computer Science::Computer Science and Game Theory
Non-cooperative game
Sequential game
business.industry
Computer science
ComputingMilieux_PERSONALCOMPUTING
Combinatorial game theory
Screening game
Strategy
Example of a game without a value
Repeated game
Simultaneous game
Artificial intelligence
business
Mathematical economics
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-540-30946-8
- ISBNs :
- 9783540309468
- Database :
- OpenAIRE
- Journal :
- Lecture Notes in Computer Science ISBN: 9783540309468, FORMATS
- Accession number :
- edsair.doi.dedup.....676f14c74b7c75d4546132d6600168c6