AIB 2009-13: Time-optimal Winning Strategies for Poset Games

[Carsten Fuhs]

The following technical report is available from
http://aib.informatik.rwth-aachen.de:

Time-optimal Winning Strategies for Poset Games
Martin Zimmermann
AIB 2009-13

We introduce a novel winning condition for infinite two-player games
on graphs which extends the request-response condition and better
matches concrete applications in scheduling or project planning. In
a poset game, a request has to be responded by multiple events in an
ordering over time that is compatible with a given partial ordering
of the events. Poset games are zero-sum, but there are plays that
are more desirable than others, i.e., those in which the requests
are served quickly. We show that optimal strategies (with respect to
long term average accumulated waiting times) exist. These strategies
are implementable with finite memory and are effectively computable.