Time-optimal Winning Strategies for Poset Games
Martin Zimmermann
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.
Technical Report AIB-2009-13, RWTH Aachen University.
Note that this document slightly differs from the original because an error in Corollary 1 has been corrected. Full version of the CIAA paper of the same name.