Thomas Gawlitza and Helmut Seidl. Computing Game Values for Crash Games. In Kedar S. Namjoshi, Tomohiro Yoneda, Teruo Higashino and Yoshio Okamura, editors, Automated Technology for Verification and Analysis, volume 4762 of Lecture Notes in Computer Science, pages 177-191, Tokyo, Japan, October 2007. Springer.

We consider crash games which are a generalization of parity games in which the play value of a play is an integer, -∞ or ∞. In particular, the play value of a finite play is given as the sum of the payoffs of the moves of the play. Accordingly, one player aims at maximizing the play value whereas the other player aims at minimizing this value. We show that the game value of such a crash game at position v, i.e., the least upper bounds to the minimal play value that can be enforced by the maximum player in a play starting at v, can be characterized by a hierarchical system of simple integer equations. Moreover, we present a practical algorithm for solving such systems. The run-time of our algorithm (w.r.t. the uniform cost measure) is independent of the sizes of occurring numbers. Our method is based on a strategy improvement algorithm. The efficiency of our algorithm is comparable to the efficiency of the discrete strategy improvement algorithm developed by Vöge and Jurdzinski for the simpler Boolean case of parity games [19].

Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com