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.
14th International Conference on Implementation and Application of Automata (CIAA 2009).
Note that this document slightly differs from the original because an error in Corollary 1 has been corrected. A technical report with full proofs is also available.
Copyright by Springer Verlag. The original publication is available at www.springerlink.com.