Time-Optimal Winning Strategies for Poset Games

Zimmermann, Martin ORCID: 0000-0002-8038-2453 (2009) Time-Optimal Winning Strategies for Poset Games. .

Text
CIAA09.pdf - Author Accepted Manuscript
Download (186kB) | Preview

Official URL: http://dx.doi.org/10.1007/978-3-642-02979-0_25

Abstract

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. © 2009 Springer Berlin Heidelberg.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	15 Jul 2019 13:09
Last Modified:	19 Jan 2023 00:37
DOI:	10.1007/978-3-642-02979-0_25
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3050016