We study games as they were played in the wild west. Two players set
out for an infinite ride through the west. For reasons long forgotten,
they were forced to stay together -- as long as both were alive.
Often enough they had different ideas on where the ride should
go. Therefore they agreed on the following rule: the players take
turns, on alternate days, to determine where the ride should go that
day. A player might well decide not to move at all (in particular if
the last day's ride stopped at a saloon). However, only a finite
distance could be covered each day. After omega days the ride is
completed and it is time for payoff.
There are variants of this game where one of the players would fade
away (these things happened in the west) and the other player was to
complete the game by himself for the remaining omega days (a lonesome
ride indeed).
Besides the wild west, path games like this also occur in other
contexts, for instance in planning in non-deterministic domains. In
this talk we will briefly consider some of such connections to the
wild west. We will then focus on the determinacy of path games for
various classes of winning conditions (the conditions which determine
the payoff at the end of the ride) and study the complexity of
deciding the winner of such games. Finally, we will consider the
definability of these games in various logics like the mu-calculus,
CTL*, FO, ...
|