06/25/2005 09:00 AM

Computer Engineering

We consider real-time games where the goal consists, for each player,

in maximizing the average amount of 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 rewards. 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 al-

gorithms are based on the relationship between the original, infinite-round, game,

and a derived game that is played for only finitely many rounds. As positional op-

timal strategies exist for both players in both games, we show that the problem of

computing the value of the game is in NP¿coNP.