Monday October 8th at 4.30pm

vertices. The players' strategies together determine an infinite path in the game graph. One player tries to

maximize, the other minimize the discounted sum of the rewards encountered on the path. These games provide one of

the few natural problems - Is the value of a game greater than k? - that are in NP interesct coNP, but for which no

polynomial-time algorithms are known. One of the main algorithms for solving these games is "strategy

improvement", however its worst case complexity is not known to be superpolynomial.

In this talk we present a simple reduction from discounted games to the P-matrix linear complementarity problem (PLCP),

and discuss the application of known algorithms for PLCPs to discounted games. In particular, we recover a variant of

strategy improvement. We also discuss the underlying combinatorial framework, which is given by unique sink

orientations of cubes. Joint work with Marcin Jurdzinski.