Discrete Mathematics and Optimization Seminar

University of Warwick
Monday October 8th at 4.30pm
Burnside 1205

Title. A simple P-matrix linear complementarity problem for discounted games.

Abstract. We consider zerosum discounted games, which are played by two players on a finite directed graph with rewards on
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.